DFT的计算量及对称性(图)
DFT 的计算量及对称性（图）
上一回说到，为了克服
DFT 存在的栅栏效应、
频谱泄漏和混叠失真等问题，
可以增加采样点数N
。但点数N
的增加又会带来DFT
计算量呈幂函数规律大幅度增加。即对于长度为N 有限长序列x （n ），完成其一个N 点DFT
（1）
需要进行的计算量为：
（2）
和
（3）
完成一个如下的逆变换运算量亦然：
（4）
假设一个点数N ＝1024的信号，则DFT 计算量仅复数乘法运算就高达104万次以上。现在工程技术实际中采样点数N 可达
（5）
那么仅复数乘法计算量就高达
（6）
简直是天文数字！如果有许多路信号序列的实时控制系统，
你让计算机怎么
来得及处理啊？可见我们必须千方百计减少DFT
的运算量！科学家们首先想到的就是利用DFT 的“对称性”。
一、复共轭序列的DFT
我们知道DFT 中的序列都可以表示为复数项级数，那么自然就有与之相对的复共轭序列。
设
是
的复共轭序列，长度也为N ，若
（7）
则复共轭序列的离散傅里叶变换为
（8）
且
（9）
证明：由DFT 的定义式（1）有
（10）
注意上式中使用了
（11
）
且因为
DFT 的概念是建立在周期序列的基础之上的，所以
X （
k ）隐含周期性，根据DFT 的定义式（1）便有
即DFT 的末点就是其起始点。证毕。 同理可证
二、共轭对称性的定义
根据序列的偶对称和奇对称性质，有限长共轭对称序列定义为
有限长共轭反对称序列定义为
由此推论出
（12）
（13）
（14）
（15）
（16）
（17
）
和
（18
）
（19）
注意：上述结论对频域序列X （k ）也成立。
此处的对称性指关于变换区间中点（N/2点）的对称性。因为x （n ）和X （k ）均是区间[0，N －1]上的有限长序列。
三、序列表示为共轭对称部分和共轭反对称部分时的DFT
因为任何有限长序列x （n ）都可以表示为其共轭对称部分和共轭反对称部分之和，即：
（20）
则
（21）
其中，X （k ）的实部对应于x （n ）的共轭对称部分的DFT ：
（22）
X （k ）的虚部（包括虚数单位j ）对应于x （n ）的共轭反对称部分的DFT ：
四、序列表示为实部和虚部时的
DFT
设
其中序列的实部为
序列的虚部（包括虚数单位j ）为
则
其中，X （k ）的共轭对称部分对应于x （n ）的实部的DFT ：
X （k ）的共轭反对称部分对应于x （n ）的虚部（含j ）的DFT ：
五、实序列的DFT 特殊地，如果有实序列：
（23）
（24）
（25）
（26）
（27）
（28）
（29）
（30
）
则其
DFT
（31）
此时不难由式（8）推论出
（32）
六、DFT 的共轭对称性的应用
利用共轭对称性，进行一次DFT 可以变换两个实序列。即构建一个新的序列：
（33）
利用上述理论和式（32）可减少一半计算量。
科学界正是从千方百计减少DFT 的计算量出发，创造出了快速傅里叶变换（FFT ），其中用途最广的一种FFT 算法公式，成为科学界历来最伟大的公式之一。详情且听周法哲下回分解。