引入

在离散时间Fourier变换(DTFT) 中，我们将时域转变到离散的数字域的同时，求得的频谱仍然是连续函数，而连续函数是不可存储的

因此，我们需要对DTFT的结果在频域进一步离散化，得到的就是离散Fourier变换(DFT)

离散Fourier变换 (DFT)

DTFT的频谱是周期性的，其周期为一个Nyquist区间[−π,π][-\pi,\pi]的长度2π2\pi

为了离散地保存DTFT频谱，我们将[0,2π][0,2\pi]区间分成NN份，即保留以下频率点上的频谱值：

ωk=0+k2πN, k=0,1,...,N−1\omega_k =0+k\frac{2\pi}{N},\ k=0,1,...,N-1

我们直接将连续DTFT频谱在频域对ωk\omega_k采样，得到的就是DFT的算法：

X(ωk)=∑n=0L−1x(n)e−jωkn=∑n=0L−1x(n)e−j2πNnkX(\omega_k)=\sum\limits_{n=0}^{L-1}x(n)e^{-j\omega_kn}=\sum\limits_{n=0}^{L-1}x(n)e^{-j\frac{2\pi}{N}nk}

为了表示方便，令

WN:=e−j2πNW_N:=e^{-j\frac{2\pi}{N}}

X(k):=X(ωk)X(k):=X(\omega_k)

则DFT可以表示为

X(k)=∑n=0L−1x(n)WNnk, k=0,1,...,N−1X(k)=\sum\limits_{n=0}^{L-1}x(n)W_N^{nk},\ k=0,1,...,N-1

DFT的矩阵化

注意到我们采取的是有限长序列的DTFT，得到的频谱亦是一个有限长序列

即：这是一个向量到向量的映射F:RL→RNF:\R^L\to\R^N

事实上，这是一个线性映射，其矩阵为

F=[WN0WN0⋯WN0WN0WN1⋯WNL−1⋮⋮⋱⋮WN0WNN−1⋯WN(N−1)(L−1)]N×L, fkn=WNkn\mathbf{F}=\begin{bmatrix}W_N^{0} & W_N^0 & \cdots & W_N^0 \\ W_N^0 & W_N^1 & \cdots & W_N^{L-1} \\ \vdots & \vdots & \ddots & \vdots \\ W_N^0 &W_N^{N-1} & \cdots & W_N^{(N-1)(L-1)}\end{bmatrix}_{N\times L},\ f_{kn}=W_N^{kn}

则DFT的矩阵形式为

X=Fx\mathbf{X}=\mathbf{F}\mathbf{x}

DFT的方阵化

在讨论和使用DFT时，往往规定L=NL=N，则F\mathbf{F}是方阵FN\mathbf{F}_N

即：我们根据希望得到的频域向量的维数NN来约束时域向量维数LL，即使本身L≠NL\neq N，也要通过某些操作把原始序列x(n)x(n)加工成NN长度的x~(n)\tilde{x}(n)

