前言

笔者并非通讯专业科班学生，本文中的一些知识解释不严谨敬请见谅

离散傅里叶变换

变换（DFT）和逆变换（IDFT）

对于x=(x_0,\cdots,x_{N-1})\in\mathbb{C}^N，内的每一个点，它的离散傅里叶变换\hat{x}=(\hat{x}_0,\cdots,\hat{x}_{N-1}):=DFTx为
::: align-center
\hat{x_k}=\sum_{j=0}^{N-1}x_jw_{N}^{jk}

:::
其中w_{N}=e^{\frac{-2\pi}{N}i}
DFT算子也可以写为矩阵的形式
::: align-center
U_N=(w_N^{jk})_{j,k=0,\cdots,N-1}=\begin{bmatrix} w_{N}^{0\cdot 0} & w_N^{0\cdot 1} &\cdots &w_N^{0\cdot (N-1)}\\ \vdots & \vdots & &\vdots\\ w_N^{(N-1)\cdot 0}\cdots& w_N^{(N-1)\cdot 1}&\cdots &w_N^{(N-1)\cdot (N-1)} \end{bmatrix}

:::
注：在计算过程中，利用复数性质，jk也可以取模N简化计算
这样DFT也可以写为
::: align-center
\hat{x}_k=U_Nx

:::

DFT的逆变换为
::: align-center
x_j=\frac{1}{N}\sum_{k=0}^{N-1}\hat{x}_kw_N^{-jk}

:::

特别的，四阶DFT矩阵为
::: align-center
U_4=\begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -i & -1 & i\\ 1 & -1 & 1 & -1\\ 1 & i & -1 & -i \end{bmatrix}

:::
而它的逆变换矩阵是U_4的共轭转置\times \frac{1}{4}
::: align-center
\frac{1}{4}U^H

:::
其中H代表共轭转置，它的特殊情况为矩阵的每个元素为实数，此时共轭转置退化为普通转置T

DFT的复杂度为\mathcal{O}(n^2)

为什么

从这篇文章可以知道，连续傅里叶变换FT是通过将信号转化为圆频率为\omega的无限个复圆上来完成的，但在实际问题中我们处理的多是采样后的数字信号，它在时域上是离散的，所以我们必然不能再使用FT的方法将其进行变换
非常粗略的解释，我们应考虑对这些“复圆”也进行“采样”，将其分为与原信号采样点数相等的N的部分，这样一个信号采样点对应复圆上的一个采样点，我们依然可以将这个时域离散的信号变换为频域离散的谱

而考虑将复圆e^{-2\pi i}拆分为N份，相当于寻找w_N=e^{-2\pi i}=1的解，由复数的知识可以知w_N=e^{\frac{-2\pi}{N}i}

对于逆变换，有类似的物理解释，但这里我们使用代数知识推导
考虑IDFT[DFT(x)]中的x_j
::: align-center
\begin{aligned} &IDFT[DFT(x)]_j=\frac{1}{N}\sum_{k=0}^{N-1}(\sum_{p=0}^{N-1}x_pw_N^{pk})w_N^{-jk}\\ &=\frac{1}{N}\sum_{p=0}^{N-1}x_p\sum_{k=0}^{N-1}w_N^{(p-j)k}\\ \end{aligned}

:::
对于\sum_{k=0}^{N-1}w_N^{(p-j)k}，有
::: align-center
\sum_{k=0}^{N-1}w_N^{(p-j)k}=N\delta_{pj}

