# Fast Type-II Hartley Transform Algorithms for Short-Length Input Sequences
## 1 Introduction
### Related Papers  
To develop fast algorithms for discrete orthogonal transforms the strategy of \"divide and conquer\" is applied [23; 34; 35; 36; 37]. This means dividing a large problem into smaller ones. Then, the solution to the big problem can be obtained by collecting the solutions of smaller problems, which are organized according to the dividing procedures. Often, an obtained solution to the big problem is modular and systematic, which is desirable for implementation. Based on the divide and conquer strategy, fast algorithms for discrete orthogonal transforms have been developed as split-radix algorithms and prime factor algorithms [23]. Split-radix algorithms assume that the length of the input data sequence can be expressed as \(N=q\times 2^{m}\), where \(m\) is a positive integer and \(q\) is an odd integer. Various sequence length values can be represented by setting different values of \(m\) and \(q\). For example, the radix-2 algorithm recursively decomposes the length \(N\) DHT-II into two \(N/2\)-length DHT-IIs. In contrast, the split-radix algorithm decomposes the \(N\)-length DHT-II using different radices. In the literature, split-radix algorithms are developed based on decimation-in-time (DIT) and decimation-in-frequency decomposition [23]. The advantages of split-radix algorithms are substantial, saving the number of arithmetic operations and supporting a wide range of sequence lengths. Despite the advantages of the cost-effective radix algorithms, computational overheads usually occur when the input sequence length is not matched to the assumptions of the available algorithm. Hence, prime factor algorithms were introduced for various sequence lengths, in particular, for sequence lengths other than a power of two. However, prime factor algorithms generally have a more complex computational structure. Specifically, they require irregular index mapping to reorder the input data sequence while computing. Therefore additional computation time and memory space are generally needed. Also,the desirable property of in-place computation, which is easily achieved by split-radix algorithms, is difficult to implement. In the literature, the fast algorithms of both categories are described for DHT-II [24; 25; 26; 27; 28; 29]. Thus, in [23], the prime factor algorithm initially decomposed \(N\)-point DHT-II into \(q\)\(p\)-point discrete cosine transforms and \(p\)\(q\)-point DHTs. Then, to reduce the required number of arithmetic operations and eliminate the irregular index mapping, the resulting decomposition was combined with the split-radix algorithm. A regular computational structure was achieved, providing flexibility for composite sequence lengths and substantially saving the computational complexity. In [24], an algorithm of the DHT-II computation was presented when two sequences of \(N/2\)-length DHT-II adjacent coefficients were given. In this way, two new radix-2 algorithms were developed for computing the \(N\)-point DHT-II. Next, obtaining the \(N\)-point DHT-II was described based on the two adjacent \(N/2\)-point DHT-IIs. Compared with the traditional [PERSON]'s algorithm, the arithmetic operations could be saved from 16% to 24% for \(N\) varying from 16 to 64 [24]. If \(N=8\), the number of arithmetic operations slightly increased. In [25], the algorithm from [24] was further developed. The obtained radix-2 recursive algorithm required a reduced number of arithmetic operations compared with existing algorithms and could be easily implemented. The algorithms proposed in [24; 25] were based on the decimation-in-frequency approach. But, if DHT-II fast algorithms need to be developed for real-time applications, then the DIT approach is preferable. That is why in [26], the radix-2 DIT fast algorithm for DHT-II calculation was presented. It was described by a regular signal flow graph, which provided flexibility to different transform lengths, substantially reducing the arithmetic complexity compared with [PERSON]'s algorithms.