这种方法的可行性体现在：

  1. 若L=NL=N，则无需操作

  2. 若L<NL<N，则对序列进行补零：

    x~(n)={x(n)n<L0L≤n<N\tilde{x}(n)=\begin{cases}x(n) & n<L\\0 & L\leq n<N \end{cases}

  3. 若L>NL>N，则对序列进行回绕：

    x~(n)=∑m=0⌊(L−n−1)/N⌋x(mN+n), n=0,1,...,N−1\tilde{x}(n)=\sum\limits_{m=0}^{\lfloor(L-n-1)/N\rfloor}x(mN+n),\ n=0,1,...,N-1

证明：对于L>NL>N的情形，回绕序列x~(n)\tilde{x}(n)和原序列x(n)x(n)的DFT相同

根据定义，有

X~=FN×Nx~\mathbf{\tilde{X}}=\mathbf{F}_{N\times N}\mathbf{\tilde{x}}

于是

X=FN×Lx\mathbf{X}=\mathbf{F}_{N\times L}\mathbf{x}

不妨假设L=qNL=qN，否则可以通过补零来得到（其实是有余数的情形我懒得写）

=[WN0WN0⋯WN0WN0WN1⋯WNqN−1⋮⋮⋮⋮WN0WNN−1⋯WN(N−1)(qN−1)]x=\begin{bmatrix}W_N^0 & W_N^0 & \cdots & W_N^0 \\ W_N^0 & W_N^1 & \cdots & W_N^{qN-1} \\ \vdots & \vdots & \vdots & \vdots \\ W_N^0 & W_N^{N-1} & \cdots &W_N^{(N-1)(qN-1)}\end{bmatrix}\mathbf{x}

=[FN×NWNNFN×NWN2NFN×N⋯WN(q−1)NFN×N][x0→N−1xN→2N−1x2N→3N−1⋮x(q−1)N→qN−1]=\begin{bmatrix} \mathbf{F}_{N\times N} & W_N^N\mathbf{F}_{N\times N} & W_N^{2N}\mathbf{F}_{N\times N} & \cdots & W_N^{(q-1)N}\mathbf{F}_{N\times N} \end{bmatrix}\begin{bmatrix} \mathbf{x}_{0\to N-1} \\ \mathbf{x}_{N\to2N-1}\\ \mathbf{x}_{2N\to3N-1}\\ \vdots \\ \mathbf{x}_{(q-1)N\to qN-1} \end{bmatrix}

=FN×N(x0→N−1+WNNxN→2N−1+⋯+WN(q−1)Nx(q−1)N→qN−1)=\mathbf{F}_{N\times N}(\mathbf{x}_{0\to N-1}+W_N^N\mathbf{x}_{N\to 2N-1}+\cdots+W_N^{(q-1)N}\mathbf{x}_{(q-1)N\to qN-1})

然而

WNN=e−2πj=1W_N^N=e^{-2\pi j}=1

于是

X=FN×N∑m=0q−1xmN→(m+1)N−1=FN×Nx~=X~\mathbf{X}=\mathbf{F}_{N\times N}\sum\limits_{m=0}^{q-1}\mathbf{x}_{mN\to (m+1)N-1}=\mathbf{F}_{N\times N}\mathbf{\tilde{x}}=\mathbf{\tilde{X}}

注意：试图使L=NL=N的意义在于

  • 稍后会提到的快速Fourier变换(FFT) 算法对N=2pN=2^p的情形有效，因此我们往往事先要求NN是某个22的幂
  • 但LL是根据采样频率和采样序列时长得到的实际量，并不能精确控制
  • 因此我们希望让LL的值去适应NN的取值

注意：从上面证明的结论可以看出，以NN长度回绕后得到相同序列的不同原始序列，其DFT是相同的，在DFT的角度无法区分

IDFT

x~(n)=1N∑k=0N−1X(k)WN−kn, n=0,1,...,N−1\tilde{x}(n)=\frac{1}{N}\sum\limits_{k=0}^{N-1}X(k)W_N^{-kn},\ n=0,1,...,N-1

注意：这里的nn的最大值是N−1N-1，即IDFT只能得到回绕后的NN长序列，无法得到原始的LL长序列

上述算法的矩阵表示为

FN−1=1N[WN0WN0⋯WN0WN0WN1⋯WNN−1⋮⋮⋱⋮WN0WNN−1⋯WN(N−1)2]=1NFN∗\mathbf{F}_N^{-1}=\frac{1}{N}\begin{bmatrix} W_N^0 & W_N^0 & \cdots & W_N^0 \\ W_N^0 & W_N^1 & \cdots & W_N^{N-1} \\ \vdots & \vdots & \ddots & \vdots \\ W_N^0 & W_N^{N-1} & \cdots & W_N^{(N-1)^2} \end{bmatrix}=\frac{1}{N}\mathbf{F}_N^*

DFT的性质

  • 频谱是离散的、周期的（只记录一个周期）
  • 实序列的DFT是共轭对称的：X(k)=X∗(N−k)X(k)=X^*(N-k)
  • DFT的线性变换（矩阵！）
  • Parseval定理：∑n=0N−1∣x(n)∣2=1N∑k=0N−1∣X(k)∣2\sum\limits_{n=0}^{N-1}|x(n)|^2=\frac{1}{N}\sum\limits_{k=0}^{N-1}|X(k)|^2
  • 反褶、共轭：
    • 时域反褶，频域反褶
    • 时域共轭，频域共轭反褶
    • 时域共轭反褶，频域共轭
  • 频移：X(k−l)=DFT[x(n)WN−nl]X(k-l)={\rm DFT}[x(n)W_N^{-nl}]
  • 时移：DFT[x(n−m)]=e−jmωkX(ωk)=WNmkX(k){\rm DFT}[x(n-m)]=e^{-jm\omega_k}X(\omega_k)=W_N^{mk}X(k)
  • 时域卷积：DFT[x(n)∗y(n)]=DFT[x(n)]⋅DFT[y(n)]{\rm DFT}[x(n)*y(n)]={\rm DFT}[x(n)]\cdot {\rm DFT}[y(n)]
  • 频域卷积：DFT[x(n)y(n)]=1NX(k)⊗Y(k){\rm DFT}[x(n)y(n)]=\frac{1}{N}X(k)\otimes Y(k)
    • 其中的离散圆卷积定义为x(n)⊗y(n)=∑m=0N−1x(m)y((n−m)mod  N)x(n)\otimes y(n)=\sum\limits_{m=0}^{N-1}x(m)y((n-m)\mod N)