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

Final Answers
© 2000-2021   Gérard P. Michon, Ph.D.

Discrete Fourier Transforms

 Joseph Fourier 
 1768-1830  Michon
 

Related articles on this site:

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

FFT,  divide & conquer  algorithm (1:20:51)  Erik Demaine  (MIT 6.046J, 2015).
FFT:  Most Ingenious Algorithm Ever? (28:22)  by  Reducible  (2020-11-14).

 
border
border

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 
vinculum
space
vinculum
Ö 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 
vinculum
space
vinculum
Ö 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.

JPEG compression  (7:17  15:11)  by  Mike Pound, image analyst  (Computerphile, 2015-04-21).

border
border
visits since January 10, 2009
 (c) Copyright 2000-2021, Gerard P. Michon, Ph.D.