二维离散哈特莱变换的乘法复杂性

本文研究了长度为2~n×2~n(n为正整数)二维离散哈特莱(Hartley)变换的乘法复杂性。虽然DHT(2~n;2)的变换核cas2π(kp+lq)/2~n]不象DFT(2~n,2)的变换核exp—2πj(kp+lq)/2~n]那样可以分离成一维DHT变换核的乘积,但是DHT(2~n;2)可以利用线性同余组和环结构转换成1个DHT(2~(n-1);2)和(3/2)2~n个一维奇DHT.一维奇DHT可以简化为一维DHT的核CHT的直和,在有理数域Q上计算长度为2~n的二维离散DHT(2~n;2)所需的最少实乘次数为2~(2n+1)—6(n—1)2~n—8。所以二维DHT(2~n;2)和相应的实DFT(2~n;2)具有相同的乘法复杂性。