Schnelle Fourier-Transformation - Digitale Signalverarbeitung mit MATLAB - page 47

Zunächst wird festgelegt, im Programm die
Eingangsfolge x(I) für I von 0 bis N 1 abzu-

arbeiten und entsprechend Tabelle 4-1 sequen-
ziell die Plätze zu tauschen. Es resultiert die
Struktur einer Laufanweisung, einer for -
Schleife, mit der temporären Hilfsvariablen T
in Bild 4-6.
Anmerkungen: (i) Beachten Sie, dass die Feldindi-
zierung in MATLAB stets mit 1 beginnt. Um das
Programm etwas zu beschleunigen, d. h. die Addi-
tion der Indizes mit 1 zu vermeiden, können Sie
später auch die Schleifenanweisung anpassen. (ii)
Durch das Tauschen der Plätze braucht kein neues
Datenarray angelegt zu werden. Bei Eingangsfolgen
der Länge 1024 und darüber ist die Speicherplatz-
ersparnis in der Praxis oft ein wichtiger Vorteil.
Im Programmausschnitt fehlt die Zuordnung
der jeweils richtigen Indizes I und J . Hier hilft
ein Blick in Tabelle 4-1 einen inkrementellen
Algorithmus zu entwickeln, der die Änderung
des Index J widerspiegelt.
Zunächst beginnt auch J mit dem Startwert 0.
Es ist zu beobachten, dass bei den Übergängen
von geraden Werten des Index I auf die nach-
folgenden ungeraden, z. B. I = 0 auf 1, von 2
auf 3, von 4 auf 5 usw., der Index J stets einen
Zuwachs von N / 2 erhält. Also im Beispiel
von J = 0 auf 8, von 4 auf 12, von 2 auf 10
usw.
Dieser Zuwachs spiegelt sich in der Bit-
reversal-Adressierung wider. Beim Übergang
von einem geraden Index I auf den folgenden
ungeraden wird I um eins erhöht. Also das Bit
mit der niedrigsten Wertigkeit, das Least-
Significant-Bit (LSB) b 0 = 1, gesetzt. Durch
die Bit-reversal-Adressierung wird daraus das
Most-Significant-Bit (MSB) mit der Wertigkeit
N / 2. Da die anderen Bits bei geradem I durch das Inkrementieren nicht betroffen sind, er-
wächst daraus genau ein Zuwachs um N / 2 für den neuen Wert J .
Den neuen Wert für J beim Übergang von ungeraden auf gerade Werte des Index I zu finden,
gestaltet sich aufwendiger, weil die Addition des LSB zu unterschiedlichen Bitüberträgen
führen kann. Die Beispiele in Bild 4-7, die Übergänge des Index I von 1 auf 2 und von 3 auf 4,
veranschaulichen dies. Im ersten Fall gibt es einmal einen Übertrag im zweiten Fall zweimal.
Die erforderliche Fallunterscheidung beim Inkrementieren eines ungeraden Indizes I wird im
Programmausschnitt in Bild 4-8 vorgenommen.
Zunächst wird das Inkrement K für den Index J auf N / 2 eingestellt. Dann wird in der Beding-
ung der while -Schleife geprüft, ob der Wert des Index J größer als N / 2 ist. Ist das der Fall,

0
8
4
12
2
10
6
14
1
9
5
13
3
11
7
15

0
4
8
12

0
2
4
6
8
10
12
14

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2
6
10
14

1
3
5
7
9
11
13
15

1
5
9
13
3
7
11
15

Bild 4-5

Ordnen der Eingangsfolge (Indi-
zes) für die DIT-Radix-2-FFT der
Länge N = 16 in drei Zwischen-
schritten von links nach rechts

J = 0;
for I=0:N-1 % exchange values
T = x(1+J);
x(1+J) = x(1+I);
x(1+I) = T;
end

Bild 4-6 Programmfragment für die Bit-
reversal-Adressierung