English
Menu

What is Fast Fourier transform (FFT)?

A family of algorithms that compute the discrete Fourier transform (DFT) exactly with few operations. The best-known approach (the Cooley-Tukey algorithm) repeatedly splits an N-point DFT into DFTs of half the size and shares the common calculations, cutting the number of operations from about N² for the definition to about N log₂N. For N = 1024 that is about 1/100. The algorithm is simplest when the number of points is a power of two, but methods exist for other sizes. Besides spectrum analysis, it is used for OFDM modulation and demodulation and for fast computation of long convolutions.

Japanese name: 高速フーリエ変換(FFT)

Fast Fourier transform (FFT) appears in 4 practice questions across 2 topics, including Digital Signal Processing Basics, Wireless Communication Basics.

Field: Digital Signal Processing Basics

Why it is fast

Splitting an N-point DFT into two N/2-point DFTs of the even-numbered and odd-numbered samples lets the original result be assembled just by multiplying by twiddle factors e^(−j2πk/N) and adding and subtracting. Repeating this gives log₂N stages of about N operations each, so the total is on the order of N log₂N. Because of its shape, this add-and-subtract pair is called a butterfly.

How much faster

The ratio is N/log₂N: 1024 ÷ 10 = 102.4 for N = 1024 and 65,536 ÷ 16 = 4096 for N = 65,536. The larger the number of points, the bigger the gain, which makes the FFT indispensable for real-time spectrum displays and for uses such as communication receivers that compute many DFTs in a row.

Convolution with the FFT

The convolution of two sequences becomes a multiplication on the frequency side. Transforming both with the FFT, multiplying them and transforming back with the inverse FFT therefore computes the convolution of a long FIR filter with fewer operations than direct computation. Multiplying DFTs, however, corresponds to circular convolution, so the lengths must be matched by zero padding to prevent wrap-around at the ends.

Try it: questions about Fast Fourier transform (FFT)

Suppose an N-point DFT takes about N² operations when computed from its definition and about N log₂N operations with the FFT (fast Fourier transform). For N = 1024, which of the following is closest to the reduction in the number of operations achieved by the FFT?

  1. AAbout 1/10
  2. BAbout 1/100
  3. CAbout 1/1000
Show answer and explanation

Answer: B. About 1/100

N² = 1024² ≈ 1.05 million and N log₂N = 1024 × 10 = 10,240, so the ratio is N/log₂N = 1024 ÷ 10 = 102.4, about 1/100. The gap widens as N grows; for N = 65,536 the reduction is about 1/4096. The FFT reduces the work by repeatedly splitting a DFT into DFTs of half the size and sharing the common calculations.

FAQ

Must the number of FFT points be a power of two?

No. A power of two is often the simplest and fastest case, but mixed-radix FFTs that factor the size into 3, 5 and so on, and methods for prime sizes also exist, and common libraries compute any size. When a power of two is preferred, the number of points may be increased by zero padding.

Are FFT results the same as the DFT?

They compute the same values, so they agree apart from rounding errors. The FFT is not an approximation but an algorithm that reorganizes the calculation to obtain the same result faster.

Fast Fourier transform (FFT) in the explanations

Questions that mention Fast Fourier transform (FFT) (4)

  1. Suppose an N-point DFT takes about N² operations when computed from its definition and about N log₂N operations with the FFT (fast Fourier transform). For N = 1024, which of the following is closest to the reduction in the number of operations achieved by the FFT?
  2. A 256-point signal is followed by 768 zeros (zero padding) and a 1024-point DFT is computed. Compared with computing the DFT of the 256 points as they are, which of the following is correct?
  3. Which describes OFDM (orthogonal frequency-division multiplexing)?
  4. In OFDM, which is the main purpose of the cyclic prefix (CP), formed by copying part of the end of each symbol to its beginning?

Books on Digital Signal Processing Basics Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

OFDM (orthogonal frequency-division multiplexing) Frequency resolution Convolution Decimation Difference equation Discrete Fourier transform FIR filter Group delay IIR filter Impulse response

Back to the glossary