Scribd
Upload
130 views

Dif FFT)

The document summarizes the Fast Fourier Transform (FFT) algorithm. It discusses two FFT methods: decimation-in-frequency and decimation-in-time. For decimation-in-frequency, the DFT definition is expanded and split into even and odd terms, reducing computations. For decimation-in-time, the input is split into even and odd indexed sequences, and the DFT definition is rearranged to compute the first and second half of frequency bins separately. Butterfly diagrams and block diagrams are provided to illustrate the computation flow for both methods. Examples are included to show applying the algorithms to compute a 4-point DFT sequence. The number of complex multiplications is also derived

Uploaded by

AHMED DARAJ
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
130 views

Dif FFT)

The document summarizes the Fast Fourier Transform (FFT) algorithm. It discusses two FFT methods: decimation-in-frequency and decimation-in-time. For decimation-in-frequency, the DFT definition is expanded and split into even and odd terms, reducing computations. For decimation-in-time, the input is split into even and odd indexed sequences, and the DFT definition is rearranged to compute the first and second half of frequency bins separately. Butterfly diagrams and block diagrams are provided to illustrate the computation flow for both methods. Examples are included to show applying the algorithms to compute a 4-point DFT sequence. The number of complex multiplications is also derived

Uploaded by

AHMED DARAJ
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

Digital Signal Processing/ 4th Class/ 2020-2021 Dr. Abbas Hussien & Dr.

Ammar Ghalib

Fast Fourier Transform (FFT)


7.1 Definition of FFT
FFT is a very efficient algorithm in computing DFT coefficients and can reduce a very
large amount of computational complexity (multiplications).

Consider the digital sequence x(n) consisting of 2m samples, where m is a positive


integer—the number of samples of the digital sequence x(n) is a power of 2, N = 2, 4, 8, 16, etc. If
x(n) does not contain 2m samples, then we simply append it with zeros until the number of the
appended sequence is equal to an integer of a power of 2 data points.

The number of points N=2m, where the stages m=log2 N.

In this section, we focus on two formats. One is called the decimation in- frequency
algorithm, while the other is the decimation-in-time algorithm. They are referred to as the radix-2
FFT algorithms.

7.1.1 Method of Decimation-in-Frequency (Reduced DIF FFT)


Beginning with the definition of DFT:

−j2π / N
Where, WN= e is the twiddle factor, and N = 0, 2, 4, 8, 16, … Equation (7.6) can be expanded
as:

If we split equation (7.7):

Then we can rewrite as a sum of the following two parts:

60
Digital Signal Processing/ 4th Class/ 2020-2021 Dr. Abbas Hussien & Dr. Ammar Ghalib

Modifying the second term in Equation (7.9) yields:

Now letting k = 2m as an even number achieves:

While substituting k = 2m + 1 as an odd number yields:

Where, a(n) and b(n) are introduced and expressed as:

61
Digital Signal Processing/ 4th Class/ 2020-2021 Dr. Abbas Hussien & Dr. Ammar Ghalib

Figure 7.7(a) illustrates the block diagram of N-point DIF FFT. Fig. 7.7(b) illustrates
reduced DIF FFT computation for the eight-point DFT, where there are 12 complex
multiplications as compared with the eight-point DFT with 64 complex multiplications. For a data
length of N, the number of complex multiplications for DFT and FFT, respectively, are determined
by:

Note: The input sequence is in normal order index and the output frequency bin number is in
reversal bits order. The Butterfly structure for DIF FFT and DIT FFT is shown below:

62
Digital Signal Processing/ 4th Class/ 2020-2021 Dr. Abbas Hussien & Dr. Ammar Ghalib

The inverse FFT is defined as:

The twiddle factor WN is changed to be , and the sum is multiplied by a factor of


1/N. Hence, the inverse FFT block diagram is achieved as shown in Fig. 7.8.

Example (1):
Given a sequence x(n) for 0 ≤ n ≤ 3, where x(0) = 1, x(1) = 2, x(2) = 3, and x(3) = 4

a. Evaluate its DFT X(k) using the decimation-in-frequency FFT method.


b. Determine the number of complex multiplications.

Solution:
a.

63
Digital Signal Processing/ 4th Class/ 2020-2021 Dr. Abbas Hussien & Dr. Ammar Ghalib

b. The number of complex multiplications is four, which can also be determined from eq. (7.19), where
N=4

7.1.2 Method of Decimation-in-Time (Reduced DIT FFT)


In this method, we split the input sequence x(n) into the even indexed x(2m) and x(2m +
1), each with N data points. Then Equation (7.6) becomes:

Define new functions as:

64
Digital Signal Processing/ 4th Class/ 2020-2021 Dr. Abbas Hussien & Dr. Ammar Ghalib

Note that:

Substituting Equations (7.24) into Equation (7.22) yields the first half frequency bins

Considering the following fact and using Equations (7.24):

Then the second half of frequency bins can be computed as follows:

The block diagram for the eight-point DIT FFT algorithm is illustrated in Fig. 7.9

65
Digital Signal Processing/ 4th Class/ 2020-2021 Dr. Abbas Hussien & Dr. Ammar Ghalib

The index for each input sequence element can be achieved by bit reversal of the frequency index in a
sequential order. Similar to the method of decimation-in-frequency, after we change WN to
in Fig. 7.9 and multiply the output sequence by a factor of 1/N, we derive the inverse FFT block
diagram for the eight-point inverse FFT in Fig. 7.10.

66
Digital Signal Processing/ 4th Class/ 2020-2021 Dr. Abbas Hussien & Dr. Ammar Ghalib

Example (2):
Given a sequence x(n) for 0 ≤ n ≤ 3, where x(0) = 1, x(1) = 2, x(2) = 3, and x(3) = 4. Evaluate its
DFT X(k) using the decimation-in-time FFT method.

a. Evaluate its DFT X(k) using the decimation-in-frequency FFT method.

b. Determine the number of complex multiplications.

Solution:

H.W Find DFT of the following sequence [1 -1 -1 -1 1 1 1 -1], using:


a) Reduced DIT FFT
b) Reduced DIF FFT

67

You might also like