数字信号处理/离散傅立叶变换

数字信号处理

顾名思义，离散傅立叶变换 (DFT) 纯粹是离散的：离散时间数据集被转换为离散频率表示。这与使用离散时间的DTFT形成对比，但转换为连续频率。由于得到的频率信息本质上是离散的，所以计算机在需要频率信息时经常使用DFT（离散傅立叶变换）计算。

使用一系列数学技巧和推广，存在一种在现代计算机上速度非常快的DFT计算算法。该算法被称为快速傅立叶变换 (FFT)，它产生与普通DFT相同的结果，但计算时间只是普通DFT计算的一小部分。FFT将在后面的章节中详细讨论。

DFT

离散傅立叶变换是傅立叶变换的一种数值变体。具体来说，给定一个包含n个输入幅度的向量，例如 {f₀, f₁, f₂, ... , f_n-2, f_n-1}，离散傅立叶变换会产生一组n个频率幅度。

DFT 的定义如下

$X[k]=\sum _{n=0}^{N-1}x[n]e^{\frac {-j2\pi kn}{N}}$

这里，k 用于表示频域序数，n 用于表示时域序数。大“N”是待变换序列的长度。

逆DFT (IDFT) 由以下公式给出

$x[n]={\frac {1}{N}}\sum _{k=0}^{N-1}X[k]W_{N}^{-kn}$

其中 $W_{N}$ 定义为

$W_{N}=e^{-j2\pi /N}$

同样，“N”是待变换序列的长度。

矩阵计算

使用矩阵方程可以更容易地计算DFT

\mathbf {X} =\mathbf {D} _{N}\mathbf {x}

小“x”是时域序列，排列为Nx1的垂直向量。大“X”是得到的频率信息，它将排列为垂直向量（根据矩阵乘法的规则）。“D_N”项是定义为这样的矩阵

