摘要
本文研究了长度为2~n×2~n(n为正整数)二维离散哈特莱(Hartley)变换的乘法复杂性。虽然DHT(2~n;2)的变换核cas[2π(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)具有相同的乘法复杂性。
The multiplicative complexity of the two-dimensional discrete Hartley trans(?)m of size 2~n×2~n, where (?) is a positive integer, is determined. Although the transform kernel cas[2π(kp+iq)/2~n] of DHT(2~n;2), is not separable into the product of the transform kernel of 1D-DHT, unlike exp[-2πj(ki+lj)/2~n] of DFT(2~n;2), but DHT(2~n;2)can be transferred into one DHT(2^(n-1);2)and (3/2). 1D odd DHTs by linear congruences and ring structures. The computation of 1D odd DHT can be reduced to a direct sum of CHT's, the core of 1D-DHT. The minimal number of real multiplications necessary to compute a length of 2~n two dimensional discrete Harfley transform over the field Q of rational numbers is 2^(2n+1)-6(~n-1)28. Therefore, DHT(2~n;2) have the same multiplicative complexity as the corresponding real data DFT(2~n;2).
出处
《数据采集与处理》
CSCD
1992年第3期157-160,共4页
Journal of Data Acquisition and Processing
基金
国家自然科学资金
