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
y fft(x);
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
data.
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
511-point DFT.
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
modified as
f
k
k À 1
f
s
N
, k 1 , 2, . . . , N
7:2:12
for indexing into the y vector that contains X(k).
The IFFT algorithm is implemented in the MATLAB function ifft, which can be
used as
y ifft(x);
or
y ifft(x,N);
The characteristics and usage of ifft are the same as those for fft.
FAST FOURIER TRANSFORMS
321