离散傅立叶变换

1. 复数形式傅里叶变换与逆变换

傅里叶变换一般指的是连续傅里叶变换，其定义如下:

\[F(\omega)=\int\limits_{-\infty}^{+\infty}f(t)e^{-i\omega t}dt\]

傅里叶逆变换的定义如下:

\[f(t)=\frac{1}{2\pi}\int\limits_{-\infty}^{+\infty}F(\omega)e^{i\omega t}d\omega\]

有了傅里叶变换了，为什么还要搞出个离散傅里叶变换呢？我们从上面公式可以看出，不管是傅里叶变换还是逆变换都是正负无穷的连续积分，这在数学公式上尚可以根据微分及极限求解公式进行计算，但却不太方便在计算机上实现，因为计算机是一个离散系统，那离散傅里叶变换就是用来解决这个问题的，使用计算机这个离散系统进行有限近似计算。不过在讲离散傅里叶变换之前，先说说离散时间傅里叶变换(DTFT)。

2. 离散时间傅里叶变换(DTFT)

离散时间傅立叶变换处理对象：无穷时间跨度的固定采样频率的离散信号点，即模拟信号本身无周期，且时间跨度无穷大，采样频率固定。虽然是离散点，但是信号本身时间跨度无穷，因此导致离散后对应的最大周期信号的周期无穷大，频率无穷小。

在离散系统中，假如\(x(t)\)为连续系统信号，要转换成离散系统，就要先进行采样，采样频率为\(f_s\) ，采样点时间间隔为\(T_s=\frac{1}{f_s}\)

冲击采样序列为:

\[\delta_s(t)=\sum\limits_{n = -\infty}^{\infty}\delta(t-nT_s)\]

取样之后的信号为:

\[x_s(t)=\sum\limits_{n = -\infty}^{\infty}x(t)\delta(t-nT_s)\]

这里t如果取的不是\(T_s\)的整数倍，其值没有定义，即只能取\(T_s\)的整数倍。

连续信号的傅里叶变换的定义为:

\[X(\omega)=\int\limits_{-\infty}^{+\infty}x(t)e^{-i\omega t}dt\]

则采样后的信号傅里叶变换为:

\[X_s(\omega)=\int\limits_{-\infty}^{+\infty}(\sum\limits_{n = -\infty}^{\infty}x(t)\delta(t-nT_s))e^{-i\omega t}dt\]

交换一下积分与求和顺序:

\[X_s(\omega)=\sum\limits_{n = -\infty}^{\infty}\int\limits_{-\infty}^{+\infty}x(t)\delta(t-nT_s)e^{-i\omega t}dt\]

由\(\delta(x)\)筛选性:

\[\int\limits_{-\infty}^{+\infty}f(x)\delta(x-x_0)dx=f(x_0)\]

可得：

\[X_s(\omega)=\sum\limits_{n = -\infty}^{\infty}x(nT_s)e^{-i\omega nT_s}\]

对数字系统而言，我们只有\(x(t)\)采样后的信号\(\left\{x[n]\right\}\)，注意，它是一个序列，第\(n\)个采样发生在时间\(t=nTs\)，因此，可将连续信号的傅里叶变换写成如下形式:

\[X_s(\omega)=\sum\limits_{n = -\infty}^{\infty}x(n)e^{-i\omega nT_s}\]

上式称为离散时间傅里叶变换(Discrete Time Fourier Transform)，简称DTFT，也就是无限长离散信号如何进行傅里叶变换。

3. 离散傅立叶变换(DFT)与逆变换(IDFT)

离散时间傅里叶变换中原始信号还是无限长的，即使采样后，采样点也是无限个，可以认为周期为无限长，导致即使离散采样后进行分解变换得到的频谱趋向于连续。因为现实中不能记录存储无穷大时间跨度的模拟信号，连续的频谱不利于计算机处理，所以频率也要离散化才行，所需要的技术就是离散傅里叶变换DFT(Discrete Fourier Transform)，即具有周期特性离散信号的傅里叶级数(就是将无限长的离散信号进行截短至N个采样点，然后将这个N个采样点进行周期延拓，变成周期信号，这样其频率就离散了)。

离散傅里叶变换与连续傅里叶变换“类似”，只不过把积分换成级数，DFT以及IDFT的定义如下:

\[X(k)=\sum\limits_{n = 0}^{N-1}x(n)e^{-i\frac{2\pi}{N}nk},k=0,1,2..N-1\]

\[x(n)=\frac{1}{N}\sum\limits_{k = 0}^{N-1}X(k)e^{i\frac{2\pi}{N}nk},n=0,1,2..N-1\]

（可知：对于\(N\)维数组的离散傅立叶变换后得到的频域数组维度也为\(N\)）

下面进行详细推导。

我们知道，周期函数可以用傅里叶级数展开，在引入\(\delta(t)\) 函数后，更一般的周期函数也能被展开了，因为可以使用\(\delta(t)\) 函数进行采样，变成有限长离散序列，可以看成是周期信号。

