On Prime Factor Mapping for the Discrete Hartley Transform

When compared with the complexity for realizing the prime factor DFT, the prime factor discrete Hartley transform requires some extra arithmetic operations for the realization of the prime factor mapping. These extra arithmetic operations can take up as much as 40% of the total arithmetic operations required. In this paper, we propose a new prime factor mapping scheme, which requires no extra arithmetic operations, for the computation of the discrete Hartley transform. It is achieved by embedding all the extra arithmetic operations into the subsequent short length computations, whereas the computational complexities of these embedded short lengths remain unchanged. Consequently, the present approach significantly eliminates the burden which is introduced by the extra arithmetic operations. With our new prime factor mapping scheme, we further demonstrate that a prime-factor-mapped DHT would have a superb performance as compared with other fast discrete Hartley transform algorithms.