The discrete Fourier transform is one of the most important computational tools in signal processing. This lesson briefly introduces you to some of the applications for the discrete Fourier transform, its definition, and develops the relationship between the discrete Fourier transform and the discrete-time Fourier transform. An understanding of this relationship is essential to proper use Read More

## Important Discrete Fourier Transform Properties

In this lesson you will learn several of the most important properties of the discrete Fourier transform (DFT) for signal processing applications. Not surprisingly, these properties are similar to those of the Fourier transform and the discrete-time Fourier transform. The convolution-multiplication property is deferred to a separate lesson due to its importance in using the Read More

## Fast Fourier Transform (FFT) Algorithm

In this lesson you will learn the principles at the core of the decimation-in-time fast Fourier transform algorithm. The (re)discovery of the fast Fourier transform algorithm by Cooley and Tukey in 1965 was perhaps the most significant event in the history of signal processing. There is evidence that Gauss first developed a fast Fourier transform-type Read More

## Introduction to Circular Convolution and Filtering with the Discrete Fourier Transform

The convolution-multiplication property is one of the most insightful and useful properties of the Fourier transform and discrete-time Fourier transform. This lesson introduces the convolution-multiplication property for the DFT. Multiplication of DFT coefficients corresponds to circular convolution of time signals. You will gain an understanding of the difference between linear and circular convolution that is Read More

## Circular Convolution Property of the Discrete Fourier Transform

The Circular Convolution Property of the Discrete Fourier Transform lesson takes a detailed look at the convolution-multiplication property for the DFT. You will learn how to derive this important property, how to evaluate circular convolution, and the relationship between linear or ordinary and circular convolution. Understanding these concepts is key for properly using the DFT Read More

## Filtering with the Discrete Fourier Transform

The discrete Fourier transform is often used to implement linear time-invariant filters in a computationally efficient manner. This is due to the availability of computationally efficient or fast algorithms for computing the discrete Fourier transform. You will learn about the overlap and add method for computing convolution in this lesson. Overlap and add exploits the efficient computation Read More

## The Discrete Fourier Transform Approximation to the Fourier Transform

The dominant application of the discrete Fourier transform is for performing spectral analysis – analyzing the frequency content of signals. The discrete Fourier transform is often used to approximate the Fourier transform of a signal. In this lesson you will learn the three types of approximations involved in using the discrete Fourier transform to represent the Fourier transform. You will also learn Read More

## The Effect of Windowing on the Discrete Fourier Transform Approximation to the Fourier Transform

The most significant effect on the fidelity of the discrete Fourier transform approximation to the Fourier transform is due to truncating or "windowing" the duration of the signal. In this lesson you will gain key insight into the loss of resolution or detail and the loss of dynamic range that is introduced by truncation. A thorough understanding Read More

## Windows and the Discrete-Time Fourier Transform: Trading Resolution for Dynamic Range

In this lesson you will learn how to use different windows to manage the loss of resolution and limited dynamic range resulting from truncation. The rectangular window leads to relatively good resolution but very poor dynamic range. Windows with less abrupt transitions provide much better dynamic range at the expense of some loss of resolution. Read More

## An Example of Approximating the Fourier Transform with the Discrete Fourier Transform

This lesson illustrates the use of the discrete Fourier transform for approximating the Fourier transform by using a signal with a known Fourier transform. You will see how the choices of window length and discrete Fourier transform length affect the quality of the approximation. This example is the culmination of the concepts discussed in the three preceding lessons and Read More

## The Short-Time Fourier Transform and the Spectrogram

The DFT is an extremely powerful tool for assessing the spectral characteristics of signals. In this lesson you will learn about a variation of the DFT called the short-time Fourier transform (STFT). The STFT is used for spectral analysis of signals whose frequency characteristics are changing over time. There are many types of signals with Read More

## A Matrix Interpretation of the Discrete Fourier Transform

This lesson teaches you how to interpret the discrete Fourier transform as the inner product between a matrix and a vector and introduces a linear algebraic viewpoint. Linear algebra is an extremely powerful and widely used tool in signal processing. You will be introduced to these ideas in this lesson and build on them in future studies. Read More

## A Matrix Interpretation of the Fast Fourier Transform Algorithm

This lesson shows you how to view the fast Fourier transform algorithm as a factorization of the discrete Fourier transform matrix into a product of matrices. The matrices in the product representation are very sparse which is why the fast Fourier transform algorithm is computationally efficient. As you see here, matrix factorization is a very useful and insightful tool in signal processing. Prerequisites Read More