$$\require{cancel}$$

# 11: Discrete Fourier Transforms

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

The Discrete Fourier Transform (DFT) is a discretized version of the Fourier transform, which is widely used in numerical simulation and analysis. Given a set of $$N$$ numbers $$\{f_0, f_1, \dots, f_{N-1}\}$$, the DFT produces another set of $$N$$ numbers $$N$$ numbers $$\{F_0, F_1, \dots, F_{N-1}\}$$, defined as follows:

$\mathrm{DFT}\Big\{f_0, f_1, \dots, f_{N-1}\Big\} = \Big\{F_0, F_1, \dots, F_{N-1}\Big\} \qquad\mathrm{where}\quad F_n = \sum_{m=0}^{N-1} e^{-2\pi i \frac{mn}{N}}\, f_m.$

The inverse of this transformation is the Inverse Discrete Fourier Transform (IDFT):

$\mathrm{IDFT}\Big\{F_0, F_1, \dots, F_{N-1}\Big\} = \Big\{f_0, f_1, \dots, f_{N-1}\Big\} \qquad\mathrm{where}\quad f_m = \frac{1}{N} \sum_{n=0}^{N-1} e^{2\pi i \frac{mn}{N}}\, F_n.$

The inverse relationship between the DFT and the IDFT is straightforward to prove, by using the identity

$\sum_{m=0}^{N-1} e^{\pm 2\pi i \frac{m(n-n')}{N}} = N \delta_{nn'},$

where $$\delta_{nn'}$$ denotes the Kronecker delta. This identity is derived from the geometric series formula.

This page titled 11: Discrete Fourier Transforms is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Y. D. Chong via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.