routines are not as available for DSP processors. Radix-2 and radix-4 FFT algorithms
are the most common, although other radix values can be employed. Different radix
butterflies can be combined to form mixed-radix FFT algorithms.
7.2.4 MATLAB Implementations
As introduced in Section 4.4.4, MATLAB provides a function
to compute the DFT of time sequence x(n) in the vector x. If x is a matrix, y is the DFT
of each column of the matrix. If the length of the x is a power of 2, the fft function
employs a high-speed radix-2 FFT algorithm. Otherwise a slower mixed-radix algo-
rithm is employed.
An alternative way of using fft function is
y fft(x, N);
to perform N-point FFT. If the length of x is less than N, then the vector x is
padded with trailing zeros to length N. If the length of x is greater than N, fft
function truncates the sequence x and only performs the FFT of the first N samples of
The execution time of the fft function depends on the input data type and the
sequence length. If the input data is real-valued, it computes a real power-of-two FFT
algorithm that is faster than a complex FFT of the same length. As mentioned earlier,
the execution is fastest if the sequence length is exactly a power of 2. For this reason, it
is usually better to use power-of-two FFT. For example, if the length of x is 511,
the function y fft(x, 512)will be computed faster than fft(x), which performs
It is important to note that the vectors in MATLAB are indexed from 1to N instead
of from 0 to N À 1given in the DFT and the IDFT definitions. Therefore the relation-
ship between the actual frequency in Hz and the frequency index k given in (7.1.9) is
k À 1
, k 1 , 2, . . . , N
for indexing into the y vector that contains X(k).
The IFFT algorithm is implemented in the MATLAB function ifft, which can be
The characteristics and usage of ifft are the same as those for fft.
FAST FOURIER TRANSFORMS