1993, 15(2): 121-127.
摘要:
本文把長為plq(p為奇數(shù),q為任意自然數(shù))的DHT轉(zhuǎn)化為Pl個(gè)長為q的DHT的計(jì)算及其附加運(yùn)算,附加運(yùn)算只涉及P點(diǎn)cos-DFT和sin-DFT的計(jì)算;對(duì)長度(P1l,1,Psls 2l (p1, , ps為奇素?cái)?shù))的DHT,用同樣的遞歸技術(shù)得到其快速算法,因而可計(jì)算任意長度的DHT;文中還論證了計(jì)算長為N的DHT所需的乘法和加法運(yùn)算量不超過O(Nlog2N)。當(dāng)長度為N=pl時(shí),本文算法的乘法量比其他已知算法更少。