摘要:
本文把长为plq(p为奇数,q为任意自然数)的DHT转化为Pl个长为q的DHT的计算及其附加运算,附加运算只涉及P点cos-DFT和sin-DFT的计算;对长度(P1l,1,Psls 2l (p1, , ps为奇素数)的DHT,用同样的递归技术得到其快速算法,因而可计算任意长度的DHT;文中还论证了计算长为N的DHT所需的乘法和加法运算量不超过O(Nlog2N)。当长度为N=pl时,本文算法的乘法量比其他已知算法更少。
Abstract:
DHT of length plq (p is odd. q is arbitrary) is turned into p-DHT's of length q and some additional operations while the additional operations only invol ves the computation of cos-DFT and sin-DFT with length p. If the length of a DHT is p1l1psls2l)(p1,, ps are odd primes), a fast algorithm is obtained by the similar recursive technique. Therefore, the algorithm can compute DHT of arbitrary length. The paper also proves that operations for computing DHT of length N by the algorithm are no more than O(Nlog2N). When the length is N=pl, operations
of the algorithm are less than that of other known algorithms.
下载:
