1 离散傅里叶变换(DFT)的推导
时域抽样：
目的：解决信号的离散化问题。
效果：连续信号离散化使得信号的频谱被周期延拓。
时域截断：
原因：工程上无法处理时间无限信号。
方法：通过窗函数(一般用矩形窗)对信号进行逐段截取。
结果：时域乘以矩形脉冲信号，频域相当于和抽样函数卷积。
时域周期延拓：
目的：要使频率离散，就要使时域变成周期信号。
方法：周期延拓中的搬移通过与 的卷积来实现。
表示：延拓后的波形在数学上可表示为原始波形与冲激串序列的卷积。
结果：周期延拓后的周期函数具有离散谱。
经抽样、截断和延拓后，信号时域和频域都是离散、周期的。过程见图1。
处理后信号的连续时间傅里叶变换：
是离散函数，仅在离散频率点 处存在冲激，强度为 ，其余各点为0。
是周期函数，周期为 ，每个周期内有 个不同的幅值。
时域的离散时间间隔(或周期)与频域的周期(或离散间隔)互为倒数。
2 DFT及IDFT的定义
DFT定义：设 是连续函数 的 个抽样值 ，这N个点的宽度为N的DFT为：
IDFT定义：设 是连续频率函数 的 个抽样值 ， 这N个点的宽度为N的IDFT为：
称为N点DFT的变换核函数， 称为N点IDFT的变换核函数。它们互为共轭。
同样的信号，宽度不同的DFT会有不同的结果。DFT正逆变换的对应关系是唯一的，或者说它们是互逆的。
引入
用途：
正逆变换的核函数分别可以表示为 和 。
核函数的正交性可以表示为：
DFT可以表示为：
IDFT可以表示为：
性质：周期性和对称性：
3 离散谱的性质
离散谱定义：称 为离散序列 的DFT离散谱，简称离散谱。
性质：
周期性：序列的N点的DFT离散谱是周期为N的序列。
共扼对称性：如果 为实序列，则其N点的DFT关于原点和N/2都具有共轭对称性。即 ； ；
幅度对称性：如果 为实序列，则其N点的DFT关于原点和N/2都具有幅度对称性。即 ； ；
改写：
简记 为
简记 为
DFT对简记为： 或
4 DFT总结
DFT的定义是针对任意的离散序列 中的有限个离散抽样 的，它并不要求该序列具有周期性。
由DFT求出的离散谱 是离散的周期函数，周期为 、离散间隔为 。离散谱关于变元k的周期为N。
如果称离散谱经过IDFT所得到的序列为重建信号， ，则重建信号是离散的周期函数，周期为 (对应离散谱的离散间隔的倒数)、离散间隔为 (对应离散谱周期的倒数)。
经IDFT重建信号的基频就是频域的离散间隔，或时域周期的倒数，为 。
实序列的离散谱关于原点和 (如果N是偶数)是共轭对称和幅度对称的。因此，真正有用的频谱信息可以从0~ 范围获得，从低频到高频。
在时域和频域 范围内的N点分别是各自的主值区间或主值周期。
5 DFT性质
线性性：对任意常数 ( )，有
奇偶虚实性：
DFT的反褶、平移：先把有限长序列周期延拓，再作相应反褶或平移，最后取主值区间的序列作为最终结果。
DFT有如下的奇偶虚实特性：
奇 奇；偶 偶；实偶 实偶；实奇 虚奇；
实 (实偶) + j(实奇)；实 (实偶)·EXP(实奇)。
反褶和共轭性：
时域
频域
反褶
反褶
共轭
共轭＋反褶
共轭＋反褶
共轭
对偶性：
把离散谱序列当成时域序列进行DFT，结果是原时域序列反褶的N倍；
如果原序列具有偶对称性，则DFT结果是原时域序列的N倍。
时移性： 。序列的时移不影响DFT离散谱的幅度。
频移性：
时域离散圆卷积定理：
圆卷积：周期均为N的序列 与 之间的圆卷积为
仍是n的序列，周期为N。
非周期序列之间只可能存在线卷积，不存在圆卷积；周期序列之间存在圆卷积，但不存在线卷积。
频域离散圆卷积定理：
时域离散圆相关定理：
周期为N的序列 和 的圆相关：
是n的序列，周期为N。
。其中 表示按k进行DFT运算。
帕斯瓦尔定理：
6 快速傅里叶变换FFT
(1) FFT不是一种新的变换，而是DFT的快速算法。
(2) 直接DFT计算的复杂度：
计算DFT需要： 次复数乘法； 次复数加法。
(3) FFT算法推导：
(i) 第L次迭代中对偶结点值的计算公式为：
， 是循环控制变量。
整序：经过r次迭代后，得到结果 ，实际结果应是 ，所以流程的最后一步是按下标的正常二进制顺序对结果进行整序。
(4) FFT算法特点：( )
(i) 共需 次迭代；
(ii) 第 次迭代对偶结点的偶距为 ，因此一组结点覆盖的序号个数是 。
(iii) 第 次迭代结点的组数为 。
(iv) 可以预先计算好，而且 的变化范围是 。
(5) FFT算法流程：( )
(i) 初始化： ；
(ii) 第 次迭代：
(a) 下标控制变量初始化 ；
(b) “结点对”的个数初始化 ;
(c)
Ø 按对偶结点对的计算公式进行置位运算，得到 和 的值；
Ø ； ；
Ø 跳过已经计算过的结点(即上面 所对应的那些结点)： ；
Ø 如果 ，转到b)继续计算下一组结点；否则结束本次迭代。
(iii) 当 次迭代全部完成后，对结果 按下标二进制位进行整序，从而得到结果 。
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 算法理论与分析 』 → 离散傅里叶变换及其快速算法
(订阅本版)
2006/8/25 10:00:00
顶端 
离散傅里叶变换及其快速算法(4198字) － 卷积内核，2006年8月25日
新浪微博
