Digital Signal Processing Reference
In-Depth Information
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, erwächst daraus ge-
nau ein Zuwachs um
N
/ 2 für den neuen Wert
J
.
Den neuen Wert für
J
beim Übergang von un-
geraden auf gerade Werte des Index
I
zu finden,
gestaltet sich aufwändiger, 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 zwei-
mal.
Die erforderliche Fallunterscheidung beim In-
krementieren 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
Bedingung der
while
-Schleife geprüft, ob der Wert des Index
J
größer als
N
/2 ist. Ist das der
Fall, so war der letzte Wert des Index
I
ungerade, siehe Tabelle 4-1. Ist das nicht der Fall, ist
der aktuelle Wert des Index
I
ungerade und der neue Wert des Index
J
ergibt sich durch inkre-
mentieren mit
K
=
N
/ 2. Die
while
-Schleife wird abgewiesen.
Im anderen Fall liegt ein Übergang von einem
ungeraden Wert des Index
I
auf einen geraden
vor. Damit sind Bitüberträge wie in Bild 4-7
möglich. Sie werden in der
while
-Schleife be-
rücksichtigt.
Ist
J
t
N
/ 2 tritt in der dualen Darstellung im
Übergang des alten Wertes von
I
auf den neuen
ein Bit-Übertrag auf, d. h. für das LSB gilt nun
b
0
= 0. Weil das LSB von
I
zum MSB des Index
J
wird, muss letzteres auch 0 sein. Das Null-
setzen des MSB geschieht im Index
J
durch
J = 0;
for I=0:N-1 %
exchange values
T = x(J+1);
x(J+1) = x(I+1);
x(I+1) = T;
end
Bild 4-6
Programmfragment A für die Bit-
reversal-Adressierung
b.-r.
1
0001
o
1000
8
10
2
2
10
b.-r.
2
0010
o
0100
4
10
2
2
10
b.-r.
3
0011
o
1100
12
10
2
2
10
b.-r.
4
0100
o
0010
2
10
2
2
10
Bild 4-7
Beispiele für die Bit-reversal-
Adressierung
%
update index J
K = N/2; %
default increment
while (K<=J)
J = J - K;
K = K/2;
end
J = J + K;
Bild 4-8
Programmfragment B für den Bit-
reversal-Adressierung
