论文部分内容阅读
对于计算离散的Fourier变换的快速算法的存在性已被证明。如果离散函数定义域上的采样点数N=r1r2…rm,则变换可用N（r1+r2…+rm）次复数乘加运算,而不必算N2次。 Welch首先注意并说明了在有限Abelian群上的调和分析同样存在快速算法。于是,通常的快速Fourier变换及快速Walsh—Hadamard变换不过是其特例而已。