數字訊號處理 - 原地計算



這種高效的記憶體使用對於設計快速計算FFT的硬體至關重要。“原地計算”這一術語用來描述這種記憶體使用方式。

按時間抽取序列

在這種結構中,我們將所有點表示為二進位制格式,即0和1。然後,我們反轉這些結構。之後得到的序列稱為位反轉序列。這也被稱為按時間抽取序列。八點DFT的原地計算如表所示:

點數 二進位制格式 反轉 等效點數
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
Decimation in Time Sequence

按頻率抽取序列

除了時間序列,N點序列也可以在頻率域表示。讓我們以一個四點序列為例來更好地理解它。

令序列為$x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7]$。我們首先將兩個點分成一組。數學上,這個序列可以寫成:

$$x[k] = \sum_{n = 0}^{N-1}x[n]W_N^{nk}$$

現在讓我們將序列號0到3分成一組,將序列4到7分成另一組。數學上,這可以表示為:

$$\displaystyle\sum\limits_{n = 0}^{\frac{N}{2}-1}x[n]W_N^{nk}+\displaystyle\sum\limits_{n = N/2}^{N-1}x[n]W_N^{nk}$$

令r=n,其中r = 0, 1, 2….(N/2-1)。數學上,

$$\displaystyle\sum\limits_{r = 0}^{\frac{N}{2}-1}x[r]W_{N/2}^{rk}$$

我們首先取前四個點 (x[0], x[1], x[2], x[3]),並嘗試用以下方式在數學上表示它們:

$\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^{4k}\rbrace \times W_8^{nk}$

現在 $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$

我們可以進一步將其分解成兩部分,這意味著我們可以將其分解成2點序列,而不是4點序列。

廣告