跳转至

离散傅里叶变换

从 DTFT 采样到 DFT

实际序列往往只得到有限记录，DTFT 未必有便于计算的解析式，而连续频率函数也不能逐点存储。DFT 用有限个频率样本表示有限个时域样本，因而能直接交给数字计算机处理。

对 DTFT 在一周期内等间隔采样，采样点为 \(\omega_k=2\pi k/N\)：

\[ X[k]=X(e^{j\omega})\big|_{\omega=2\pi k/N}=\sum_{n=-\infty}^{\infty}x[n]e^{-j2\pi kn/N} \]

频域采样会在时域产生周期延拓。令

\[ \widehat x[n]=\sum_{r=-\infty}^{\infty}x[n-rN] \]

若把周期序列写成 \(\widehat x[n]=\sum_{k=0}^{N-1}a_ke^{j2\pi kn/N}\)，则 \(a_k=X[k]/N\)；\(X[k]\) 是采用 DFT 归一化约定的频域序列。若原序列只在某个连续的 \(N\) 点区间内非零，周期延拓之间不重叠，可由 \(N\) 个频域样本无失真恢复这段序列；否则不同周期相加，产生时域混叠。这里的条件与连续时间采样定理互为对偶：连续时间采样要求频域无混叠，频域采样要求时域无混叠。

从线性方程看，\(N\) 个频域样本只能给出 \(N\) 条独立约束。若待恢复记录有 \(L\leq N\) 个未知样本，可把它视为在 \(N\) 维傅里叶基上的投影并补零求逆；若 \(L>N\)，方程欠定，能确定的只是相隔 \(N\) 点样本的周期和，这正是时域混叠。

把一个周期的主值记为 \(x[0],\ldots,x[N-1]\)，定义

\[ W_N=e^{-j2\pi/N} \]

则 \(N\) 点 DFT 与 IDFT 为

\[ X[k]=\sum_{n=0}^{N-1}x[n]W_N^{nk},\qquad 0\leq k\leq N-1 \]
\[ x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]W_N^{-nk},\qquad 0\leq n\leq N-1 \]

\(x[n]\) 和 \(X[k]\) 在运算中都按 \(N\) 周期理解。因而 DFT 同时有三种含义：有限长序列 DTFT 的等间隔采样、周期序列的离散傅里叶级数，以及 \(N\) 维复向量在一组正交复指数基上的坐标变换。

变换矩阵写成

\[ \boldsymbol X=\boldsymbol W_N\boldsymbol x,\qquad [\boldsymbol W_N]_{k,n}=W_N^{kn} \]

其列向量彼此正交，满足

\[ \boldsymbol W_N^{H}\boldsymbol W_N=N\boldsymbol I,\qquad \boldsymbol W_N^{-1}=\frac{1}{N}\boldsymbol W_N^{H} \]

这也说明 IDFT 只是在 DFT 矩阵上取共轭并乘 \(1/N\)。

频域样本之间的插值

若 \(x[n]\) 在 \(0\leq n<N\) 之外为零，完整 DTFT 可由 DFT 样本恢复：

\[ X(e^{j\omega})=\sum_{k=0}^{N-1}X[k]\,\Phi_N\!\left(\omega-\frac{2\pi k}{N}\right) \]

其中

\[ \Phi_N(\theta)=\frac{1}{N}e^{-j(N-1)\theta/2}\frac{\sin(N\theta/2)}{\sin(\theta/2)} \]

\(\Phi_N\) 是周期的 Dirichlet 插值核，在本采样点取 1，在其余 DFT 采样点取 0。零填充并没有增加原序列所含的信息；它只是更密地采样同一条 DTFT，相当于在已有 DFT 样本之间作精确的带限周期插值。

例如长度 \(L=10\) 的全 1 序列在 \(N=10\) 时只有直流 DFT 样本非零；补零到 \(N=50\) 或 100 后，会在同一个 Dirichlet 幅度包络上取得越来越密的样本。包络、主瓣宽度和原有信息都没有改变。

常用的基本变换对包括

