# Fast Type-II Hartley Transform Algorithms for Short-Length Input Sequences
## 3 Fast Algorithms for Small-Size DHT-II
### Algorithm for 8-Point DHT-II  
Let us design the algorithm for the eight-point DHT-II. The eight-point DHT-II is expressed as follows:  
\[\mathbf{Y}_{8\times 1} =\mathbf{C}_{8}\mathbf{X}_{8\times 1}, \tag{28}\]  
Figure 6: Data flow graph of the algorithm for the computation of seven-point DHT-II. \[\text{where}\ \mathbf{Y}_{8\times 1}\ =\ [y_{0},\ y_{1},\ y_{2},\ y_{3},\ y_{4},\ y_{5 },\ y_{6},\ y_{7}]^{\text{T}},\mathbf{X}_{8\times 1}\ =\ [x_{0},\ x_{1},\ x_{2},\ x_{3},\ x_{4},\ x_{5},\ x_{6},\ x_{7}]^{ \text{T}},\] \[\mathbf{C}_{8}\ =\ \left[ \begin{array}{cccccccc}1&b_{8}&d_{8}&b_{8}&1&c_{8 }&0&-c_{8}\\ 1&b_{8}&0&-b_{8}&-1&c_{8}&d_{8}&c_{8}\\ 1&c_{8}&-d_{8}&c_{8}&1&-b_{8}&0&b_{8}\\ 1&-c_{8}&0&c_{8}&-1&b_{8}&-d_{8}&b_{8}\\ 1&-b_{8}&d_{8}&-b_{8}&1&-c_{8}&0&c_{8}\\ 1&-b_{8}&0&b_{8}&-1&-c_{8}&d_{8}&-c_{8}\\ 1&-c_{8}&-d_{8}&-c_{8}&1&b_{8}&0&-b_{8}\\ 1&\mathcal{C}_{8}&0&-c_{8}&-1&-b_{8}&-d_{8}&-b_{8}\\ \end{array} \right]\text{ with }b_{8}=1.3066,\ c_{8}=0.5412,\] \[d_{8}=1.4142.\]  
Let us define the permutation  
\[\pi_{8}\ =\ \begin{pmatrix}1&2&3&4&5&6&7&8\\ 1&5&3&7&2&4&6&8\\ \end{pmatrix} \]  
to change the order of columns of \(\mathbf{C}_{8}\):  
\[\mathbf{C}_{8}^{(a)}\ =\ \begin{bmatrix}1&1&d_{8}&0&b_{8}&b_{8}&c_{8}&-c_{8}\\ 1&-1&0&d_{8}&b_{8}&-b_{8}&c_{8}&c_{8}\\ 1&1&-d_{8}&0&c_{8}&c_{8}&-b_{8}&b_{8}\\ 1&-1&0&-d_{8}&-c_{8}&c_{8}&b_{8}&b_{8}\\ 1&1&d_{8}&0&-b_{8}&b_{8}&-c_{8}&c_{8}\\ 1&-1&0&d_{8}&-b_{8}&b_{8}&-c_{8}&-c_{8}\\ 1&1&-d_{8}&0&-c_{8}&-c_{8}&b_{8}&-b_{8}\\ 1&-1&0&-d_{8}&c_{8}&-c_{8}&-b_{8}&-b_{8}\\ \end{bmatrix} \]  
After permutations, the matrix \(\mathbf{C}_{8}^{(a)}\) acquires the structure  
\[ \begin{bmatrix}\mathbf{A}_{4}&\mathbf{B}_{4}\\ \mathbf{A}_{4}&-\mathbf{B}_{4}\end{bmatrix} \text{with}\ \mathbf{A}_{4}\ =\ \begin{bmatrix}1&1&d_{8}&0\\ 1&-1&0&d_{8}\\ 1&1&-d_{8}&0\\ 1&-1&0&-d_{8}\end{bmatrix} \text{and}\ \mathbf{B}_{4}\ =\ \begin{bmatrix}b_{8}&b_{8}&c_{8}&-c_{8}\\ b_{8}&-b_{8}&c_{8}&c_{8}\\ c_{8}&c_{8}&-b_{8}&b_{8}\\ -c_{8}&c_{8}&b_{8}&b_{8}\end{bmatrix} .\]  
Then, \(\mathbf{C}_{8}^{(a)}\!=(\mathbf{H}_{2}\otimes\mathbf{I}_{4})(\mathbf{A}_{4} \oplus\mathbf{B}_{4})\). Based on the properties of structural matrices [30; 31], the matrix \(\mathbf{A}_{4}\) has the following structure:  
\[ \begin{bmatrix}\mathbf{A}_{2}^{(a)}&\mathbf{B}_{2}^{(\mathbf{A})}\\ \mathbf{A}_{2}^{(\mathbf{A})}&-\mathbf{B}_{2}^{(\mathbf{A})}\end{bmatrix}  \text{with}\ \mathbf{A}_{2}^{(\mathbf{A})}\!=\mathbf{H}_{2}\ \text{and}\ \mathbf{B}_{2}^{(a)}\!=d_{8}\mathbf{I}_{2}.\]  
Hence, the matrix \(\mathbf{A}_{4}\) is represented as  
\[\mathbf{A}_{4}\!=(\mathbf{H}_{2}\otimes\mathbf{I}_{2})(\mathbf{H}_{2}\oplus \ diag(s_{0}^{(8)},\ s_{1}^{(8)}))\]  
where \(s_{0}^{(8)}\!=s_{1}  
where \(\mathbf{T}_{23}^{(4)}\) and \(\mathbf{T}_{32}^{(3)}\) are defined as in (16), \(\mathbf{A}_{2}^{(b)}-\mathbf{B}_{2}^{(b)}= \begin{bmatrix}b_{8}{-}c_{8}&b_{8}{-}c_ {8}\\ b_{8}{-}c_{8}&-b_{8}{+}c_{8}\end{bmatrix} \), \(-\mathbf{A}_{2}^{(b)}-\mathbf{B}_{2}^{(b)}= \begin{bmatrix}-b_{8}{-}c_{8}&-b_{8}{-}c_ {8}\\ -b_{8}{-}c_{8}&-b_{8}{+}c_{8}\end{bmatrix} \), \(\mathbf{B}_{2}^{(b)}= \begin{bmatrix}c_{8}&c_{8}\\ c_{8}&-c_{8}\end{bmatrix} \). Next, we present \(\mathbf{A}_{2}^{(b)}-\mathbf{B}_{2}^{(b)}-\mathbf{A}_{2}^{(b)}-\mathbf{B}_{2} ^{(b)}\), and \(\mathbf{B}_{2}^{(b)}\) as [5]  
\[ \begin{array}{c}\mathbf{A}_{2}^{(b)}-\mathbf{B}_{2}^{(b)}=\mathbf{H}_{2}{ \times}diag(s_{2}^{(8)},\ s_{3}^{(8)}),\ s_{2}^{(8)}=s_{3}^{(8)}=b_{8}{-}c_{8},\\ -\mathbf{A}_{2}^{(b)}-\mathbf{B}_{2}^{(b)}=\mathbf{H}_{2}{\times}diag(s_{4}^{ (8)},\ s_{5}^{(8)}),\ s_{4}^{(8)}=s_{5}^{(8)}=-b_{8}{-}c_{8},\\ \mathbf{B}_{2}^{(b)}{=}\mathbf{H}_{2}{\times}diag(s_{6}^{(8)},\ s_{7}^{(8)}), \ s_{6}^{(8)}=s_{7}^{(8)}=c_{8}.\end{array} \]  
Relying on the properties of structural matrices [5; 32], the computational procedure for the eight-point DHT-II is represented by the expression  
\[\mathbf{Y}_{8\times 1}{=}\;\mathbf{W}_{8}\mathbf{W}_{8\times 10}\mathbf{W}_{10} \mathbf{D}_{10}\mathbf{W}_{10\times 8}\mathbf{P}_{8}\mathbf{X}_{8\times 1}, \tag{30}\]  
where  
\[