# Fast Type-II Hartley Transform Algorithms for Short-Length Input Sequences
## 3 Fast Algorithms for Small-Size DHT-II
### Algorithm for 7-Point DHT-II  
To elaborate the algorithm for the seven-point DHT-II, the matrix notation of this transform is expressed as follows:  
\[\mathbf{Y}_{7\times 1}=\mathbf{C}_{7}\mathbf{X}_{7\times 1}, \tag{22}\]  
where \(\mathbf{Y}_{7\times 1}=[y_{0},\,y_{1},\,y_{2},\,y_{3},\,y_{4},\,y_{5},\,y_{6}]^{ \mathrm{T}},\mathbf{X}_{7\times 1}=[x_{0},\,x_{1},\,x_{2},\,x_{3},\,x_{4},\,x_{5},\,x_{6}]^{ \mathrm{T}},b_{7}\)=1.3349, \(c_{7}\)=1.1974, \(d_{7}\)=0.1583, \(e_{7}\)=1.4053, \(g_{7}\)=0.4671, \(f_{7}\)=0.7524,  
\[\mathbf{C}_{7}\,=\, \begin{bmatrix}1&b_{7}&e_{7}&c_{7}&f_{7}&d_{7}&-g_{7}\\ 1&c_{7}&-g_{7}&-e_{7}&-d_{7}&b_{7}&f_{7}\\ 1&d_{7}&-c_{7}&b_{7}&-g_{7}&-f_{7}&e_{7}\\ 1&-1&1&-1&1&-1&1\\ 1&-e_{7}&f_{7}&g_{7}&-b_{7}&c_{7}&-d_{7}\\ 1&-f_{7}&b_{7}&d_{7}&e_{7}&g_{7}&-c_{7}\\ 1&g_{7}&-d_{7}&-f_{7}&-c_{7}&-e_{7}&-b_{7}\end{bmatrix} .\]  
Now, we need to change the order of rows and columns. Let us define the permutations \(\pi_{7},\,\pi_{8}\) in the following form:  
\[\pi_{7}\,=\, \begin{pmatrix}1&2&3&4&5&6&7\\ 4&1&2&3&7&6&5\end{pmatrix} ,\,\pi_{8}\,=\, \begin{pmatrix}1&2&3&4&5&6&7\\ 1&2&3&4&7&6&5\end{pmatrix} .\]  
Then, we permute rows and columns of \(\mathbf{C}_{7}\) according to \(\pi_{7},\,\pi_{8}\). After permutations, the matrix acquires the following structure:  
\[\mathbf{C}_{7}^{(a)}\,=\, \begin{bmatrix}1&-1&1&-1&1&-1&1\\ 1&b_{7}&e_{7}&c_{7}&-g_{7}&d_{7}&f_{7}\\ 1&c_{7}&-g_{7}&-e_{7}&f_{7}&b_{7}&-d_{7}\\ 1&d_{7}&-c_{7}&b_{7}&e_{7}&-f_{7}&-g_{7}\\ 1&g_{7}&-d_{7}&-f_{7}&-b_{7}&-e_{7}&-c_{7}\\ 1&-f_{7}&b_{7}&d_{7}&-c_{7}&g_{7}&e_{7}\\ 1&-e_{7}&f_{7}&g_{7}&-d_{7}&c_{7}&-b_{7}\end{bmatrix} .\]  
Further, the matrix \(\mathbf{C}_{7}^{(a)}\) is decomposed into two components:  
\[\mathbf{C}_{7}^{(a)}\mathbf{=C}_{7}^{(b)}\mathbf{+C}_{7}^{(c)}, \tag{23}\]  
Figure 5: Data flow graph of the algorithm for the computation of six-point DHT-II. where  
\[\mathbf{C}_{7}^{(b)}\ =\ \begin{bmatrix}1&-1&1&-1&1&-1&1\\ 1&&&&&&&\\ 1&&&&&&&\\ 1&&&&&&&\\ 1&&&&&&&\\ \end{bmatrix} ,\]  
\[\mathbf{C}_{7}^{(c)}\ =\ \begin{bmatrix}b_{7}&e_{7}&c_{7}&-g_{7}&d_{7}&f_{7}\\ c_{7}&-g_{7}&-e_{7}&f_{7}&b_{7}&-d_{7}\\ d_{7}&-c_{7}&b_{7}&e_{7}&-f_{7}&-g_{7}\\ g_{7}&-d_{7}&-f_{7}&-b_{7}&-e_{7}&-c_{7}\\ -f_{7}&b_{7}&d_{7}&-c_{7}&g_{7}&e_{7}\\ -e_{7}&f_{7}&g_{7}&-d_{7}&c_{7}&-b_{7}\end{bmatrix} .\]  
Matrix \(\mathbf{C}_{7}^{(B)}\) has the same entries except on the sign in the first column and first row, which allows us to reduce the number of operations without the need for further transformations [31]. After eliminating the rows and columns containing only zero entries in matrix \(\mathbf{C}_{7}^{(c)}\), we obtain matrix \(\mathbf{C}_{6}^{(d)}\):  
\[\mathbf{C}_{6}^{(d)}\ =\ \begin{bmatrix}b_{7}&e_{7}&c_{7}&-g_{7}&d_{7}&f_{7}\\ c_{7}&-g_{7}&-e_{7}&f_{7}&b_{7}&-d_{7}\\ d_{7}&-c_{7}&b_{7}&e_{7}&-f_{7}&-g_{7}\\ g_{7}&-d_{7}&-f_{7}&-b_{7}&-e_{7}&-c_{7}\\ -f_{7}&b_{7}&d_{7}&-c_{7}&g_{7}&e_{7}\\ -e_{7}&f_{7}&g_{7}&-d_{7}&c_{7}&-b_{7}\end{bmatrix} .\]  
The obtained matrix acquires the structure \( \begin{bmatrix}\mathbf{A}_{3}&\mathbf{B}_{3}\\ -\mathbf{B}_{3}&-\mathbf{A}_{3}\end{bmatrix} \), with \(\mathbf{A}_{3}\ =\ \begin{bmatrix}b_{7}&e_{7}&c_{7}\\ c_{7}&-g_{7}&-e_{7}\\ d_{7}&-c_{7}&b_{7}\end{bmatrix} \) and \(\mathbf{B}_{3}\ =\ \begin{bmatrix}-g_{7}&d_{7}&f_{7}\\ f_{7}&b_{7}&-d_{7}\\ e_{7}&-f_{7}&-g_{7}\end{bmatrix} \). Then [5; 32],  
\[\mathbf{C}_{6}^{(d)}\ =\ (\bar{\mathbf{I}}_{2}\otimes\mathbf{I}_{3})(\mathbf{H} _{2}\otimes\mathbf{I}_{3})1/2[(\mathbf{A}_{3}+\mathbf{B}_{3})\oplus(\mathbf{A }_{3}-\mathbf{B}_{3})](\mathbf{H}_{2}\otimes\mathbf{I}_{3}). \tag{24}\]  
Submatrices \((\mathbf{A}_{3}+\mathbf{B}_{3})\), \((\mathbf{A}_{3}-\mathbf{B}_{3})\) of quasi-diagonal matrix \((\mathbf{A}_{3}+\mathbf{B}_{3})\oplus(\mathbf{A}_{3}-\mathbf{B}_{3})\) are represented as circular convolution matrices [32]:  
\[\mathbf{A}_{3}+\mathbf{B}_{3}= \begin{bmatrix}b_{7}-g_{7}&e_{7}+d_{7}&c_{7}+f_{ 7}\\ c_{7}+f_{7}&b_{7}-g_{7}&-(e_{7}+d_{7})\\ e_{7}+d_{7}&-(c_{7}+f_{7})&b_{7}-g_{7}\end{bmatrix} ,\ \mathbf{A}_{3}-\mathbf{B}_{3}=