现在的位置: 首页 > 综合 > 正文

离散傅里叶变换及其快速算法 (转载)

2012年05月16日 ⁄ 综合 ⁄ 共 1948字 ⁄ 字号 评论关闭

 

离散傅里叶变换及其快速算法
2007-08-20 20:14
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) 当 次迭代全部完成后,对结果 按下标二进制位进行整序,从而得到结果

抱歉!评论已关闭.