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

Related Links (Outside this Site)

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

---

(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 ( - 2pi / N ). We have:

w^N = 1 ( and w^k = 1 <=> N | k ) 0 = N-1 w ^k

å

k = 0

Two sequences of N complex numbers (X₀ ... X_N-1 ) and (Y₀ ... Y_N-1 ) are Fourier transforms of each other when the following relation holds:

Discrete Fourier Transform (as a unitary involution)

Y_m =

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):

X_m =

1

vinculum

space

vinculum

Ö N

[ N-1 w ^km Y_k ]^*

å

k = 0

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

å | Y_k |² = å | X _k |²

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日).