[<<][math][>>][..]
Sat Jul 14 22:31:22 EDT 2012

## FFT: recursive construction of analysis functions

Some simplified visualization of composition of analysis functions in
the FFT.  A bin in an FFT/DFT is the input signal modulated by an
oscillatory analysis function, then summed (averaged).

The oscillatory functions have the property that time shift is the
same as multiplication by a phase rotation factor.

The idea is that for N, the basic oscillation has N phase
states, here represented as numbers from 0 to N-1.

N=2

0 0
0 1

N=4

0 0 0 0
0 1 2 3
0 2 0 2
0 3 2 1

N=8

0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7
0 2 4 6 0 2 4 6
0 3 6 1 4 7 2 5
0 4 0 4 0 4 0 4
0 5 2 7 4 1 6 3
0 6 4 2 0 6 4 2
0 7 6 5 4 3 2 1

Going from N=2 -> N=4 we have composition of 2 decimated signals with
the following base functions.  Here '.' means amplitude zero (we use 0
to indicate phase angle 0, amplitude 1).

( Expressed as angle = x \in [0,1] )

0 . 0 .
0 . 1 .
. 0 . 0
. 0 . 1

( Expressed as angle = x \in [0,3] )

0 . 0 .
0 . 2 .
. 0 . 0
. 0 . 2

To create the 4 base functions for N=4 it is clear that the rotated
odd sampled base functions need to be added to the even sampled ones
to create all 4 base functions.  Rotation of base functions commutes
with weighted summation, hence in the FFT the rotation happens on the
composition of FFT bins from the 2 shifted contributions, i.e. the
combination of 2 weighted sums.

even/odd contr     rotation of odd base function
------------------------------------------------

N=4

0 . 0 .
. 0 . 0            0

0 . 2 .
. 1 . 3            1

0 . 0 .
. 2 . 2            2  (= phase 0, ampl: -1)

0 . 2 .
. 3 . 1            3  (= phase 1, ampl: -1)

N=8

0 . 0 . 0 . 0 .
. 0 . 0 . 0 . 0    0

0 . 2 . 4 . 6 .
. 1 . 3 . 5 . 7    1

0 . 4 . 0 . 4 .
. 2 . 6 . 2 . 6    2

0 . 6 . 4 . 2 .
. 3 . 1 . 7 . 5    3

...

Note that a phase rotation by N/2 is a multiplication by -1, which
allows for some optimizations.

So what does an FFT do in plain language?

1) It uses 2 phase-shifted coarse analysis functions for frequency f
(expressed wrt. decimation factor N) to construct a new, finer
detailed analysis function for frequency f.  This is done by applying
a phase shift to the second analysis function such that the decimation
gaps line up.

2) Using this finer analysis function f it constructs an analysis
function f+N/2 by modulating the first one with 1,-1,1,...  This
doubles the frequency resolution on each step.


[Reply][About]
[<<][math][>>][..]