DSP - 快速傅里叶变换

在早期的DFT方法中，我们发现计算部分太长。我们希望减少这种情况。这可以通过 FFT 或快速傅立叶变换来完成。因此，我们可以说FFT只不过是以算法形式进行离散傅里叶变换的计算，其中计算部分会减少。

FFT 的主要优点是通过它，我们可以设计 FIR 滤波器。从数学上来说，FFT 可以写成如下：

$$x[K] = \displaystyle\sum\limits_{n = 0}^{N-1}x[n]W_N^{nk}$$

让我们举个例子来更好地理解它。我们考虑了从 $x_0\quad 到 \quad x_7$ 命名的八个点。我们将在一组中选择偶数项，在另一组中选择奇数项。上述内容的示意图如下所示 -

这里，点x ₀、x ₂、x ₄和x ₆已被分组为一个类别，类似地，点x ₁、x ₃、x ₅和x ₇已被放入另一类别中。现在，我们可以进一步将它们分成两个一组并继续计算。现在，让我们看看这些分解为另外两个如何有助于计算。

$x[k] = \displaystyle\sum\limits_{r = 0}^{\frac{N}{2}-1}x[2r]W_N^{2rk}+\displaystyle\sum\limits_{r = 0 }^{\frac{N}{2}-1}x[2r+1]W_N^{(2r+1)k}$

$= \sum_{r = 0}^{\frac{N}{2}-1}x[2r]W_{N/2}^{rk}+\sum_{r = 0}^{\frac{N }{2}-1}x[2r+1]W_{N/2}^{rk}\times W_N^k$

$= G[k]+H[k]\times W_N^k$

最初，我们采用了一个八点序列，但后来我们将其分成两部分 G[k] 和 H[k]。G[k]代表偶数部分，而H[k]代表奇数部分。如果我们想通过图来实现的话，可以如下图所示：

从上图我们可以看出

$W_8^4 = -1$

$W_8^5 = -W_8^1$

$W_8^6 = -W_8^2$

$W_8^7 = -W_8^3$

同样，最终值可以写成如下 -

$G[0]-H[0] = x[4]$

$G[1]-W_8^1H[1] = x[5]$

$G[2]-W_8^2H[2] = x[6]$

$G[1]-W_8^3H[3] = x[7]$

以上是一个周期系列。该系统的缺点是K不能突破4点以上。现在让我们把上面的内容进一步分解。我们会得到这样的结构

考虑序列 x[n]={ 2,1,-1,-3,0,1,2,1}。计算 FFT。

解决方案- 给定序列为 x[n]={ 2,1,-1,-3,0,1,2,1}

按如下所示排列条款；