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.