Digital Signal Processing Reference
In-Depth Information
Den Anfang macht die Abschätzung des Rechenaufwandes der DFT als einfaches Maß für die
Komplexität
des Algorithmus. Der Definitionsgleichung der DFT
N
1
¦
n
N
X k
[]
x n
[]
w
für
k
= 0:
N
1
(4.1)
n
0
mit den komplexen Faktoren
2
S
j
k
(4.2)
nk
N
N
we
ist zu entnehmen, dass zur Berechnung der
N
DFT-Koeffizienten jeweils
N
Multiplikationen
der komplexen Folgenelemente mit den komplexen Faktoren und
N
1 Additionen der Multipli-
kationsprodukte auszuführen sind.
Mit 4 + 2
Gleitkomma-Operationen
(FLOPs, Floating Point Operations) für jede komplexe
Multiplikation und 2 FLOPs für jede komplexe Addition, erhält man die Abschätzung des
Rechenaufwands der direkten Form der DFT.
2
R
| FLOPs
8
N
(4.3)
DFT direkt
,
Die komplexen Faktoren werden dabei als gespeicherte Konstanten angesehen. Bei großen
Transformationslängen ist ein dementsprechend großer Speicher vorzusehen. Handelt es sich
um externen Speicher, so kann die Speicherzugriffszeit zu einer kritischen Größe werden. Ver-
zichtet man auf die Speicherung und berechnet die komplexen Faktoren, entsteht ein zusätzli-
cher Rechenaufwand. Darüber hinaus kann die fortlaufende Berechnung wegen der Fehlerfort-
pflanzung zu nicht tolerierbaren numerischen Ungenauigkeiten führen.
4.3
Radix-2-FFT-Algorithmus
Der Rechenaufwand der direkten Form der DFT (4.3) steigt quadratisch mit der Transforma-
tionslänge. Die Radix-2-FFT setzt genau an dieser Stelle an, indem Sie die DFT sukzessive in
je zwei DFT der halben Länge zerlegt, bis schließlich die Transformationslänge 2 erreicht ist.
Dazu muss die DFT-Länge
N
eine Zweierpotenz sein, also
N
= 2
P
mit der natürlichen Zahl
p
.
Zunächst kann die DFT (4.1) in zwei Teilsummen zerlegt werden für gerade und ungerade
Indizes.
N
1
N
2
N
1
¦
nk
¦
nk
¦
nk
Xk
[]
xn w
[]
xn w
[]
xn w
[]
(4.4)
N
N
N
n
0
n
0,2,
!
n
1,3,
!
Die Substitutionen
nm
2
für
n
gerade
nm
2
1
für
n
ungerade
(4.5)
und
M
N
2
liefern dann
