第四节 基--2按频率抽取的FFT算法Decimation-in-Frequency(DIF) (Sander-Tukey)

Slides:



Advertisements
Similar presentations
一、 一阶线性微分方程及其解法 二、 一阶线性微分方程的简单应用 三、 小结及作业 §6.2 一阶线性微分方程.
Advertisements

第五节 函数的微分 一、微分的定义 二、微分的几何意义 三、基本初等函数的微分公式与微分运算 法则 四、微分形式不变性 五、微分在近似计算中的应用 六、小结.
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
第八章 第四节 机动 目录 上页 下页 返回 结束 一个方程所确定的隐函数 及其导数 隐函数的微分法.
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
信号与系统 第三章 傅里叶变换 东北大学 2017/2/27.
第3章 离散傅立叶变换 DFS DFS的性质 DFT DFT的性质 圆周卷积 利用DFT计算线性卷积 频率域抽样.
圆的一般方程 (x-a)2 +(y-b)2=r2 x2+y2+Dx+Ey+F=0 Ax2+Bxy+Cy2+Dx+Ey+ F=0.
6.9二元一次方程组的解法(2) 加减消元法 上虹中学 陶家骏.
第四章 快速付里叶变换(FFT) Fast Fourier Transforming
讲座: 快速离散傅立叶变换 本讲的教学内容 改进DFT计算的方法 按时间抽取的FFT算法(DIT FFT)
第2章 时域离散信号和系统的频域分析 教学内容包括: 序列的傅立叶变换定义及性质 Z变换的定义与收敛域 利用z变换分析信号和系统的频域特性.
第一章 绪论.
第四节 对数留数与辐角原理 一、对数留数 二、辐角原理 三、路西定理 四、小结与思考.
一、原函数与不定积分 二、不定积分的几何意义 三、基本积分公式及积分法则 四、牛顿—莱布尼兹公式 五、小结
第四章 函数的积分学 第六节 微积分的基本公式 一、变上限定积分 二、微积分的基本公式.
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
第二章 导数与微分 第二节 函数的微分法 一、导数的四则运算 二、复合函数的微分法.
2-7、函数的微分 教学要求 教学要点.
第7章 离散信号的频域分析 离散Fourier级数 离散Fourier变换 第3章 连续信号的频域分析 连续Fourier级数
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
实验二 FFT与DFT计算时间的比较及圆周卷积代替线性卷积的有效性实验
第三章 DFT 离散傅里叶变换.
第2章 Z变换 Z变换的定义与收敛域 Z反变换 系统的稳定性和H(z) 系统函数.
Fast Fourier Transforms
第二章 离散傅里叶变换 及其快速算法(8学时 )
走进编程 程序的顺序结构(二).
元素替换法 ——行列式按行(列)展开(推论)
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
Biomedical signal processing
Chapter 3 Discrete Fourier-Transform (Part Ⅰ)
第七讲 快速傅里叶变换 (FFT) Q&A 办公室: 手 机:
引言 1.DFT是信号分析与处理中的一种重要变换。 年,Cooley, Tukey《机器计算傅里叶级数的一种算法》
第三章 付里叶分析 离散付氏级数的数学解释(The Mathematical Explanation of DFS)
第一章 函数与极限.
第三章学习目标 1.理解傅里叶变换的几种形式 2.理解离散傅里叶变换及性质,掌握圆周移位、共轭对称性,掌握圆周卷积、线性卷积及两者之间的关系
2.1.
第四章习题.
实数与向量的积.
线段的有关计算.
Three stability circuits analysis with TINA-TI
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
5.2 常用统计分布 一、常见分布 二、概率分布的分位数 三、小结.
信号处理原理 F F T 实 验 张哲 沈阳广播电视大学.
实验三 16位算术逻辑运算实验 不带进位控制的算术运算 置AR=1: 设置开关CN 1 不带进位 0 带进位运算;
2019/5/4 实验三 离散傅立叶变换的性质及应用 06:11:49.
第4章 快速傅立叶变换 问题的提出 解决问题的思路与方法 基2时间抽取FFT算法 基2时间抽取FFT算法的计算复杂度
复习: 若A(x1,y1,z1) , B(x2,y2,z2), 则 AB = OB - OA=(x2-x1 , y2-y1 , z2-z1)
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
3.1 变化率与导数   3.1.1 变化率问题 3.1.2 导数的概念.
3.1.2 空间向量的数量积运算 1.了解空间向量夹角的概念及表示方法. 2.掌握空间向量数量积的计算方法及应用.
2019/5/11 实验四 FIR滤波器的特性及应用 05:31:12.
2019/5/11 实验三 线性相位FIR滤波器的特性 05:31:30.
第三章 函数的微分学 第二节 导数的四则运算法则 一、导数的四则运算 二、偏导数的求法.
4) 若A可逆,则 也可逆, 证明: 所以.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
学习任务三 偏导数 结合一元函数的导数学习二元函数的偏导数是非常有用的. 要求了解二元函数的偏导数的定义, 掌握二元函数偏导数的计算.
第三章 DFT 离散傅里叶变换.
2.2矩阵的代数运算.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
2019/5/21 实验一 离散傅立叶变换的性质及应用 实验报告上传到“作业提交”。 11:21:44.
§7.3 离散时间系统的数学 模型—差分方程 线性时不变离散系统 由微分方程导出差分方程 由系统框图写差分方程 差分方程的特点.
欢迎大家来到我们的课堂 §3.1.1两角差的余弦公式 广州市西关外国语学校 高一(5)班 教师:王琦.
第8章 FFT设计 8.1 FFT的原理 8.2 FFT与蝶形运算 8.3 使用DSP Builder设计FFT
定义5 把矩阵 A 的行换成同序数的列得到的矩阵,
第四章 快速傅里叶变换 §4-1 引言 频域分析:一种有效的工具 DFT: △ 问题:.
第四章 函数的 积分学 第七节 定积分的换元积分法     与分部积分法 一、定积分的换元积分法 二、定积分的分部积分法.
第三节 数量积 向量积 混合积 一、向量的数量积 二、向量的向量积 三、向量的混合积 四、小结 思考题.
第二次课后作业答案 函数式编程和逻辑式编程
Presentation transcript:

第四节 基--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)变址单元:根据输入数据,进行码位倒置排序。