数字信号处理（清华大学第二版）第四章快速傅里叶变换(1)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,直接,DFT,方法/,CZT,方法：当要求准确的,N,点,DFT,，且,N,是素数时,五、N为复合数的FFT算法混合基算法,基-2,FFT,算法：,补零使满足,混合基,FFT,算法：,N,是复合数,1、整数的多基多进制表示形式,（1）二进制：,（2）,r,进制：,3多基多进制混合基：,例：,2、的快速算法,行 列,行序号,列序号,行 列,行变量,列变量,的,DFT,算法,(1)改写 成,做 个 点,DFT,，,得,为参量，输入变量 ，输出变量 的 点,DFT,(3),N,个 （旋转因子）,做,个 点,DFT,，,得,为参量，输入变量 ，输出变量 的 点,DFT,(5)整序,例,当,N,为高组合素数时：,个 点,DFT,，乘以旋转因子,个 点,DFT,个 点,DFT,，乘以旋转因子,个 点,DFT,，乘以旋转因子,L,级,r,点,DFT,称基 算法，,基,算法,混合基算法（基 算法）,基 算法,混合基算法的运算量,不计译序、整序工作量,2乘N个旋转因子 复乘 N,总计：,（1）个 点,DFT,复乘,复加,（3）个 点,DFT,复乘,复加,混合基节省的运算量,次,乘,N,个旋转因子,个 点,DFT,个 点,DFT,个 点,DFT,