To be honest most of the time I just type FFT or FFT2 in to matlab and it takes care of things. I am however familiar with the use of fourier transforms in optics which is quite intuitive and also gives some unique insights in to things. You mentioned that the Youngs slits experiment gives the Fourier transform and this is true, if you code the diffraction of light you sort of end up coding an FT without knowing about it.
A few ideas:
* I think a spectrum analyser is a good way to help introduce the basic concept of spectrum, it is tangible, you stick a sine wave in and a little line pops up. Talking about them is a good substitute.
* Another key part of the Fourier transform is that it is a many to one map. Each point on the spectrum is a weighted summation (sounds better than integral) of all the parts of the original signal. This makes a lot of sense if you think about it because it is the whole signal that determines its frequency not just one point in time/space. This is exactly what you see when you code up diffraction, at a distant plane each point is a weighted sum which takes phase into account.
* The complex number thing is just another way of representing amplitude and phase in a mathematically convenient way, there is really nothing to it. I wish they had not called it complex cos it isn't. It does help however if you understand what a vector is and that it can be divided into two parts in two directions at 90 degrees to each other (I avoided normal/orthogonal). Really complex numbers just keep these two parts together in a special number and that number has some interesting algebraic properties that help out.
I really think that an animation would be the best way to teach these ideas, I'd quite like to animate the Cordic for dummies, that might be even better.
Another important point is generally that waves/frequency components can be added to each other without effecting each other.
Drop two stones in a pool, the waves cross each other, there is interference where they cross (peaks where they rise together, troughs where the fall together and points where the rising and falling cancel). However once they have crossed each other's paths they are just as they were. The same is true of the frequency components that make up a signal, they add up to cause an effect but they are unique and don't affect each other.
I think when "dumming down" it is important not to forget some principles like this.
What you described as the behavior of a real system in math is called "linearity". Whenever we describe something in terms of math, we make a mistake and we have to accept this, as we do not have another way to gain a deeper understanding. The problem is: fun mostly comes from nonlinear behavior, like surfing on the beach. That may be one reason, why math is so boring to the most!
We have learned, that a system of equations has a solution, if there are as many equations as unknown and if these equation are linearly independent. So we can see the fourier transform as such an system of equations, where given an array of n numbers -the known, the signal over time- and searched is another array of n numbers - the unknown, the amplitude of a set of frequencies: a DC-level, the fundamental and the harmonics-.
Normally we have a set of equations, and we use for example the gaussian elimination to inverse a matrix, or if we have just two equations, as in primary or secondary school, I don't remember. Here in FT it is not obvious, that we have a set of those equations, because we just say "lets do an FT".
If we realize, what "harmonics" means, we can see, how these equations look like. There are "border conditions"
1. All the sinusoids have a certain amplitude. 2. the square of sinus and co-sinus is constant. Multiplying the amplitude of two functions for all values along the x-Axis and summing up results in zero, when the two functions are not equal and in 1, whenever they are equal.
This behavior is equivalent to a set of n linear independent equations to find n unknown.
I'm wondering if we don't need an "Advanced Engineering Mathematics For Dummies".
Anyone who has not studied such things, will be totally blinded by the normal definition of the DFT with its sigma and "e" and "i" gibberish. If they try to read up on such things they will be diverted and lost by a great wall of mathematics.
Problem is how to explain enough of that stuff so that someone can see that the mathematical definition is equivalent to Beans explanation and how to get from the mathematical definition to some code that looks like Beans Spin program.
Next, bigger, problem is I can't get from the basic DFT definition to what we need for that recursive FFT without all that sigma, e, and i gibberish.
Along the way the Euler identity needs to be introduced.
So for example:
The sigma thing needs to be explained as being a sum notation. It should be shown how a simple "repeat" loop can do that. It should be shown how things can be factored out of the sum in order to remove excess multiplications (Required for FFT decimation)
Then the is "e". I reckon it is not necessary to know why the "e" is special or used, or even what it's value is. Why? Because we are going to get rid of it soon enough thanks to Euler.
Then the is "i". Well books can be written about "i" and all the funky things yo can do with imaginary numbers. BUT for our purposes only a simple explanation of what it is is required and a demonstration of a few simple manipulations. I would probably skip all thoughts of complex numbers as containing phase or being like vectors.
To get from the definition to code you need Euler. Turn the exp into sin and cos. Euler's identity can be stated and discussed without proof.
With those things out of the way we can get the reader form DFT definition to code. In a few steps. We can show that the result is the same as Beans Spin example which was arrived at from a more graphical approach.
But now the biggy. With those simple maths concepts set up we can go with simple steps from DFT to FFT mathematically and from there to code. Perhaps not the ultra optimized, bit-reversing, in-place, no-recursive FFT that you see around a lot but the simple recursive implementation that comes naturally from the maths.
Math for dummies, that it! Maybe we create a lecture "math for mummies". No joke, the Egypt and Greek had a very basic understanding of math and could solve a lot of problems using this knowledge.
A very important step to understand math is, that math is not existing from alone and for itself, but was intended to solve problems. Look for example: logarithm. Logarithm was invented to handle problem "ten times more difficult" than what we can do just now. That means: the difference between 1 and 10 is 9, but between 10 and 100 90, 90 is 10 times 9, so the difference is 9 times more. Facing the problem to come from 10 to 100 is not more frightening than standing at 1 and going to 10. At least, sometimes.
So this problem is solved by logarithm, because log10 say: from 0 to 1 is 1, from 1 to 10 is 1, ... And now, what are the properties of a function, which solves such a problem. This is, where math come from. At least: there is some evidence for that. ;-)
I have heard the story of Galilei, who by discovering the moons of Jupiter came very close to discover "i". Why? He saw little bright dots moving along line crossing Jupiter with a sinusoidal velocity and thought: either there is a hole in Jupiter, so the dots can just tunnel through, or there is a hole in the spheres, so the dots are moons running around Jupiter. As he was sure, what he saw is not imagination (imaginary, "i"), he just said: there is no sphere where the stars are fixed to and so he removed the barriers between earth and heaven. But as he also feared about his pension, he stated, that there was imagination and so the evil came to the world.
OK, that is not really the story. The truth is: The sphere in reality was made quickly, quickly and had a leak. Or two.
So we know, that Galilei also was one of the first tourists to visit Hawaii !
It might be easier to understand the FFT by first looking at the fast Walsh-Hadamard transform (WHT) http://en.wikipedia.org/wiki/Fast_Hadamard_transform . The basic vectors for the WHT consist of only +1's and -1's. The fast WHT has a similar algorithm as the FFT with butterfly operations and bit reversal. All of the fast WHT bufferfly operations consists of just the sum and difference of a pair of numbers. The transform matrix for a two-point WHT (and any other orthogonal transform, such as the DFT) is as follows:
Y = H * X
where Y and X are 2-point vectors and H is the 2x2 transform matrix
|y0| = | 1 1 | * |x0|
|y1| | 1 -1 | |x1|
which is the same as
y0 = x0 + x1
y1 = x0 - x1
Larger WHT transforms can be recursively broken down into 2-point operations because the WHT is defined as
H2n = |Hn Hn|
|Hn -Hn|
as an example, the 4-point WHT matrix is given by
H4 = |H2 H2| = |1 1 1 1|
|H2 -H2| |1 -1 1 -1|
|1 1 -1 -1|
|1 -1 -1 1|
There is also a scaling factor of 1/sqrt(N), which I have ignored for simplicity.
* it is fast and simple [8^)
* the bit reversal is a bit funky...it's actually the bit-reversed Gray code of the index (at least for the version I have)
* a nice little paper relating Walsh functions to the FFT is: http://www.wiseguysynth.com/larry/schematics/walsh/walsh-small.pdf (Note: basically look at the 1st page, after that it's mostly about implementing this using flip-flops!)
* the forward transform is the same as the reverse transform
* instead of scaling each transform by 1/sqrt(N), you can just transform it, transform it back, then divide by N, which since N is a power of 2, means a simple bit shift.
I would like to stop here and and ask a few questions because I feel this thread is bogging down. It is not my intention to side track the discussion and apologize in advance.
So this here thread is titled "Fourier for Dummies" so exactly who are the dummies we are talking about?
Dummies as in high school math? or Dummies with advanced degrees?
Personally I think we are talking about dummies in the middle who
have some pretty good math but aren't interested in the theoretical bottom line.
We have jobs to do and we are very curious and don't want to spend
a lot of time trying to really and truly understand every detail. Most of us know about the Fourier transform and we have seen and used spectrum analizers.
We are software engineers or hardware engineers and serious hobbyists.
We did complex math in school and know what you mean when you say multiply two complex numbers.
What we really want to know is how the thing works and are ok if we gloss over some of the theoretical stuff.
This is the category I fit in and if I'm on the right track lets hear from you and if I am wrong, I again apologize to everyone and will be quiet.
At this point I understand what Bean wrote on multiplying waveforms and Heater has removed the mystery from the reordering.
I now realize that after this reordering we shifted from the time domain to frequency domain and how that happened. So we now have to put things back in the correct order, on the fly, as we multiply by the various sin and cos waves and why simply reversing the reordering process wont work.
Chapter 12 of the Scientists and engineers guide to DSP outlines very nicely how this is accomplished and has some nice diagrams that helped me understand that process.
Along the way I learned a bunch of terms that now make a lot more sense.
So at this point I am truly dangerous, I think I understand the FFT, at least enough to satisfy my curiosity and I am just dangerous enough to actually try it and as you can see talk about it with people who really do know.
What I would like to see now is this description all written up nice in one paper with some nice diagrams.
And thats what this thread was/is all about isn't it?
And just for the record I couldn't have gotten here without this thread so everyone has much to be proud of.
...who are the dummies we are talking about? Dummies as in high school math? or Dummies with advanced degrees?
Good question?
The first dummy to satisfy is me:). I think it was me who first asked bean for an FFD after his superb CORDIC work.
Or, both. I'll elaborate later.
What we really want to know is how the thing works and are ok if we gloss over some of the theoretical stuff.
Yes. For example I'm prepared to not expect an understanding of the Euler Identity. Euler is required to get from the standard definition of DFT to working code with cos() and sin() instead of exp(bla bla). Euler can be stated without proof. Point is that one may not know why the DFT is defined the way it is, but once you have seen it re-written in terms of sin() and cos() it makes intuitive sense when put together with something like Beans exposition.
Heater has removed the mystery from the reordering. I now realize that after this reordering we shifted from the time domain to frequency domain and how that happened
I'm afraid you understand wrongly.
The input to the Fourier Transform is a bunch of signal amplitude samples taken at equal time intervals. A signal in the "Time Domain".
The final output of the FT is a bunch of amplitudes of frequency components at equal frequency spacing. Same signal expressed in the "frequency domain".
In the in-place (non-recursive) implementations of DFT the bit reversal is just a sort of preprocessing prior to the real work being done. The reordered samples are still our time domain signal, just munged up. The bit-reversal just gets the data into an order that it finds it self being used in during the recursive implementations.
Now about the target audience. Many people with the maths skills know all about Fourier, but they can't make the jump to actually writing a Fast FT. Of course life is too short to try and understand everything so they end up just using library code or cutting and pasting FFT code they find. As software engineers we should feel a bit queasy about that, we should be curious to know how algorithms work. And what happens when we want an FFT for say, a Propeller, where there is no existing implementation in Spin or PASM? Carefully reverse engineer a C version, still without knowing how it works, blech.
I think we have at least two major target groups, the curious high school kids (or those whose math is at that level) and then the engineering grads who have done the math but are still blinded by FFT or even the actual meaning of the standard DFT definition. (That was me for over twenty years!)
But then we have a couple of levels of "scope", that is to say the target level of understanding to be imparted by the document. Perhaps more than one document are required. For example:
1) To get the idea that multiplying a signal by a bunch of sinusoids and averaging the result of each is a good way to measure the amount of a frequency in the input signal. Leading up to some code that actually does that. Bean has a good handle on the approach. This is teaching the DFT without needing to know the mathematical DFT definition or even hearing the term DFT. This is an excellent level to shoot for for high school level types. This is "Fourier for Dummies".
2) Starting with a high school level math introduce one to the DFT definition, explain enough of all that sigma, "e", "i" stuff to get the reader to connect the definition with what we have in 1) above. It should be shown that you can get form all that sigma, "e", "i" stuff to the same code as Bean presents.
3) Continuing on from 2) but presenting the idea of "divide and conquer", which is after all a simple rearrangement of the DFT equation. And then build that up into a recursive code FFT implementation, as per my C++ example.
4) Some how explain how an "in-place" non-recursive FFT algorithm comes about. Bit reversal and all. This is still beyond me:)
By the way the FFT is truly remarkable.
For a 16K sample set the DFT, like Beans example code, in C on my PC takes over 25 seconds.
My simple recursive FFT in C++ only takes 50ms. A speed up of about 500 times!
An in-place non-recursive implementation with bit-reversal is another 2 or 3 time faster.
As it is so amazing it is very intriguing to know how it works.
Again a good contribution from Heater.
So I try to compensate that.
As on the behalf of complex numbers, I just wanted to show, that real numbers are not real by pointing to the moons of jupiter, running a sinusoidal path on sky spheres, but we only see one axis and the projection (or shadow) to a imaginative plain. The real movement, as we all believe to know, is more or less a circle around jupiter. Precisely: it a ellipsis. So we always should raise the question: what is it, what we see.
We feel familiar with voltages, so we see a voltage changing value over time as a sinusoidal. This voltage can be generated artificially, by a computer and a DAC, or "naturally", by a capacitor connected to an inductor. Then, as we store energy in this circuit, the energy has to oscillate between C and L, so current and voltage show sinus and cosinus. But the energy is a constant! Now, if energy is constant over time, why do we need time? If something doesn't change, why there is time? Time is needed to have a potential change!!
Only the fact, that something could change, is sufficient to talk about time. OK, that again is very principle. But we all know, that time is passing by, time can not be collected or "saved". We have the impression, that there is just a moment. But that again is only half the truth. And half a truth is just not the truth. So, as we might have seen: even if something is constant, like the energy, some properties of this energetic system may change and they may change according to a very simple differential equation, where the solution is a sinusoidal change over time. Like voltage and current and, as there is the border condition "constant energy", voltage and current sinusoids have to be shifted in time 90°. that is a quarter of one period.
Another way to generate a sinusoidal voltage is an AC generator in a power station. This is done by having a rotation inertia and energy is flowing out with a sinusoidal voltage and the same current IN PHASE, so the power output (or energy flow) is not constant over time. How to heal this? A turbine delivers energy to the generator constant and continuously, but the generator delivers energy discontinuously and not at all constant. Now, this again is quite tricky solved by the nature. As we connect three ac-generators to the turbine, each delivering pulsed energy, and shift the three voltages/currents by a third of a period, the pulses add up to a constant value!
As heater said: a lot of things come together and you can not understand the full picture by just looking to an algorithm.
Lets go on and see, what happens!
I've just cottoned onto what you meant by the Galilei story...
If you see a big planet in the sky,
and if you see it has a little moon moving back and forth from side to side of the planet,
and if you believe these must be both on the same "heavenly sphere",
then it follows that the big planet has a hole in it!
Brilliant.
See how ideas get entrenched in our psyche? From our modern perspective we would never even consider the possibility of a hole in a planet.
Still, if planets had such holes then moons could have such orbits...
Never thought about power stations much. As you say a single phase generator into a resistive load would be rather bumpy.
I have no idea about time but consider this:
There is no "time" in the Fourier Transform.
If I have 1024 samples of a sine wave signal in memory, or drawn out on a graph on paper, all those maxima and minima and all the values in between exist there in the same moment. I can count the maxima, maybe there are 16 of them. Perhaps my samples were collected over 1 second, then I could say I have a frequency of 16 cycles per second. But perhaps those samples are not of a time varying signal at all. Perhaps they are the measurements of the height of a brick wall along it's length.
As I was not surprised, that I didn't like to follow the explanation in the DSP-paper linked above, I put another question:
How is it possible, to generate a sinusoidal signal with infinite precision just by saying: let everything be zero and one thing be one?
Because this is, what we do!
In the frequency domain you are creating an array of values, where virtually all are zero, one is one. OK, again have the truth, we have to mirror this array to have a second 1.
Now we are just multiplying, adding and reordering and in the end, we have a perfect sinusoid.
The insight I hope to gain in the end is: I have a feeling I understood this and why the number of periods in the time domain is determined by the shift of the one in the frequency domain.
We could start this way:
We place the one in the middle, so we generate the highest frequency, in time there have to be two values, one for odd and one for even elements.
Now we shift the one by one place and we will have half the frequency.
Further we can try to understand, why, if we do not enter a 1 to one of the twin-arrays, and a zero to the other, but it divide this value into two parts, have the sinusoid phase shifted.
Yes, Galilei was just brilliant. His conclusion was inversely. He saw the dots moving along a line crossing the planets, and as people, even the pope, where not ready to say: there is a hole in the planet, there had to be a hole in the sphere, so the sphere was no longer impenetrable and therefor one could have direct access to heaven. That was a threat to the establishment. And there was another guy at that time. He wrote: I do not publish, what I found, not because I know about Galilei, but some people, not clever enough to understand, what I discovered will take me as witness for there doctrine, and that is not my intention. ;-)
Sure, there is time in the time domain: if you write down a signal as a function of time and you determine frequency, you do not care about the fact, that a time distance doesn't exist, you freeze the signal on a paper or whatever means. But you surely will not say: this value in the frequency domain represents a spacial period of 2.21" on sheet of paper coming from an instrument with a feed rate of 1"/second
@Heater
I beg to differ about misunderstanding the reordering and for the sake of those reading let me explain.
We start with a time ordered set of samples s0,s1 etc and we reorder them as in the bit reversal. So what did we end up with in terms of the FFT? A scrambled set of samples in time? or something else? The answer depends on how you think of it. (This by the way was another of several aha moments for me so I make a big deal of it rightly or wrongly.)
From chapter 12 of the engineers guide
"The next step in the FFT algorithm is to find the frequency spectra of the 1 point time domain signals. Nothing could be easier; the frequency spectrum of a 1 point signal is equal to itself. This means that nothing is required to do this step. Although there is no work involved, don't forget that each of the 1 point signals is now a frequency spectrum, and not a time domain signal."
This frequency spectra still needs to be multiplied by sin and cos to get the power and phase for each frequency bin and it still needs to get put back into the correct order. Which is a a big piece of this discussion still to be written.
It sounds like the engineer's guide has an error. Reording the original samples just produces a scrambled set of samples in time. The conversion from the time domain to the frequency domain is done by multiplying times the sine and cosine basis vectors, and computing the sums of the products. The frequency spectrum is the absolute magnitude of the frequency components.
Dave:
you are making my head spin. and I find it hard to believe the book is wrong, it is possible but until proven otherwise....
but my skills are not good enough to make a strong arguement. I think of it this way...
From Beans graphical, multiplying a 5 volt sin by a 1 volt sine produced a magnitude 5 at the FREQUENCY of the 1 volt sine
When we have the signal scrambled and multiplied it by some frequency we get the magnitude at that frequency only if we guessed right about frequency and phase,
if our guess was wrong we get something else representing magnitude and phase.
Isn't that what we did in theory at the single sample point where the scrambling is complete?
and can not that be thought of as being in the frequency domain?
The FFT is just a fast implementation of the DFT. The original data is in the time domain, and the final output of the FFT is in the frequency domain. Intermediate stages of the FFT are neither in the time domain or the frequency domain, they are just intermediate results.
Let me start over:
1.) what is the fourier transform good for and why
2.) how is the fourier transform realized
3.) what can the fourier transform be compared to, what we already believe to understand
These are three questions, having only in common, that the are related to fourier transform.
Let me start with the third question:
We know, that a vector is just a pointer into space, having a length and pointing into a certain direction. This direction could be fixed, so all vector show to the same direction, but could have different length. This could even be the case, if the direction is one of many in a plane, one of many in a 3-dimensional space, one of many in an higher, even infinitely dimensional space.
As a vector is manifested by giving the coordinates, and as the vectors length is the square root of the sum of the squares of all coordinates, we can always generate a vector with a length of 1 by division of every component by the length of the original vector.
Having this done, we can create a second vector, perpendicular to the first one, a third perpendicular to those two, and so on until we are having as many vectors of length 1 and perpendicular to all the others, as we have coordinates. This set of vectors we call a Basis.
Now imagine, in three dimensional space we have a coordinate system x, y, z and we shift or rotate this system, then we can give an description of any vector in either base.
The same is true, if we have an higher, lets say 1024 dimensional vector space.
What can be shown is: if you are defining a vector, where the components are a sinusoidal of a fundamental or harmonic frequency, then this vector is perpendicular to every other vector with this condition. Therefore "the harmonics" are nothing but the basis of a vector space.
If now we have a signal in the time domain, and lets say, this signal has 16 samples, we could say: the first sample designates the x-axis, the second the y, the third the z, the forth ?? and so on. And now, as we already have the vectors, representing the sinusoids generated, we only have to determine, how the signals coordinates are in the frequency base. That is all.
So a fourier transform is nothing but a change of the basis coordinate system of a vector. The only problem is to accept, that a vector with 10000000 components is not really different from an vector with 1 component: Because a single vector always has only a length and a direction and if the vector points to the x-axis, his representation is just ( length, 0, 0, 0, ..... -->)
I like to view the data as an Nx1 matrix (i.e., a vector). The transform is implemented by multiplying an NxN matrix times the data vector to produce a new vector. Each row of the DFT matrix consist of a sine or cosine of increasing frequency. The data can be transformed back to the original domain by multiplying it times the inverse DFT matrix.
One nice property of the DFT, and all orthogonal transforms, is that the inverse matrix is just the transpose of the forward matrix. Therefore, the each column of the inverse DFT matrix consists of a sine or cosine of increasing frequency.
The DFT matrix can be factored into log2(N) sparse NxN matices, where each row and each column only have two non-zero values. Each stage of the FFT is implemented by dong a matrix multiply of one of the sparse matrices. The sparse matrix multiplications can be perfomed on individual pairs of data. This is known as the butterfly operation.
So what's all this talk of "vectors", "matrices" and "1024 dimensional space"?
Perhaps that's all true and a nice way to look at it, but my understanding of the FFT, does not require any such concepts. That is not a language for dummies. After all a simple 32 bit integer can be regarded as a vector in a 32 dimensional space or it can be seen as a polynomial of degree 32. These are useful views in some cases.
ErNa,
Sure, there is time in the time domain: if you write down a signal as a function of time and you determine frequency, you do not care about the fact, that a time distance doesn't exist, you freeze the signal on a paper or whatever means.
Sure there is not. After all we are just punching numbers into a calculator, The numbers can represent whatever we like. As I said, the input could be samples of the height of a brick wall along it's length. No time involved there. The FT of that may tell you something about the skill of the bricklayers.
Ray0665
I cannot see the output of the bit reversal stage as being in the time domain. No more than the rearrangement of numbers in my SUM() game, prior to addition, is the sum. Sure the Fourier Transform of a one element sample set is the value of the sample, but all those following multiplications by sin and cos is what gets you the FT of the entire set.
There are two ways to make FFT for dummies. The first one is the one, Cooley–Tukey showed. It's so clever, even computers are able do to it. The other way is to enable man to understand, what is behind the scenes. So FFT for Dummies means to me, not to change man (we all are Dummies), but to improve our abilitiy to understand. Make better use of reason.
"my understanding of the FFT, does not require": as far as I understood, there is no understanding yet.
OK, now about Time- and Frequency-domain. There is no time, there is no frequency. Time and frequency are concepts. Time is a way to express, that something changes. Frequency is a way to express, that something is not changing. Time excludes Frequency and vice versa.
There is a saying: they never come back. Relates to boxers. But, rarely, they come back. So, who is wrong? It it better to have more cogs or more memory? Better to have skills to work or money to spend? So, if there is a statement: there is not time and just punching numbers into a calculator, then I have to argue: obviously the sequence of punching the numbers matters. So the sequence creates or defines time. To the calculator it matters in which order the numbers are punched in, but for example it is not relevant, if they are punched in into the same timely distance. So, as the numbers are stored into an array of memory cells, the index defines time. That is different form sampling the numbers with ticks of a clock.
OK, I agree, it is difficult to imagine a 1024 dimensional space and to see, how vectors are rotated relative to an axis. But decomposing the transformation matrix t * A = f (time domain* Matrix = frequency domain) into 2X2 sparce matrices seems to me a very well suited idea to gain an understanding, even if the used 3-dimensional space is not sufficient to visualize even 2 point time domain signal with complex input values. And all of this without a graphical representation. But I am sure, we are on the right way.
But decomposing the transformation matrix t * A = f (time domain* Matrix = frequency domain) into 2X2 sparce matrices seems to me a very well suited idea to gain an understanding...
Except, I can't for the life of me understand any of that:)
"...all of this without a graphical representation"
I think that's my problem, I pretty much can't understand anything unless I can form a picture of it in my mind. With the picture all of a sudden the equations and derivations start to have meaning rather than just being a bunch of symbols shuffled around on paper according to some set of rules.
I have included ch 12 of the engineers guide as a pdf below. From our discussions so far we have the samples scrambled and we know we need to multiply by sin and cos, and we also know that we need to get the sample unscrambled to get our final power spectra. We need to determine what sample to multiply with what other sample and we need a strategy to cycle through all the samples to accomplish that. And oh yes it would be nice if we understood what we are doing.
I have read through pages 230, 231, and 232 of the attached pdf about six times (Yes it takes awhile to get through several inches of bone, and this is not about which domain we are in, as Dave said we start here and end there and thats all that matters), that, if I understand correctly, we are being shown not only the theory of what we are doing but in a very practical way being shown how to select the samples for multiplication such that we unscramble the samples into the final order. Namely which odd even pairs to use at each level of the butterfly.
Does this clarify anything for anyone else like it does for me?
Can we use it?
Is this stuff right for the "Fourier for Dummies" paper?
The last few pages are about actual programs that for me are now understandable.
Creating a picture in somebodies mind! That is the big challenge. So, if we fail, it's not a fault. It's just the hint to try it a different way. As everybody has an idea about symmetry, it should be a hook to bring into mind an expanded understanding of this concept. What we learn is: we look to a mirror and we see our face to be symmetrical. We plot a dot on a paper and draw a line and are able to draw a mirrored dot. We draw a dot and a second dot and we mirror the first dot at the second. So even if we are not able to use a single point as a mirror physically, we can do this in our mind. And as we are sketching and mirror all the single dots of the sketch on this "mirror point" we realize, that mirroring at a point, we get a rotation. So rotation is a type of symmetry we are not aware of intuitively. So, as everything is relative, it doesn't matter if we make the dummies more clever or the problems simpler. Experience shows: whenever a "dummy" was able to fix a problem, that was simplified, it turns out, that his some is able to solve other, not simplified problems. Or why do we send children to school ? Just to enable the dummies to teach children ;-)
I started to work through this paper few days ago and found, to me it makes no sense. Look just to fig.12-1 and you find, that this paper was not written carefully. In the time domain you have N values, in the frequency domain 2*(N/2+1) values, making N+2 values. That can not happen, there is no way to create something from nothing.
Going on there are other statements, just settings, where you do not the reason, and so you can not get an deeper understanding.
The time domain has 14 elements, the real and imaginary part of frequency domain having each 8.
It is just the wrong way to start with an real dft, because the natural way is to have a complex in and output. Even if this is not intuitively to see.
As there is the problem with the "imaginary" part not solved, that is, still open, why not explain this firstly, and then explain, why, if the imaginary part has the value "0" for all samples, try to find out, how we can use this to reduce computation effort by making use of some symmetries
ErNa did you error? I see (n/2) + 1 not n/(2+1)
Remember My Dear Aunt Sally?
And the diagram is labled 0 - - n-1 regardless of the box count
With Apologies ErNa
This illustrates the difference between practical guys and theoretical guys .
The theorists are upset with outlayers (and for good reasons) and
practical guys are perfectly happy ignoring them as long as they get results.
I do not know the reason, why they didn't take an "double-even" number of samples like 12, if they didn't like to use a 2^n number. Was it just to show, that there is a limitation of FFT to 2^n samples, but not for DFT? But the box count just reflects what the text say: create 2 times n/2 + 1 frequency points from N time points. That may be seen negligible, but isn't accepted. If there is a hole in a pot, the whole pot will be worthless. (if not made from rare earthes ;-) )
OK, I just found this here: http://nietzsche.holtof.com/Nietzsche_human_all_too_human/sect1_of_first_and_last_things.htm and go on to paragraph 19, this shows why we have to be so precise, at least we should try. The subtle things make the difference between the parts and the unit. Sometimes only the arrangement of the parts. So if you try to analyze something by breaking it apart, you will never find, what makes the thing unique.
Comments
A few ideas:
* I think a spectrum analyser is a good way to help introduce the basic concept of spectrum, it is tangible, you stick a sine wave in and a little line pops up. Talking about them is a good substitute.
* Another key part of the Fourier transform is that it is a many to one map. Each point on the spectrum is a weighted summation (sounds better than integral) of all the parts of the original signal. This makes a lot of sense if you think about it because it is the whole signal that determines its frequency not just one point in time/space. This is exactly what you see when you code up diffraction, at a distant plane each point is a weighted sum which takes phase into account.
* The complex number thing is just another way of representing amplitude and phase in a mathematically convenient way, there is really nothing to it. I wish they had not called it complex cos it isn't. It does help however if you understand what a vector is and that it can be divided into two parts in two directions at 90 degrees to each other (I avoided normal/orthogonal). Really complex numbers just keep these two parts together in a special number and that number has some interesting algebraic properties that help out.
I really think that an animation would be the best way to teach these ideas, I'd quite like to animate the Cordic for dummies, that might be even better.
Graham
Drop two stones in a pool, the waves cross each other, there is interference where they cross (peaks where they rise together, troughs where the fall together and points where the rising and falling cancel). However once they have crossed each other's paths they are just as they were. The same is true of the frequency components that make up a signal, they add up to cause an effect but they are unique and don't affect each other.
I think when "dumming down" it is important not to forget some principles like this.
Graham
We have learned, that a system of equations has a solution, if there are as many equations as unknown and if these equation are linearly independent. So we can see the fourier transform as such an system of equations, where given an array of n numbers -the known, the signal over time- and searched is another array of n numbers - the unknown, the amplitude of a set of frequencies: a DC-level, the fundamental and the harmonics-.
Normally we have a set of equations, and we use for example the gaussian elimination to inverse a matrix, or if we have just two equations, as in primary or secondary school, I don't remember. Here in FT it is not obvious, that we have a set of those equations, because we just say "lets do an FT".
If we realize, what "harmonics" means, we can see, how these equations look like. There are "border conditions"
1. All the sinusoids have a certain amplitude. 2. the square of sinus and co-sinus is constant. Multiplying the amplitude of two functions for all values along the x-Axis and summing up results in zero, when the two functions are not equal and in 1, whenever they are equal.
This behavior is equivalent to a set of n linear independent equations to find n unknown.
Anyone who has not studied such things, will be totally blinded by the normal definition of the DFT with its sigma and "e" and "i" gibberish. If they try to read up on such things they will be diverted and lost by a great wall of mathematics.
Problem is how to explain enough of that stuff so that someone can see that the mathematical definition is equivalent to Beans explanation and how to get from the mathematical definition to some code that looks like Beans Spin program.
Next, bigger, problem is I can't get from the basic DFT definition to what we need for that recursive FFT without all that sigma, e, and i gibberish.
Along the way the Euler identity needs to be introduced.
So for example:
The sigma thing needs to be explained as being a sum notation. It should be shown how a simple "repeat" loop can do that. It should be shown how things can be factored out of the sum in order to remove excess multiplications (Required for FFT decimation)
Then the is "e". I reckon it is not necessary to know why the "e" is special or used, or even what it's value is. Why? Because we are going to get rid of it soon enough thanks to Euler.
Then the is "i". Well books can be written about "i" and all the funky things yo can do with imaginary numbers. BUT for our purposes only a simple explanation of what it is is required and a demonstration of a few simple manipulations. I would probably skip all thoughts of complex numbers as containing phase or being like vectors.
To get from the definition to code you need Euler. Turn the exp into sin and cos. Euler's identity can be stated and discussed without proof.
With those things out of the way we can get the reader form DFT definition to code. In a few steps. We can show that the result is the same as Beans Spin example which was arrived at from a more graphical approach.
But now the biggy. With those simple maths concepts set up we can go with simple steps from DFT to FFT mathematically and from there to code. Perhaps not the ultra optimized, bit-reversing, in-place, no-recursive FFT that you see around a lot but the simple recursive implementation that comes naturally from the maths.
A very important step to understand math is, that math is not existing from alone and for itself, but was intended to solve problems. Look for example: logarithm. Logarithm was invented to handle problem "ten times more difficult" than what we can do just now. That means: the difference between 1 and 10 is 9, but between 10 and 100 90, 90 is 10 times 9, so the difference is 9 times more. Facing the problem to come from 10 to 100 is not more frightening than standing at 1 and going to 10. At least, sometimes.
So this problem is solved by logarithm, because log10 say: from 0 to 1 is 1, from 1 to 10 is 1, ... And now, what are the properties of a function, which solves such a problem. This is, where math come from. At least: there is some evidence for that. ;-)
OK, that is not really the story. The truth is: The sphere in reality was made quickly, quickly and had a leak. Or two.
So we know, that Galilei also was one of the first tourists to visit Hawaii !
Larger WHT transforms can be recursively broken down into 2-point operations because the WHT is defined as
H2n = |Hn Hn| |Hn -Hn| as an example, the 4-point WHT matrix is given by H4 = |H2 H2| = |1 1 1 1| |H2 -H2| |1 -1 1 -1| |1 1 -1 -1| |1 -1 -1 1|There is also a scaling factor of 1/sqrt(N), which I have ignored for simplicity.* it is fast and simple [8^)
* the bit reversal is a bit funky...it's actually the bit-reversed Gray code of the index (at least for the version I have)
* a nice little paper relating Walsh functions to the FFT is: http://www.wiseguysynth.com/larry/schematics/walsh/walsh-small.pdf (Note: basically look at the 1st page, after that it's mostly about implementing this using flip-flops!)
* the forward transform is the same as the reverse transform
* instead of scaling each transform by 1/sqrt(N), you can just transform it, transform it back, then divide by N, which since N is a power of 2, means a simple bit shift.
Jonathan
So this here thread is titled "Fourier for Dummies" so exactly who are the dummies we are talking about?
Dummies as in high school math? or Dummies with advanced degrees?
Personally I think we are talking about dummies in the middle who
have some pretty good math but aren't interested in the theoretical bottom line.
We have jobs to do and we are very curious and don't want to spend
a lot of time trying to really and truly understand every detail. Most of us know about the Fourier transform and we have seen and used spectrum analizers.
We are software engineers or hardware engineers and serious hobbyists.
We did complex math in school and know what you mean when you say multiply two complex numbers.
What we really want to know is how the thing works and are ok if we gloss over some of the theoretical stuff.
This is the category I fit in and if I'm on the right track lets hear from you and if I am wrong, I again apologize to everyone and will be quiet.
At this point I understand what Bean wrote on multiplying waveforms and Heater has removed the mystery from the reordering.
I now realize that after this reordering we shifted from the time domain to frequency domain and how that happened. So we now have to put things back in the correct order, on the fly, as we multiply by the various sin and cos waves and why simply reversing the reordering process wont work.
Chapter 12 of the Scientists and engineers guide to DSP outlines very nicely how this is accomplished and has some nice diagrams that helped me understand that process.
Along the way I learned a bunch of terms that now make a lot more sense.
So at this point I am truly dangerous, I think I understand the FFT, at least enough to satisfy my curiosity and I am just dangerous enough to actually try it and as you can see talk about it with people who really do know.
What I would like to see now is this description all written up nice in one paper with some nice diagrams.
And thats what this thread was/is all about isn't it?
And just for the record I couldn't have gotten here without this thread so everyone has much to be proud of.
~
Good question?
The first dummy to satisfy is me:). I think it was me who first asked bean for an FFD after his superb CORDIC work.
Or, both. I'll elaborate later.
Yes. For example I'm prepared to not expect an understanding of the Euler Identity. Euler is required to get from the standard definition of DFT to working code with cos() and sin() instead of exp(bla bla). Euler can be stated without proof. Point is that one may not know why the DFT is defined the way it is, but once you have seen it re-written in terms of sin() and cos() it makes intuitive sense when put together with something like Beans exposition.
I'm afraid you understand wrongly.
The input to the Fourier Transform is a bunch of signal amplitude samples taken at equal time intervals. A signal in the "Time Domain".
The final output of the FT is a bunch of amplitudes of frequency components at equal frequency spacing. Same signal expressed in the "frequency domain".
In the in-place (non-recursive) implementations of DFT the bit reversal is just a sort of preprocessing prior to the real work being done. The reordered samples are still our time domain signal, just munged up. The bit-reversal just gets the data into an order that it finds it self being used in during the recursive implementations.
Now about the target audience. Many people with the maths skills know all about Fourier, but they can't make the jump to actually writing a Fast FT. Of course life is too short to try and understand everything so they end up just using library code or cutting and pasting FFT code they find. As software engineers we should feel a bit queasy about that, we should be curious to know how algorithms work. And what happens when we want an FFT for say, a Propeller, where there is no existing implementation in Spin or PASM? Carefully reverse engineer a C version, still without knowing how it works, blech.
I think we have at least two major target groups, the curious high school kids (or those whose math is at that level) and then the engineering grads who have done the math but are still blinded by FFT or even the actual meaning of the standard DFT definition. (That was me for over twenty years!)
But then we have a couple of levels of "scope", that is to say the target level of understanding to be imparted by the document. Perhaps more than one document are required. For example:
1) To get the idea that multiplying a signal by a bunch of sinusoids and averaging the result of each is a good way to measure the amount of a frequency in the input signal. Leading up to some code that actually does that. Bean has a good handle on the approach. This is teaching the DFT without needing to know the mathematical DFT definition or even hearing the term DFT. This is an excellent level to shoot for for high school level types. This is "Fourier for Dummies".
2) Starting with a high school level math introduce one to the DFT definition, explain enough of all that sigma, "e", "i" stuff to get the reader to connect the definition with what we have in 1) above. It should be shown that you can get form all that sigma, "e", "i" stuff to the same code as Bean presents.
3) Continuing on from 2) but presenting the idea of "divide and conquer", which is after all a simple rearrangement of the DFT equation. And then build that up into a recursive code FFT implementation, as per my C++ example.
4) Some how explain how an "in-place" non-recursive FFT algorithm comes about. Bit reversal and all. This is still beyond me:)
By the way the FFT is truly remarkable.
For a 16K sample set the DFT, like Beans example code, in C on my PC takes over 25 seconds.
My simple recursive FFT in C++ only takes 50ms. A speed up of about 500 times!
An in-place non-recursive implementation with bit-reversal is another 2 or 3 time faster.
As it is so amazing it is very intriguing to know how it works.
So I try to compensate that.
As on the behalf of complex numbers, I just wanted to show, that real numbers are not real by pointing to the moons of jupiter, running a sinusoidal path on sky spheres, but we only see one axis and the projection (or shadow) to a imaginative plain. The real movement, as we all believe to know, is more or less a circle around jupiter. Precisely: it a ellipsis. So we always should raise the question: what is it, what we see.
We feel familiar with voltages, so we see a voltage changing value over time as a sinusoidal. This voltage can be generated artificially, by a computer and a DAC, or "naturally", by a capacitor connected to an inductor. Then, as we store energy in this circuit, the energy has to oscillate between C and L, so current and voltage show sinus and cosinus. But the energy is a constant! Now, if energy is constant over time, why do we need time? If something doesn't change, why there is time? Time is needed to have a potential change!!
Only the fact, that something could change, is sufficient to talk about time. OK, that again is very principle. But we all know, that time is passing by, time can not be collected or "saved". We have the impression, that there is just a moment. But that again is only half the truth. And half a truth is just not the truth. So, as we might have seen: even if something is constant, like the energy, some properties of this energetic system may change and they may change according to a very simple differential equation, where the solution is a sinusoidal change over time. Like voltage and current and, as there is the border condition "constant energy", voltage and current sinusoids have to be shifted in time 90°. that is a quarter of one period.
Another way to generate a sinusoidal voltage is an AC generator in a power station. This is done by having a rotation inertia and energy is flowing out with a sinusoidal voltage and the same current IN PHASE, so the power output (or energy flow) is not constant over time. How to heal this? A turbine delivers energy to the generator constant and continuously, but the generator delivers energy discontinuously and not at all constant. Now, this again is quite tricky solved by the nature. As we connect three ac-generators to the turbine, each delivering pulsed energy, and shift the three voltages/currents by a third of a period, the pulses add up to a constant value!
As heater said: a lot of things come together and you can not understand the full picture by just looking to an algorithm.
Lets go on and see, what happens!
I've just cottoned onto what you meant by the Galilei story...
If you see a big planet in the sky,
and if you see it has a little moon moving back and forth from side to side of the planet,
and if you believe these must be both on the same "heavenly sphere",
then it follows that the big planet has a hole in it!
Brilliant.
See how ideas get entrenched in our psyche? From our modern perspective we would never even consider the possibility of a hole in a planet.
Still, if planets had such holes then moons could have such orbits...
Never thought about power stations much. As you say a single phase generator into a resistive load would be rather bumpy.
I have no idea about time but consider this:
There is no "time" in the Fourier Transform.
If I have 1024 samples of a sine wave signal in memory, or drawn out on a graph on paper, all those maxima and minima and all the values in between exist there in the same moment. I can count the maxima, maybe there are 16 of them. Perhaps my samples were collected over 1 second, then I could say I have a frequency of 16 cycles per second. But perhaps those samples are not of a time varying signal at all. Perhaps they are the measurements of the height of a brick wall along it's length.
How is it possible, to generate a sinusoidal signal with infinite precision just by saying: let everything be zero and one thing be one?
Because this is, what we do!
In the frequency domain you are creating an array of values, where virtually all are zero, one is one. OK, again have the truth, we have to mirror this array to have a second 1.
Now we are just multiplying, adding and reordering and in the end, we have a perfect sinusoid.
The insight I hope to gain in the end is: I have a feeling I understood this and why the number of periods in the time domain is determined by the shift of the one in the frequency domain.
We could start this way:
We place the one in the middle, so we generate the highest frequency, in time there have to be two values, one for odd and one for even elements.
Now we shift the one by one place and we will have half the frequency.
Further we can try to understand, why, if we do not enter a 1 to one of the twin-arrays, and a zero to the other, but it divide this value into two parts, have the sinusoid phase shifted.
I beg to differ about misunderstanding the reordering and for the sake of those reading let me explain.
We start with a time ordered set of samples s0,s1 etc and we reorder them as in the bit reversal. So what did we end up with in terms of the FFT? A scrambled set of samples in time? or something else? The answer depends on how you think of it. (This by the way was another of several aha moments for me so I make a big deal of it rightly or wrongly.)
From chapter 12 of the engineers guide
"The next step in the FFT algorithm is to find the frequency spectra of the 1 point time domain signals. Nothing could be easier; the frequency spectrum of a 1 point signal is equal to itself. This means that nothing is required to do this step. Although there is no work involved, don't forget that each of the 1 point signals is now a frequency spectrum, and not a time domain signal."
This frequency spectra still needs to be multiplied by sin and cos to get the power and phase for each frequency bin and it still needs to get put back into the correct order. Which is a a big piece of this discussion still to be written.
you are making my head spin. and I find it hard to believe the book is wrong, it is possible but until proven otherwise....
but my skills are not good enough to make a strong arguement. I think of it this way...
From Beans graphical, multiplying a 5 volt sin by a 1 volt sine produced a magnitude 5 at the FREQUENCY of the 1 volt sine
When we have the signal scrambled and multiplied it by some frequency we get the magnitude at that frequency only if we guessed right about frequency and phase,
if our guess was wrong we get something else representing magnitude and phase.
Isn't that what we did in theory at the single sample point where the scrambling is complete?
and can not that be thought of as being in the frequency domain?
1.) what is the fourier transform good for and why
2.) how is the fourier transform realized
3.) what can the fourier transform be compared to, what we already believe to understand
These are three questions, having only in common, that the are related to fourier transform.
Let me start with the third question:
We know, that a vector is just a pointer into space, having a length and pointing into a certain direction. This direction could be fixed, so all vector show to the same direction, but could have different length. This could even be the case, if the direction is one of many in a plane, one of many in a 3-dimensional space, one of many in an higher, even infinitely dimensional space.
As a vector is manifested by giving the coordinates, and as the vectors length is the square root of the sum of the squares of all coordinates, we can always generate a vector with a length of 1 by division of every component by the length of the original vector.
Having this done, we can create a second vector, perpendicular to the first one, a third perpendicular to those two, and so on until we are having as many vectors of length 1 and perpendicular to all the others, as we have coordinates. This set of vectors we call a Basis.
Now imagine, in three dimensional space we have a coordinate system x, y, z and we shift or rotate this system, then we can give an description of any vector in either base.
The same is true, if we have an higher, lets say 1024 dimensional vector space.
What can be shown is: if you are defining a vector, where the components are a sinusoidal of a fundamental or harmonic frequency, then this vector is perpendicular to every other vector with this condition. Therefore "the harmonics" are nothing but the basis of a vector space.
If now we have a signal in the time domain, and lets say, this signal has 16 samples, we could say: the first sample designates the x-axis, the second the y, the third the z, the forth ?? and so on. And now, as we already have the vectors, representing the sinusoids generated, we only have to determine, how the signals coordinates are in the frequency base. That is all.
So a fourier transform is nothing but a change of the basis coordinate system of a vector. The only problem is to accept, that a vector with 10000000 components is not really different from an vector with 1 component: Because a single vector always has only a length and a direction and if the vector points to the x-axis, his representation is just ( length, 0, 0, 0, ..... -->)
One nice property of the DFT, and all orthogonal transforms, is that the inverse matrix is just the transpose of the forward matrix. Therefore, the each column of the inverse DFT matrix consists of a sine or cosine of increasing frequency.
The DFT matrix can be factored into log2(N) sparse NxN matices, where each row and each column only have two non-zero values. Each stage of the FFT is implemented by dong a matrix multiply of one of the sparse matrices. The sparse matrix multiplications can be perfomed on individual pairs of data. This is known as the butterfly operation.
So what's all this talk of "vectors", "matrices" and "1024 dimensional space"?
Perhaps that's all true and a nice way to look at it, but my understanding of the FFT, does not require any such concepts. That is not a language for dummies. After all a simple 32 bit integer can be regarded as a vector in a 32 dimensional space or it can be seen as a polynomial of degree 32. These are useful views in some cases.
ErNa,
Sure there is not. After all we are just punching numbers into a calculator, The numbers can represent whatever we like. As I said, the input could be samples of the height of a brick wall along it's length. No time involved there. The FT of that may tell you something about the skill of the bricklayers.
Ray0665
I cannot see the output of the bit reversal stage as being in the time domain. No more than the rearrangement of numbers in my SUM() game, prior to addition, is the sum. Sure the Fourier Transform of a one element sample set is the value of the sample, but all those following multiplications by sin and cos is what gets you the FT of the entire set.
"my understanding of the FFT, does not require": as far as I understood, there is no understanding yet.
OK, now about Time- and Frequency-domain. There is no time, there is no frequency. Time and frequency are concepts. Time is a way to express, that something changes. Frequency is a way to express, that something is not changing. Time excludes Frequency and vice versa.
There is a saying: they never come back. Relates to boxers. But, rarely, they come back. So, who is wrong? It it better to have more cogs or more memory? Better to have skills to work or money to spend? So, if there is a statement: there is not time and just punching numbers into a calculator, then I have to argue: obviously the sequence of punching the numbers matters. So the sequence creates or defines time. To the calculator it matters in which order the numbers are punched in, but for example it is not relevant, if they are punched in into the same timely distance. So, as the numbers are stored into an array of memory cells, the index defines time. That is different form sampling the numbers with ticks of a clock.
OK, I agree, it is difficult to imagine a 1024 dimensional space and to see, how vectors are rotated relative to an axis. But decomposing the transformation matrix t * A = f (time domain* Matrix = frequency domain) into 2X2 sparce matrices seems to me a very well suited idea to gain an understanding, even if the used 3-dimensional space is not sufficient to visualize even 2 point time domain signal with complex input values. And all of this without a graphical representation. But I am sure, we are on the right way.
Except, I can't for the life of me understand any of that:)
"...all of this without a graphical representation"
I think that's my problem, I pretty much can't understand anything unless I can form a picture of it in my mind. With the picture all of a sudden the equations and derivations start to have meaning rather than just being a bunch of symbols shuffled around on paper according to some set of rules.
I have read through pages 230, 231, and 232 of the attached pdf about six times (Yes it takes awhile to get through several inches of bone, and this is not about which domain we are in, as Dave said we start here and end there and thats all that matters), that, if I understand correctly, we are being shown not only the theory of what we are doing but in a very practical way being shown how to select the samples for multiplication such that we unscramble the samples into the final order. Namely which odd even pairs to use at each level of the butterfly.
Does this clarify anything for anyone else like it does for me?
Can we use it?
Is this stuff right for the "Fourier for Dummies" paper?
The last few pages are about actual programs that for me are now understandable.
Going on there are other statements, just settings, where you do not the reason, and so you can not get an deeper understanding.
The time domain has 14 elements, the real and imaginary part of frequency domain having each 8.
It is just the wrong way to start with an real dft, because the natural way is to have a complex in and output. Even if this is not intuitively to see.
As there is the problem with the "imaginary" part not solved, that is, still open, why not explain this firstly, and then explain, why, if the imaginary part has the value "0" for all samples, try to find out, how we can use this to reduce computation effort by making use of some symmetries
Remember My Dear Aunt Sally?
And the diagram is labled 0 - - n-1 regardless of the box count
With Apologies ErNa
This illustrates the difference between practical guys and theoretical guys .
The theorists are upset with outlayers (and for good reasons) and
practical guys are perfectly happy ignoring them as long as they get results.
Fourier for Dummies is for the Practical guys.