我对快速离散傅里叶变换(FFT)的理解
我对快速离散傅里叶变换(FFT)的理解
记录一下自己对快速离散傅里叶变换 (FFT) 的理解
离散傅里叶变换(DFT)是假设个数为N个的任意离散数据
可以变换为 ,
其中为对应原始数据k倍频率分量的复数常量(幅值和相位)，
是随着n变化 k倍频率的复数周期函数，
求 的公式为
k=0,1,2,3....N-1
如果将 以
标记来代替，
用
标记来代替，公式可写成
，
的一些特性
将公式 按n值分别为 偶数 奇数 分成两部分 如下一步步化简
可以看到
与
形式上是相同的
是
是
当 时，
实际上是 在原始数据
抽取偶数 和 奇数序列的 离散傅里叶变换 分别标记为
和
(-1是指上标， 并不是指求幂)
所以
那么当时呢？？？
记
可以转换成
也就是说 当
小总结
k=0,1,2,3....N-1 可以分成
和
两部分计算
--------------------------------------------------------------------------------------------------------------------------------------------
当时
当
--------------------------------------------------------------------------------------------------------------------------------------------
又或者
--------------------------------------------------------------------------------------------------------------------------------------------
是抽取的偶序列数据
的傅里叶变换
是抽取的奇序列数据
的傅里叶变换
--------------------------------------------------------------------------------------------------------------------------------------
可简化成下面的图形， （因此叫做 蝶形算法吧）
对FFT 原始数据 序列重选择的 规律总结
假设 有原始数据
那么它的傅里叶变换 X(0...15) 一级简化如下图所示，由于2的4次方为16，所以可以用4位二进制位表示原始数据的索引号
下图中 将原始数据分成奇偶两组 即索引号分为 4'bxxx0 和 4'bxxx1 xxx为从 000~111二进制数
二级简化如下图所示 索引号从上一次为 4'bxxx0 和 4'bxxx1 的两组 再依次分别分成奇偶两组
即 4'bxxx0 -> 4'bxx00, 4'bxx10 4'bxxx1 -> 4'bxx01, 4'bxx11
三级简化如下图所示
索引号从上一次为 4'bxx00, 4'bxx10, 4'bxx01, 4'bxx11 的四组 再依次分别分成奇偶两组
即 4'bxx00 -> 4'bx000, 4'bx100 4'bxx10-> 4'bx010, 4'bx110 4'bxx01 -> 4'bx001, 4'bx101 4'bxx11-> 4'bx011, 4'bx111
四级简化如下图 由于上一级输入端本来就剩余两个数据，也就是一偶一奇 不能再分组 ， 所以索引号与上面一级相同
总结出的原始索引号 变化规律如下图所示 xxx代表自增序列
观察最后一次化简的原始数据索引号，实际上是 4'b0000 ~ 4'b11111 自增序列的镜像 如下表所示
这种规律同样也适用于多于或小于16个数据的情况，但二进制索引号最大位数要作相应的变化