设信号的数据长度为L，其N点DFT定义为信号的DTFT在奈奎斯特区间
上N个等间距的频率点处的频谱密度值，即信号的N点DFT结果是N个频谱密度值。
在奈奎斯特区间上均匀分布的N个DFT频率为
根据DFT的定义，将这些频率值代入DTFT的频谱公式中，得
在算法上，DFT计算式的一种最简单的实现是：套用前一节所讲的任意区间上的DTFT计算方法，将区间的起点和终点分别给定为0和
即可，如下面的程序实现。
#include <comlx.h>
void dtftr();
void dft (int L, double * x, int N, complex * X)
{
double pi=4*atan(1.0);
for(k=0;k<N;k++)
dtftr(L, x , N , X , 0.0 , 2*pi);
}
3.5.2
显然，DFT是DTFT的一种特殊均匀抽样方式：（为什么说它特殊呢？）它的频段范围是整个奈奎斯特区间，因此，要考察的频率点的位置仅与DFT要求的点数N有关（因为抽取范围是固定的啊）。对所有的N点DFT来讲，它们所涉及的频率点位置都是一样的，即
因此，通常我们可以将N点DFT直接写作
若令 
，则上式可以简记为
其中， 
与DFT的点数N有关，称为DFT的旋转因子。这可以看作是DFT的另一种更直接的定义式。
从数学上看，序列的N点DFT可以看作是一个线性矩阵变换，即将L维的时域向量变成N维的频域向量的一种线性变换。即：
其中， 
。
因此，我们可以用下面的矩阵形式来定义DFT
或
其中，矩阵元素为
3.5.3
从理论上讲，DFT变换中的N与L相互之间是可以独立确定的。L是数据记录中时域样本的数目，它可能是无限的；而N则是对DTFT进行抽样的频率的数目。
通常在讨论DFT时，一般都假定L＝N。既然L与N没有什么必然的联系，那为什么要假定它们相等呢？下面我们从“L<N”和“L>N”两个方面来分析这样假定的原因，或者说这样假定的好处。
（1）当L＜N时
这时，数据长度小于DFT的点数，我们添加N-L个零到数据尾部，使序列长度等于N。令人高兴的是：在序列尾部补任意数目的零，新序列与旧序列的DFT结果是一样的。
证明如下：
设原序列为
现在，我们添加D个零到序列尾部，得到长为L+D的数据，即：
它也可以写成
3.5.4
根据DFT正变换的矩阵公式，我们定义IDFT为
即
现在的问题是：如何求逆矩阵的各元素呢？
容易证明DFT的变换阵满足下面的关系：
所以
于是
这样，IDFT可以写作
或写作
这是IDFT的第一种实现方法。
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 算法理论与分析 』 → 离散傅里叶变换DFT
(订阅本版)
2006/8/25 10:03:00
新浪微博
离散傅里叶变换DFT