Algorithms and architectures for discrete Hartley transform

Abstract

Discrete Hartley transform (DHT) is attractive mainly due to its real-valued kernel and identical forward and inverse transforms. This dissertation focuses two aspects of DHT: (i) development of fast algorithms, and (ii) development of architectures to implement the algorithms to compute DHT. The elements of the DHT matrix can be computed using the direct method in which each element of the matrix is computed based on its definition. Computationally fast position-based method is developed and implemented. In the method, the characteristics of the DHT matrix and its sub-matrix are identified. They are utilized to assign values to some elements, and compute only a few elements using the definition. These elements are then utilized to obtain the remaining elements based on their positions. An algorithm utilizing this method is developed which is faster in computing the elements than the direct method based on its definition. New radix-2 decimation-in-time and decimation-in-frequency algorithms are developed. Their distinct feature is that they explicitly introduce multiplying structures in the signal flow-diagram. The summing structures are modified to perform only addition and subtraction. They exhibit a signal flow-diagram with butterflies identical for each stage which make them suitable for implementation. The multiplying structures take care of all the multiplications and their related additions. The analytical expressions for the operation counts of these algorithms are derived and shown to require less number of multiplications. Similar exercise is carried for radix-4 DHT. It is found that radix-4 is faster than radix-2. The work is extended to develop the signal flow diagram of the split-radix DIT algorithm which utilizes combination of radix-2 and radix-4. Finally, a general-radix algorithm computes DHT for an arbitrary value of N, where either radix-4, radix-2 or the algorithm by definition is utilized.Basic analog circuits are designed to perform the summing structure and multiplying structure operations