home | index | units | counting | geometry | algebra | trigonometry & functions | calculus analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

## Discrete Fourier Transforms

### Related Links (Outside this Site)

Fast Fourier Transform  by  Eric Weisstein.
Fast Fourier Analysis on Groups  by  Dan Rockmore  and  Peter Kostelec.

Wikipedia :   Discrete Fourier Transform   |   Fourier Transform on Finite Groups   |   Fast Fourier Transform   |   Cooley Tukey FFT algorithm

Mathematics for the Physical Sciences (1966)  by  Laurent Schwartz  (Dover, 2008)

VideoThe Fourier Transform and its Applications   by  Brad Osgood
(Stanford University, EE261)     ...    |  20  |  21  |  22  |  ...   [ Playlist ]

## Discrete Fourier Transforms

(2008-11-03)   Discrete Fourier Transform  (DFT)
The Discrete Fourier Transform can be defined as a  unitary involution.

Let  N  be a positive integer  (for convenience,  N  is often a power of 2).  Let  w  be a  primitive  N-th root of unity,  like   w = exp ( - 2p/ N ).  We have:

 wN = 1       ( and   wk = 1    <=>    N | k )       0   = N-1 w k å k = 0

Two sequences of  N  complex numbers  (X0 ... XN-1 )  and  (Y0 ... YN-1 )  are  Fourier transforms of each other  when the following relation holds:

Discrete Fourier Transform  (as a unitary involution)
Ym   =
1
 Ö N
[   N-1   w km  X k  ]*
å
k = 0

This definition may not be the simplest one (see below) but it's arguably the best theoretical one... The DFT so defined is an  involution  (i.e., it's its own inverse):

Xm   =
1
 Ö N
[   N-1   w km  Yk  ]*
å
k = 0

It is also  unitary.  The counterpart of  Parseval's Theorem  is coefficient-free:

å | Yk |2   =   å | X k |2

One popular competing way to define the DFT retains only the square bracket and forgoes the overall coefficient and the complex conjugation.  This yields a  bare  finite Fourier transform  (BFFT or  barefoot )  which is neither unitary nor involutive but can be  simpler to compute  (especially in a recursive context):

 Z m   = N-1 w km  X k å k = 0

(2015-05-27)   Discrete Cosine Transform  (DCT)
At the heart of the JPEG lossy compression algorithm.

by  Mike Pond, image analyst.