§5 Fast Fourier Transform
1.
Finite discrete Fourier transform
[ Various Forms of Finite Discrete Fourier Transform ]
real (or complex) sequence f ( kh ) |
Finite discrete Fourier transform and its inversion formula _{} |
hd |
_{} ( N is a positive integer) |
_{} |
_{} |
_{} ( N is a positive integer) |
_{} |
_{} |
_{} ( k , N is an integer) |
_{} |
_{} |
[ Convolution and its properties ] Let the real (or complex) sequence g ( kh ) be a sequence with period Nh , which is called_{}_{}
_{}
is the convolution of the sequences f and g . Let
_{}
_{} _{}
then _{}
_{}
Second, the
fast Fourier transform algorithm
The Fast Fourier Transform ( FFT ) algorithm is a fast method for computing finite discrete Fourier transforms .
[ FFT algorithm of complex sequence ] To calculate the finite discrete Fourier transform of the complex sequence { z _{k} } , is to calculate the form _{}_{}_{}
_{}, _{}
The finite term sum of . For the inversion formula, the calculation method is similar .
Let N = 2 ^{m} , , _{}then
_{}
set again _{}
_{}
are the binary representations of k and j , respectively , and take the value 0 or 1. Then_{}_{}
_{}
because = _{}_{}
=_{}
=_{}
so
_{}_{}
This leads to the recursive formula:
_{}
_{}
_{}
_{}
_{}_{}
_{}
_{}_{}
Finally there is
_{}
[ FFT Algorithm for Real Sequences ] Finite Discrete Fourier Cosine Transforms and Sine Transforms to be Calculated for Real Sequences with 2 N ( N = 2 ^{m} ) Elements ^{}_{}_{}_{}
_{} _{}
_{} _{}
The FFT algorithm can be used first for complex sequences
z _{k} =x _{k} +iy _{k}_{ }
calculate
_{}
And c _{j} , s _{j} use the following formula to find _{}_{}
_{} _{}
As for c _{j}_{} , the value of s _{j} is when _{}
_{}