\mathbf {D} _{N}={\begin{bmatrix}1&1&1&\cdots &1\\1&W_{N}&W_{N}^{2}&\cdots &W_{N}^{(N-1)}\\1&W_{N}^{2}&W_{N}^{4}&\cdots &W_{N}^{2(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&W_{N}^{N-1}&W_{N}^{2(N-1)}&\cdots &W_{N}^{(N-1)(N-1)}\end{bmatrix}}

以类似的方式，可以使用矩阵计算 IDFT，如下所示

\mathbf {x} =\mathbf {D} _{N}^{-1}\mathbf {X}

我们将定义 $\mathbf {D} _{N}^{-1}$ 如下

\mathbf {D} _{N}^{-1}={\begin{bmatrix}1&1&1&\cdots &1\\1&W_{N}^{-1}&W_{N}^{-2}&\cdots &W_{N}^{-(N-1)}\\1&W_{N}^{-2}&W_{N}^{-4}&\cdots &W_{N}^{-2(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&W_{N}^{-(N-1)}&W_{N}^{-2(N-1)}&\cdots &W_{N}^{-(N-1)(N-1)}\end{bmatrix}}

离散傅里叶变换的可视化

可以很容易地看到，该项

e^{-\pi t}

表示复平面上的一个单位向量，对于任何 j 和 k 的值。对于 $j=0$ 或 $k=0$ ，该向量的角度最初为 0 弧度（沿实轴）。随着 j 和 k 的增加，该角度以圆周的 1/n 为单位递增。因此，总角度变为 $2\pi *jk/n$ 弧度。

为了理解离散傅里叶变换的意义，将该变换写成矩阵形式，以图形方式描述复数项会很有效。

例如，当 $n=8$ 时，可以将傅里叶变换写成

最上面一行（或最左边一列）没有变化；因此，F0 是当振幅互相增强时的结果。第二行变化了圆周的 1/n，从左到右。第三行变化了圆周的 2/n；第四行变化了圆周的 3/n；第五行，这里，变化了 4/n = 4/8 = 圆周的 1/2。因此，F4 是当偶数项与奇数项相矛盾时的结果。

因此，我们从方阵中看到，DFT 是输入振幅所有二维向量组合的结果。

与 DTFT 的关系

DFT 和 DTFT 之间的关系非常简单。如果我们对给定的时间序列 x[n] 进行 DTFT，我们将得到一个连续频率函数，称为 $X(e^{j\omega })$ 。如果我们在 N 个等间隔的位置对 $X(e^{j\omega })$ 进行采样，结果将是 DFT，X[k]。

循环时间移位

循环时间移位与常规的线性时间移位非常相似，只是当项目移过某个点时，它们会循环到序列的另一端。这个主题可能看起来有点离题，但当我们在下一章讨论循环卷积操作时，这个主题的重要性将变得显而易见。

假设我们有一个给定的序列 x[n]，如下所示

x[n] = [1& 2 3 4]

众所周知，我们可以通过从自变量中减去或加上数字来将该序列向左或向右进行时间移位

x[n+1] = [1 2& 3 4 0]

x[n-1] = [0& 1 2 3 4]

在这里，我们已经用零填充了两个序列，以使下一个项目的来源变得显而易见。现在，假设当我们移位一组时，不是用零填充，而是将第一个数字循环到周围以填补空白。我们将使用符号 x[<n+A>] 来表示 A 点循环移位

x[<n+1>] = [2& 3 4 1]

请注意序列的长度最初是 4，最后是 4，我们不需要用零填充。还要注意，1“掉落”了组的左侧，并“重新出现在”右侧。就好像该组是一个圆圈，从一个方向旋转出去的对象会从另一个方向回来。同样，让我们向另一个方向旋转

x[<n-1>] = [4& 1 2 3]

如果我们旋转 N 点，其中 N 是组的长度，我们将得到一个重要的恒等式

x[<n+N>] = x[<n-N>] = x[n]

时间反转

现在，让我们来看看一个更复杂的情况：将循环移位与时间反转混合。让我们定义示例集 x[n]

x[n] = [1& 2 3 4]

我们可以将时间反转集定义如下

x[n] = [4 3 2 1&]

请注意，“4”从 n=3 变成了 n=-3，但“1”仍然位于零点。现在，让我们尝试将此与循环移位操作结合起来，以产生结果 x[<-n>]。我们知道“1”（位于零位置）没有向任何方向移动，我们也没有向左或向右移动，因为我们没有向自变量（n）添加或减去任何东西。因此，我们可以将 1 放回与之前相同的位置。所有其他数字（2 3 和 4）都移到了序列的右侧，因此我们将它们循环到另一侧

x[<-n>] = [1& 4 3 2]

这是一个通用的循环时间反转规则

x[<-n>]=\left\{{\begin{matrix}x[0],&{\mbox{if }}n=0\\x[<N-n>],&{\mbox{if }}n\neq 0\end{matrix}}\right.

循环卷积

循环卷积是一个重要的操作，因为在使用 DFT 时它起着重要的作用。

假设我们有两个长度都为 N 的离散序列 x[n] 和 h[n]。我们可以将循环卷积操作定义如下

y[n]=\sum _{m=0}^{N-1}x[m]h[<n-m>_{N}]

请注意，我们使用的是循环时间移位操作，而不是常规线性卷积中使用的线性时间移位。

循环卷积定理

DFT 具有一定的属性，使其与常规卷积定理不兼容。但是，DFT 确实与循环卷积操作有着类似的关系，非常有用。我们将这种关系称为循环卷积定理，并将其陈述如下

循环卷积定理: 离散时间域中的乘法在离散频率域中变为循环卷积。离散时间域中的循环卷积在离散频率域中变为乘法。

与线性卷积的关系

循环卷积与线性卷积有关，我们可以使用循环卷积操作来计算线性卷积结果。假设我们有两个长度为 N 的集合 x[n] 和 h[n]

在右侧用 N-1 个零填充这两个集合。
对长度为 N+(N-1) 的新集合执行循环卷积
结果是原始两个集合的线性卷积结果。

快速傅里叶变换 (FFT)

快速傅里叶变换指的是以数值有效的方式计算 DFT 的算法。算法如下：- 时间抽取和频率抽取。这是一种在现代计算机上速度非常快的用于计算 DFT 的算法。