一窥数字傅里叶变换矩阵

DFT技术虽然很神奇，但总觉得是个黑洞，摸不着头脑，今天研究一下DFT matrix，能更加清楚的了解一些内核的东西。

这是一个N*N方阵，矩阵的基本元素由 W = e − j 2 π / N W=e^{-j2\pi/N} W=e−j2π/N来构成，每个位置元素 a i j = W ( i − 1 ) ∗ ( j − 1 ) = e − j 2 π ( i − 1 ) ( j − 1 ) / N a_{ij}=W^{(i-1)*(j-1)}=e^{-j2\pi (i-1)(j-1)/N} aij​=W(i−1)∗(j−1)=e−j2π(i−1)(j−1)/N。即矩阵元素的索引是从自然数1开始的，但指数运算需要从0（据说现在小学已经把0化为自然数了。。。）开始。简单的列一下这个矩阵： W = [ e − j 0 e − j 0 e − j 0 ⋯ e − j 0 e − j 0 e − j 2 π / N e − j 4 π / N ⋯ e − j 2 ( N − 1 ) π / N e − j 0 e − j 4 π / N e − j 8 π / N ⋯ e − j 4 ( N − 1 ) π / N ⋮ ⋮ ⋮ ⋱ ⋮ e − j 0 e − j 2 ( N − 1 ) π / N e − j 4 ( N − 1 ) π / N ⋯ e − j 2 ( N − 1 ) ( N − 1 ) π / N ] = [ 1 1 1 ⋯ 1 1 e − j 2 π / N e − j 4 π / N ⋯ e − j 2 ( N − 1 ) π / N 1 e − j 4 π / N e − j 8 π / N ⋯ e − j 4 ( N − 1 ) π / N ⋮ ⋮ ⋮ ⋱ ⋮ 1 e − j 2 ( N − 1 ) π / N e − j 4 ( N − 1 ) π / N ⋯ e − j 2 ( N − 1 ) ( N − 1 ) π / N ] \bold W=\begin{bmatrix} e^{-j0} &e^{-j0} &e^{-j0} & \cdots & e^{-j0} \\ e^{-j0} &e^{-j2\pi /N} &e^{-j4\pi /N} & \cdots &e^{-j2(N-1)\pi /N} \\ e^{-j0} &e^{-j4\pi /N} &e^{-j8\pi /N} & \cdots &e^{-j4(N-1)\pi /N} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ e^{-j0} &e^{-j2(N-1)\pi /N} &e^{-j4(N-1)\pi /N} & \cdots & e^{-j2(N-1)(N-1)\pi /N} \end{bmatrix}\\ =\begin{bmatrix} 1 &1 &1 & \cdots & 1 \\ 1 &e^{-j2\pi /N} &e^{-j4\pi /N} & \cdots &e^{-j2(N-1)\pi /N} \\ 1 &e^{-j4\pi /N} &e^{-j8\pi /N} & \cdots &e^{-j4(N-1)\pi /N} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 &e^{-j2(N-1)\pi /N} &e^{-j4(N-1)\pi /N} & \cdots & e^{-j2(N-1)(N-1)\pi /N} \end{bmatrix} W=⎣⎢⎢⎢⎢⎢⎡​e−j0e−j0e−j0⋮e−j0​e−j0e−j2π/Ne−j4π/N⋮e−j2(N−1)π/N​e−j0e−j4π/Ne−j8π/N⋮e−j4(N−1)π/N​⋯⋯⋯⋱⋯​e−j0e−j2(N−1)π/Ne−j4(N−1)π/N⋮e−j2(N−1)(N−1)π/N​⎦⎥⎥⎥⎥⎥⎤​=⎣⎢⎢⎢⎢⎢⎡​111⋮1​1e−j2π/Ne−j4π/N⋮e−j2(N−1)π/N​1e−j4π/Ne−j8π/N⋮e−j4(N−1)π/N​⋯⋯⋯⋱⋯​1e−j2(N−1)π/Ne−j4(N−1)π/N⋮e−j2(N−1)(N−1)π/N​⎦⎥⎥⎥⎥⎥⎤​ 这个矩阵是主对角对称矩阵。即 W T = W \bold W^T=\bold W WT=W

上述矩阵满足 W † W = N I \bold W^\dagger \bold W=NI W†W=NI 即厄米特共轭与原矩阵的乘积是N倍的单位阵。具有酉矩阵的特点（差了N倍，不知道失算uniary，还是paraunitary）。上面的式子还暗示了 W † / N = W − 1 \bold W^\dagger/N=\bold W^{-1} W†/N=W−1，另外一个推论是 W † = W ∗ \bold W^\dagger=\bold W^* W†=W∗

假设一组序列为 X = [ x ( 0 ) , x ( 1 ) , . . . x ( N − 1 ) ] T X=[x(0),x(1),...x(N-1)]^T X=[x(0),x(1),...x(N−1)]T，这组序列的DFT变换 X ( k ) = ∑ n = 0 N − 1 x ( n ) e − j 2 π k n / N = ∑ n = 0 N − 1 x ( n ) W k n = W X X(k) = \sum_{n=0}^{N-1}x(n)e^{-j2\pi kn/N} = \sum_{n=0}^{N-1}x(n) W^{kn} =\bold WX X(k)=n=0∑N−1​x(n)e−j2πkn/N=n=0∑N−1​x(n)Wkn=WX这里的n和k都是0开始的了。 x ( n ) = 1 N ∑ n = 0 N − 1 X ( k ) e j 2 π k n / N = 1 N ∑ n = 0 N − 1 X ( k ) W − k n x(n) =\frac{1}{N} \sum_{n=0}^{N-1}X(k)e^{j2\pi kn/N} =\frac{1}{N} \sum_{n=0}^{N-1}X(k)W^{-kn} x(n)=N1​n=0∑N−1​X(k)ej2πkn/N=N1​n=0∑N−1​X(k)W−kn

我们利用python代码来一窥DFT矩阵的样子

当M=2时，得到如下的值，最后一个值 e − j 2 π / 2 = − 1 e^{-j2\pi /2}=-1 e−j2π/2=−1

M=4时，

根据【2】提供的图形，对256个点进行DFT变换，将时域频域画在一张图里，就差不多这个样子了。图中每个算法采样点换成256，然后增加几行代码：

纯属娱乐，但这个工具对于不要求运算速度的话，还是很直观的。

这个小算法能够比较清晰的将DFT算子展现在你面前，帮助理解DFT的玄妙之处

1.Multirate Systems and Filter Banks, P.Vaidyanathan 2.Python信号分析 | 信号的表示（二）【三角、复指数、矩形脉冲、阶跃】