二、快速傅立叶变换算法

    快速傅立叶变换算法（简称FFT算法）是计算有限离散傅立叶变换的快速方法.

    [复序列的FFT算法]  计算复序列{z_k} 的有限离散傅立叶变换，就是计算形如

                         ，    

的有限项和.对于反演公式，计算的方法类似.

    设N=2^m,  , 那末

                           

又设                 

                     

分别是k和j的二进制表示，取值为0或1，.那末

             

因为    =

                       =

                       =

所以

   

从而得出递推公式：

                  

                

                

                

                  

                

                

最后有

                

[实序列的FFT算法]   设有2N (N=2^m)个元素构成的实序列要计算的有限离散傅立叶余弦变换和正弦变换

                      

                      

可先用FFT算法关于复序列

                  z_k=x_k+iy_k         

计算

                      

而 c_j , s_j 用下列公式去求

  

至于c_j , s_j 当的数值是