§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