版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
Chap.6ComputationofTheDiscreteFourierTransformcontents§6.1EfficientcomputationofDFT§6.2Decimation-in-timeFFTalgorithms(DIT)§6.3Decimation-in-frequencyFFTalgorithms(DIF)
§6.4FastIDFTalgorithms§6.1EfficientcomputationofDFT一、ThecomputationofDFT1.CompareDFTwithIDFT
2.ThedirectcomputationofDFTN
ComplexmultiplicationComplexadditionsRealmultiplicationRealadditionsoneX[k]N-pointDFTN-1N(N-1)4N
2N+2(N-1)=4N-24realmultiplication2realadditionse.g.N:
Complexmultiplication:
8
64
1024
1048576Theamountofcomputation(thecomputationtime)requiredtocomputetheDFTbythedirectmethodbecomesverylargeforlargeN.
Forthisreason,weareinterestedincomputationalproceduresthatreducethenumberofmultiplicationsandadditions.2)Complexconjugatesymmetry:
1)Periodicityinnandk:
3)
Reducibility
可约性:CanreducethecomputationofDFTbyusingtheseProperties.4)others二、Propertiesof【BasicideasforFFTalgorithm】Dividealongsequenceintoseveralshortsequences.UsingallpropertiesoftocombineSomeitems
InDFT
Example:N=8,By
'decimation'Decimation-In-TimeFFT(DIT-FFT)Decimation-In-FrequencyFFT(DIF-FFT)radix-2FFT
hybrid-radixFFT
split-radixFFTradix-4FFTBy'radix'FFTalgorithmsTheothers
CTZ§6.2Decimation-in-timeFFTAlgorithms(DIT)(Coolkey-Tukey)Let
——radix-2FFT0123456789101112131415nx(n)If,padzerosto16points.
一、Principal
CalculateN-DFTusingDivideNpoints
intotwo
pointssequenceLet,AnotherhalfofX[k]:
So,ButterflyComputation:
AN-pointDFTisdecomposedintotwoN/2-pointDFTs1complexmultiplication+2complexaddition——ButterflyComputation
inDIT-FFTplex×
:complex+:
Computation=twoN/2-pointDFTs+N/2butterflies计算量减少大约一半+:N(N-1)DFT2.The2nddecomposition:Similarly,Then,aN-pointDFTisdecomposedintofourN/4-pointDFTs.计算量进一步减少大约一半e.g.Computation=4N/4-pointDFTs+2
stagesbutterflies3.Furtherdecompositionuntil2-pointDFTsareleftbutterflye.g.The8-pointDIT-FFTStagem=0m=1m=2group421Coefficient4、Computation:Complexmultiplication:Complexaddition:DFT+:N(N-1)
ComparisonofthecomputationofDFTandDIT-FFT
DFTDIT-FFTRatio
DFTDIT-FFTRatioNN2
L
NN2
L2414.01281638444836.641644.025665536102464.0864125.45122621442304113.816256328.0102410485765120204.83210288012.82048419430411264372.464404919221.4
二、PropertiesofDIT1.In-PlaceComputations(原位运算、同址运算)Theoutputofeverystagecanbestoredintheregisterswhichstoringtheinputdata.SoNregistersarenecessary.2、Bit-reversedorder(倒位序)Input:bit-reversedorder.Output:normalordernormalorderbinarydigits(n2n1n0)bit-reservedbinarydigits(n0n1n2)bit-reservedorder00000000100110042010010230111106410000115101101561100113711111173.
Distancebetweentwosourcenodesofonebutterfly
Stagem=0m=1m=2Distance124三、AlternativeFormsinputinnormalorder,outputinbit-reserved
orderbothinputandoutputinnormalorderinputinbit-reservedorder,outputinnormalorder,withthesamegeometryforeachstage§6.3Decimation-in-frequencyFFTAlgorithms
(DIF)一、Principal
CalculateN-DFTusing——ButterflyComputation
inDIF-FFTSo,2complexaddition+1complexmultiplicationLetcompareThen
plex×
:complex+:
Computation=twoN/2-pointDFTs+N/2butterflies计算量减少大约一半+:N(N-1)DFT2.The2nddecomposition:e.g.Computation=2
stagesbutterflies+FourN/4-pointDFTs3.Furtherdecompositionuntil2-pointDFTsareleftbutterflye.g.The8-pointDIF-FFT8-pointDIF-FFT:compareStagem=0m=1m=2group124Coefficient4、Computation:Complexmultiplication:Complexaddition:DFT+:N(N-1)
二、PropertiesofDIF1.In-PlaceComputations(原位运算、同址运算)2.Bit-reversedorder(倒位序)Output:bit-reversedorder.Input:normalorder3.
Distancebetweentwosourcenodesofonebutterfly
Stagem=0m=1m=2Distance421四、ComparisonofDIT-FFTandDIF-FFT1.ideaDIT-FFT:
dividetheinputsequencex[n]intosmallerandsmallersubsequencesDIF-FFT:
dividetheoutputsequenceX[k]intosmallerandsmallersubsequences2.ButterflycomputationisdifferentDIT-FFT:
DIF-FFT:
(fig.9.11)
(fig.9.21)
3.StructuresaretransposedeachotherDIT-FFT:
(fig.9.10)
DIF-FFT:
(fig.9.20)
4.Botharein-placecomputation5.Thecomputation
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2022年黑龙江省哈尔滨市道里区中考一模物理试卷
- 公司经营工作总结
- 《土木工程材料》课件 01建筑材料的基本性质
- 消防工作总结及消防宣传活动效果
- 公司工作总结及营销策略
- 医院工作总结:医院医疗服务的效率与便捷
- 公司业务工作总结报告和规划
- 浅析云领网络科技有限公司员工流失原因
- 父母对子女教育心得体会(21篇)
- 英语1B 基础模块(修订版)-Unit 1-单元测试题(含答案)
- 2022届云南专升本考试《护理综合》练习题
- 法定计量检定机构考评员管理规范
- 战斗机发展简史-课件
- 可摘局部义齿修复最全
- 消防设施设备检查表实用文档
- SL288-2014 2014水利工程施工监理规范
- 2023小学道德与法治(部编版)六年级下册 第三单元复习课件
- 三氟氯乙烯安全技术说明书(msds)
- 部编版四年级语文下册习作《我的“自画像”》优质课件
- 《乘风破浪的姐姐》招商方案
- 2023年03月民航新疆空管局校园招考8名应届毕业生管制“+1”笔试参考题库答案解析
评论
0/150
提交评论