Multidimensional Polynomial Transform Algorithm For Multidimensional Discrete Hartley Transform

In this paper, we present an index permutation-based fast algorithm for the multidimensional discrete Hartley transform (MD-DHT). By reordering the MD-DHT input sequence, we first convert the MD-DHT into a multiple sum that contains a number of one-dimensional discrete W transforms (1D-DWTs). We then use a combination of the 1D-DWTs and the multidimensional polynomial transform to compute the multiple sum. It is shown that the number of multiplications and additions required for the proposed algorithm are approximately 1/m and 2m+1/3m times that of the commonly used row-column DHT method, respectively. The developed algorithm is also simple in structure and easy to realize in programming.