一种用于计算器复杂傅里叶级数的算法.docVIP

一种用于计算器复杂傅里叶级数的算法 By James W. Cooley and John W. Tukey Yates提出了一种用于计算2m 因数试验相互作用的有效算法，这种算法以他的名字被广泛传播。而Box则将它扩充到了3m 。Good 不仅推广了这个算法，并且对傅里叶级数给出了更为巧妙的计算。他的算法可以普遍性的用于某类问题，如，N维向量乘以N *N阶的矩阵，这个矩阵可以被分解为m个矩阵，且m与logN成正比。这样结果的操作复杂度只需要NlogN，与原先的N2 有了一定的优化。本文中，这种计算方法被用来计算复杂傅里叶级数。当数据是或者可以被合成为复数时，它是非常有用的。这里扩展了这种算法，并将以另一种形式给出。在此我们需要注意对N的选取。当N为2m 时，我们可以看到用二进制计算机来进行计算具有无可比拟的优势。对于给定的傅里叶系数，整个计算过程只需要存储在一组N个数据存储空间。 考虑如下的离散傅里叶变换。 （1） 其中系数A(k)是复数形式，W是单位上的N次方根 （2） 使用（1）直接计算需要次的运算，在这里，一次运算指一次复乘运算以及一次复数加法运算。 这里所述的算法是基于离散傅里叶的振幅和增益的迭代，仅需要少于2Nlog2N次运算，且不需要更多的存储空间。为了得到这种算法，假定N是一个合数，，那么可以将（1）中的指数表示为： （3） 然后我们可以得到 （4） 因为 （5） 对k1 来说，内部的和只与j0 k0 有关，被整理为 （6） 那么结果可以写为 （7） 此时，A1中有N个元素，每个元素要求r1次运算，所以得到A1需要一共计算Nr1次。同样，我们需要计算Nr2次从A1中再得到X。因此，（6）（7）这两步算法，共需要运算次数为： （8） T=N(r1+r2) 很容易看到，连续重复以上过程，需要的计算量为 （9） T=N(r1+r2+…+rm) （10） N=r1*r2*…*rm 如果，且，那么，除非当有。 总而言之， 我们尽可能的采用更多的因子来减少计算量，但如果采用因子2，计算过程没有减少。如果我们选择一个高合成的数N，那么我们就会得到很大的便利。如果所有的rj等于r，那么有 (11) 总的运算量是 （12） 如果,我们可以发现 （13） 那么 是，，…的加权平均量 它们的值如下所示， rj=3是最有效的形式，但也仅比使用2或者4高了6%，而它们还有其他的好处。如有必要，即使rj的值高达10的时，运算量的增加也不会超过50%。相应的，对于任何大的数，我们都可以在一定的范围内寻找多因数N的值。 只要有可能，使用r=2或4，在寻址和计算效率上，会为二进制算法的计算机带来重要的优势。 取r=2时 （14） 其中jv和kv等于0或1，且就是在二进制位上表示j和k时，各个位地址上的值。 （15） kv=0，1，因为， （16） 式（15）中最里面的和仅依赖于,所以 （17） 继续运算加一个和式，依次类推，同时使用 得到 （19） 将加法形式改写为 （20） 根据规定，这个结果将保存在指标为 （21） 位置处。 可以看到，在式（20）中，仅仅两个在2m-l的位地址上参予了运算。又因为对于式（20）中表示的运算，计算机可以同时执行各个位地址j0，...，jl-2和k0，...，km-l-1的值的计算，因此可以进行并行计算。在一些应用中*，假定，r=4，可以很方便的通过Al-2来表达A。 通过计算最后的数组得到最终的离散傅里叶变换 （22） 在这样的规则顺序下，X的编码就必须通过倒序得到正确的数组Am的编码。 在一些应用中，傅里叶级数累加和需要被两次两次使用，此时就不需要进行倒序的过程。例如，考虑下面的差分方程。 （23） 现在的方法可以首先用来计算F(j)的幅度。通过 （24） 求得 （25） B(k)和A(K)成倒序关系，但是根据式（20）的修正后，A（k）可以用来得到正确顺序的解。 在IBM7094上编写了基于上述三阶傅里叶和计算方法的程序。计算大小的三维数据所使用的运算时间如下图所