根据连续信号\(x(t)\)按照采样时间\(T_s\)进行抽样\(N\)次\(\delta(t-nT_s)\)，并将这\(N\)个数值进行周期延拓，可以得到周期的离散信号\(x[n]\)，其周期\(T=N*T_s\)，频率为\(f=\frac{2\pi}{T}\)，在一个周期\(T\)内，其共表达式为:

\[x_s(t)=\sum\limits_{n = -\infty}^{\infty}x(t)\delta(t-nT_s)\]

令\(\omega = f = \frac{2\pi}{T}\)

可以获得离散周期信号的傅里叶级数为:

\(X[k\omega] = \frac{1}{T}\int\limits_{0}^{T}(\sum\limits_{n=0}^{N-1}x(t)\delta(t-nT_s))e^{-i\frac{2\pi}{T}kt}dt\)

由\(\delta(t)\)函数的筛选性，有

\(X[k\omega]=\frac{1}{NT_s}\sum\limits_{n=0}^{N-1}x(nT_s)e^{-i\frac{2\pi}{N}nk}\)

令\(X[k\omega]T_s=X[k]\)

\(X[k]=\frac{1}{N}\sum\limits_{n=0}^{N-1}x(nT_s)e^{-i\frac{2\pi}{N}nk}=\frac{1}{N}\sum\limits_{n=0}^{N-1}x[n]e^{-i\frac{2\pi}{N}nk}\)

这就是离散周期信号的傅里叶变换，理论上离散周期信号的频谱是有无穷多的，但是由于\(e^{-i\frac{2\pi}{N}nk}\)的的周期性(将其展开成三角函数后sin和cos)，一般我们只取主值区间\(0=k<N-1\)进行研究。

4. 离散傅立叶变换的物理意义

奈奎斯特采样定理：采样频率大于信号中最高频率的2倍时，采样后的数字信号可以完整地恢复出原始信号。一般实际应用中保证采样频率为信号最高频率的2.56~4倍。

假设信号频率为\(F\)，采样频率为\(F_s\)，采样点数为\(N\)。为了方便进行DFT运算，通常\(N\)取2的整数次幂。

\(N\)个采样点，经过DFT变换后的结果为N个复数，每个复数对应一个频率(第n<=N/2个点对应的频率为(n-1)/N*Fs)，该复数的模值表示该频率的振幅特征。怎么去理解这段话呢，还要从信号的傅里叶级数复数形式说起，对于时域信号f(t)，其傅里叶级数展开为:

\(f(t) =c_0 + \sum\limits_{n=1}^{\infty}(c_ne^{i\frac{n\pi t}{l}}+c_{-n}e^{-i\frac{n\pi t}{l}})= \sum\limits_{n=-\infty}^{+\infty}c_ne^{i\frac{n\pi t}{l}}\)

其中

\(c_0 = \frac{a_0}{2},c_n = \frac{a_n-ib_n}{2},c_{-n} = \frac{a_n+ib_n}{2},n=1,2,3...\)

在离散傅里叶中，\(n\)不是取无穷个，而是\(N\)个，于是有:

\(f(t) =c_0 + \sum\limits_{n=1}^{\frac{N}{2}}(c_ne^{i\frac{n\pi t}{l}}+c_{-n}e^{-i\frac{n\pi t}{l}})= \sum\limits_{n=-\frac{N}{2}}^{\frac{N}{2}}c_ne^{i\frac{n\pi t}{l}}\)

可以看到，原始时域信号f(t)经DFT后，DFT的结果其实是原始信号傅里叶展开的个项系数，\(c_0\)为常数项，\(c_n\)是不同频率的正余弦系数。

该振幅特征和原始信号的振幅之间的关系是：如果原始信号的振幅为A，则DFT结果的每个点(除了第一个直流分量点)的模值就是A的N/2倍；而第一个点的模值是直流分量振幅的N倍。同时，这N个复数点去掉第一个点(直流分量)后剩下的N-1个点是关于其中心共轭对称的，因此实际只需要取前一半点的频谱即可，因为共轭对称的两个点的模值(振幅)相同。

\(\color{red}注意\)，\(\colorbox{Orange}{以上结论是针对numpy的fft运算结果总结的，在numpy.fft中没有进行1/N归一化处理，而上面推导中都是除N的}\)，即

\(X[k]=\frac{1}{N}\sum\limits_{n=0}^{N-1}x[n]e^{-i\frac{2\pi}{N}nk},0\le k \le N-1\)离散傅立叶变换的物理意义

5. 总结

连续信号傅立叶变换

模拟信号时间跨度无穷，采样频率无穷小，分解后对应的无穷个频率项

离散时间傅立叶变换

模拟信号时间跨度无穷，采样频率固定，具有无穷个（无周期）时域离散点，分解后对应无穷个频率项

离散傅立叶变换

对模拟信号时间跨度截断（再周期性延拓），采样频率固定，具有无穷个有周期的时域离散点（或者在实际处理中，不进行延拓的有限个时域离散点），分解后对应有限个频率项

参考文献

https://zhuanlan.zhihu.com/p/405143684

https://www.luogu.com.cn/blog/IowaBattleship/latex-gong-shi-tai-quan

https://www.zhihu.com/question/489681533