[<<][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][>>][..]