快速傅里叶变换(FFT)——按频率抽取DIF的基
【1】回顾DIT
https://blog.csdn.net/qq_42604176/article/details/105559756
【2】算法原理
设序列点数:N=2^M,M为正整数。将输入序列按照前一半、后一半分开。(并非按照奇偶分)
由于,所以化简为:
按照k奇数偶数进行分类讨论:
注意,此时X(2r):前半输入与后半输入之和的N/2点DFT
X(2r+1):前半输入与后半输入之差的与WN^n之积的N/2点DFT;
将括号内的式子写作整体:
基本的蝶形运算单元:
以N=8为例,展示出1级,2级,3级分解层次:
1、第一次分解
2、第二次分解:
3、第三次分解:
由于N=2^M,N/2仍然为偶数,将N/2点DFT输出再次分解,一直进行到第M次,第M次做两点DFT。
【3】运算特点
1、通过(N/2)*M个蝶形运算完成。(N/2:行数的一半,M:列数,运算的级数)
都有这样的迭代运算:
2、DIT与DIF方法异同点:
【1】:DIF:输入自然序列,输出倒位序列。
DIT:输入倒位序列,输出自然序列。
(本质上都是重新排序)
【2】:基本蝶形运算单元不同:
DIF:复数乘积只出现在减法运算之后
DIT:先做复数乘法运算,再做加减法
【3】:运算量相同
【4】:都需要进行变址运算,且转换的方法是一样的
【5】:DIT、DIF的基本蝶形互为转置
转置:流图中所有支路方向都反向,并且交换输入输出。节点变量值不做变换。
—————————————————————————————————————————————————————————————
参考资料:
《数字信号处理第三版.刘顺兰版》