# 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
\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} .\]  
Now, we will move onto dealing with matrices \((\mathbf{A}_{3}+\mathbf{B}_{3})\) and \((\mathbf{A}_{3}-\mathbf{B}_{3})\). In this case, the expressions for calculating the entries of a circular convolution matrix \(\mathbf{H}_{3}\ =\ \begin{bmatrix}h_{0}&h_{2}&h_{1}\\ h_{1}&h_{0}&h_{2}\\ h_{2}&h_{1}&h_{0}\end{bmatrix} \) for \(N=3\) are as follows [32]:  
\[\mathbf{H}_{3}=\mathbf{T}_{3}^{(1)}\mathbf{T}_{3\times 4}\times diag(s_{0},\ s_{1}, \ s_{2},\ s_{3})\times\mathbf{T}_{4\times 3}\mathbf{T}_{3}^{(0)}, \tag{25}\]\[\text{where}\,s_{0}{=(h_{0}{+}h_{1}{+}h_{2})/3},\,s_{1}{=h_{0}{-}h_{2}},\,s_{2}{=h_{1 }{-}h_{2}},\,s_{3}{=(h_{0}{+}h_{1}{-}2h_{2})/3};\,\mathbf{T}_{3}^{(1)}\,=\, \begin{bmatrix}1&1\\ 1&-1&-1\\ 1&&1\end{bmatrix} ,\]  
\[\mathbf{T}_{3\times 4}\ =\ \begin{bmatrix}1&&\\ &1&-1\\ &&1&-1\end{bmatrix} ,\,\mathbf{T}_{4\times 3}\ =\ \begin{bmatrix}1&&\\ &1&\\ &1&1\end{bmatrix} ,\mathbf{T}_{3}^{(0)}\ =\ \begin{bmatrix}1&1&1\\ 1&-1\\ &1&-1\end{bmatrix} .\]  
To make the \(\,(\mathbf{A}_{3}{+}\mathbf{B}_{3}),\,\,(\mathbf{A}_{3}{-}\mathbf{B}_{3})\) matrices consistent with the circular convolution expression, we need to modify them. In the \(\,(\mathbf{A}_{3}{+}\mathbf{B}_{3})\) matrix, we change the sign of all terms in the first column and first row. In the \(\,(\mathbf{A}_{3}{-}\mathbf{B}_{3})\) matrix, we change the sign in the second column. In this way, we obtain the matrices:  
\[ \begin{array}{c}(\mathbf{A}_{3}{+}\mathbf{B}_{3})^{(0)}{=}\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})^{(0)}{=}\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}.\end{array} \]  
Using the three-point convolution algorithm, the values \(s_{i}\), \(I=0,\,1,\,2,\,3\) for matrices \(\,(\mathbf{A}_{3}{+}\mathbf{B}_{3})^{(0)}\) and \(\,(\mathbf{A}_{3}{-}\mathbf{B}_{3})^{(0)}\) take the following form:  
\[ \begin{array}{c}s_{0}^{(7)}{=(b_{7}-\ g_{7}-\ (e_{7}{+}d_{7})\ -\ (c_{7}{+}f_{7}))/6};\,s_{1}^{(7)}{=(b_{7}-\ g_{7}{+}e_{7}{+}d_{7})/2};\,s_{2}^{(7 )}{=(e_{7}{+}d_{7}-c_{7}-f_{7})/2};\\ s_{3}^{(7)}{=(b_{7}-g_{7}-c_{7}-f_{7}{+}2(e_{7}{+}d_{7}))/6};\,s_{4}^{(7)}{=(b_ {7}+g_{7}{+}c_{7}-f_{7}{-}e_{7}{+}d_{7})/6};\,s_{5}^{(7)}{=(b_{7}+g_{7}{+}e_{7} -\ d_{7})/2};\\ s_{6}^{(7)}{=(c_{7}-f_{7}{+}e_{7}-\ d_{7})/2};\,s_{7}^{(7)}{=(b_{7}+g_{7}{+}c _{7}-f_{7}{+}2(e_{7}-\ d_{7}))/6}.\end{array} \]  
Then,  
\[ \begin{array}{c}\mathbf{C}_{6}^{(d)}\ =\ (\mathbf{\tilde{I}}_{2}\otimes\mathbf{I}_{3}) (\mathbf{H}_{2}\otimes\mathbf{I}_{3})(\mathbf{T}_{3}^{(1)}\mathbf{T}_{3}^{(1)} \mathbf{T}_{3}^{(1)}\mathbf{T}_{3}^{(1)}\mathbf{T}_{3}^{(1)}\mathbf{T}_{3}^{( 1)}\mathbf{T}_{3}^{(1)}\mathbf{T}_{3}^{(1)}\mathbf{T}_{3}^{(2)},\,s_{2}^{(7)},\, s_{3}^{(7)},\,s_{4}^{(7)},\,s_{5}^{(7)},\,s_{6}^{(7)},\,s_{7}^{(7)})\times\\ \times(\mathbf{T}_{4\times 3}\mathbf{T}_{3}^{(0)}\oplus\mathbf{T}_{4\times 3} \mathbf{T}_{3}^{(0)})(\mathbf{H}_{2}\otimes\mathbf{I}_{3}).\end{array}  \tag{26}\]  
Based on the properties of structural matrices [5; 32], the computational procedure for the seven-point DHT-II is represented by the expression  
\[\mathbf{Y}_{7\times 1}{=}\,\mathbf{P}_{7}^{(1)}\mathbf{W}_{7\times 9}\mathbf{W}_{9 }\mathbf{W}_{9\times 11}\mathbf{D}_{11}\mathbf{W}_{11\times 9}\mathbf{W}_{9 \times 14}\mathbf{W}_{14\times 7}\mathbf{P}_{7}^{(0)}\mathbf{X}_{7\times 1}, \tag{27}\]where  
\[\mathbf{P}_{7}^{(0)}\;=\; \begin{bmatrix}1&&&&\\ &1&&\\ &&&1&&\\ &&&1&\\ &&&1&\\ &&&1&\\ &&&1&\\ \end{bmatrix} ,\] \[\mathbf{P}_{7}^{(1)}\;=\; \begin{bmatrix}1&&&&\\ &1&&\\ &&&1&\\ 1&&&&\\ &&&1&\\ &&&1&\\ &&&1&\\ &&&1&\\ \end{bmatrix}