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.

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.

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.

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) 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.

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.

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.

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).

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.

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.

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).