Fast Algorithms for Short-Length Odd-Time and Odd-Frequency Discrete Hartley Transforms

This paper proposes fast algorithms for odd-time and odd-frequency discrete Hartley transforms (DHTs) with normalization if the size of the input sequence ranges from 2 to 8. Fast algorithms for small-sized inputs can be included as modules in fast algorithms for discrete transforms of large-length input sequences. The existing fast odd-time DHT and odd-frequency DHT algorithms are primarily radix-type algorithms, specifically, radix-2 and prime factor algorithms. However, the algorithms in the literature do not normalize the initial transform. This means that after applying such algorithms, additional N multiplications are required. In this paper, the structural approach is exploited supposing that the starting point to design the fast algorithms is a matrix vector product expression. The factorization of the matrices of DHT coefficients is produced to reduce computational complexity taking into account the repetition and arranging of the matrix entries. The strict mathematical background proves the correctness of the obtained algorithmic solutions. Also, the MATLAB R2023b environment was applied for testing of the performance of the proposed algorithms. The obtained factorizations of the odd-time DHT and odd-frequency DHT matrices allow us to reduce the number of multiplications by 69%, while the amount of additions is decreased by about of 5% for odd-time DHTs and 8% for odd-frequency DHTs if the length of input data is in the range from 2 to 8. A comparison is provided with the direct calculation of the matrix vector product. Additionally, the computational complexity for each obtained solution is compared with the computational complexity of the existing fast algorithms for odd-time DHTs and odd-frequency DHTs. In addition, data flow graphs have been created for the proposed odd-time DHT and odd-frequency DHT algorithms. The modular space–time structure of the resulting data flow graphs is suitable for VLSI implementation.