Fast Radix-3 Algorithm for the Generalized Discrete Hartley Transform of Type II

We present a new fast radix-3 algorithm for the computation of the length-N generalized discrete Hartley transform of type-II (GDHT-II), where N = 3^m, m ≥ 2. Then we apply this algorithm to the direct computation of length-N GDHT-II coefficients when given three adjacent length-N/3 GDHT-II coefficients. The computational complexity of the proposed method is lower than that of the traditional approach for length N ≥ 9. The arithmetic operations can be saved from 19% to 29% for N = 3^m varying from 9 to 243 and from 17% to 29% for N = 3×2^m varying from 12 to 384. Furthermore, the new approach can be easily implemented.

I. Introduction

The generalized discrete hartley transform (GDHT) has been used in many digital signal and image processing tasks. The GDHT can be used as an alternative of the corresponding discrete Fourier transform when the input sequence is real [1], [2]. It was shown [3] that the type-I, -II, -III, and -IV GDHT and the discrete transform (DWT) have similar definitions with different scaling factors. Many fast algorithms for efficient computation of GDHT have been reported in the literature [4]–[7]. Among them, Hu [4] proposed a fast algorithm for computing the GDHT, which is devoted to sequences with length being power of two. Zhao [6] derived a fast radix-3 decimation in frequency algorithm for computing the type-I GDHT. Bi [7] developed fast algorithms for calculating GDHT of composite sequence lengths.