I’m really intrigued with Fourier Transforms, and was wondering if someone could clarify a few points for me:
Is there only one possible decomposition of any given transform into sine waves?
Knowing what a Fourier Transform does, I’ve concocted the following algorithm (which I’m aware would be useless in real life) and I’m curious if it would work:
Input Data Points
Execute sinusoidal regression
calculate output of resultant sinusoidal function for the x values of given data points
Subtract, yeilding new data points
Jump back to step 2 using new data points unless data points are more or less linear at this point
(If question number two didn’t make any sense to you, the basic idea is to do sinusoidal regression on the data points, “subtract” the resultant function, and repeat, yeilding a bunch of sinusoidal functions comprising the output of the Fourier transform)
Can you explain to someone (whose highest level of math education is roughly Calculus AB) how a FFT or DFT works?
So it’s probably not at all helpful, but I’m preparing to stuff myself with turkey tomorrow and it’s been long enough that I don’t remember FTs and FFTs in detail, but yeah. A FT is unique for a particular function. A FFT is unique for a given function and frequency division thing. I don’t remember about DFTs either and yeah, there’s allsorts of discretization issues there. Now, to melt your brain, here’s a site that can eventually answer all sort questions:
I have been Puzzled by FTs and FFTs etc for a while too. I don’t have much of a math background. I am currently taking precal. I have learned a bit on my own. I am reasonably comfortable with integrals, derivitaves, limits etc. Is there any hope in me trying to understand this stuff with my level of education? I am looking to understand HOW/WHY they work. There is plenty of information on how to implement them, but but not how they work.
There is an excellent book, “Music, Physics, and Engineering”, in which fourier analysis and basic transforms are explored. You don’t need much beyond Precalc to understand their explanations.
However the book only has Fourier analysis as a tiny element (roughly 15-20 pages in the whole thing) and does not talk about Fast fourier transforms or the like, so its not worth buying if you are only interested in Fourier. Its an old book, and should be in many libraries.
If you define a function on the interval [0,2PI] (you can scale and offset to take care of any other interval) and the function is periodic outside of it, you can represent the function as:
A0 + S1 sin(x) + C1 cos(x) + S2 sin(2x) + C2 cos(2x) + …
A0 is just the average of the function in the interval, evaluated by integrating it. If your “regression” fit delivers the same answer,
you are in.
The other coefficients are obtained by integrating against the appropriate function, sin(x) in order to get S1, for instance, normalizing by dividing by the integral of sin^2(x). This works because the functions are orthogonal on the interval, that is the integral of sin(x) cos(x) is zero, for instance.
The discrete DFT is just a discrete version of all of the integration that is required, and the FFT is a factored form of the DFT matrix that is much more efficient to compute.
Now, back to your idea. If your “regression” fit of a flat line would deliver the same result as the average, A0, subtracting it would not disturb the coefficients of C# and S#. The question, then, is whether the presense of higher order terms in the data would distrub your “regression” fits of cos(x) and sin(x), and so forth. If the regression fit of a lower order term is not disturbed by the presense of a higher order term, your idea would work, but you would not want to do it that way, at least due to the build up of errors due to the subractions.
Your basic subtraction scheme, however, is used in order to produce a set of orthogonal functions from a set that is not orthogonal, and is therefore valid and quite useful in other circumstances.
I too had a great interest in the magical Fourier transform when I was young(er). If you have an interest in pursuing the more hard-engineering fields, like EE & ME, I cannot stress enough how important it is to master the ideas behind the FT. As an EE myself, I can use these ideas to solve some really tough problems just by thinking about what’s happening in “Fourier space”. As an example, I’m working on a new class of spacecraft avionics that use distributed computational nodes that are interconnected via a gigabit-class network. Trying to figure out why I’m getting transmission errors between those nodes by examining the network signals in the time domain is next to impossible. But, if you can imagine what’s happening in Fourier or frequency space, the problem just might become easier to solve. There are also instruments that will do this for you as well, like a spectrum analyzer (like the one that comes with winamp). More sophisticated instruments, like a network analyzer, can also show you what’s happening in other cool spaces like modulation and phase space.
You don’t need sophisticated instruments to investigate the magic that is the Fourier transform, you can do it with a copy of Matlab, Mathematica, Igor Pro or even Excel (yes, Excel!). Start by creating a table that represents a series of samples of your waveform. Using a discrete time version of the Fourier transform, known as the Fast Fourier Transform (FFT), you can convert this waveform into a table of its frequency components. Start with something simple like a pure sine wave and work yourself up to more complex waveforms like a triangle wave. A really cool waveform to use is a square wave. By modifying the resulting frequency components of the square wave and then converting back to time space, you can see how the square wave can be distorted by attenuating the higher frequency components. Square wave fidelity is important in high speed digital signals, like the network I mentioned above. For the more adventurous, you can also write the c code that does the above. Try googling on something like “FFT example source code” for some examples.
FFT are easy to implement with DSP ICs or programming. One of my pass engineering job was to used the these ICs to execute 10x10 FFT for a spread spectrum project. We choose hardware because of the “Need for Speed!”
It was the most fun I ever had with engineering, programming and math.
Fourier Transforms are very interesting, and they seem almost magical to most people that don’t fully understand the math behind them. Once you realize what mathematical concept is behind them, they are actually quite easy to understand.
The basis of the Fourier Transform is simple Linear Algebra. If you don’t know anything about linear algebra, I apologize, but I’ll try to make this as simple to understand as possible.
There are two simple principles of Linear Algebra that the Fourier Transform uses:
Any vector in n-dimensional space can be written as a linear combination of n linearly independent vectors. For example, in 3-dimensional space, let vector X = 1i + 0j + 0k; let Y = 0i + 1j + 0k; let Z = 0i + 0j + 1k. Then, the vector W = 3i + 4j + 5k can be written as: W = 3X + 4Y + 5*Z (i.e., W can be written as a linear combination of the 3 linearly independent vectors X,Y, and Z).
Any vector can be projected onto another vector that is not orthogonal (perpendicular) to that vector. This is like saying that any vector will cast a shadow on another vector. For example, assume that there is a vector along the ground pointing due north. Then assume you have another vector that is also pointing due north, but also a little bit up in the air (in other words, the vector is pointing diagonally north and up). Now assume you have a light bulb directly above where the two vectors intersect. The diagonal vector would cast a shadow onto the vector on the ground. This shadow is called the “vector projection onto” the vector on the ground. In the example in part 1) above, If we projected vector W onto vector X, the projection would be 3i+0j+0k (or 3X). You can also say that “the X component of W is 3”.
Okay, now you ask, “what on earth does this have to do with Fourier Transforms”. I guess I forgot to mention one other principle of linear algebra: a function can act exactly like a vector, and a set of functions can act exactly like a set of vectors.
What does this mean? It means that any function can be written as a linear combination of other linearly independent functions (i.e., principle (1) above).
Okay, so now we know that we can write any function using a bunch of sine waves. How do we know what you multiply each of the waves by? That is simple: use principle (2). You simply project your desired function onto each of the sine waves to get the component of each sine wave for your desired function.
Of course, this sounds fairly simple and the details are a little more difficult, but not much, really. Once you have a little linear algebra under your belt, making projections of vectors onto other vectors is fairly easy. Making projections of functions onto other functions is just a simple extension. Once you understand these principles, Fourier Transforms are not that magical or mysterious, but just make a lot of sense. Also, one you understand these principles, there isn’t much need to memorize the Fourier Transform formulas.
Quite a coincidence this thread came up; I’m currently studying Fourier Transforms in my Applied Math course, and I have to hand in a paper detailing one of its uses in my future field (Electrical Engineering).
So, I’d like to ask some suggestions to the engineers who use them in their day job - I’m particular interested in Controls applications (I think Chris Hibner can help me on this one, right? ;))
Here is how I’ve used Fourier Transforms at my job:
To determine frequency content of a set of data that we collected. This helps us to understand how we might want to filter the data. It also helps us to see if there are any unusual characteristics of the data in the frequency domain.
To remove unwanted frequency content. We were looking at some data we collected and noticed something strange. In the frequency domain we noticed a huge spike at a certain frequency. We went back to the test setup and noticed that one piece of data acquisition equipment radiated a lot of energy at that frequency and that created the large spike at that frequency. In order to remove the frequency, we took the FFT of the data, removed the spike by setting the frequency domain data to that of the average value of the data surrounding the spike, then took the inverse FFT.
Creating complex transfer function models. If we can identify the frequency response of a system emperically (like by using a sine sweep), we can use Fourier convolution to model the behavior of a signal through that system. This can get tricky, though.
One thing to keep in mind when using FFTs: The process of taking a Fourier Transform of a finite-time set of data will introduce false content into the frequency domain (and vice versa when you take the inverse). If you take a straight-up FFT of a time history of data, you are actually superimposing a square wave on top of the data, which becomes a sinc function in the frequency domain. If you understand the effect you can take some care to minimize how it affects your data. Just be sure you don’t blindly use Fourier methods without doing a few experiments and looking at the results closely. Once you take the inverse FFT, be sure to look at the beginning of the time-domain data for windowing effects.
I wanted to make this a separate post, just so it doesn’t get lost in the above post.
The concept that I pointed out in my first post (about writing a function as a linear combination of other functions) is a very powerful concept. In fact, it is the basis of virtually all approximation methods.
If you’ve ever heard of Wavelet Transforms, Spline Functions, Finite Element Methods, Element-Free Methods, etc.; these are all applications of using a set of functions like vectors. All of these methods try to approximate complex functions as linear combinations of simpler functions. And they also all use the concept of projecting a function onto these simpler basis functions.
If you’re going into a masters program involving control or computational engineering of any sort (i.e. any sort of computer simulation), you should take a good theoretical linear algebra class and a linear systems class. After this, your other classes will make a lot more sense and will be much easier to understand. My Finite Elelment Methods course (the course in which we had to write our own finite element solvers in Matlab and compare the results to commercially available solvers like Nastran and Abaqus), the drop-out rate was over 50%. Since I had a good understanding of the math, I thought the class wasn’t too bad. I have my boss at work (a PhD) for giving me the advice to take the other classes first - it helped a lot.
Manoel,
I use two pieces of equipment that actually are using FFT to make acoustic measurements in situ, i.e. in the room of interest. By using FFT and sweeping the room you can easily see the effects on frequency response as a function of reflections or by adjusting the parameters you can close down the sample cycle so that you can actually sweep the room while you are talking without affecting the measurement. The instrument also allows a manipulation to take a look at phase vs. frequency. The instrument I use most is called TEF (Time Energy Frequency) and it was originally designed and built by Crown International. You can now see the product line at http://www.gold-line.com/tef/tef.htm. This instrument allows us to quantify anomalies that we hear but could not measure. It has made great advances in acoustic design and treatment. We now know for instance that your ear shape has significant effect on how you hear. We also know that there is a delay after you hear a sound while you ear processes the data called the Hass Effect. By far the biggest effect in an acoustic environment revolves around reflections and the time it takes to arrive at your ears. In mixing rooms, for instance, reflections from the audio console face can cause severe notches in the frequency response. In electrical terms, two signals, in phase and equal in level, will only add to +6dB. The same two signals, 180 degrees out of phase, will produce a notch of infinite depth. What is more surprising is that there are rapid phase changes when sweeping across the notch. Rapidly changing phase plays havoc with human hearing as phase (one ear compared with the other ear) is what helps give us directional clues as to the source of the sound. Additionally, significant reflections will be in phase at some frequencies and out of phase at others, causing what is known as a comb filter. This type of filter will have frequency related notches in response throughout the audible spectrum.
In typical Catholic churches, particularly in the US, sound system designers have installed two speakers, one on each side of the altar. In this design, the only people who will hear without interference are those who are walking down the center of the center aisle. All others will experience some form of notched response due to the time misalignment of sound arriving at their ears at two different times.