按时间抽取的FFT算法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,7-2,按时间抽取的,FFT,算法,7-2,按,时间抽取的,FFT,算法,一、按时间抽取的算法原理,二、按时间抽取的算法特点,三、按时间抽取,FFT,算法的其他形式,一、按时间抽取的算法原理,设序列点数,N,=2,L,，,L,为整数。,若不满足，则补零,N,为,2,的整数幂的,FFT,算法称基,-2FFT,算法。,将序列,x,(,n,),按,n,的奇偶分成两组,：,则,x,(,n,),的,DFT:,再利用周期性求,X,(,k,),的后半部分,一个“蝶形运算”包含,1,次乘法，,2,次加法,复数乘法,复数加法,一个,N,/2,点,DFT,(,N,/2),2,N,/2(,N,/2,1),两个,N,/2,点,DFT,N,2,/2,N,(,N,/2,1),一个蝶形,1,2,N,/2,个蝶形,N,/2,N,总计,分解后的运算量：,运算量减少了近一半,N,/2,仍为偶数，进一步分解,：,N,/2,N,/4,同理,：,其中：,这样逐级分解，直到,2,点,DFT,基,2,时间抽取,FFT,算法流图,N,=2,x,k,=,x,0,x,1,4,点基,2,时间抽取,FFT,算法流图,x,0,x,2,x,1,x,3,X,1,0,X,1,1,X,2,0,X,2,1,2,点,DFT,2,点,DFT,-,1,-,1,-,1,-,1,X,0,X,1,X,2,X,3,4,点基,2,时间抽取,FFT,算法流图,8,点基,2,时间抽取,FFT,算法流图,4,点,DFT,4,点,DFT,x,0,x,2,x,4,x,6,x,1,x,3,x,5,x,7,X,1,0,X,1,1,X,1,2,X,1,3,X,2,0,X,2,1,X,2,2,X,2,3,X,0,X,1,X,2,X,3,X,4,X,5,X,6,X,7,-,1,-,1,-,1,-,1,4,点,DFT,4,点,DFT,x,0,x,2,x,4,x,6,x,1,x,3,x,5,x,7,X,1,0,X,1,1,X,1,2,X,1,3,X,2,0,X,2,1,X,2,2,X,2,3,X,0,X,1,X,2,X,3,X,4,X,5,X,6,X,7,-,1,-,1,-,1,-,1,8,点基,2,时间抽取,FFT,算法流图,基,2,时间抽取,FFT,算法,第一级,第二级,第三级,二、按时间抽取的算法特点,1.,计算速度,当,N,=2,L,时，共有,L,级蝶形，每级,N,/2,个蝶形，每个蝶形有,1,次复数乘法,2,次复数加法。,复数乘法,：,复数加法,：,比较,DFT,算法的计算复杂度,复乘次数,N,N,2,例,.,如果一台通用计算机的速度为平均每次复乘 ，每次复加 ，用它来计算,512,点的 ，问直接计算需要多少时间，用 运算需要多少时间。,解：,(1),直接利用 计算：,复乘次数为 ，复加次数为 。,复乘所需时间,复加所需时间,所以直接利用,DFT,计算所需时间：,复乘所需时间,复加所需时间,所以用,FFT,计算所需时间,(2),利用 计算：,复乘次数为 ，复加次数为 。,2.,倒序排列,n,0,n,1,n,2,0,0,0,1,1,0,1,1,0,0,1,1,0,1,倒位序,自然序,000,0,0,000,100,4,1,001,010,2,2,010,110,6,3,011,001,1,4,100,101,5,5,101,011,3,6,110,111,7,7,111,倒序,k,0,k,1,k,2,x,k,2,k,1,k,0,x,00,0,x,10,0,x,01,0,0,1,0,1,1,1,2,x,k,k,0,x,k,2,k,1,0,1,x,11,0,x,001,x,101,x,01,1,x,111,0,1,0,1,0,1,0,1,3.,同址运算,在同一级蝶形运算中，两信号只参与一次运算。,4.,蝶距规律,三、按时间抽取,FFT,算法的其它形式,