




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
离散傅里叶变换的矩阵表示及其运算量第一页,共五十页,2022年,8月28日离散傅里叶变换对为:
(4.1) (4.2)式中
。
下面要用矩阵来表示DFT关系。
第二页,共五十页,2022年,8月28日
一般情况下,信号序列x(n)及其频谱序列X(k)都是用复数来表示的,WN当然也是复数。因此,计算DFT的一个值X(k)需要进行N次复数乘法(与1相乘也包括在内)和N-1次复数加法;所以,直接计算N点的DFT需要进行N2次复数乘法和N(N-1)复数加法。
第三页,共五十页,2022年,8月28日显然,直接计算N点的IDFT所需的复乘和复加的次数也是这么多。当N足够大时,N2≈N(N-1),因此,DFT与IDFT的运算次数与N2成正比,随着N的增加,运算量将急剧增加,而在实际问题中,N往往是较大的,因此有必要对DFT与IDFT的计算方法予以改进。第四页,共五十页,2022年,8月28日
4.1.2因子的特性
DFT和IDFT的快速算法的导出主要是根据因子的特性。
1.周期性:
对离散变量n有同样的周期性。第五页,共五十页,2022年,8月28日
2.对称性:
或
3.其它:
第六页,共五十页,2022年,8月28日4.2基2时间抽选的FFT算法
4.2.1算法推导
已经知道:
令DFT的长度N=2M,M为正整数。第七页,共五十页,2022年,8月28日令:
于是有:第八页,共五十页,2022年,8月28日其中,
是由x(n)的偶数抽样点形成的DFT;而
第九页,共五十页,2022年,8月28日是由x(n)的奇数抽样点形成的DFT。但是这两个式子并不完全是N/2点的DFT,因为k的范围仍然是由0到N-1,因此,还应该进一步考虑k由N/2到N-1范围的情况。第十页,共五十页,2022年,8月28日现在令,故对于后半段有:
同理:
又知:
第十一页,共五十页,2022年,8月28日
图
4.1N点DFT分解为两个N/2点的DFT(N=8)第十二页,共五十页,2022年,8月28日
图
4.2N/2点的DFT分解为两个N/4点的DFT(N=8)第十三页,共五十页,2022年,8月28日综上所述,可以得到:
其中G(k)、P(k)分别是x(n)的偶数点和奇数点的N/2点DFT。
第十四页,共五十页,2022年,8月28日
这样,我们就将一个N点的DFT分解成了两个N/2点的DFT,由于DFT的运算量与其点数的平方成正比,因此使运算量减少了。但是,还应该将每一个N/2点的DFT再分解为两个N/4点的DFT,如此下去,直到分解为2点的DFT为止,总共需要进行log2N-1=log2(N/2)次分解。第十五页,共五十页,2022年,8月28日图
4.32点
DFT信号流图(蝶形图)第十六页,共五十页,2022年,8月28日对于2点DFT,有:
所以2点DFT的运算只需一次加法和一次减法,这样的运算叫做蝶形运算,这样的信号流图叫做蝶形图。第十七页,共五十页,2022年,8月28日该算法每次分解都是将时域序列按奇偶分为两组,因此要求N等于2的正整数幂,故将这种FFT算法叫做基2时间抽选法。第十八页,共五十页,2022年,8月28日
4.2.2算法特点
1.倒序重排这种FFT算法的每次分解都是将输入序列按照奇偶分为两组,故要不断地将每组输入数据按奇偶重排,直到最后分解为2点的DFT,输入数据才不再改变顺序。这样做的结果,使得作FFT运算时,输入序列的次序要按其序号的倒序进行重新排列。
第十九页,共五十页,2022年,8月28日现在将图4.4中输入序号以及重排后的序号按二进制写出如下(注:下标“2”表示二进制数)。可以看出,将输入序号的二进制表示(n2n1n0)位置颠倒,得到(n0n1n2),就是相应的倒序的二进制序号。因此,输入序列按倒序重排,实际上就是将序号为(n2n1n0)的元素与序号为(n0n1n2)的元素的位置相互交换。第二十页,共五十页,2022年,8月28日第二十一页,共五十页,2022年,8月28日
2.同址计算
从图4.4可以看出,整个算法流图可以分为四段,(0)段为倒序重排,后面3段为3(log28=3)次迭代运算:首先计算2点DFT,然后将2点DFT的结果组合成4点DFT,最后将4点DFT组合为8点DFT。因此,对于N点FFT,只需要一列存储N个复数的存储器。
第二十二页,共五十页,2022年,8月28日
3.运算量观察图4.4可知,图4.3所示的蝶形图实际上代表了FFT的基本运算,它实际上只包含了两次复数加法运算。一个N(N=2M)点的FFT,需要进行M=log2N次迭代运算。每次迭代运算包含了N/2个蝶型,因此共有N次复数加法;此外,除了第一次的2点DFT之外,每次迭代还包括了N/2次复数乘法(即乘WN的幂)。因此,一个N点的FFT共有复数乘法的次数为:第二十三页,共五十页,2022年,8月28日
复数加法的次数为:
因此,FFT算法比直接计算DFT大大减少了运算量,尤其是当N较大时,计算量的减少更为显著。比如,当N=1024时,采用FFT算法时复数乘法的次数,不超过直接计算DFT时复乘次数的千分之五。
第二十四页,共五十页,2022年,8月28日4.3基2频率抽选的FFT算法
时间抽选法是在时域内将输入序列x(n)逐次分解为偶数点子序列和奇数点子序列,通过求子序列的DFT而实现整个序列的DFT。而频率抽选法则是在频域内将X(k)逐次分解成偶数点子序列和奇数点子序列,然后对这些分解得越来越短的子序列进行DFT运算,从而求得整个的DFT。当然,同样要求N为2的正整数幂。
第二十五页,共五十页,2022年,8月28日
设,则可以分别表示出k为偶数和奇数时的X(k)。
其中,
第二十六页,共五十页,2022年,8月28日第二十七页,共五十页,2022年,8月28日其中,
显然,X(2r)为g(n)的N/2点DFT,X(2r+1)为p(n)WNn
的N/2点DFT。这样,一个N点的DFT分解为两个N/2点的DFT。将分解继续下去,直到分解为2点的DFT为止。当N=8时,基2频率抽选的FFT算法的整个信号流图如图4.6所示。第二十八页,共五十页,2022年,8月28日将图4.6与图4.4比较,可知频率抽选法的计算量与时间抽选法相同,而且都能够同址计算。时间抽选法是输入序列按奇偶分组,故x(n)的顺序要按倒序重排,而输出序列按前后分半,故X(k)的顺序不需要重排;频率抽选法则是输出序列按奇偶分组,故X(k)的顺序要按倒序重排,而输入序列按前后分半,故x(n)不需要重排。第二十九页,共五十页,2022年,8月28日
4.5快速傅里叶反变换(IFFT)IFFT是IDFT的快速算法。由于DFT的正变换和反变换的表达式相似,因此IDFT也有相似的快速算法。可以用三种不同的方法来导出IFFT算法。方法1
设
,
则有:,n=0,1,┅,N-1第三十页,共五十页,2022年,8月28日根据基2FFT的时间抽选法的第一次分解的结果:第三十一页,共五十页,2022年,8月28日可以得到:第三十二页,共五十页,2022年,8月28日
图
4.8由
X(k)、X(k+N/2)得到
G(k)、P(k)第三十三页,共五十页,2022年,8月28日再由N/2点的DFT求得N/4点的DFT,依次类推下去,就可推到求出x(n)的各点,如图4.9所示。将此流图与图4.4比较,相当于整个流向反过来,此外,因子WNk成为WN-k,还增加了因子1/2。但是,图4.9的IFFT算法不能直接利用按照图4.4编写的FFT算法程序,却可以利用图4.6的频率抽选FFT算法的程序,只需要将X(k)作为输入序列,因子WNk变为WN-k,并且将最后所得的输出序列的每个元素都除以N。第三十四页,共五十页,2022年,8月28日方法2
将DFT的正变换式:
与其反变换式:
第三十五页,共五十页,2022年,8月28日比较,很容易知道,可以利用FFT算法的程序来计算IFFT,只需要将X(k)作为输入序列,x(n)则是输出序列,另外将因子WNk
变为WN-k,
当然,最后还必须将输出序列的每个元素除以N。第三十六页,共五十页,2022年,8月28日
方法3
对DFT的反变换式取共轭,有:
第三十七页,共五十页,2022年,8月28日与DFT的正变换式比较,可知完全可以利用FFT的计算程序,只需要将X*(k)作为输入序列,并将最后结果取共轭,再除以N就得到x(n)。第三十八页,共五十页,2022年,8月28日4.7.1两个长度相同的实序列
可以将两个长度相同的实序列组合成一个复序列来进行FFT运算,从而一次完成这两个实序列的FFT,减少了总的计算量。第三十九页,共五十页,2022年,8月28日
设p(n)和g(n)是两个长度均为N的实序列,并设:
又设
,
,
则由DFT的线性有:(4.36)第四十页,共五十页,2022年,8月28日P(k)和G(k)这两个复序列的实部都是周期性的偶序列,而其虚部都是周期性的奇序列。
对复序列Y(k)又有
(4.37)这里下标r、i分别表示实部和虚部,Y(k)与其实部、虚部的长度都为N。现将(4.37)式中各序列作周期延拓,有
(4.38)第四十一页,共五十页,2022年,8月28日由周期性有: (4.39)
(4.40)第四十二页,共五十页,2022年,8月28日现在将序列
与
作如下分解:
(4.41)
(4.42)第四十三页,共五十页,2022年,8月28日由(4.39)式和(4.40)式,容易证明在(4.41)和(4.42)这两个式子中,前一项都是偶序列,而后一项都是奇序列。
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 二零二五年度医疗器械采购合同模板
- 二零二五年度加气站新能源项目可行性研究与技术评估合同
- 二零二五年高端私人定制接送机服务合同
- 二零二五年度出租车租赁与自动驾驶技术研发合同
- 二零二五年度建筑工程项目竣工验收及移交合同
- 二零二五年度智能家居产品销售与售后服务合同
- 2025版海上医疗物资运输合同样书及应急响应
- 农村集体经济发展项目合作合同
- 房源买卖协议年
- 专业法律服务合同书
- DB34T 4676-2024数字茶园建设指南
- 建筑项目主要劳动力配置计划
- 2025-2030中国孤独症及治疗市场规模与需求研究报告
- 地质调查员职业技能考试题(附答案)
- 儿童低钾血症的诊疗
- JJG(交通) 072-2024 燃烧法沥青含量测试仪
- 老年人护眼知识课件
- 国际压力性损伤-溃疡预防和治疗临床指南(2025年版)解读课件
- 110kV变电站及110kV输电线路运维投标技术方案
- 民办非企业单位内部管理制度
- 500kV变电站工程主变压器安装
评论
0/150
提交评论