\[ \delta[((n-n_0))_N]\quad\overset{\mathrm{DFT}}{\longleftrightarrow}\quad W_N^{kn_0} \]
\[ 1\quad\overset{\mathrm{DFT}}{\longleftrightarrow}\quad N\delta[((k))_N] \]
\[ W_N^{-k_0n}\quad\overset{\mathrm{DFT}}{\longleftrightarrow}\quad N\delta[((k-k_0))_N] \]

其中 \(((n))_N\) 表示以 \(N\) 为模的下标。

循环移位、卷积与相关

设 \(x[n]\overset{N}{\longleftrightarrow}X[k]\)、\(y[n]\overset{N}{\longleftrightarrow}Y[k]\)，主要性质为：

时域操作 频域结果
\(ax[n]+by[n]\) \(aX[k]+bY[k]\)
\(x[((n-m))_N]\) \(W_N^{km}X[k]\)
\(W_N^{-ln}x[n]\) \(X[((k-l))_N]\)
\(x[((-n))_N]\) \(X[((-k))_N]\)
\(x^*[n]\) \(X^*[((-k))_N]\)
\(x[n]\circledast_N y[n]\) \(X[k]Y[k]\)
\(x[n]y[n]\) \(\frac1N X[k]\circledast_NY[k]\)

表中的移位都是循环移位。若需要有限记录的普通移位，可先补足零样本，使移出的非零部分不会绕回，再在扩展长度上作循环移位。

长度 \(N\) 的循环卷积定义为

\[ (x\circledast_Ny)[n]=\sum_{m=0}^{N-1}x[m]y[((n-m))_N] \]

它等于线性卷积的 \(N\) 周期混叠：

\[ x\circledast_Ny=\sum_{r=-\infty}^{\infty}(x*y)[n-rN] \]

若 \(x[n]\)、\(y[n]\) 的有限长度分别为 \(L\)、\(P\)，先补零到

\[ N\geq L+P-1 \]

则周期之间不再重叠，\(N\) 点循环卷积与线性卷积完全相同。这是用 DFT 实现线性卷积时必须补零的原因。

循环互相关定义为

\[ r_{xy}^{(N)}[m]=\sum_{n=0}^{N-1}x[((n+m))_N]y^*[n] \]

并满足

\[ r_{xy}^{(N)}[m]\quad\overset{N}{\longleftrightarrow}\quad X[k]Y^*[k] \]

要得到有限长序列的线性相关，同样需要补足避免循环折叠。DFT 的 Parseval 等式为

\[ \sum_{n=0}^{N-1}x[n]y^*[n]=\frac1N\sum_{k=0}^{N-1}X[k]Y^*[k] \]

取 \(x=y\) 时，两端分别是时域能量和缩放后的频域能量。

DFT 还具有对偶性：

\[ x[n]\overset{N}{\longleftrightarrow}X[k]\quad\Longrightarrow\quad X[n]\overset{N}{\longleftrightarrow}N x[((-k))_N] \]

实序列的 DFT 共轭对称，即 \(X[N-k]=X^*[k]\)。当 \(N\) 为偶数时，\(X[0]\) 与 \(X[N/2]\) 必为实数，只需保存或计算略多于半个频谱。实偶、实奇、虚偶、虚奇分量仍分别对应实偶、纯虚奇、纯虚偶、实奇的频谱分量。

一般复序列也可按模 \(N\) 的共轭对称性拆成

\[ x_e[n]=\frac12\left\{x[n]+x^*[((-n))_N]\right\},\qquad x_o[n]=\frac12\left\{x[n]-x^*[((-n))_N]\right\} \]

其中 \(x_e\) 的 DFT 为 \(\operatorname{Re}\{X[k]\}\)，\(x_o\) 的 DFT 为 \(j\operatorname{Im}\{X[k]\}\)。

离散时域和离散频域之间的对偶关系可概括为：一侧采样会使另一侧周期化，一侧周期化会使另一侧采样；一侧相乘会在另一侧形成循环卷积，一侧循环移位会在另一侧附加线性相位。

评论