# 离散傅里叶变换 在实际应用中，数字信号处理器中会大量的使用离散时间信号的频率分析，即将时域序列转换成等价的频域表达。在上一章中，我们学习了了利用离散时间傅里叶变换来分析离散时间序列（信号）的频谱。但是，离散时间傅里叶变换往往是频率的连续函数，所以计算机直接处理连续的函数是非常不方便的。我们知道，DTFT 变换等价于将连续时间傅里叶变换在时间轴上均匀采样。那么，在本章中，我们将进一步在频率上对序列的 DTFT 变换进行采样，从而得到时域和频域都离散的频域表达，那么这个过程我们称为离散傅里叶变换，即 DFT。 序列经过 DFT 变换后的到的频域表达仍然是离散的，因此这种频域分析方法更适用于计算机或者数字处理器，在实际应用中被广泛的使用。 ## 从 DTFT 到 DFT ### DTFT 回顾 根据上一章的内容，如果离散时间信号能量有限或者是绝对可和的，那么其离散时间傅里叶变换是关于频率的连续且周期的函数。 \begin{equation} X\left(e^{j \omega}\right)=\sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n} \label{eq:dtft} \end{equation} 我们知道，DTFT 变换是对CTFT 变换在时间上的等间隔抽样。离散时间信号$x[n]$可以写成 ```math x_T(t) = \sum_{n} x[n] \delta\left(t-n / F_{s}\right) ``` 其中，$F_s$为对连续时间信号$x(t)$的采样频率。令$\omega=\Omega/F_s$，对$x_T(t)$计算连续傅里叶变换 ```math \begin{split} X_{T}(j \Omega)&=\int_{-\infty}^{\infty} x_{T}(t) e^{-j \Omega t} d t \\ &= \sum_{n=-\infty}^{\infty} x[n] \underbrace{ \left(\int_{-\infty}^{\infty} \delta\left(t-n / F_{s}\right) e^{-j \Omega t} d t \right) }_{e^{-j\omega n} } \\ &=\sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n}=X\left(e^{j \omega}\right) \end{split} ``` 因此，公式\eqref{eq:dtft}实际上就是对$x_T(t)$的连续时间傅里叶变换在时间上的采样（第二个等式中的括号部分）。 ### 对 DTFT 变换的频率采样 由公式\eqref{eq:dtft}定义的DTFT 变换关于频率$\omega$是连续的，不便于计算机直接处理，我们需要进一步对频率离散化。那么，离散傅里叶变换（DFT）就是一种时间和频率上都离散的正交变换，它是通过对 DTFT 变换直接在频域进行等间隔采样来得到。 首先，我们知道 DTFT 变换是周期为$2\pi$的连续周期函数。对于长度为$L$的序列$x[n]$的 DTFT 变换，我们将频率$\omega$以$\frac{2\pi}{N}$等间隔离散化，得到等间隔的频率样本$\omega_{N}[k]$ ```math \underbrace{\omega_{N}[k]}_{\text { rad/sample }}=\underbrace{2 \pi k / N}_{\text { frequency in } k} ``` 那么定义$X[k]$为 DTFT 变换$X\left(e^{j \omega}\right)$的第$k$个样本点，带入到公式\eqref{eq:dtft}中，可以得到 ```math \begin{split} X[k] = \left. X\left(e^{j \omega}\right) \right\vert_{\omega=\omega_{N}[k]} &=\sum_{n=0}^{L-1} x[n] W_{N}^{kn} \\ \end{split} ``` 其中第二个等式是因为序列$x[n]$的有效长度为$N$，且$ W_{N} = e^{-j 2 \pi / N} $为旋转因子。 ![](asset/dtft_sample.png) ```eval_rst .. attention:: 对 DTFT 变换在频域上的等间隔抽样，对时域中原序列会造成什么影响呢？ ``` 同时域采样一样，定义采样序列$p_N(\omega) = \sum_{k=-\infty}^{\infty} \delta (\omega - 2k\pi /N)$。那么，将频域采样前后的关系写为 ```math \begin{aligned} X_p(e^{j\omega}) &= X(e^{j\omega})\cdot p_N(\omega) = \sum_{k=-\infty}^\infty \delta\left(\omega - \frac{2k\pi}{N}\right) \cdot X(e^{j\omega}) \\ & = \sum_{k=-\infty}^\infty \delta\left(\omega - \frac{2k\pi}{N}\right) \cdot X[k] \end{aligned} ``` 其中$X_p(e^{j\omega})$为$X[k]$的连续形式，表达的信号是等价的。那么对上式进行 IDTFT 变换，就可以得到频域采样后时域的信号，这里记作$\tilde{x}[n]$ ```math \tilde{x}[n] &= \text{IDTFT}\{X_p(e^{j\omega})\} \\ & =\frac{1}{2 \pi} \int_{-\pi}^{\pi}\left(\sum_{k=-\infty}^{\infty} X[k] \delta(\omega-2 \pi k / N)\right) e^{j \omega n} d \omega \\ & = \frac{1}{2 \pi} \sum_{k=-\infty}^{\infty} X[k] \cdot \underbrace{\int_{-\pi}^{\pi} \delta(\omega-2 \pi k / N) e^{j \omega n} d \omega}_{=e^{j 2 \pi k n / N}, \ \text{ for } k\in [0,N-1]} \\ &= \frac{1}{2 \pi} \sum_{k=0}^{N-1} X[k] e^{j 2 \pi k n / N} \\ &= \frac{1}{2 \pi} \sum_{l=-\infty}^{\infty} x[l] \underbrace{\sum_{k=0}^{N-1} e^{j 2 \pi k / N(n-l)}}_{=N\sum_{m=-\infty}^{\infty}\delta[l-n-Nm]} \\ &= \frac{N}{2 \pi} \sum_{m=-\infty}^{\infty} x[n+mN] ``` 上式最后一个等式的求和符号的含义就是，将原信号$x[n]$以$N$为长度，周期延拓。也就是说，如果对 DTFT 变换的频率进行离散化，会导致时域上信号的周期延拓，幅度也会变为原来的$N/2\pi$倍。这个结论与对信号在时域进行采样，频域周期延拓是类似的。 当序列$x[n]$长度$L$大于一个周期内频率采样的点数$N$的时，即$L>N$，在频率上的采样会导致时域序列混叠；而当序列$x[n]$长度$L\leq N$，就不会在时域发生混叠问题，此时只需要截取从0到$L-1$内的序列，就能无失真重建出原始时域序列。这个结论与采样定理的重建过程也是类似的。 下面我们将根据这些结论来推导出DFT变换的形式。 ### 从 DTFT 变换到 DFT 变换 当序列$x[n]$的长度$L=N$时，对该序列的 DTFT 变换的频率等间隔采样。 **从时域到频域：** \begin{equation} X[k] =\sum_{n=0}^{N-1} x[n] W_{N}^{kn}, \quad k=0,...,N-1 \label{eq:dft} \end{equation} **从频域到时域：** 根据公式\eqref{eq:prove} ```math \begin{split} \tilde{x}[n] &= \frac{1}{2 \pi} \sum_{k=0}^{N-1} X[k] e^{j 2 \pi k n / N} \\ &= \frac{N}{2 \pi} \sum_{m=-\infty}^{\infty} x[n+mN], \quad n\in \mathbb{Z} \\ \end{split} ``` 因为$L=N$，时域反变换序列没有混叠，所以在一个周期内$[0,N-1]$， $$ \tilde{x}[n] = \frac{N}{2\pi}x[n], \quad n = 0,...,N-1 $$ 联合上面两个式子，我们可以得到如下等式 \begin{equation} x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] W_N^{-kn} \quad n=0,...,N-1 \label{eq:idft} \end{equation} 由此可见，对于长度为$N$的序列$x[n]$来说，等式\eqref{eq:dft}和等式\eqref{eq:idft}是一个变换对。这个变换对是有限长度、且是离散的变换，在很多课本中，这种类型的变换称为“有限长变换”。 这里，我们将公式\eqref{eq:dft}称为离散傅立叶变换（DFT），公式\eqref{eq:idft}为DFT变换的逆变换，称为逆离散傅立叶变换（IDFT）。 ```eval_rst .. note:: 对于长度为$N$的序列$x[n]$的DFT和IDFT变换如下： **DFT变换：** \\begin{equation} X[k] =\\sum_{n=0}^{N-1} x[n] W_{N}^{kn}, \\quad k=0,...,N-1 \\end{equation} **IDFT变换：** \\begin{equation} x[n] = \\frac{1}{N} \\sum_{k=0}^{N-1} X[k] W_N^{-kn}, \\quad n=0,...,N-1 \\end{equation} ``` DFT变换实际上就是对DTFT变换的频率进行等间隔采样的版本。 ### 从DFT变换到DTFT变换 #### 频域插值 我们在前一章节已经学习了信号的采样定理。如果采样频率满足奈奎斯特频率，通过线性插值函数（Sinc）可以将采样后的离散时间信号无失真还原成原始的模拟信号。那么，我们如果对序列的DTFT变换的频率进行采样，得到频域中离散的序列，那么如何从这些离散的频率点重建原始连续且周期的DTFT变换呢？ 根据DFT和IDFT变换的定义，若已知序列$x[n]$的DFT变换$X_N[k]$， ```math x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X_N[k] W_N^{-kn} \quad n=0,…,N-1 ``` 另外，根据DTFT变换的定义 ```math X\left(e^{j \omega}\right) &=\sum_{n=0}^{N-1} \underbrace{\left(\frac{1}{N} \sum_{k=0}^{N-1} X_{N}[k] W_{N}^{-k n}\right)}_{x[n]} e^{-j \omega n} \\ &=\frac{1}{N} \sum_{k=0}^{N-1} X_{N}[k] \sum_{n=0}^{N-1} e^{-j(\omega-2 \pi k / N) n} \\ &=\frac{1}{N} \sum_{k=0}^{N-1} X_{N}[k] \cdot \frac{\sin N \frac{\omega-2 \pi k / N}{2}}{\sin \frac{\omega-2 \pi k / N}{2}} e^{-j \frac{N-1}{2}(\omega-2 \pi k / N)} ``` 定义 ```math \Phi(\omega) \triangleq \frac{\sin N \frac{\omega}{2}}{N\sin \frac{\omega}{2}} e^{-j \frac{N-1}{2}\omega} ``` 我们可以很容易验证函数$\Phi$满足下面的条件 ```math \Phi(2 \pi l / N)=\left\{\begin{array}{ll}{1} & {l=0} \\ {0} & {1 \leq l \leq N-1}\end{array}\right. ``` ![](asset/2019-07-29-21-06-37.png) 最后，我们可以将$X(e^{j\omega})$和$X_N[k]$的关系写成如下形式 \begin{equation} X\left(e^{j \omega}\right)=\sum_{k=0}^{N-1} X_N[k] \Phi(\omega-2 \pi k / N) \label{eq:dft2dtft} \end{equation} 这说明序列$x[n]$的DTFT变换$X(e^{j\omega})$可以通过对序列的DFT变换进行插值得到，插值方式如公式\eqref{eq:dft2dtft}。 #### 时域补零 DFT变换是对DTFT变换的频率进行采样得到的，如果我们已经计算出一个序列的$N$点DFT变换$X_N[k]$，就可以通过公式\eqref{eq:dft2dtft}重建出连续的DTFT变换$X\left(e^{j \omega}\right)$。 另外一方面，正是因为DFT变换是DTFT变换频域的采样，DFT变换的每个样本点对应的归一化频率为$2\pi k/N$。当DFT变换的点数$N$越高，DTFT变换频域采样的频率就越高，所以更逼近连续的DTFT变换。也就是说，我们可以通过不断增大DFT变换的长度$N$来逼近DTFT变换。令$x_N[n]$为对长度为$L