Adam Panagos / Engineer / Lecturer

###### Fourier Analysis of Discrete-Time Signals: The Fast Fourier Transform (FFT)

###### This set of videos continues with a variety of DFT examples. The DFT introduction, derivation, and first several examples can be found in the previous members-only playlist.

We then introduce the Fast Fourier Transform, derive the FFT equation, and show how to use the FFT to efficiently perform linear convolution in Matlab.

#### The DFT of a Finite-Length Discrete-Time Signal

1/13/2019

Running Time: 10:24

The DFT equation is evaluated to compute samples of the Discrete-Time Fourier Transform of a discrete-time signal x[k]. The discrete-time signal examined here is rather simple as it only has 3 non-zero values. We also analytically compute the Discrete-Time Fourier Transform and amplitude spectrum of the signal to compare with the DFT computation. The last part of the video performs the DFT computation in Matlab and shows that the DFT coefficients do indeed properly sample the DTFT as desired. A more complicated discrete-time signal that has infinite time-duration and its DFT are examined in the next video.

#### The DFT an Infinite-Length Discrete-Time Signal

1/13/2019

Running Time: 9:41

This video also evaluates the DFT of a discrete-time signal x[k] to get samples of the signal’s Discrete-Time Fourier Transform. However, this signal is more complicated than our previous example since this signal has infinite duration in time. To compare the results of the DFT computation we also analytically compute the Discrete-Time Fourier Transform and amplitude spectrum of the signal. The last part of the video performs the DFT computation in Matlab and shows that the DFT coefficients do indeed properly sample the DTFT as desired.

#### Resolution and Zero-Padding of the Discrete Fourier Transform (DFT)

1/13/2019

Running Time: 11:27

For the final DFT example in this series, we examine a discrete-time signal that contains the sum of two sinusoids that are closely spaced in frequency. Using a simple Matlab script we examine a variety of cases where different numbers of samples are taken, as well as different amounts of zero padding. In cases where the number of samples taken is small, the DFT resolution is not sufficient to resolve both sinusoid signals. As the number of samples is increased, we observe how the DFT resolution improves and the signals are resolved. Zero padding is also used to provide more samples in the frequency domain.

#### Discrete Fourier Transform (DFT) Properties and Summary

1/13/2019

Running Time: 7:12

We conclude this series of videos on the Discrete Fourier Transform (DFT) by discussing a variety of its properties. Since the DFT provides samples of the FT or DTFT, it shouldn’t be too surprising that the DFT has very similar properties to these other transforms. For example, the DFT is a linear transform; shifting in time results in a complex phase in frequency; convolution in time is equivalent to circular convolution, etc.

In the next set of videos we introduce the Fast Fourier Transform (FFT). The FFT is a specific algorithm for efficiently computing the DFT. Once this algorithm has been introduced will discuss circular convolution further and provides an example of how linear convolution can be performed with the FFT/DFT by zero padding properly.

#### The Fast Fourier Transform (FFT) - 01 - Introduction

6/30/2014

Running Time: 5:19

The Fast Fourier Transform (FFT) is an efficient way of computing the Discrete Fourier Transform (DFT). This video discusses the difference in the number of operations required for a brute-force implementation of the DFT (i.e. N^2) versus the number of operations required for the FFT (i.e. Nlog2(N)). The efficient FFT implementation is why this algorithmic approach is called the "Fast" Fourier Transform.

#### The Fast Fourier Transform (FFT) - 02 - Algorithm Details

6/30/2014

Running Time: 5:36

We begin our development of the FFT by examining the number of operations required to compute a Discrete Fourier Transform (DFT). We revisit the definition of the DFT and count the number of complex multiplications and complex additions required to perform an length N0 DFT.

#### The Fast Fourier Transform (FFT) - 03 - Derivation Part 1

6/30/2014

Running Time: 7:28

We begin deriving the FFT algorithm. We introduce the "W" notation frequently defined as W_N0 = exp(-j2pi/N0). The key step in this part of the derivation is being able to write a single DFT coefficient as a summation of two other DFT coefficients, i.e. Fr = Gr + W_{N0}^{r}Gr.

#### The Fast Fourier Transform (FFT) - 04 - Derivation Part 2

6/30/2014

Running Time: 11:10

We finish the derivation of the FFT algorithm. We see that the FFT algorithm achieves efficiency by systematically breaking a large signal into smaller pieces. The number of stages required to break the original even-length signal is log2(N0). Each state requires N0 operations, thus the FFT has computational complexity of N0log2(N0).

#### The Fast Fourier Transform (FFT) - 05 - Linear Convolution With FFTs

6/30/2014

Running Time: 4:53

This video discusses the steps required to perform linear convolution via FFTs and an IFFT. We know that convolution in the time domain is equivalent to multiplication in the frequency domain. Since use of an FFT assumes a periodic signal, time-domain signals must be zero-padded properly before being transformed into the time domain to obtain linear convolution (else we would get circular convolution). A simple example is examined.

#### The Fast Fourier Transform (FFT) - 06 - Linear Convolution With FFTs in Matlab

6/30/2014

Running Time: 4:13

This video investigates the same linear convolution problem as presented in the previous video. However, this video walks through the Matlab code used to perform linear convolution via FFTs and multiplication in the frequency domain.

#### Fourier Analysis Summary

1/30/2014

Running Time: 5:11

This video summarizes the material covered in this part of the course regarding frequency domain analysis of discrete-time signals. We summarize the Discrete-Time Fourier Series (DTFS), Discrete-Time Fourier Transform (DTFT), Discrete Fourier Transform (DFT), and Fast Fourier Transform (FFT).