unctions are sometimes known as 'twiddle factors'. The basis functions are periodic and define points on the unit circle in the complex plane. Figure 2.4 illustrates the cyclic property of the This summation can be evaluated using the geometric series basis functions for an eight point DFT, and the basis functions are summation to give Equation 2.66. equally spaced around the unit circle at frequency increments of F/N, where F is the sampling rate of the input signal sequence. In (2.66) this figure the cyclic character of the twiddle factors are illustrated as follows: Defining S by Equation 2.67, the DFT of x(n) can be written as in Equation 2.68. = 2x(A-1) 2r (2.67) (2.68) The set of frequency samples which define the spectrum X(k), are given on a frequency axis whose discrete frequency locations are The first term in this expression is the phase of the response, and given by Equation 2.63 where k = 0, 1. N-1. the ratio of sines is the amplitude response. If k is an integer, then X(k) = 1, for these values of k, and zero elsewhere. If k is not an (2.63) integer, then none of the DFT values are zero. This is called spectral leakage. Hence, an unit impulse at the kth frequency location is only obtained when Equation 2.69 is satisfied, where k is an integer. The inverse discrete Fourier transform 2/9 Magnitude Phase Degrees Fractional sampling frequency Figure 2.5 Frequency and phase response of a DFT bin output for an eight point FFT: (a) magnitude; (b) phase angle fk = KN (2.69) The FFT is a fast algorithm for the efficient implementation of the DFT where the number of time samples of the input signal N are transformed into N frequency points, and the required number of Figure 2.5 shows the frequency response of a DFT bin output for arithmetic operations are reduced to the order of N 1082 (N ). Sev- an eight point DFT, and the high sidelobe levels are a consequence of truncation. eral approaches can be used to develop the FFT algorithm. Starting with the DFT expression, consider factorising it into two DFT's of,