DanielsonLanczos Lemma Observations

Note two things about the equations 7, 9 and 11, repeated below. First, the order of input values, x(n), is "reverse binary".For example, left to right the order for the 4 term equation is x(0), x(2), x(1) and x(3). The order for the 8 term equation is x(0), x(4), x(2), x(6), x(1), x(5), x(3), and x(7). This naturally happens when the DL Lemma is expanded. The Butterfly Diagram makes use of this fact. The second thing to note is that the "twiddled factors",W, build up with each new expansion, so that you multiply more together. The Butterfly diagram also deals with this by the adding of "stages", which you will see later in this tutorial.
Equation 7
Equation 9
Equation 11
More on the "Reverse Binary" pattern.
Here are two examples of the "reverse binary" example:
For 4 inputs:
Count from 0 to 3 in binary 00, 01, 10, 11. Now, reverse the bits of each number and you get 00, 10, 01, 11. In decimal this is 0, 2, 1, and 3.
So, the values in the DL equation would be x(0), x(2), x(1), and x(3). This is what you see in equation 9 above.
For 8 inputs:
Count from 0 to 7 in binary 000, 001, 010, 011, 100, 101, 110, 111. Now, reverse the bits of each number and you get 000, 100, 010, 110, 001, 101, 011, 111. In decimal this sequence is 0, 4, 2, 6, 1, 5, 3, and 7.
So, the values in the DL equation for 8 samples would be x(0), x(4), x(2), x(6), x(1), x(5), x(3), and x(7). This is what you see in equation 11 above.
The same pattern holds for all expansions of the DL Lemma, and is made use of by the Butterfly Diagram.
Next I'll discuss the "twiddle factor" and then put it together with the DanielsonLanczos Lemma to create the Butterfly diagram, which is the FFT in diagram form.
<< Previous  Next >> 