DSP - 就地计算

---

内存的有效利用对于设计快速硬件来计算 FFT 非常重要。术语“就地计算”用于描述这种内存使用情况。

时间序列抽取

在这个结构中，我们以二进制格式表示所有点，即用 0 和 1 表示。然后，我们反转这些结构。之后我们得到的序列称为位反转序列。这也称为时间序列抽取。八点 DFT 的就地计算以表格格式显示，如下所示 -

频率序列抽取

除了时间序列之外，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_{n = 0}^{\frac{N}{2}-1}x[r]W_{N/2}^{nr}$$

我们首先取前四个点 (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^{(4)k}\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 点序列。