第四节 基--2按频率抽取的FFT算法Decimation-in-Frequency(DIF) (Sander-Tukey)
一、算法原理 设输入序列长度为N=2M(M为正整数,将该序列的频域的输出序列X(k)(也是M点序列,按其频域顺序的奇偶分解为越来越短的子序列,称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。
二、算法步骤 1.分组 DFT变换: 已证明频域上X(k)按k的奇偶分为两组,在时域上x(n)按n的顺序分前后两部分,现将输入x(n)按n的顺序分前后两部分: 前半子序列x(n),0≤n≤N/2-1; 后半子序列x(n+N/2),0≤n≤N/2-1; 例:N=8时,前半序列为:x(0),x(1),x(2),x(3); 后半序列为: x(4),x(5),x(6),x(7); 则由定义输出(求DFT)
2.代入DFT中
3. 变量置换--1
3. 变量置换--2
3. 变量置换--3
3. 变量置换--4
4.结论1 一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照:
4.结论2
三、蝶形流图表示 蝶形单元:时域中,前后半部表示式用蝶形结表示。 x(n) x(n+N/2) 与时间抽取法的推演过程一样,由于N=2L,N/2仍为偶数,所以可以将N/2点DFT的输出X(k)再分为偶数组和奇数组,这样就将一个N/2点的DFT分成两个N/4点DFT的输入,也是将N/2点的DFT的输入上、下对半分后通过蝶形运算而形成,直至最后为2点DFT。
例子:求 N=23=8点DIF (1)先按N=8-->N/2=4,做4点的DIF: 先将N=8DFT分解成2个4点DFT: 可知:时域上:x(0),x(1),x(2),x(3)为偶子序列 x(4),x(5),x(6),x(7)为奇子序列 频域上:X(0),X(2),X(4),X(6)由x1(n)给出 X(1),X(3),X(5),X(7),由x2(n)给出
将N=8点分解成2个4点的DIF的信号流图 前半部分序列 X1(k) x1(n) x(0) x(1) x(2) x(3) 4点 DFT 后半部分序列 x(4) x(5) x(6) x(7) 4点 DFT X(1) X(3) X(5) X(7)
(2)N/2(4点)-->N/4(2点)FFT (a)先将4点分解成2点的DIF:
(b)一个2点的DIF蝶形流图 X(0) X(4) X(2) X(6) x3(0) x1(0) 2点DFT x1(1) x3(1)
(c)另一个2点的DIF蝶形流图 X(1) X(5) X(3) X(7) x5(0) x2(0) 2点DFT x2(1) x5(1)
(3)将N/4(2点)DFT再分解成2个1点的DFT (a)求2个一点的DFT 最后剩下两点DFT,它可分解成两个一点DFT,但一点DFT就等于输入信号本身,所以两点DFT可用一个蝶形结表示。取x3(0)、x3(1)为例。
(b)2个1点的DFT蝶形流图 X(0) 1点DFT x3(0) X(4) x3(1) 1点DFT 进一步简化为蝶形流图: X(0)
(4)一个完整N=8的按频率抽取FFT的运算流图 m=2 m=1 X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7) m=0 x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)
(5)DIF的特点 (a)输入自然顺序,输出乱序且满足码位倒置规则。 (b)根据时域、频域互换,可知: 输入乱序,输出自然顺序。
(6)DIF与DIT比较1 相同之处: (1)DIF与DIT两种算法均为原位运算。 (2)DIF与DIT运算量相同。 它们都需要
(6)DIF与DIT比较2 不同之处: (1)DIF与DIT两种算法结构倒过来。 DIT为输入乱序,输出顺序。先运行“二进制倒读”程序,再进行求DFT。 (2)DIF与DIT根本区别:在于蝶形结不同。 DIT的复数相乘出现在减法之前。 DIF的复数相乘出现在减法之后。
作业 试画出N=16点的基-2按频率抽取的FFT流图(DIF)。
第五节IFFT运算方法 以上所讨论的FFT的运算方法同样可用于IDFT的运算,简称为IFFT。即快速付里叶反变换。从IDFT的定义出发,可以导出下列二种利用FFT来计算FFT的方法。
一、利用FFT计算IFFT的思路1 将下列两式进行比较
二、利用FFT计算IFFT的思路2 利用FFT计算IFFT时在命名上应注意: (1)把FFT的时间抽取法,用于IDFT运算时,由于输入变量由时间序列x(n)改成频率序列X(k),原来按x(n)的奇、偶次序分组的时间抽取法FFT,现在就变成了按X(k)的奇偶次序抽取了。 (2)同样,频率抽取的FFT运算用于IDFT运算时,也应改变为时间抽取的IFFT。
三、改变FFT流图系数的方法 1.思路 在IFFT的运算中,常常把1/N分解为(1/2)m,并且在M级运算中每一级运算都分别乘以1/2因子,就可得到IFFT的两种基本蝶形运算结构。(并不常用此方法)
2.IFFT的基本蝶形运算 A A B B (b)时间抽取IFFT的蝶形运算 (a)频率抽取IFFT的蝶形运算
四.直接利用FFT流图的方法 1.思路 前面的两种IFFT算法,排程序很方便,但要改变FFT的程序和参数才能实现。
2.直接利用FFT流图方法的推导 此为DFT可用FFT程序 可知:只须将频域成份一个求共轭变换,即(1)将X(k)的虚部乘以-1,即先取X(k)的共轭,得X*(k)。(2)将X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再对运算结果取一次共轭变换,并乘以常数1/N,即可以求出IFFT变换的x(n)的值。
3.直接利用FFT流图方法的注意点 (1)FFT与IFFT连接应用时,注意输入输出序列的排列顺序,即应注意是自然顺序还是倒序。 (2)FFT和IFFT共用同一个程序时,也应注意利用FFT算法输入输出的排列顺序,即应注意自然顺序还是例位序 (3)当把频率抽取FFT流图用于IDFT时,应改称时间抽取IFFT流图。 (4)当把时间抽取FFT流图用于IDFT时,应改称频率抽取IFFT流图。
作业 用C语言完成N=128点的DIT,DIF及IDIT,IDIF。
第六节 线性调频Z变换
一、引入 以上提出FFT算法,可以很快地求出全部DFT值。即求出有限长序列x(n)的z变换X(z)在单位园上N个等间隔抽样点zk处的抽样值。它要求N为高度复合数。即N可以分解成一些因子的乘积。例N=2L 实际上:(1)也许对其它围线上z变换取样发生兴趣。如语音处理中,常常需要知道某一围线z变换的极点所处的复频率。 (2)只需要计算单位圆上某一段的频谱。如窄带信号,希望在窄带频率内频率抽样能够非常密集,提高分辨率,带外则不考虑。 (3)若N是大素数时,不能加以分解,又如何有效计算这种序列DFT。例N=311,若用基2则须补N=28=512点,要补211个零点。
二、问题提出 由上面三个问题提出: 为了提高DFT的灵活性,须用新的方法。 线性调频z变换(CZT)就是适用这种更为一般情况下,由x(n)求X(zk)的快速变换 CZT:来自于雷达专业的专用词汇。
三、算法原理 1.定义 Z 变 换 采 用 螺 线 抽 样, 可 适 用 于 更 一 般 情 况 下 由 x(n) 求X(zk) 的 快 速 算 法, 这 种 变 换 称 为 线 性 调 频 Z 变 换 ( 简 称 CZT ).
2.CZT公式推导1 已 知 x(n) ,0≤n≤N-1,则它的z变换是: 为适应z可以沿平面内更一般的路径取值,故: 沿z平面上的一段螺线作等分角的抽样,则z的取样点Zk可表示为: 其中M:表示欲分析的复频谱的点数。M不一定等于N。A, 都为任意复数。
2.CZT公式推导2
2.CZT公式推导3
3.用CZT求解DFT的流图
4.CZT变换各点的值
5、图形
6、说明1 (1)A为起始样点位置
6、说明2 (2)zk是z平面一段螺线上的等分角上某一采样点。
6、说明3
6、说明4
6、说明5
7、CZT的实现步骤1
7、CZT的实现步骤2
7、CZT的实现步骤3
7、CZT的实现步骤4
7、CZT的实现步骤5
7、CZT的实现步骤6
7、CZT的实现步骤7
8、CZT变换运算流程图
9、CZT运算量的估算1
9、CZT运算量的估算2
10、CZT运算量与直接运算量比较 当M、N足够小时,直接算法运算量少。 但M、N值比较大时(大于50),CZT算法比直接算法的运算量少得多。 例M=50,N=50,N*M=2500次 而CZT<1600次。
11、CZT算法的特点 与标准FFT算法相比,CZT算法有以下特点: (1)输入序列长N及输出序列长M不需要相等。 (3)Zk的角间隔 是任意的,其频率分辨率也是任意的。 (4)周线不必是z平面上的圆,在语音分析中螺旋周线具有某些优点。 (5)起始点z0可任意选定,因此可以从任意频率上开始对输入数据进行窄带高分辨率的分析。 (6)若A=1,M=N,可用CZT来计算DFT,即使N为素数时,也可以。 总之,CZT算法具有很大的灵活性,在某种意义上说,它是一个一般化的DFT。
12、CZT变换的应用1 (1)利用CZT变换计算DFT。
12、CZT变换的应用2 (2)对信号的频谱进行细化分析。其中对窄带信号频谱或对部分感兴趣的频谱进行细化分析。
12、CZT变换的应用3 (3)求解z变换X(z)的零、极点。 用于语音信号处理过程中。 具体方法:利用不同半径同心圆,进行等间隔的采样。
作业
第七节FFT的应用 凡是利用付里叶变换来进行分析、综合、变换…的地方,都可以利用FFT算法来减少其计算量。 FFT主要应用在 (1)快速卷积 (2)快速相关 (3)频谱分析
一、快速卷积 设x(n)的长度为N点,h(n)的长度为M点,则: y(n)的长度为N+M-1点。所以直接计算y(n)线性卷积运算量为NM。
1.利用圆周卷积代替线卷积 用圆周卷积(FFT)代替线卷积的必要条件:x(n)、h(n)补零加长至L=N+M-1. 然后计算圆卷积。求出y(n)代表线卷积。
2、用FFT计算y(n)的步骤 (1)求H(k)=DFT[h(n)] (L点) (2)求X(k)=DFT[x(n)] (L点) (3)计算Y(k)=X(k)H(k) (L点) (4)求y(n)=IDFT[Y(k)] (L点)
2、用FFT计算y(n)与直接计算y(n)的运算量比较
3、分段卷积的方法 (1)重叠相加法 (2)重叠保留法 设x(n)的长度为长序列N,h(n)为短序列列M。
(1)重叠相加法1 (1)x(n)为分段,每段长为p点,p选择与M数量组相同。用xi(n)表示x(n)的第i段.
(1)重叠相加法2
(1)重叠相加法例子
(2)重叠保留法1
(2)重叠保留法2
(2)重叠保留法例子
二、快速相关 1.方法
2.步骤
三、频谱分析 这里我们仅介绍FFT的仪器设备:快速付里叶分析仪。 其功能为: (1)能分析确定性信号的频谱。 (2)估计随机信号的功率谱 (3)并对信号进行快速卷积滤波 (4)计算相关函数
1.频谱分析仪的框图 数据选择器 数据存储器 运算器 数据选择器 A/D 输出缓冲器 控制器 保护滤波器 变址单元 函数发生器 D/A 输入电路 输出 输入
2.部件说明 (1)保护滤波器:对输入信号进行模拟滤波,滤掉噪声,提取感兴趣的有用信号,以便分析频谱。 (2)运算器:完成时间抽取FFT或Chirp-Z变换所要求运算。 (3)RAM:存储输入数据。 (4)ROM(函数发生器)。以表格形式存放蝶形运算因子W. (5)变址单元:根据输入数据,进行码位倒置排序。