Fast Algorithms for the Small-Size Type IV Discrete Hartley Transform

This paper presents new fast algorithms for the fourth type discrete Hartley transform (DHT-IV) for input data sequences of lengths from 3 to 8. Fast algorithms for small-sized trigonometric transforms can be used as building blocks for synthesizing algorithms for large-sized transforms. Additionally, they can be utilized to process small data blocks in various digital signal processing applications, thereby reducing overall system latency and computational complexity. The existing polynomial algebraic approach and the approach based on decomposing the transform matrix into cyclic convolution submatrices involve rather complicated housekeeping and a large number of additions. To avoid the noted drawback, this paper uses a structural approach to synthesize new algorithms. The starting point for constructing fast algorithms was to represent DHT-IV as a matrix–vector product. The next step was to bring the block structure of the DHT-IV matrix to one of the matrix patterns following the structural approach. In this case, if the block structure of the DHT-IV matrix did not match one of the existing patterns, its rows and columns were reordered, and, if necessary, the signs of some entries were changed. If this did not help, the DHT-IV matrix was represented as the sum of two or more matrices, and then each matrix was analyzed separately, if necessary, subjecting the matrices obtained by decomposition to the above transformations. As a result, the factorizations of matrix components were obtained, which led to a reduction in the arithmetic complexity of the developed algorithms. To illustrate the space–time structures of computational processes described by the developed algorithms, their data flow graphs are presented, which, if necessary, can be directly mapped onto the VLSI structure. The obtained DHT-IV algorithms can reduce the number of multiplications by an average of 75% compared with the direct calculation of matrix–vector products. However, the number of additions has increased by an average of 4%.