数字信号处理 - 原地计算

---

---

这种高效的内存使用对于设计快速计算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_{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点序列。