离散傅里叶变换基础知识

离散傅里叶变换基础知识傅里叶是一位法国数学家，他发现任何周期函数都可以用正弦函数和余弦函数构成的无穷级数做为基函数来表示，也就是我们数学上面学到的傅里叶级数，设一个周期函数𝑓(𝑡)，其周期为𝑇，则其角频率为𝑤0=2𝜋𝑇，则该函数可以展开为一系列三角函数的累加：𝑓(𝑡)=𝑎0+𝑎1𝑐𝑜𝑠𝑤0𝑡+𝑏1𝑠𝑖𝑛𝑤0𝑡+𝑎2𝑐𝑜𝑠2𝑤0𝑡+𝑏2𝑠𝑖𝑛𝑤2𝑡+⋯=𝑎02+∑𝑎𝑛𝑐𝑜𝑠𝑛𝑤0𝑡+𝑏𝑛𝑠𝑖𝑛𝑛𝑤0𝑡∞𝑛=1其中，上式中的各个系数：𝑎0=2𝑇∫𝑓(𝑡)𝑑𝑡𝑇2⁄−𝑇2⁄𝑎𝑛=2𝑇∫𝑓(𝑡)𝑐𝑜𝑠𝑛𝑤0𝑡𝑑𝑡𝑇2⁄−𝑇2⁄𝑏𝑛=2𝑇∫𝑓(𝑡)𝑠𝑖𝑛𝑛𝑤0𝑡𝑑𝑡𝑇2⁄−𝑇2⁄但这个形式不太好用，因为正弦和余弦项是分开的，我们要考虑把他们两个整合起来，这样对每一个频率nw0我们就可以得到一个系数项（比如上式的an或者bn），这其实就是该频率对应的幅值。然后我们以频率为X轴，以其对应的幅值为Y轴，就可以得到该函数在频域里面的图像了。对于周期函数，其频域里面的图像是不连续的，只在𝑤=0,±𝑤0,±2𝑤0…才有图像。那么我们该如何将上面的正弦项和余弦项整合到一块呢？答案是欧拉公式。下面就是鼎鼎大名的欧拉公式：𝑒𝑖𝑤𝑡=𝑐𝑜𝑠𝑤𝑡+𝑖𝑠𝑖𝑛𝑤𝑡换个表达方式：𝑐𝑜𝑠𝑤𝑡=12(𝑒𝑖𝑤𝑡+𝑒−𝑖𝑤𝑡)𝑠𝑖𝑛𝑤𝑡=12𝑖(𝑒𝑖𝑤𝑡−𝑒−𝑖𝑤𝑡)将上面的公式代入傅里叶级数中：𝑓(𝑡)=𝑎0+𝑎1𝑐𝑜𝑠𝑤0𝑡+𝑏1𝑠𝑖𝑛𝑤0𝑡+𝑎2𝑐𝑜𝑠2𝑤0𝑡+𝑏2𝑠𝑖𝑛𝑤2𝑡+⋯=𝑎02+∑𝑎𝑛𝑐𝑜𝑠𝑛𝑤0𝑡+𝑏𝑛𝑠𝑖𝑛𝑛𝑤0𝑡∞𝑛=1=𝑎02+∑{𝑎𝑛𝑒𝑖𝑛𝑤0𝑡+𝑒−𝑖𝑛𝑤0𝑡2+𝑏𝑛𝑒𝑖𝑛𝑤0𝑡−𝑒−𝑖𝑛𝑤0𝑡2𝑖}∞𝑛=1=𝑎02+∑{𝑎𝑛−𝑏𝑛𝑖2𝑒𝑖𝑛𝑤0𝑡+𝑎𝑛+𝑏𝑛𝑖2𝑒−𝑖𝑛𝑤0𝑡}∞𝑛=1=𝑎02+∑{𝑐𝑛𝑒𝑖𝑛𝑤0𝑡+𝑐−𝑛𝑒−𝑖𝑛𝑤0𝑡}∞𝑛=1我们将上面的𝑎𝑛和𝑏𝑛的计算式代入，可以发现：𝑐𝑛=1𝑇∫𝑓(𝑡)(𝑐𝑜𝑠𝑛𝑤0𝑡−𝑖𝑠𝑖𝑛𝑛𝑤0𝑡)𝑑𝑡=1𝑇∫𝑓(𝑡)𝑒−𝑖𝑛𝑤0𝑡𝑑𝑡𝑇2⁄−𝑇2⁄𝑇2⁄−𝑇2⁄𝑐−𝑛=1𝑇∫𝑓(𝑡)(𝑐𝑜𝑠𝑛𝑤0𝑡+𝑖𝑠𝑖𝑛𝑛𝑤0𝑡)𝑑𝑡=1𝑇∫𝑓(𝑡)𝑒𝑖𝑛𝑤0𝑡𝑑𝑡𝑇2⁄−𝑇2⁄𝑇2⁄−𝑇2⁄所以我们可以将级数中的累计范围变为-∞到∞，这样就可以将𝑐𝑛和𝑐−𝑛给统一起来，即：𝑓(𝑡)=∑𝑐𝑛𝑒𝑖𝑛𝑤0𝑡∞−∞其中𝑐𝑛=1𝑇∫𝑓(𝑡)𝑒−𝑖𝑛𝑤0𝑡𝑑𝑡𝑇2⁄−𝑇2⁄上式的𝑐𝑛就是我们在频域所需要的，它是关于频率w的函数，其函数值为频率w对应的幅值。这样，对于周期函数，我们可以通过上面的变换得到其在频域的函数。那马上有人会想到，如果我这个函数不是周期函数该怎么办呢？这就是下面所要说的傅里叶变换。对于没有周期的函数，我们可以认为其周期趋于无穷大，这样我们还是可以用上面的流程进行分析，只不过现在由于周期无穷大，级数里面的累加符号就变成积分形式：𝑓(𝑡)=12𝜋∫𝐹(𝑤)∞−∞𝑒𝑖𝑤𝑡𝑑𝐹(𝑤)=∫𝑓(𝑡)𝑒−𝑖𝑤𝑡∞−∞𝑑𝑡上面第二个式子就是经过傅里叶变换后频域里面的函数，它其实就是上面傅里叶级数里面的𝑐𝑛，而第一个式子就叫做傅里叶逆变换，即将频域里面的函数变换到时域中来。经傅里叶变换后频域函数，可想而知，它是一个连续函数，即每个频率都都对应有幅值。经过上面的傅里叶级数和傅里叶变换的学习，我们是不是万事大吉了呢？不是，因为做过现场实测的同学都知道，我们实际测得的数据其实是一个个离散数据，而上面介绍的其实是连续函数的变化，所以我们还得学习针对离散数据的离散傅里叶变换（DFT）。而在学习离散傅里叶变换之前，我们还得学习一下关于采样的知识以及离散时间傅里叶变换（DTFT）。假设现在有一个连续函数𝑥(𝑡)，现在我们用一个采用频率为𝑓𝑠的信号采集器去采集，那采集到的信号序列怎么表示呢？我们引入狄利克雷函数：𝛿(𝑥)={+∞,𝑥=00,𝑥≠0在采用中，基于狄利克雷函数，我们构造一个采样函数：𝛿𝑠(𝑡)=∑𝛿(𝑡−𝑛𝑇𝑠)∞−∞该函数只在𝑡=𝑛𝑇𝑠处的值为1，其他处均为0，即为周期𝑇𝑠的单位脉冲序列。故我们以频率𝑓𝑠采集得到得到数据可以表示为𝑥𝑠(𝑡)=∑𝑥(𝑡)𝛿(𝑡−𝑛𝑇𝑠)∞−∞对于无限长离散数据，我们可以看成是周期是无穷大，进行傅里叶变换：𝑋𝑠(𝑤)=∫(∑𝑥(𝑡)𝛿(𝑡−𝑛𝑇𝑠)∞−∞)𝑒−𝑖𝑤𝑡∞−∞𝑑𝑡=∑∫𝛿(𝑡−𝑛𝑇𝑠)(𝑥(𝑡)𝑒−𝑖𝑤𝑡)∞−∞∞−∞𝑑𝑡=∑𝑥(𝑛𝑇𝑠)𝑒−𝑖𝑤𝑛𝑇𝑠∞−∞=∑𝑥[𝑛]𝑒−𝑖𝑤𝑛𝑇𝑠∞−∞上式中，𝑥[𝑛]代表我们采集的第n个数据，采样时间为𝑡=𝑛𝑇𝑠。上面进行的变换称为离散时间傅里叶变换（DTFT），即将一个无限长的离散信号进行了傅里叶变换。其在频域内的图像是一个连续图像。但对于我们实际情况中，我们往往只能采集有限个数据，比如N个，那么该如何进行傅里叶变换呢？也就是要用到我们的离散傅里叶变换（DFT），即对于连续信号𝑥(𝑡)，按照采样时间𝑇𝑠进行采样N次𝛿(𝑡−𝑛𝑇𝑠)，并将这N个数据进行周期延拓，即认为采样的时间𝑁𝑇𝑠为一个周期，这样可以得到周期的离散信号，在一个周期内，其表达式为：𝑥𝑠(𝑡)=𝑥(𝑡)∑𝛿(𝑡−𝑛𝑇𝑠)𝑁−10运用离散时间傅里叶变换所得的结果，此时只需将累加区间改为[0,N]，然后将w改为𝑘2𝜋𝑁𝑇𝑠，即可得到离散傅里叶变换的表达形式：𝑋[𝑘]=∑𝑥[𝑛]𝑒−𝑖2𝜋𝑁𝑛𝑘𝑁−1𝑛=0,0≤𝑘≤𝑁−1或者写成：𝑋[𝑘]=∑𝑥[𝑛]𝑊𝑁𝑘𝑛𝑁−1𝑛=0,0≤𝑘≤𝑁−1其中：𝑊𝑁=𝑒−𝑖2𝜋𝑁其逆变换的表达形式如下：𝑋[𝑛]=1𝑁∑𝑥[𝑘]𝑒𝑖2𝜋𝑁𝑛𝑘𝑁−1𝑛=0,0≤𝑘≤𝑁−1或者写成：𝑥[𝑛]=1𝑁∑𝑋[𝑘]𝑊𝑁−𝑘𝑛𝑁−1𝑛=0,0≤𝑛≤𝑁−1可以看出，有限个离散数据进行傅里叶变换之后的频域中的频率也是离散的，对第k个数据，其对应的角频率为2𝜋𝑘𝑁𝑇𝑠，总之，通过离散傅里叶变换（DFT），可以将周期信号的有限长离散序列的转换到频域的离散系列，而不是频域的连续序列。我们可以将上面的离散傅里叶变换展开成方程组：𝑋(0)=𝑥(0)+𝑥(1)𝑊𝑁0·1+⋯+𝑥(𝑁−1)𝑊𝑁0·(𝑁−1)𝑋(1)=𝑥(0)𝑊𝑁1·0+𝑥(1)𝑊𝑁1·1+⋯+𝑥(𝑁−1)𝑊𝑁1·(𝑁−1)𝑋(2)=𝑥(0)𝑊𝑁2·0+𝑥(1)𝑊𝑁2·1+⋯+𝑥(𝑁−1)𝑊𝑁2·(𝑁−1)……𝑋(𝑁−1)=𝑥(0)𝑊𝑁(𝑁−1)·0+𝑥(1)𝑊𝑁(𝑁−1)·1+⋯+𝑥(𝑁−1)𝑊𝑁(𝑁−1)·(𝑁−1)写成矩阵形式：[𝑋(0)𝑋(1)…𝑋(𝑁−1)]=[𝑊𝑁0·0𝑊𝑁1·0…𝑊𝑁(𝑁−1)·0𝑊𝑁0·1𝑊𝑁1·1…𝑊𝑁(𝑁−1)·1…………𝑊𝑁0·(𝑁−1)𝑊𝑁1·(𝑁−1)…𝑊𝑁(𝑁−1)·(𝑁−1)][𝑥(0)𝑥(1)…𝑥(𝑁−1)]即：𝑿=𝑾𝒙由于离散傅里叶变换的计算量太大，就算对于计算来说也很吃力，所以基于上式中𝑾一些特性，开发出了计算量更少的快速傅里叶变换（FFT）。