<html><head>
<meta http-equiv="Content-Type" content="text/html; charset=big5">
<meta name="GENERATOR" content="Microsoft FrontPage Express 2.0"><title>Fast Fourier Transform (FFT)</title>
<meta name="Microsoft Theme" content="indust 111, default"></head><body alink="#ff3300" background="fft_files/indtextb.jpg" bgcolor="#ffffff" link="#3366cc" text="#000000" vlink="#666666">
<p align="center">�@</p>
<p align="center"><font face="Times New Roman" size="6"><strong>Fast
Fourier Transform (FFT)</strong></font></p>
<p>�@</p>
<p><font face="Times New Roman" size="3">In this section we
present several methods for computing the DFT efficiently. In
view of the importance of the DFT in various digital signal
processing applications, such as linear filtering, correlation
analysis, and spectrum analysis, its efficient computation is a
topic that has received considerable attention by many
mathematicians, engineers, and applied scientists.</font></p>
<p><font face="Times New Roman" size="3">From this point, we
change the notation that <em>X(k)</em>, instead of <em>y(k)</em>
in previous sections, represents the Fourier coefficients of<em>
x(n)</em>.</font></p>
<p><font face="Times New Roman" size="3">Basically, the
computational problem for the DFT is to compute the sequence {<em>X</em>(<em>k</em>)}
of <em>N</em> complex-valued numbers given another sequence of
data {<em>x</em>(<em>n</em>)} of length <em>N</em>, according to
the formula</font></p>
<p align="center"><img src="fft_files/image39.gif" height="72" width="253"></p>
<p><font face="Times New Roman" size="3">In general, the data
sequence <em>x</em>(<em>n</em>) is also assumed to be complex
valued. Similarly, The IDFT becomes</font></p>
<p align="center"><img src="fft_files/image40.gif" height="45" width="276"></p>
<p><font face="Times New Roman" size="3">Since DFT and IDFT
involve basically the same type of computations, our discussion
of efficient computational algorithms for the DFT applies as well
to the efficient computation of the IDFT.</font></p>
<p><font face="Times New Roman" size="3">We observe that for each
value of <em>k</em>, direct computation of <em>X</em>(<em>k</em>)
involves <em>N</em> complex multiplications (4<em>N</em> real
multiplications) and <em>N</em>-1 complex additions (4<em>N</em>-2
real additions). Consequently, to compute all <em>N</em> values
of the DFT requires <em>N</em><sup> 2</sup> complex
multiplications and <em>N</em><sup> 2</sup>-<em>N</em> complex
additions.</font></p>
<p><font face="Times New Roman" size="3">Direct computation of
the DFT is basically inefficient primarily because it does not
exploit the symmetry and periodicity properties of the phase
factor W<sub>N</sub>. In particular, these two properties are : </font></p>
<p align="center"><img src="fft_files/image34.gif" height="50" width="231"></p>
<p><font face="Times New Roman">The computationally efficient
algorithms described in this sectio, known collectively as fast
Fourier transform (FFT) algorithms, exploit these two basic
properties of the phase factor.</font></p>
<p>�@</p>
<p><font face="Times New Roman" size="4"><strong>Radix-2 FFT
Algorithms</strong></font></p>
<p><font face="Times New Roman">Let us consider the computation
of the <em>N</em> = 2<sup>v</sup> point DFT by the divide-and
conquer approach. We split the <em>N</em>-point data sequence
into two <em>N</em>/2-point data sequences <em>f</em><sub>1</sub>(<em>n</em>)
and <em>f</em><sub>2</sub>(<em>n</em>), corresponding to the
even-numbered and odd-numbered samples of <em>x</em>(<em>n</em>),
respectively, that is,</font></p>
<p align="center"><font face="Times New Roman"><img src="fft_files/image35.gif" height="56" width="257"></font></p>
<p><font face="Times New Roman">Thus <em>f</em><sub>1</sub>(<em>n</em>)
and <em>f</em><sub>2</sub>(<em>n</em>) are obtained by decimating
<em>x</em>(<em>n</em>) by a factor of 2, and hence the resulting
FFT algorithm is called a <em>decimation-in-time algorithm</em>.</font></p>
<p><font face="Times New Roman">Now the N-point DFT can be
expressed in terms of the DFT's of the decimated sequences as
follows:</font></p>
<p align="center"><img src="fft_files/image41.gif" height="130" width="316"></p>
<p><font face="Times New Roman">But <em>W</em><sub><em>N</em></sub><sup><em>2</em></sup><em>
= W</em><sub><em>N/2</em></sub>. With this substitution, the
equation can be expressed as</font></p>
<p align="center"><img src="fft_files/image42.gif" height="72" width="297"></p>
<p><font face="Times New Roman">where <em>F</em><sub>1</sub>(<em>k</em>)
and <em>F</em><sub>2</sub>(<em>k</em>) are the <em>N</em>/2-point
DFTs of the sequences <em>f</em><sub>1</sub>(<em>m</em>) and <em>f</em><sub>2</sub>(<em>m</em>),
respectively.</font></p>
<p><font face="Times New Roman">Since <em>F</em><sub>1</sub>(<em>k</em>)
and <em>F</em><sub>2</sub>(<em>k</em>) are periodic, with period<em>
N</em>/2, we have <em>F</em><sub>1</sub>(<em>k+N/2</em>)<em> = F</em><sub>1</sub>(<em>k</em>)
and <em>F</em><sub>2</sub>(<em>k+N/2</em>) = <em>F</em><sub>2</sub>(<em>k</em>).
In addition, the factor <em>W</em><sub><em>N</em></sub><sup><em>k+N/2</em></sup><em>
= -W</em><sub><em>N</em></sub><sup><em>k</em></sup><em>. </em>Hence
the equation may be expressed as</font></p>
<p align="center"><img src="fft_files/image43.gif" height="85" width="331"></p>
<p><font face="Times New Roman">We observe that the direct
computation of <em>F</em><sub>1</sub>(<em>k</em>) requires (<em>N</em>/2)<sup>2</sup>
complex multiplications. The same applies to the computation of <em>F</em><sub>2</sub>(<em>k</em>).
Furthermore, there are <em>N</em>/2 additional complex
multiplications required to compute <em>W</em><sub><em>N</em></sub><sup><em>k</em></sup><em>F</em><sub>2</sub>(<em>k</em>).
Hence the computation of <em>X</em>(<em>k</em>) requires 2(<em>N</em>/2)<sup>2</sup>
+ <em>N</em>/2 = <em>N </em><sup>2</sup>/2 + <em>N</em>/2 complex
multiplications. This first step results in a reduction of the
number of multiplications from <em>N</em><sup> 2 </sup>to <em>N </em><sup>2</sup>/2
+ <em>N</em>/2, which is about a factor of 2 for <em>N</em>
large.</font></p>
<p align="center"><font face="Times New Roman"><img src="fft_files/figure6.gif" height="425" width="799"></font></p>
<p align="center"><font face="Times New Roman"><strong>Figure
TC.3.1 </strong>First step in the decimation-in-time algorithm.</font></p>
<p>�@</p>
<p><font face="Times New Roman">By computing <em>N</em>/4-point
DFTs, we would obtain the <em>N</em>/2-point DFTs <em>F</em><sub>1</sub>(<em>k</em>)
and <em>F</em><sub>2</sub>(<em>k</em>) from the relations</font></p>
<p align="center"><font face="Times New Roman"><img src="fft_files/image44.gif" height="202" width="564"></font></p>
<p><font face="Times New Roman">The decimation of the data
sequence can be repeated again and again until the resulting
sequences are reduced to one-point sequences. For <em>N</em> = 2<sup>v</sup>,
this decimation can be performed v = log<sub>2</sub><em>N</em>
times. Thus the total number of complex multiplications is
reduced to (<em>N</em>/2)log<sub>2</sub><em>N</em>. The number of
complex additions is <em>N</em>log<sub>2</sub><em>N</em>.</font></p>
<p><font face="Times New Roman">For illustrative purposes, Figure
TC.3.2 depicts the computation of <em>N</em> = 8 point DFT. We
observe that the computation is performed in tree stages,
beginning with the computations of four two-point DFTs, then two
four-point DFTs, and finally, one eight-point DFT. The
combination for the smaller DFTs to form the larger DFT is
illustrated in Figure TC.3.3 for <em>N</em> = 8.</font></p>
<p align="center"><font face="Times New Roman"><img src="fft_files/figure7.gif" height="308" width="704"></font></p>
<p align="center"><font face="Times New Roman"><strong>Figure
TC.