Sei eine ganze Zahl
gegeben. Sei
. Insbesondere ist
.
Unter der diskreten Fouriertransformation versteht man die
-lineare Abbildung
Bei Bedarf sei
und
für
, i.e. die Vektorindizierung werde
-periodisch fortgesetzt.
Die Darstellungsmatrix von
bezüglich Standardbasen ist gegeben durch
Regeln. Seien
, und schreibe
und
. Seien
.
Mit der sog. Schnellen Fouriertransformation kann man die Rechengeschwindigkeit für den Fall, daß
eine Potenz von
ist (oder jedenfalls durch eine große
-Potenz teilbar ist), noch
verbessern. Die resultierende Abbildung ist dieselbe wie bei der gewöhnlich durchgeführten Fouriertransformation.