DSP - In-Place-Berechnung
Diese effiziente Speichernutzung ist wichtig für den Entwurf schneller Hardware zur Berechnung der FFT. Der Begriff In-Place-Berechnung wird verwendet, um diese Speichernutzung zu beschreiben.
Dezimierung in zeitlicher Abfolge
In dieser Struktur stellen wir alle Punkte im Binärformat dar, dh in 0 und 1. Dann kehren wir diese Strukturen um. Die Sequenz, die wir danach erhalten, wird als Bitumkehrsequenz bezeichnet. Dies wird auch als Dezimierung in der Zeitfolge bezeichnet. Die In-Place-Berechnung einer Achtpunkt-DFT wird in einem tabellarischen Format angezeigt, wie unten gezeigt -
PUNKTE | BINÄRFORMAT | UMKEHRUNG | Äquivalente Punkte |
---|---|---|---|
0 | 000 | 000 | 0 |
1 | 001 | 100 | 4 |
2 | 010 | 010 | 2 |
3 | 011 | 110 | 6 |
4 | 100 | 001 | 1 |
5 | 101 | 101 | 5 |
6 | 110 | 011 | 3 |
7 | 111 | 111 | 7 |
Dezimierung in Frequenzfolge
Neben der Zeitfolge kann auch eine N-Punkt-Folge in der Frequenz dargestellt werden. Nehmen wir eine Vier-Punkte-Sequenz, um sie besser zu verstehen.
Die Folge sei $ x [0], x [1], x [2], x [3], x [4], x [5], x [6], x [7] $. Wir werden zunächst zwei Punkte zu einer Gruppe zusammenfassen. Mathematisch kann diese Sequenz geschrieben werden als;
$$ x [k] = \ sum_ {n = 0} ^ {N-1} x [n] W_N ^ {nk} $$Lassen Sie uns nun eine Gruppe der Folgenummern 0 bis 3 und eine andere Gruppe der Folgenummern 4 bis 7 bilden. Nun kann dies mathematisch wie folgt dargestellt werden:
$$ \ Anzeigestil \ Summe \ Grenzen_ {n = 0} ^ {\ frac {N} {2} -1} x [n] W_N ^ {nk} + \ Anzeigestil \ Summe \ Grenzen_ {n = N / 2} ^ {N-1} x [n] W_N ^ {nk} $$Ersetzen wir n durch r, wobei r = 0, 1, 2… (N / 2-1). Mathematisch,
$$ \ displaystyle \ sum \ limit_ {n = 0} ^ {\ frac {N} {2} -1} x [r] W_ {N / 2} ^ {nr} $$Wir nehmen zunächst die ersten vier Punkte (x [0], x [1], x [2], x [3]) und versuchen, sie wie folgt mathematisch darzustellen:
$ \ sum_ {n = 0} ^ 3x [n] W_8 ^ {nk} + \ sum_ {n = 0} ^ 3x [n + 4] W_8 ^ {(n + 4) k} $
$ = \ lbrace \ sum_ {n = 0} ^ 3x [n] + \ sum_ {n = 0} ^ 3x [n + 4] W_8 ^ {(4) k} \ rbrace \ times W_8 ^ {nk} $
jetzt $ X [0] = \ sum_ {n = 0} ^ 3 (X [n] + X [n + 4]) $
$ X [1] = \ sum_ {n = 0} ^ 3 (X [n] + X [n + 4]) W_8 ^ {nk} $
$ = [X [0] -X [4] + (X [1] -X [5]) W_8 ^ 1 + (X [2] -X [6]) W_8 ^ 2 + (X [3] -X [7]) W_8 ^ 3 $
Wir können es weiter in zwei weitere Teile aufteilen, was bedeutet, dass wir sie nicht als 4-Punkt-Sequenz, sondern in 2-Punkt-Sequenz aufteilen können.