---

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^{n-k}$$

现在让我们将序列号 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} brace imes 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 点序列。

---