Fast Fourier Transform - Signal Processing of Random Physiological Signals - page 146

periodically the values taken on when r < N / 2. Therefore, substituting r + N / 2 for r

in (13.7), one can obtain (13.8) by using the Twiddle Factor, W = exp( − 2 π j / N ).

W r C r A r = B r + (13.7)

W r C r A r + = B r − (13.8)

N
2

2 points of the discrete Fourier
transform of the data x k can be simply obtained from the DFT of both sequences of N

From (13.7) and (13.8), the first N / 2 and last N /

2
samples. Assuming that one has a method that computes DFTs in a time proportional to
the square of the number of samples, the algorithm can be used to compute the transforms
of the odd and even data sequences using the Ar (13.7) and Ar

/

+ N / 2 (13.8) equations

2) 2 .
Since it has been shown that the computation of the DFT of N samples can be
reduced to computing the DFTs of two sequences of N

to find Ar . The N operations require a time proportional to 2( N /

2 samples, the computation
of the sequence B k or C k can be reduced by decimation in time to the computation of
sequences of N

/

4 samples. These reductions can be carried out as long as each function
has a number of samples that are divisible by 2. Thus, if N

/

2 n , n such reductions (often =

referred to as “Stages”) can be made.
For example, the successive decimation (reduction) of a Discrete Fourier Transform
will result in a Fast Fourier Transform with fewer computations. In general, N log 2 N
complex additions and at most (1 2) N log 2 N complex multiplications are required for

computation of the Fast Fourier Transform of an N point sequence, where N is a power
of2( N

/

2 n ). =

13.4.1 Derivation of FF T Algorithm
Consider the N -point DFT that can be reduced into two N / 2 DFTs (even and odd

indexed sequences), as x ( n ) is decomposed into two N / 2-point sequences (decimation-

in-time) and is shown in (13.9).

N
2

N
2

− 1 − 1

x (2 n ) W 2 nk 1) W (2 n +1) k x ( k ) = + x (2 n + (13.9)

· · ·

N N

n = 0 n = 0