一种新的推导快速傅立叶变换(FFT)的方法---50年前FFT的原创者本应该是你

hitzqm78

摘要:
本文提出了一种基于对称分组思想的快速傅立叶变换的推导方法，此方法从离散傅立叶变换(DFT)的矩阵表示出发，通过一系列的矩阵变换，可以直观明了地推导出快速傅立叶变换及其碟型图，这种推导方法可以替代现行教材中复杂枯燥的Cooley-Tukey推导过程。其对称分组的思想也能给那些已经掌握快速傅立叶变换的学者以新的启示。
关键词 快速傅立叶变换 FFT

0　引　言
在应用数字信号处理技术的所有领域，快速傅立叶变换(FFT)算法起着极其重要的作用。自从1965年美国学者Cooley-Tukey发表FFT算法以来，基于FFT的各种快速算法得到了深入的研究，但多年来对怎样简单明了地推导FFT却没有引起太多地关注。人们对FFT及其碟型图的理解仍然停留在枯燥的代数推导与文字说明阶段，对于初学数字信号处理的人来说，FFT算法始终是理解傅立叶分析的一道难关。甚至对于许多已经掌握快速傅立叶变换的学者来说， 快速傅立叶变换(FFT)究竟快在哪儿，序列W的周期性与对称性在推导FFT的过程中究竟表现在哪儿，这些问题也不是很容易说明白。本文提出了一种基于对称分组思想的快速傅立叶变换的推导方法， 这种方法从离散傅立叶变换(DFT)的矩阵表示出发，通过一系列的矩阵变换，可以直观明了地推导出快速傅立叶变换及其碟型图，序列W的周期性与对称性[local]1[/local]的分开处理更是清晰地说明FFT算法的快速所在。这种推导方法可以替代现行教材中复杂枯燥的Cooley-Tukey推导过程。

1 基于奇偶分组思想的按时间抽取的FFT算法(Cooley-Tukey算法)
设x(n)为 N点的有限长序列 ，则其DFT的正变换为 :