After choking on that twiddle factors table...
and since this thread was born from Beans excellent Description of the CORDIC algorithm
and it is something that can be used when building the twiddle factors.
I think we should pay homage to Bean and use a cordic package.
I am uploading the Trig package I cobbled together (after stealing it out of Beau Schwabs Compass module) along with a very simple demo of its use.
This discussion helped stupid me to an deeper understanding of complex numbers and I try to share my "insight":
Complex numbers are written: A + iB and that doesn't mean, that two numbers are added, but the "+" just shows: a complex number has two components, that are not comparable and so they can not be added. The two parts of a complex have nothing in common, therefor they have to be combined to be a unity.
Sounds complicated, but is really simple. 5 + 6 = 11. But 5 beer and 6 coke = 5 beer + coke. As we were used to drink beer, before coke was discovered, we just wrote: give me 5 and we all knew: he meant beer. And now, after coke, we order 5 + 6 coke. And as coke was invented after, they called: give me 4 and imaginary 6.
Now, as there are different brands of coke, beer, and so many hard and soft drinks, we have forgotten, how everything began.
Back to complex numbers: we are used to put down complex numbers in a plane and could write: Ax + By. So we can identify a complex number as a two dimensional vector. And instead of the Cartesian coordinates X,Y we also could use polar coordinates L, phi (length and angle). And from this back to Cartesian, we could write L * cos (phi) x + L * sin (Phi) y, or: L * cos (phi) + i L * sin (Phi)
But there is still one question: what is the difference between a 2 dimensional vector and a complex number?
To me the answer is: a number is just a number, but a number only makes sense, if there are rules to combine numbers, rules to add and multiply. And that makes the difference.
If we add two vectors, we add the components like we add normal numbers: a1x + b1y (first vector) + a2x + b2y (second vector) = (a1+a2)x + (b1+b2)y
Still be aware: a1x + b1y means: we combine two numbers, a1 and b1 to form one unit and a1 and b1 have nothing in common, they show into perpendicular directions. We normally write (a1, b1)
Addition is the same for complex numbers, drawn as vectors, but noted in the form a1 + ib1
The difference comes from multiplication of two vectors:
If we multiply a1x + b1y (first vector) * a2x + b2y we apply the rule, that the x- and y-components are individually multiplied and both results are added.
If we multiply complex numbers, a1 + i b1 and a2 + i b2 we multiply them similar to binominals, (a1 + i b1) * (a2 - i b2) = a1*a2 - ib1*ib2 - a1*ib2 + a2*ib1
There is a little, but important difference: in the second complex number the sign of the imaginary part is flipped!
Why is this important:
Imagine you have to 2-dimensional vectors 0x + 1y and 1x + 0y, so these vectors obviously are orthogonal, because one shows to y, one to x. There scalar product is 0*1 + 1*0 = 0
Now we have to complex numbers: 0x + 1y and 1x + 0y, or as we like to write: 0 + i1 and 1 + 0i.
If we multiply them we have: ( 0 + i1 ) * ( 1 - i0) = 0*1 - i1*i0 - 0*i0 + i1*1 = 0 - 0 - 0 - i*1
And that obviously is not zero! But if we had seen the two numbers as vectors, they were orthogonal and there scalar product must be zero.
So, from this follows: sometimes it makes sense to see complex numbers as vectors in the X/Y-plane, but this is just to have a visualization. To do math it is not sufficient to have the numbers, it needs the rules too!
As usual we have a somewhat opposite views of things:) Although the practical result should be the same.
Complex numbers are written: A + iB and that doesn't mean, that two numbers are added,
Actually I believe it does mean that they are added. For example, in simple algebra I might give you a number in the form:
x = 4 + 3y
That's not much use to you until you have a value for y. Say 2, then you know x is 10. You can't do the actual addition before you know the value of y
So it's the same with "i":
x = 4 + 3i
If we had a value for i we could do the addition. There is no fundamental difference of types like adding "coke" and "beer". In fact there are no types implied here at all.
Only problem is that we have defined "i" to be unknowable, the square root of minus one, therefore we can never do the addition.
Sometimes when writing code I realize I need a function to do something, also that I don't know how to do that thing yet, also that I'm busy thinking about some other part of the program right now. What to do? Easy, pretend I have such a function, give it a name, "foo", write a call to "foo()" at the appropriate point in the code, then get on with what I was doing. I will create foo() later.
The number "i" is the mathematical equivalent. We think of a thing, square root of minus one, and realize we can't evaluate it. We don't give up and stop there, no, we give it a name "i" and drop it into equations like anything else. After all we don't know what it is but we can say things about it "i squared is minus one". Magically the "i" can disappear at the end of our musings and leave as with a solid knowable result.
Excuse the intrusion, but I happen to be so dumb that I am waiting for the end product in order to learn proper
Fourier. Best wishes to all.
I am wondering if I can use this to determine THD (total harmonic distortion) of an inserted sine wave into a quality audio amp. That seems likely to be a good 'first project'.
I am wondering if I can use this to determine THD (total harmonic distortion) of an inserted sine wave into a quality audio amp. That seems likely to be a good 'first project'.
Indeed you can. However it is not so easy. Let's say you want measure down to 0.01% distortion. That's one part in 10000 so already it looks like we need a good 16 bit ADC. Nowadays we might want 24 bits. We need to know that the ADC is distortion free to that level.
When it comes to doing it on the Prop, my code is not up to it. I'm using 32 bit arithmetic on fixed point values. 1.0 is scaled up to 4096 giving only 14 bit precision for the sine and cos tables. The input samples are limited to +/- 4096 so as to prevent overflow.
Of course it would be straight forward to extend this to 64 bit arithmetic or use the float32 object if it has enough accuracy. At a great loss of speed.
OK heater, that gives handle to answer and we should come closer:
You say: x = 4 +3y is not much use, I say: from my view it's of much use. This equation gives you not one value, as you would have it with y=2, but you have a whole set of values and this equation defines a straight line with an inclination of 1/3 and crossing the y-axis at - 4/3 and the x-axis at 4. So this equation give you a infinite number of pairs of numbers.
And it is completely different situation with "i". If you write x = 4 + 3 i, than x is a symbol for the complex number (4, 3). x is no longer just a number, as it would be with an equation.
You say: if we had a value for "i", I say: we have this value for "i". And the value is given by the fact, that i*i = -1.
So it is not correct, if you state: "i" is defined to be unknowable. The square root of -1 is knowable, it is just not a real number.
Further: the "i" never disappears, and there is no magic.
Remember how we are taught to calculate. First the teacher introduced Pi, then "e", then one million, then he told us: don't be afraid, we leave this aside and come back to it later. That is, were all the problems come from: they didn't tell us, that there are complex numbers too, and hermitian vector spaces of infinite dimensionality. ;-)
OK, what I want to say: there is a way top down and bottom up. The whole picture we see in the end. And there is no difference.
Imagine: you are starting with natural numbers, then we introduce negative number, as the inverse operation to + creates numbers, we do not get, when adding natural numbers. That we introduce p/q to have the inversion of multiplication.
Imagine: you could say: it is only allowed to subtract a number from another one, if this number was added before. Then you never would get negative numbers. But what if you added 4 and subtracted 3 and 1? Still there is no negative value. But if you subtracted 4 twice?
You see, the natural way is to "invent" negative numbers or to "discover" negative numbers.
Step by step we fill the gaps between the natural numbers and we discover, that there is even between 0 and 1 an infinite amount of numbers. And if we calculate 1/x we see, that just in the neighborhood of 0 there is a infinite amount of numbers. And that there are numbers like Pi, which only can be expressed exactly by saying: this is the relation of an circles circumference and his diameter.
And "i" is just the square root of -1. But why do we not need the square root of -2? Because this would be a very complicated number. As we know, we do not know the value of sqrt(2), but we only know, that the square of this value is 2. And what, if the situation will be complicated by introducing "i"? We would just by overstressed.
But, rescue is near: we remember,. that -2 = -1 * +2 and that sqrt( -2) =sgrt( -1) * sqrt(+2), and so we divided the problem an conquered!
Of course we do. Sometimes:) I just occasionally find myself walking around an idea, looking at it from different angles, kicking the wheels, and seeing if I want to buy it or not.
You say: x = 4 + 3y is not much use, I say: from my view it's of much use.
Yes, you are right. I just meant that it could not be simplified any more, down to an actual single number. As with my statement about "i", we may not know what "y" is but that does not stop us using it in equations and getting useful statements.
And it is completely different situation with "i".
Not from my current point of view. What if I give you "x = 4 + y" and I don't tell that "y = 3i"? You could work with that up until the point you want to get a single result.
[/quote]
If you write x = 4 + 3i, than x is a symbol for the complex number (4, 3). x is no longer just a number, as it would be with an equation.
Ah, there is the thing. "x" here is not just a normal value, it has two parts. So:
x = 4 + 3i
is actually two equations:
1) Knowable part of x = 4
2) Unknowable part of x = 3
We just can't simplify any more. When we write "x = ..." and say x is complex" then all we are doing is inventing a short hand notation for the two equations. That's all.
You say: if we had a value for "i", I say: we have this value for "i". And the value is given by the fact, that i*i = -1.
What?!
How can you say "we have this value for "i"" whilst at the same time saying "i" is the square root of minus one? Which is a value we for sure do not have!
So it is not correct, if you state: "i" is defined to be unknowable. The square root of -1 is knowable, it is just not a real number.
It is not knowable. Please write it down if you have it:) But as we see using the trick of "just name it and continue anyway" it becomes useful.
Further: the "i" never disappears, and there is no magic.
Sure it can disappear. The output of the FFT, for example, is not normally presented directly in (real, imag) form but the magnitudes of each frequency are calculated. POOF! The i's vapourize.
Alternatively one could somehow display the FFT result showing both frequency and phase. POOF! the i's have gone again.
Or one could just present the results a raw real, imag pairs. But then one is just casually dropping the i's, acknowledging that it was just a notational trick anyway and we were working with two sets of equations all along.
Perhaps we should avoid the word "magic" when talking maths, although it does quite often seem quite spooky, full of happy coincidences that just happen to get you where you want to be.
Now here is a thing, from simple algebra we can show that:
(a + ib) * (c + id) = (ac - bd) + i(ad + bc)
I will say there is "magic" here. We have previously stated that we can't combine the so called "real" and "imaginary" parts through addition and simplify our complex numbers.
BUT look what has happened here. The "b" and "d" of the imaginary world are showing up and having an effect in the real world side of the result. And vice-versa. Cool hey?
Here is another thing:
The input to the FFT is in (real,imaginary) pairs. We put the input signal into the real part.
BUT we could put the input signal into the "imaginary" part. The frequency magnitude result would be the same. There is nothing more or less real about either part of the input.
If memory serves me correctly, when I was learning complex numbers i (but j was used instead, go figure) was indeed the square root of minus one but we further defined it as a 90 degree counter clock wise rotation of the X axis. it followed then that higher powers of i produced more rotation and sign changes.
OK, it take some time to argue, and I am a bit short. So a short answer:
"Now here is a thing, from simple algebra we can show that: (a + ib) * (c + id) = (ac - bd) + i(ad + bc)"
Yes, you can show this from simple algebra, the problem is: we are not facing "simple algebra".
Let me explain: the value of 1 is, funny things happen, : 1 And: here value and absolute value are equal. This is not true for -1. Here the value is -1, the absolute value: +1! So, why should we define a property for 1 and -1, which is equal, so that there is no difference between -1 and 1? There is a reason: sometimes it doesn't matter, like when calculation kinetic energy.
Now take this situation: you are here, another person1 is one mile away. The persons are 1 mile apart. There is a third person2, also one mile distant from you. But what is the distance person2-person1. We can not know this, but the distance is not negative and less equal 2 miles. Depending on the situation, we may run into a problem if we do not know more. That is a reason to introduce coordinates. Again: we assume, the persons are in a plane, so we have a 2-dimensional case. Now, as the persons have X and Y coordinates, we are able to determine the distances from the coordinates.
Now, we could introduce coordinates X, Y, because we are used to do so. And we know, that very easily we can expand this to Z and even more, if necessary.
But there is a second way when we know, that we are looking to a plane and there are only 2 coordinates: We call the X- coordinate with no name and the Y-coordinate with the name "i".
Now we place one person in the center, the second somewhere else. Ok, for simplicity: let the second be in a distance of 1, so actually, somewhere on a circle with radius 1.
In the first case we determine the distance by calculation sqrt (x*x + y*y)
Now we are used to express positions in a plane by using distance and angle phi. And from this we know: the x-axis is cos(phi), y: sin(phi), if radius = 1
Let us see this scene from a different point of view:
We are used to see numbers arranged on a number ray. And there is no place for a number sqrt(-1). So we invent the plane of complex numbers. And i now defines the y-coordinate.
Now we expanded our universe of numbers from one-component numbers to two-component numbers.
But as we use the same representation for complex numbers as we use for 2-dimensional vectors, we still have to see them as different things! But to a certain degree there is a relation.
Now we have two ways to define a circle in a plane:
By giving two coordinates X, Y cos(phi), sin(phi)
or by giving a complex number cos(phi) + i sin(phi)
No let us calculate the distance from center to a point on the circle:
D = sqrt (cos(phi)²+ sin(phi)²) for the first case, and the length is 1, as we commonly believe ;-)
or, using "simple algebra"
D² = (cos(phi) + i sin(phi)) * (cos(phi) + i sin(phi)) = cos(phi)² - sin(phi)² + i * 2 * (sin(phi) * cos(phi))
So, this equation is not really simple to solve. What is the distance?
As mathematicians are men and men are lazy, the solved this problem that way:
Knowing, that (a+b)*(a-b) = a² - b² they just said: if we have to multiply two complex numbers, we have to invert the sign of the complex part of the second number!
D² = (cos(phi) + i sin(phi)) * (cos(phi) - i sin(phi)) = cos(phi)² + sin(phi)²
And now, oh miracle, we have the same result as we have it from X/Y point of view!
If memory serves me correctly, when I was learning complex numbers i (but j was used instead, go figure) was indeed the square root of minus one but we further defined it as a 90 degree counter clock wise rotation of the X axis. it followed then that higher powers of i produced more rotation and sign changes.
So this thread has gone quiet. What is a reasonable "next step"?
a) draft an outline of the explanation document
b) try to define target and scope of the explanation
c) just go through the thread and stitch together the various points from the discussion
d) continue the discussion, there is still not enough to work with
Do any of these choices seem more appropriate than the others? Any other suggestions?
Not Idle or forgotten, my head is still spinning with new found knowledge and holiday preps..
but to answer you directly:
First before anything else we need to define the audience because no matter what we write (as we have already seen here) there will be some that will feel it just doesn't get it without something else or it went too far in such and such an area. This is not a put down on anything or anyone in this thread it just reflects the reality of different levels and personalities.
As for myself I vote for a straight forward explanation of the algorithm with as little theory and math as possible. Beginning with the bit reversal and why it exists continuing through to the butterflys with Beans description and finally a description of the three loops. In other words a straight forward description of the classic algorithm and in the order it is most commonly written.
Yes it's quiet. That's because we are all deep in thought. Did you see my description of "Fourier Syndrome"?
I have Fourier syndrome so bad that I had the overwhelming compulsion to recast my Spin FFT program into PASM.
The result is the attached program heater_fft.spin that has both Spin and PASM FFTs in it. Either use BST and the #define syntax to select which version is compiled or manually remove the version you don't want.
Now, here is the amazing part. heater_fft turns out to be almost twice as fast as the FFT_1024.SPIN that is knocking around these threads! 1024 point FFT in 40ms. That's 25 per second and I have not even tried to optimize the PASM yet.
I will attempt to tidy this up a bit, use the Props sin table instead of my own, optimize a few things. But this basically works.
Now to think about that "Fast Fourier Transform For Dummies" before I forget the troubles I had getting to this point.
I vote for a straight forward explanation of the algorithm with as little theory and math as possible
I totally agree but...
Beginning with the bit reversal and why it exists
Straight away there is a problem. The bit reversal exist because of the way we split the DFT sum into two sums of odd and even elements. That already calls for some tolerance of maths notation.
...continuing through to the butterflys with Beans description
There are no butterflies in Beans description. However I would like "FFD" to get the reader from the mathematical definition of the DFT to Beans code with the minimum of pain. I believe that is possible. Only requires getting the reader to accept Euler's formula without proof.
...finally a description of the three loops
I can't for the life of me see how to give an account of those three loops in a meaningful way without going through the basic mathematical steps of splitting up the DFT sum and factoring out the common "twiddle" factors. Then optimizing the two "twiddles" down to one using a trig identity. All the while suffering from "e" and "i" and "pi".
I agree with the above, and my massive gelatinous cranium comes up with this:
The Fourier for Dummies should be divided into sections of increasing compleity and detail, but each section potentially stand alone.
1) the 'kid' explanation with no math
2) the 'girlfriend/boyfriend' explanation that talks about what going on without scaring them off
3a) the programmer's explanation for somebody that just want to use it and get on with life; doesn't particularly care why it works
3b) the engineer's explanation for somebody that might want to adapt it for the hardware?
4) heater's explanation, for those on the brink of real understanding
5) Erna's explanation, that includes the darkest, scariest math secrets and alchemy
Sorry if these classifications are rude, this is the only way to express this thought in the short time available to me; I'll edit it out if need be.
Tricky already. The fundamental idea with Fourier is that if you multiply the amplitudes of a sine wave by those of another sine wave then take the average value of the results over an infinite time you get zero except when both frequencies are exactly the same. Therefore you can use that fact to detect a particular frequency in your signal by multiplying the signal by a sine wave of the frequency of interest and averaging the result. How to get over that idea without the reader being aware of sin and cos at least?
2) the 'girlfriend/boyfriend' explanation that talks about what going on without scaring them off
Impossible for me to imagine. The woman in my life speaks Finnish, Swedish, English and Hebrew. But try to talk anything technical and she's soon changing the subject and/or language.
3a) the programmer's explanation for somebody that just want to use it and get on with life; doesn't particularly care why it works
No. Not here. Isn't there plenty of that on the net already?
3b) the engineer's explanation for somebody that might want to adapt it for the hardware?
Yep.
4) heater's explanation, for those on the brink of real understanding
I think it is possible. As I said before, from equation to code with barely more maths required than cos and sin.
5) Erna's explanation, that includes the darkest, scariest math secrets and alchemy
Here's an interesting Fourier related coincidence.
In 1965 Gordon Moore predicted that the number of transistors that could be integrated onto a chip would double every 18 months or so. Thus predicting the massive increases in computer performance that we have seen since. (Small transistors means you can have more to do work but also that you can run them faster).
1965 just happens to be the year that Cooley and Tookey published their paper on the Fast Fourier Transform. An algorithm that increased the speed at which one could perform Fourier analysis by a factor of thousands and more.
These two events are kind of related by this paper that points out that for many tasks the increase in performance has been more due to better algorithms being discovered than by brute force increase of computer speed.
Lets go a little back and see, that there is at periodical way to think: http://www.nsf.gov/od/lpa/nsf50/vbush1945.htm. Hopefully, this time someone will follow recommendations. Event if this new report has much more pages to read!
Tricky already. The fundamental idea with Fourier is that if you multiply the amplitudes of a sine wave by those of another sine wave then take the average value of the results over an infinite time you get zero except when both frequencies are exactly the same. Therefore you can use that fact to detect a particular frequency in your signal by multiplying the signal by a sine wave of the frequency of interest and averaging the result. How to get over that idea without the reader being aware of sin and cos at least?
Sorry, I was unclear. I meant no formulas. Everybody can recognize a graph of sin and cos. I was trying to express somehow using the picture.
This link shows the direction I hope to go with all this. "Kids publish study in Royal Society Journal"
So using the list from post #168, it looks like heater and Erna's team will be focusing on items 3 and over; myself and others will be another team focusing on items 3 and under. Are there any primary school educators watching? Please PM me, I would like to talk to you.
You showed a graph, so did you store the output to a file and made the graphical representation separately or is the graph created in real time? If yes, I could try to use Aribas PropTerminal
Ah the graphs. Actually I used gtkterm as a serial terminal under Linux, saved the data from the Prop to a file and used gnuplot to draw the graph from that.
I didn't want to add any more I/O code than the minimum to show that it works.
OK reading the preface of the "Black Box" book has made me feel better. For years I could not connect the FFT algorithm as seen in example codes with the maths of the Fourier Transform as presented in uni. Now I know why:
However, to many computing and engineering professionals, the large collection of serial and parallel algorithms remain hidden inside the FFT black box because:
(1) coverage of the FFT in computing and engineering text books is usually brief, typically only a few pages are spent on the algorithmic aspects
of the FFT
(2) cryptic and highly variable mathematical and algorithmic notation
(3) limited length of journal articles
(4) important ideas and techniques in designing efficient algorithms are sometimes buried in software or hardware-implemented FFT programs, and not published in the open literature.
Also
Although the FFT, like binary search and quicksort, is commonly used in textbooks to illustrate the divide and conquer paradigm and recursive algorithms, the FFT has a unique feature: the application of the basic FFT algorithm to naturally ordered input, if performed in place, yields output in bit-reversed order. While this feature may be taken for granted by FFT insiders, it is often not addressed in detail in textbooks.
I am thankful for your work, many great explanations. I thank you very much for your ability and willingness to explain the mathematical side of these concepts.
You definitely seem to me (from that I have read of yours) to be more a Mathematician than a scientist (mathematics is a language of absolutes were one exception disproves a rule, while science is the art of the indefinite, were in no theory, "LAW", or axiom is considered as an absolute).
I must say that sometimes your view is way to concrete, in dealing with concepts. There is an importance in considering the more ethereal side of this, Especially in light of the accepted (near axiom) that to observe anything is to change its very nature, or the fact that the result of the DFT if reversed beyond the bounds of the original samples would indeed produce a repeating waveform that matches the initial sample and may or may not match any portion of the waveform after or before the sample period, and the reversal could be extended on to infinity both directions.
ErNa
Thank you for providing the ethereal side to balance out the absolutes. I do not think this thread would have been comprehensible without both sides. Now if it were possible for one person to provide and understand both sides as the perfectly interwoven area of knowledge and method that they are.
I thank you for you thanks. Whilst we have had a good talk about FFT we still have not created that "FFT For Dummies" that gets the reader from the FFT definition, to an understanding of why it is defined that way, to being able to create the FFT in code. Preferably without too much unnecessary math that fogs the essential idea. I hope to have time to work on that again one day.
Your comment about me being a mathematician made me chuckle. It would have made my maths proffs chuckle to:) I've never considered it one of my strong points, if indeed I have any strong points. After all it has taken many years for the FFT penny to drop for me. As it happens I am a physics graduate, but then 90% of our studies there was maths.
I do agree about the "ethereal side". Assuming I understand what you are getting at that is And I do appricieate this business about visualizing extention of waveform out to infinity in both directions.
Thing is you can take almost any part of mathematics and everyone will be looking at it from different directions and take different things away from it. That's how maths progresses I guess. For rmy FFT explanations I like to stick within the finite bounds of the computer we are going to use to calculate it. Those limits are a cold, hard, practical reality. The computer knows nothing of the "infinity" of which you speak.
Upshot is that we might think of the thing extending to infinity and mathematically we might think in terms of continuous functions rather than discreet samples. Integrals instead of sums. But we should be aware of the limitations that occur once we have digitized all this into a machine.
As calling you a mathematician I refer to this preference to confine to confine to the absolute bounds, In this case the limit of sampled waveforms for Fourier operations. I must chuckle at your statement about summation verses integration as even the real world summation approaches integration as the sample rate approaches infinity (I know, I do not wish to write this all out as it would take me many pages).
Comments
Optimized the butterfly from 4 multiplies to 3
Reduced "twiddle" tables from words to longs.
and since this thread was born from Beans excellent Description of the CORDIC algorithm
and it is something that can be used when building the twiddle factors.
I think we should pay homage to Bean and use a cordic package.
I am uploading the Trig package I cobbled together (after stealing it out of Beau Schwabs Compass module) along with a very simple demo of its use.
Complex numbers are written: A + iB and that doesn't mean, that two numbers are added, but the "+" just shows: a complex number has two components, that are not comparable and so they can not be added. The two parts of a complex have nothing in common, therefor they have to be combined to be a unity.
Sounds complicated, but is really simple. 5 + 6 = 11. But 5 beer and 6 coke = 5 beer + coke. As we were used to drink beer, before coke was discovered, we just wrote: give me 5 and we all knew: he meant beer. And now, after coke, we order 5 + 6 coke. And as coke was invented after, they called: give me 4 and imaginary 6.
Now, as there are different brands of coke, beer, and so many hard and soft drinks, we have forgotten, how everything began.
Back to complex numbers: we are used to put down complex numbers in a plane and could write: Ax + By. So we can identify a complex number as a two dimensional vector. And instead of the Cartesian coordinates X,Y we also could use polar coordinates L, phi (length and angle). And from this back to Cartesian, we could write L * cos (phi) x + L * sin (Phi) y, or: L * cos (phi) + i L * sin (Phi)
But there is still one question: what is the difference between a 2 dimensional vector and a complex number?
To me the answer is: a number is just a number, but a number only makes sense, if there are rules to combine numbers, rules to add and multiply. And that makes the difference.
If we add two vectors, we add the components like we add normal numbers: a1x + b1y (first vector) + a2x + b2y (second vector) = (a1+a2)x + (b1+b2)y
Still be aware: a1x + b1y means: we combine two numbers, a1 and b1 to form one unit and a1 and b1 have nothing in common, they show into perpendicular directions. We normally write (a1, b1)
Addition is the same for complex numbers, drawn as vectors, but noted in the form a1 + ib1
The difference comes from multiplication of two vectors:
If we multiply a1x + b1y (first vector) * a2x + b2y we apply the rule, that the x- and y-components are individually multiplied and both results are added.
If we multiply complex numbers, a1 + i b1 and a2 + i b2 we multiply them similar to binominals, (a1 + i b1) * (a2 - i b2) = a1*a2 - ib1*ib2 - a1*ib2 + a2*ib1
There is a little, but important difference: in the second complex number the sign of the imaginary part is flipped!
Why is this important:
Imagine you have to 2-dimensional vectors 0x + 1y and 1x + 0y, so these vectors obviously are orthogonal, because one shows to y, one to x. There scalar product is 0*1 + 1*0 = 0
Now we have to complex numbers: 0x + 1y and 1x + 0y, or as we like to write: 0 + i1 and 1 + 0i.
If we multiply them we have: ( 0 + i1 ) * ( 1 - i0) = 0*1 - i1*i0 - 0*i0 + i1*1 = 0 - 0 - 0 - i*1
And that obviously is not zero! But if we had seen the two numbers as vectors, they were orthogonal and there scalar product must be zero.
So, from this follows: sometimes it makes sense to see complex numbers as vectors in the X/Y-plane, but this is just to have a visualization. To do math it is not sufficient to have the numbers, it needs the rules too!
As usual we have a somewhat opposite views of things:) Although the practical result should be the same.
Actually I believe it does mean that they are added. For example, in simple algebra I might give you a number in the form:
x = 4 + 3y
That's not much use to you until you have a value for y. Say 2, then you know x is 10. You can't do the actual addition before you know the value of y
So it's the same with "i":
x = 4 + 3i
If we had a value for i we could do the addition. There is no fundamental difference of types like adding "coke" and "beer". In fact there are no types implied here at all.
Only problem is that we have defined "i" to be unknowable, the square root of minus one, therefore we can never do the addition.
Sometimes when writing code I realize I need a function to do something, also that I don't know how to do that thing yet, also that I'm busy thinking about some other part of the program right now. What to do? Easy, pretend I have such a function, give it a name, "foo", write a call to "foo()" at the appropriate point in the code, then get on with what I was doing. I will create foo() later.
The number "i" is the mathematical equivalent. We think of a thing, square root of minus one, and realize we can't evaluate it. We don't give up and stop there, no, we give it a name "i" and drop it into equations like anything else. After all we don't know what it is but we can say things about it "i squared is minus one". Magically the "i" can disappear at the end of our musings and leave as with a solid knowable result.
Fourier. Best wishes to all.
I am wondering if I can use this to determine THD (total harmonic distortion) of an inserted sine wave into a quality audio amp. That seems likely to be a good 'first project'.
Indeed you can. However it is not so easy. Let's say you want measure down to 0.01% distortion. That's one part in 10000 so already it looks like we need a good 16 bit ADC. Nowadays we might want 24 bits. We need to know that the ADC is distortion free to that level.
When it comes to doing it on the Prop, my code is not up to it. I'm using 32 bit arithmetic on fixed point values. 1.0 is scaled up to 4096 giving only 14 bit precision for the sine and cos tables. The input samples are limited to +/- 4096 so as to prevent overflow.
Of course it would be straight forward to extend this to 64 bit arithmetic or use the float32 object if it has enough accuracy. At a great loss of speed.
You say: x = 4 +3y is not much use, I say: from my view it's of much use. This equation gives you not one value, as you would have it with y=2, but you have a whole set of values and this equation defines a straight line with an inclination of 1/3 and crossing the y-axis at - 4/3 and the x-axis at 4. So this equation give you a infinite number of pairs of numbers.
And it is completely different situation with "i". If you write x = 4 + 3 i, than x is a symbol for the complex number (4, 3). x is no longer just a number, as it would be with an equation.
You say: if we had a value for "i", I say: we have this value for "i". And the value is given by the fact, that i*i = -1.
So it is not correct, if you state: "i" is defined to be unknowable. The square root of -1 is knowable, it is just not a real number.
Further: the "i" never disappears, and there is no magic.
Remember how we are taught to calculate. First the teacher introduced Pi, then "e", then one million, then he told us: don't be afraid, we leave this aside and come back to it later. That is, were all the problems come from: they didn't tell us, that there are complex numbers too, and hermitian vector spaces of infinite dimensionality. ;-)
OK, what I want to say: there is a way top down and bottom up. The whole picture we see in the end. And there is no difference.
Imagine: you are starting with natural numbers, then we introduce negative number, as the inverse operation to + creates numbers, we do not get, when adding natural numbers. That we introduce p/q to have the inversion of multiplication.
Imagine: you could say: it is only allowed to subtract a number from another one, if this number was added before. Then you never would get negative numbers. But what if you added 4 and subtracted 3 and 1? Still there is no negative value. But if you subtracted 4 twice?
You see, the natural way is to "invent" negative numbers or to "discover" negative numbers.
Step by step we fill the gaps between the natural numbers and we discover, that there is even between 0 and 1 an infinite amount of numbers. And if we calculate 1/x we see, that just in the neighborhood of 0 there is a infinite amount of numbers. And that there are numbers like Pi, which only can be expressed exactly by saying: this is the relation of an circles circumference and his diameter.
And "i" is just the square root of -1. But why do we not need the square root of -2? Because this would be a very complicated number. As we know, we do not know the value of sqrt(2), but we only know, that the square of this value is 2. And what, if the situation will be complicated by introducing "i"? We would just by overstressed.
But, rescue is near: we remember,. that -2 = -1 * +2 and that sqrt( -2) =sgrt( -1) * sqrt(+2), and so we divided the problem an conquered!
Do we share now the same point of view?
Of course we do. Sometimes:) I just occasionally find myself walking around an idea, looking at it from different angles, kicking the wheels, and seeing if I want to buy it or not.
Yes, you are right. I just meant that it could not be simplified any more, down to an actual single number. As with my statement about "i", we may not know what "y" is but that does not stop us using it in equations and getting useful statements.
Not from my current point of view. What if I give you "x = 4 + y" and I don't tell that "y = 3i"? You could work with that up until the point you want to get a single result.
[/quote]
Ah, there is the thing. "x" here is not just a normal value, it has two parts. So:
x = 4 + 3i
is actually two equations:
1) Knowable part of x = 4
2) Unknowable part of x = 3
We just can't simplify any more. When we write "x = ..." and say x is complex" then all we are doing is inventing a short hand notation for the two equations. That's all.
What?!
How can you say "we have this value for "i"" whilst at the same time saying "i" is the square root of minus one? Which is a value we for sure do not have!
It is not knowable. Please write it down if you have it:) But as we see using the trick of "just name it and continue anyway" it becomes useful.
Sure it can disappear. The output of the FFT, for example, is not normally presented directly in (real, imag) form but the magnitudes of each frequency are calculated. POOF! The i's vapourize.
Alternatively one could somehow display the FFT result showing both frequency and phase. POOF! the i's have gone again.
Or one could just present the results a raw real, imag pairs. But then one is just casually dropping the i's, acknowledging that it was just a notational trick anyway and we were working with two sets of equations all along.
Perhaps we should avoid the word "magic" when talking maths, although it does quite often seem quite spooky, full of happy coincidences that just happen to get you where you want to be.
Now here is a thing, from simple algebra we can show that:
(a + ib) * (c + id) = (ac - bd) + i(ad + bc)
I will say there is "magic" here. We have previously stated that we can't combine the so called "real" and "imaginary" parts through addition and simplify our complex numbers.
BUT look what has happened here. The "b" and "d" of the imaginary world are showing up and having an effect in the real world side of the result. And vice-versa. Cool hey?
Here is another thing:
The input to the FFT is in (real,imaginary) pairs. We put the input signal into the real part.
BUT we could put the input signal into the "imaginary" part. The frequency magnitude result would be the same. There is nothing more or less real about either part of the input.
"Now here is a thing, from simple algebra we can show that: (a + ib) * (c + id) = (ac - bd) + i(ad + bc)"
Yes, you can show this from simple algebra, the problem is: we are not facing "simple algebra".
Let me explain: the value of 1 is, funny things happen, : 1 And: here value and absolute value are equal. This is not true for -1. Here the value is -1, the absolute value: +1! So, why should we define a property for 1 and -1, which is equal, so that there is no difference between -1 and 1? There is a reason: sometimes it doesn't matter, like when calculation kinetic energy.
Now take this situation: you are here, another person1 is one mile away. The persons are 1 mile apart. There is a third person2, also one mile distant from you. But what is the distance person2-person1. We can not know this, but the distance is not negative and less equal 2 miles. Depending on the situation, we may run into a problem if we do not know more. That is a reason to introduce coordinates. Again: we assume, the persons are in a plane, so we have a 2-dimensional case. Now, as the persons have X and Y coordinates, we are able to determine the distances from the coordinates.
Now, we could introduce coordinates X, Y, because we are used to do so. And we know, that very easily we can expand this to Z and even more, if necessary.
But there is a second way when we know, that we are looking to a plane and there are only 2 coordinates: We call the X- coordinate with no name and the Y-coordinate with the name "i".
Now we place one person in the center, the second somewhere else. Ok, for simplicity: let the second be in a distance of 1, so actually, somewhere on a circle with radius 1.
In the first case we determine the distance by calculation sqrt (x*x + y*y)
Now we are used to express positions in a plane by using distance and angle phi. And from this we know: the x-axis is cos(phi), y: sin(phi), if radius = 1
Let us see this scene from a different point of view:
We are used to see numbers arranged on a number ray. And there is no place for a number sqrt(-1). So we invent the plane of complex numbers. And i now defines the y-coordinate.
Now we expanded our universe of numbers from one-component numbers to two-component numbers.
But as we use the same representation for complex numbers as we use for 2-dimensional vectors, we still have to see them as different things! But to a certain degree there is a relation.
Now we have two ways to define a circle in a plane:
By giving two coordinates X, Y cos(phi), sin(phi)
or by giving a complex number cos(phi) + i sin(phi)
No let us calculate the distance from center to a point on the circle:
D = sqrt (cos(phi)²+ sin(phi)²) for the first case, and the length is 1, as we commonly believe ;-)
or, using "simple algebra"
D² = (cos(phi) + i sin(phi)) * (cos(phi) + i sin(phi)) = cos(phi)² - sin(phi)² + i * 2 * (sin(phi) * cos(phi))
So, this equation is not really simple to solve. What is the distance?
As mathematicians are men and men are lazy, the solved this problem that way:
Knowing, that (a+b)*(a-b) = a² - b² they just said: if we have to multiply two complex numbers, we have to invert the sign of the complex part of the second number!
D² = (cos(phi) + i sin(phi)) * (cos(phi) - i sin(phi)) = cos(phi)² + sin(phi)²
And now, oh miracle, we have the same result as we have it from X/Y point of view!
Mathematicians use i, engineers use j!
a) draft an outline of the explanation document
b) try to define target and scope of the explanation
c) just go through the thread and stitch together the various points from the discussion
d) continue the discussion, there is still not enough to work with
Do any of these choices seem more appropriate than the others? Any other suggestions?
but to answer you directly:
First before anything else we need to define the audience because no matter what we write (as we have already seen here) there will be some that will feel it just doesn't get it without something else or it went too far in such and such an area. This is not a put down on anything or anyone in this thread it just reflects the reality of different levels and personalities.
As for myself I vote for a straight forward explanation of the algorithm with as little theory and math as possible. Beginning with the bit reversal and why it exists continuing through to the butterflys with Beans description and finally a description of the three loops. In other words a straight forward description of the classic algorithm and in the order it is most commonly written.
But this is just my take on how to proceed.
Yes it's quiet. That's because we are all deep in thought. Did you see my description of "Fourier Syndrome"?
I have Fourier syndrome so bad that I had the overwhelming compulsion to recast my Spin FFT program into PASM.
The result is the attached program heater_fft.spin that has both Spin and PASM FFTs in it. Either use BST and the #define syntax to select which version is compiled or manually remove the version you don't want.
Now, here is the amazing part. heater_fft turns out to be almost twice as fast as the FFT_1024.SPIN that is knocking around these threads! 1024 point FFT in 40ms. That's 25 per second and I have not even tried to optimize the PASM yet.
I will attempt to tidy this up a bit, use the Props sin table instead of my own, optimize a few things. But this basically works.
Now to think about that "Fast Fourier Transform For Dummies" before I forget the troubles I had getting to this point.
I totally agree but...
Straight away there is a problem. The bit reversal exist because of the way we split the DFT sum into two sums of odd and even elements. That already calls for some tolerance of maths notation.
There are no butterflies in Beans description. However I would like "FFD" to get the reader from the mathematical definition of the DFT to Beans code with the minimum of pain. I believe that is possible. Only requires getting the reader to accept Euler's formula without proof.
I can't for the life of me see how to give an account of those three loops in a meaningful way without going through the basic mathematical steps of splitting up the DFT sum and factoring out the common "twiddle" factors. Then optimizing the two "twiddles" down to one using a trig identity. All the while suffering from "e" and "i" and "pi".
The Fourier for Dummies should be divided into sections of increasing compleity and detail, but each section potentially stand alone.
1) the 'kid' explanation with no math
2) the 'girlfriend/boyfriend' explanation that talks about what going on without scaring them off
3a) the programmer's explanation for somebody that just want to use it and get on with life; doesn't particularly care why it works
3b) the engineer's explanation for somebody that might want to adapt it for the hardware?
4) heater's explanation, for those on the brink of real understanding
5) Erna's explanation, that includes the darkest, scariest math secrets and alchemy
Sorry if these classifications are rude, this is the only way to express this thought in the short time available to me; I'll edit it out if need be.
Tricky already. The fundamental idea with Fourier is that if you multiply the amplitudes of a sine wave by those of another sine wave then take the average value of the results over an infinite time you get zero except when both frequencies are exactly the same. Therefore you can use that fact to detect a particular frequency in your signal by multiplying the signal by a sine wave of the frequency of interest and averaging the result. How to get over that idea without the reader being aware of sin and cos at least?
Impossible for me to imagine. The woman in my life speaks Finnish, Swedish, English and Hebrew. But try to talk anything technical and she's soon changing the subject and/or language.
No. Not here. Isn't there plenty of that on the net already?
Yep.
I think it is possible. As I said before, from equation to code with barely more maths required than cos and sin.
The sky is the limit on complexity here:)
In 1965 Gordon Moore predicted that the number of transistors that could be integrated onto a chip would double every 18 months or so. Thus predicting the massive increases in computer performance that we have seen since. (Small transistors means you can have more to do work but also that you can run them faster).
1965 just happens to be the year that Cooley and Tookey published their paper on the Fast Fourier Transform. An algorithm that increased the speed at which one could perform Fourier analysis by a factor of thousands and more.
These two events are kind of related by this paper that points out that for many tasks the increase in performance has been more due to better algorithms being discovered than by brute force increase of computer speed.
http://agtb.wordpress.com/2010/12/23/progress-in-algorithms-beats-moore%E2%80%99s-law/
Sorry, I was unclear. I meant no formulas. Everybody can recognize a graph of sin and cos. I was trying to express somehow using the picture.
This link shows the direction I hope to go with all this. "Kids publish study in Royal Society Journal"
http://blogs.discovermagazine.com/notrocketscience/2010/12/21/eight-year-old-children-publish-bee-study-in-royal-society-journal/
So using the list from post #168, it looks like heater and Erna's team will be focusing on items 3 and over; myself and others will be another team focusing on items 3 and under. Are there any primary school educators watching? Please PM me, I would like to talk to you.
Do you mean the heater_fft? It just uses FullDuplexSerial to print 512 frequency magnitudes for display with the terminal screen in the Prop Tool or BST.
heater_fft has it's own thread now: http://forums.parallax.com/showthread.php?128292-Heater-s-Fast-Fourier-Transform.
I didn't want to add any more I/O code than the minimum to show that it works.
"INSIDE the FFT BLACK BOX Serial and Parallel Fast Fourier Transform Algorithms"
By Eleanor Chu (University of Guelph, Ontario, Canada) and Alan George (University of Waterloo, Ontario, Canada).
http://www.google.fi/url?sa=t&source=web&cd=9&ved=0CGIQFjAI&url=http%3A%2F%2Fread.pudn.com%2Fdownloads155%2Fdoc%2Fcomm%2F686281%2F(ebook)%2520CRC%2520Press%2520-%2520Inside%2520The%2520Fft%2520Black%2520Box-%2520Serial%2520And%2520Parallel%2520Fast%2520Fourier%2520Transform%2520Algorith.pdf&rct=j&q=Inside%20the%20FFT%20Black%20Box&ei=GC4nTcyQLMfDswb37IGzAg&usg=AFQjCNExQjMm276-O87m1mDuBRs63MlEtg&sig2=1Dx9-mr3K3juyWH_JDA0FA&cad=rja
Mind bending!
Also
I don't feel some dumb anymore:)
I am thankful for your work, many great explanations. I thank you very much for your ability and willingness to explain the mathematical side of these concepts.
You definitely seem to me (from that I have read of yours) to be more a Mathematician than a scientist (mathematics is a language of absolutes were one exception disproves a rule, while science is the art of the indefinite, were in no theory, "LAW", or axiom is considered as an absolute).
I must say that sometimes your view is way to concrete, in dealing with concepts. There is an importance in considering the more ethereal side of this, Especially in light of the accepted (near axiom) that to observe anything is to change its very nature, or the fact that the result of the DFT if reversed beyond the bounds of the original samples would indeed produce a repeating waveform that matches the initial sample and may or may not match any portion of the waveform after or before the sample period, and the reversal could be extended on to infinity both directions.
ErNa
Thank you for providing the ethereal side to balance out the absolutes. I do not think this thread would have been comprehensible without both sides. Now if it were possible for one person to provide and understand both sides as the perfectly interwoven area of knowledge and method that they are.
I thank you for you thanks. Whilst we have had a good talk about FFT we still have not created that "FFT For Dummies" that gets the reader from the FFT definition, to an understanding of why it is defined that way, to being able to create the FFT in code. Preferably without too much unnecessary math that fogs the essential idea. I hope to have time to work on that again one day.
Your comment about me being a mathematician made me chuckle. It would have made my maths proffs chuckle to:) I've never considered it one of my strong points, if indeed I have any strong points. After all it has taken many years for the FFT penny to drop for me. As it happens I am a physics graduate, but then 90% of our studies there was maths.
I do agree about the "ethereal side". Assuming I understand what you are getting at that is
Thing is you can take almost any part of mathematics and everyone will be looking at it from different directions and take different things away from it. That's how maths progresses I guess. For rmy FFT explanations I like to stick within the finite bounds of the computer we are going to use to calculate it. Those limits are a cold, hard, practical reality. The computer knows nothing of the "infinity" of which you speak.
Upshot is that we might think of the thing extending to infinity and mathematically we might think in terms of continuous functions rather than discreet samples. Integrals instead of sums. But we should be aware of the limitations that occur once we have digitized all this into a machine.
As calling you a mathematician I refer to this preference to confine to confine to the absolute bounds, In this case the limit of sampled waveforms for Fourier operations. I must chuckle at your statement about summation verses integration as even the real world summation approaches integration as the sample rate approaches infinity (I know, I do not wish to write this all out as it would take me many pages).