离散傅里叶变换 离散傅里叶变换（-- ，缩写为-- ），是傅里叶变换在时域和频域上都呈离散的形式，将信号的时域采样变换为其DTFT的频域采样。 在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作其周期延拓的变换。在实际应用中通常采用快速傅里叶变换计算DFT。 定义. 对于formula_1点序列formula_2，它的离散傅里叶变换（DFT）为 formula_3 其中formula_4是自然对数的底数，formula_5是虚数单位。通常以符号formula_6表示这一变换，即 formula_7 离散傅里叶变换的逆变换（IDFT）为： formula_8 可以记为： formula_9 实际上，DFT和IDFT变换式中和式前面的归一化系数并不重要。在上面的定义中，DFT和IDFT前的系数分别为formula_10和formula_11。有时会将这两个系数都改成formula_12。 从连续到离散. 连续时间信号formula_13以及对应的连续傅里叶变换formula_14都是连续函数。由于数位系统只能处理有限长的离散信号，因此必须将formula_15和formula_16都离散化，并且建立对应的傅里叶变换。 假设formula_13时限于formula_18，再通过时域采样将formula_13离散化，就可以得到有限长离散信号，记为formula_20。设采样周期为formula_21，则时域采样点数formula_22。 formula_23 它的傅里叶变换为 formula_24 这就是formula_13在时域采样后的连续傅里叶变换，也就是离散时间傅里叶变换，它在频域依然是连续的。 下面将频域信号转化为有限长离散信号。与对时域信号的处理类似，假设频域信号是带限的，再经过离散化，即可得到有限长离散信号。依据采样定理，频域采样若要能完全重建原信号，频域信号formula_14应当带限于formula_27。由于时域信号时限于formula_18，由采样定理以及时频对偶的关系，频域的采样间隔应为formula_29。故，频域采样点数为： formula_30 即频域采样的点数和时域采样同为formula_1，频域采样点为formula_32。 而DTFT在频域上采样： formula_33 令formula_34，将其归一化，就得到前面定义的离散傅里叶变换。因此，DFT就是先将信号在时域离散化，求其连续傅里叶变换后，再在频域离散化的结果。 DFT与CFT. 下面考察离散傅里叶变换与连续傅里叶变换（CFT，Continuous Fourier Transform）的关系。连续傅里叶变换 formula_35 的采样为： formula_36 将这个积分以黎曼和的形式近似，有： formula_37 这一结论指出离散傅里叶变换确实是连续傅里叶变换在某种意义上的近似。不过必须注意以下两点： 为此，通常对连续信号的时域采样再做一次加窗处理（Windowing），这样就得到带限的有限长离散信号。 DFT与DTFT. 离散时间傅里叶变换（DTFT）是在时域上对连续傅里叶变换的采样。DFT则是在频域上对DTFT的均匀采样。离散信号formula_38（n=0...,N-1）的DTFT为： formula_39 对formula_40在离散的频点formula_41上采样 formula_42 即为formula_15的DFT。由于DTFT在频域是周期的，所以在DTFT频域上的均匀采样也应是周期的。formula_44实际上是这个周期序列的主值序列。 栅栏效应. formula_1点序列的DFT只能在有限的formula_1个频点上观察频谱，这相当于从栅栏的缝隙中观察景色，对于了解信号在整个频域上的特性是不够的。为了观察到其他频率的信息，需要对原信号formula_38做一些处理，以便在不同的频点上采样。 将原来在DTFT频域上的采样点数增加到formula_48点，这样采样点位置变为formula_49。则对应的DFT成为 formula_50 若在序列formula_38之后补上M-N个零，设为formula_52，则上式变为 formula_53 因此将formula_38补零再做DFT就可以得到formula_38的DTFT在其他频率上的值，相当于移动了栅栏，因而能够从其他位置进行观察。 频谱分辨率. formula_1点DFT的频谱分辨率是formula_57。栅栏效应一节指出可以通过补零观察到更多的频点，但是这并不意味着补零能够提高真正的频谱分辨率。这是因为formula_38实际上是formula_13采样的主值序列，而将formula_38补零得到的formula_52周期延拓之后与原来的序列并不相同，也不是formula_13的采样。因此formula_63与formula_16是不同离散信号的频谱。对于补零至formula_48点的formula_66的DFT，只能说它的分辨率formula_67仅具有计算上的意义，formula_63并不是真正的、物理意义上的频谱。频谱分辨率的提高只能在满足采样定理的条件下增加时域采样长度来实现。 从空间的角度分析. 周期为N的离散信号构成一个"N"维欧几里得空间formula_69。在这一空间上两个信号"x"和"y"的内积定义为 formula_70 下面给出formula_69上的一组正交基： formula_72 将信号"x"在这组正交基上分解，得 formula_73 令 formula_74 此即为离散傅里叶变换。又 formula_75 则有 formula_76 此即为离散傅里叶变换的逆变换。 由此可知，在正交分解的角度上说，离散周期信号formula_15的离散傅里叶变换formula_16实质上是formula_15在正交基formula_80上的分量。而从线性变换的角度上说，formula_80是圆周卷积的特征向量，formula_16则是对应的特征值。 DFT与圆周卷积. 根据卷积定理，离散信号x与y的圆周卷积对偶于频域上x与y离散傅里叶变换的乘积。下面揭示DFT与圆周卷积的内在关系。 对长为N的离散信号formula_83与formula_84，如果要计算它们的卷积，就必须定义formula_85与formula_86在"0≤n deg("a"("x")) + deg("b"("x"))。然后作圆周卷积： formula_117 其中c就是"c"("x")系数的向量。由于圆周卷积的DFT是乘积，有： formula_118 则 formula_119 利用快速傅里叶变换，这一算法的运算复杂度为formula_120。 OFDM. OFDM（正交频分复用）在宽带无线通信中有重要的应用。这种技术将带宽分为"N"个等间隔的子载波，可以证明这些子载波相互正交。尤其重要的是，OFDM调制可以由IDFT实现，而解调可以由DFT实现。OFDM还利用DFT的移位性质，在每个帧头部加上循环前缀（Cyclic Prefix），使得只要信道延时小于循环前缀的长度，就能消除信道延时对传输的影响。 特殊例子. 数论转换. 数论转换是离散傅利叶转换(DFT)的一个特例 formula_121，此运算是根据模运算 而取得的，formula_122需要是质数 ，如此可以建构出有限域，并且存在 formula_123 个可以整除 formula_124 的实数根。如此可以得到formula_125，formula_126 为正整数。令 formula_127 为第 formula_124 个单位根，则第 formula_123 个单位根 formula_130 可以表示成 formula_131 。另外，再令formula_1 为 formula_130 次方 formula_122 模运算之循环个数。 则数论矩阵为 formula_135 formula_136 与 formula_137 各为 Column 与 Row 的指数(index), 令 formula_138 与 formula_139 各代表Column 与 Row 的总数，则formula_140， formula_141. 举个例子来说，当 formula_142 则 formula_143 formula_144 formula_145 formula_146 因为 formula_147 经 formula_148 的模运算为 formula_149 ，因此可以判定此情况为 formula_150 个次方一循环，所以 formula_151，formula_1可以整除 formula_124。则数论矩阵可以表示成 formula_154 在一些特殊的情况下，令 formula_155 ，而 formula_100 不是值数也是有意义的。像是 Fermat Number Transform 中formula_157，以及 Mersenne Number Transform 中 formula_158.