# Fast Type-II Hartley Transform Algorithms for Short-Length Input Sequences
## 3 Fast Algorithms for Small-Size DHT-II
### Algorithm for 5-Point DHT-II  
Let us obtain the algorithm for the five-point DHT-II. The five-point DHT-II is expressed as follows:  
\[\mathbf{Y}_{5\times 1}=\mathbf{C}_{5}\mathbf{X}_{5\times 1}, \tag{13}\]  
where \(\mathbf{Y}_{5\times 1}=\left[y_{0},\,y_{1},\,y_{2},\,y_{3},\,y_{4}\right]^{ \mathrm{T}},\mathbf{X}_{5\times 1}=\left[x_{0},\,x_{1},\,x_{2},\,x_{3},\,x_{4} \right]^{\mathrm{T}}\), \(b_{5}=1.3968\), \(c_{5}=0.6420\), \(d_{5}=1.2601\), \(e_{5}=0.2212\),  
\[\mathbf{C}_{5}= \begin{bmatrix}1&b_{5}&d_{5}&c_{5}&-e_{5}\\ 1&c_{5}&-b_{5}&e_{5}&d_{5}\\ 1&-1&1&-1&1\\ 1&-d_{5}&-e_{5}&b_{5}&-c_{5}\\ 1&e_{5}&-c_{5}&-d_{5}&-b_{5}\end{bmatrix} .\]  
To change the order of rows and columns of \(\mathbf{C}_{5}\), the permutations \(\pi_{5}\) and \(\pi_{6}\) are defined in the following form:  
\[\pi_{5}= \begin{pmatrix}1&2&3&4&5\\ 3&1&2&5&4\end{pmatrix} ,\,\pi_{6}= \begin{pmatrix}1&2&3&4&5\\ 1&2&3&5&4\end{pmatrix} .\]  
The rows of \(\mathbf{C}_{5}\) are permutated according to \(\pi_{5}\) and the columns of \(\mathbf{C}_{5}\) are permutated according to \(\pi_{6}\). After permutations, the matrix acquires the following structure:  
\[\mathbf{C}_{5}^{(a)}= \begin{bmatrix}1&-1&1&-1&1\\ 1&b_{5}&d_{5}&-e_{5}&c_{5}\\ 1&c_{5}&-b_{5}&d_{5}&e_{5}\\ 1&e_{5}&-c_{5}&-b_{5}&-d_{5}\\ 1&-d_{5}&-e_{5}&-c_{5}&b_{5}\end{bmatrix} .\]  
Then, the matrix \(\mathbf{C}_{5}^{(a)}\) is decomposed into two components:  
\[\mathbf{C}_{5}^{(a)} =\mathbf{C}_{5}^{(b)}+\mathbf{C}_{5}^{(c)}, \tag{14}\]  
\[\text{where}\ \mathbf{C}_{5}^{(b)}= \begin{bmatrix}1&-1&1&-1&1\\ 1&&&&\\ 1&&&&\\ 1&&&&\\ 1&&&&\\ \end{bmatrix} \ \text{and}\ \mathbf{C}_{5}^{(c)}= \begin{bmatrix}b_{5}&d_{5}&-e_{5}&c_{5} \\ c_{5}&-b_{5}&d_{5}&e_{5}\\ e_{5}&-c_{5}&-b_{5}&-d_{5}\\ -d_{5}&-e_{5}&-c_{5}&b_{5}\end{bmatrix} .\]  
Matrix \(\mathbf{C}_{5}^{(b)}\) has the same entries except on the sign in the first column and first row, which allows for reducing the number of operations without the need for further transformations [32]. After eliminating rows and columns containing only zero entries in matrix \(\mathbf{C}_{5}^{(c)}\), we obtain matrix \(\mathbf{C}_{4}^{(d)}\):  
\[\mathbf{C}_{4}^{(d)}= \begin{bmatrix}b_{5}&d_{5}&-e_{5}&c_{5}\\ c_{5}&-b_{5}&d_{5}&e_{5}\\ e_{5}&-c_{5}&-b_{5}&-d_{5}\\ -d_{5}&-e_{5}&-c_{5}&b_{5}\end{bmatrix} \]  
which matches the matrix pattern \( \begin{bmatrix}\mathbf{A}_{2}&\mathbf{B}_{2}\\ -\mathbf{B}_{2}&-\mathbf{A}_{2}\end{bmatrix} \), where \(\mathbf{A}_{2}= \begin{bmatrix}b_{5}&d_{5}\\ c_{5}&-b_{5}\end{bmatrix} \), \(\mathbf{B}_{2}= \begin{bmatrix}-e_{5}&c_{5}\\ d_{5}&e_{5}\end{bmatrix} \). Hence, the matrix \(\mathbf{C}_{4}^{(d)}\) can be represented as [5; 30]  
\[\mathbf{C}_{4}^{(d)}= \begin{pmatrix}\mathbf{I}_{2}\otimes\mathbf{I}_{2}\end{pmatrix}  (\mathbf{H}_{2}\otimes\mathbf{I}_{2})1/2[(\mathbf{A}_{2}+\mathbf{B}_{2}) \oplus(\mathbf{A}_{2}-\mathbf{B}_{2})](\mathbf{H}_{2}\otimes\mathbf{I}_{2}), \tag{15}\]where \(\bar{\mathbb{I}}_{2}\ =\ \begin{bmatrix}1&0\\ 0&-1\end{bmatrix} \). Considering the structures of the resulting matrices \(\mathbf{A}_{2}+\mathbf{B}_{2}\) and \((\mathbf{A}_{2}-\mathbf{B}_{2})\), we note that these matrices match the patterns \( \begin{bmatrix}a&b\\ b&-a\end{bmatrix} \) and \( \begin{bmatrix}c&d\\ -d&-c\end{bmatrix} \), respectively. Here, \(a\ =\ b_{5}-e_{5}\); \(b\ =\ c_{5}+d_{5}\); \(c\ =\ b_{5}+e_{5}\); \(d=-\ c_{5}+d_{5}\). Then [5,31],  
\[\begin{array}{c}\mathbf{A}_{2}+\mathbf{B}_{2}\ =\ \mathbf{T}_{2\times 3}^{(4)} \times\ diag(a-b,\ -a-b,\ b)\mathbf{T}_{3\times 2}^{(3)}\\ \mathbf{A}_{2}-\mathbf{B}_{2}=\ \bar{\mathbb{I}}_{2}\mathbf{H}_{2}\times diag((c+d)/2,\ (c-d)/2)\ \mathbb{H}_{2}\\ \\ \text{where}\ \mathbf{T}_{2\times 3}^{(4)}\ =\ \begin{bmatrix}1&0&1\\ 0&1&1\end{bmatrix} ,\mathbf{T}_{3\times 2}^{(3)}\ =\ \begin{bmatrix}1&0\\ 0&1\\ 1&1\end{bmatrix}