:::
其中
::: align-center
\delta_{pj}=\left\{ \begin{matrix} 1 & p=j\\ 0 & p\ne j \end{matrix} \right .

:::
为克罗内克Dealta函数（离散的狄拉克Dealta函数）
在p\ne j时，因为\sum_{k=0}^{N-1}w_N^{(p-j)k}是一个等比级数，展开有
::: align-center
\sum_{k=0}^{N-1}w_N^{(p-j)k}=\frac{1-w_N^{(p-j)N}}{1-w_N^{p-j}}=\frac{1-e^{-2\pi (p-j)i}}{1-e^{\frac{-2\pi(p-j)}{N}i}}

:::
其中e^{-2\pi (p-j)i}由欧拉公式得始终为1，故整体结果为0
在p=j和时，w_N^{(p-j)k}=1，求和得N

故
::: align-center
\begin{aligned} &IDFT[DFT(x)]_j=\frac{1}{N}\sum_{p=0}^{N-1}x_p\sum_{k=0}^{N-1}w_N^{(p-j)k}\\ &=\frac{1}{N}\sum_{p=0}^{N-1}x_pN\delta_{pj}\\ &=x_j \end{aligned}

:::
这里我们间接证明了Dealta函数的筛选性

性质

线性性

::: align-center
DFT(ax+by)=aDFT(x)+bDFT(y)

:::
不再解释

时间反转

定义时域反转信号y_k=x_{N-k}（下标取模N，准确地说-n\space mod\space N），则其DFT满足
::: align-center
\hat{y}_k=\hat{x}_{N-k}

:::
即频域谱也会对称反转

这里有一个性质，那就是将变换后的信号反转后进行DFT变换，之后\times \frac{1}{N}即完成了信号的逆变换，即
::: align-center
x_k=IDFT(\hat{x_k})=\frac{1}{N}DFT(x_{N-k})

:::
因为对于变换前/后的信号而言，DFT/IDFT的指数项对其施加的相位是相反的，若我们人为反转变换后信号的相位，并对其作DFT，这就相当于我们在对原信号作IDFT（这里我们省略了对\frac{1}{N}的效应的叙述，它类似于频域到时域的能量修正）

时间共轭

若对时域信号取共轭y=x^*，则其DFT满足
::: align-center
y_k=\hat{x}_{N-K}^*

:::
下标取模N
即频谱信号会共轭对称

类似于上面，这里我们也可以给出
::: align-center
x_k=IDFT(\hat{x_k})=\frac{1}{N}[DFT(x_k^*)]^*

:::

类似的，对变换后的信号作共轭，相位会反转并且施加一个共轭效应，我们再通过一次DFT，之后再取共轭抵消之前的共轭效应，最后得到的信号就相当于我们在对原信号作IDFT（这里我们省略了对\frac{1}{N}的效应的叙述，它类似于频域到时域的能量修正）

三角插值

给定离散信号x=(x_0,x_1,\cdots,x_{N-1})\in\mathbb{C}^N，其DFT变换为\hat{x}=\mathcal{F}(x)
可以考虑构造三角插值多项式
::: align-center
T_N(z)=\frac{1}{N}\sum_{k=0}^{N-1}\hat{x}_ke^{2\pi ikz}

:::
其中x_k是DFT的第k个分量，z\in[0,1)为连续变量
该多项式在离散点z=\frac{l}{N},l=0,1,\cdots,N-1处满足
::: align-center
T_N(\frac{l}{N})=x_l

:::
即该多项式精确的通过所有的原始数据点
这样便完成了对有限个点的多项式拟合

证明：
将z=\frac{l}{N}代入T_N(z)，有
::: align-center
\begin{aligned} T_N(\frac{l}{N})=\frac{1}{N}\sum_{k=0}^{N-1}(\sum_{p=0}^{N-1}x_pw_N^{pk})w_N^{-lk} \end{aligned}

:::
根据上面IDFT的代数证明易得结果

帕斯瓦尔定理

表明信号在时域和频域能量相等的帕斯瓦尔定理在DFT中的表述（以下为广义表述）为
::: align-center
\sum_{n=0}^{N-1}x_ny_n^*=\frac{1}{N}\sum_{k=0}^{N-1}\hat{x}_k\hat{y}_k^*

:::
证明：
::: align-center
\begin{aligned} &\sum_{k=0}^{N-1}\hat{x_k}\hat{y}_k^*\\ &=\sum_{k=0}^{N-1}\sum_{j=0}^{N-1}x_jw_N^{jk}\sum_{p=0}^{N-1}y^*_pw_N^{-pk}\\ &=\sum_{j=0}^{N-1}\sum_{p=0}^{N-1}x_jy_p^*\sum_{k=0}^{N-1}w_N^{(j-p)k}\\ &=\sum_{j=0}^{N-1}\sum_{p=0}^{N-1}x_jy_p^* N\delta_{jp}\\ &=N\sum_{j=0}^{N-1}x_jy_p^* \end{aligned}

:::
同除N得结果

同时在狭义情况下，即信号y_n=x_n时，由复数的知识可得狭义的帕斯瓦尔定理
::: align-center
\sum_{n=0}^{N-1}|x_n|^2=\frac{1}{N}\sum_{k=0}^{N-1}|\hat{x}_k|^2

:::

圆周卷积

DFT也拥有时域卷积等于频域乘积的性质
::: align-center
\widehat{(x\circledast y)_k}=\hat{x_k}\hat{y_k}

:::
其中离散时间的圆周卷积定义为
::: align-center
(x\circledast y)_j=\sum_{l=0}^{N-1}x_ly_{j-l\space mod\space N}

:::
下标j-l取模N，所以有诸如y_{-m}=y_{N-m}的情况，相当于“绕着”N进行取值，故得名“圆周”卷积

证明：
::: align-center
\begin{aligned} &\widehat{(x\circledast y)_k}=\sum_{j=0}^{N-1}\sum_{l=0}^{N-1}x_ly_{j-l}w_N^{jk}\\ &=\sum_{j=0}^{N-1}\sum_{l=0}^{N-1}\frac{1}{N}\sum_{p=0}^{N-1}\hat{x}_pw_N^{-lp}\frac{1}{N}\sum _{q=0}^{N-1}\hat{y}_qw_N^{-(j-l)q}w_N^{jk}\\ &=\sum_{p=0}^{N-1}\hat{x}_p\sum_{q=0}^{N-1}\hat{y}_q\frac{1}{N}\sum_{l=0}^{N-1}w_N^{(q-p)l}\frac{1}{N}\sum_{j=0}^{N-1}w_N^{(k-q)j}\\ &=\sum_{p=0}^{N-1}\hat{x}_p\sum_{q=0}^{N-1}\hat{y}_q\delta_{qq}\delta_{kq}\\ &=\hat{x}_k\hat{y}_k \end{aligned}

:::
圆周卷积可以写为矩阵乘法的形式
::: align-center
x=Yx

:::
其中Y是圆周卷积矩阵
::: align-center
Y=\begin{bmatrix} y_0&y_{N-1}&\cdots&y_2&y_1\\ y_1&y_0&\cdots&y_3&y_2\\ \vdots&\vdots&&\vdots&\vdots\\ y_{N-1}&y_{N-2}&\cdots&y_1&y_{N-1} \end{bmatrix}

:::

卷积的算法较为复杂，但是由DFT性质有
::: align-center
x\circledast y=IDFT[DFT(x)DFT(y)]

:::
而DFT有FFT算法可以大大简化算法复杂度，请见这里