# Structure and Principles of Operation of a Quaternion VLSI Multiplier
## 3 Algorithmic Aspect  
Let us multiply the first row of \(\mathbf{B}_{4}\) by \((-1)\). Then, we obtain \[\widehat{\mathbf{B}}_{4} = \left[ \begin{array}{cccc}-b_{0}&b_{1}&b_{2}&b_{3}\\ b_{1}&b_{0}&b_{3}&-b_{2}\\ b_{2}&-b_{3}&b_{0}&b_{1}\\ b_{3}&b_{2}&-b_{1}&b_{0}\end{array} \right]. \tag{7}\]  
Therefore, the procedure for multiplying quaternions can be reduced to the following equivalent expression:  
\[\underbrace{\left[ \begin{array}{c}-y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\end{array} \right]}_{\widehat{\mathbf{y}}_{4}} = \underbrace{\left[ \begin{array}{cccc}-b_{0}&b_{1}&b_{2}&b_{3}\\ b_{1}&b_{0}&b_{3}&-b_{2}\\ b_{2}&-b_{3}&b_{0}&b_{1}\\ b_{3}&b_{2}&-b_{1}&b_{0}\end{array} \right]}_{\widehat{\mathbf{B}}_{4}}\left[ \begin{array}{c}x_{0}\\ x_{1}\\ x_{2}\\ x_{3}\end{array} \right]. \tag{8}\]  
This modification will eventually result in a reduction in the final algorithm's computational complexity. Through this transformation, the matrix that has been altered in this way is represented as the algebraic sum of a block-symmetric Toeplitz-type matrix \(\overline{\mathbf{B}}_{4}\) and a sparse matrix \(\underline{\mathbf{B}}_{4}\), or a matrix with only a few non-zero elements:  
\[\widehat{\mathbf{B}}_{4} = \underbrace{\left[ \begin{array}{cccc}b_{0}&b_{1}&b_{2}&b_{3}\\ b_{1}&b_{0}&b_{3}&b_{2}\\ b_{2}&b_{3}&b_{0}&b_{1}\\ b_{3}&b_{2}&b_{1}&b_{0}\end{array} \right]}_{\overline{\mathbf{B}}_{4}}-2 \underbrace{\left[ \begin{array}{cccc}b_{0}&&&b_{2}\\ &b_{3}&&b_{1}\\ &&&b_{1}\\ \end{array} \right]}_{\overline{\mathbf{B}}_{4}}, \tag{9}\] \[\widehat{\mathbf{y}}_{4}=(\overline{\mathbf{B}}_{4}-2\underline{ \mathbf{B}}_{4})\mathbf{x}_{4}=\overline{\mathbf{B}}_{4}\mathbf{x}_{4}-2 \underline{\mathbf{B}}_{4}\mathbf{x}_{4}. \tag{10}\]  
Omitting mathematical derivations, we represent the multiplication of a matrix \(\overline{\mathbf{B}}_{4}\) by a vector \(\mathbf{x}_{4}\) in the form of the following matrix-vector procedure:  
\[\overline{\mathbf{B}}_{4}\mathbf{x}_{4} = \mathbf{H}_{4}\Big{(}\frac{1}{4}\mathbf{D}_{4}\Big{)}\mathbf{H}_{4 }\mathbf{x}_{4}=\underbrace{\mathbf{W}_{4}^{(0)}\mathbf{W}_{4}^{(1)}\Big{(} \frac{1}{4}\mathbf{D}_{4}\Big{)}}_{\mathbf{H}_{4}}\underbrace{\mathbf{W}_{4}^ {(1)}\mathbf{W}_{4}^{(0)}\mathbf{x}_{4}}_{\mathbf{H}_{4}}, \tag{11}\]  
where  
\[\mathbf{H}_{4} = \left[ \begin{array}{cccc}1&1&|&1&1\\ 1&-1&|&1&-1\\ \longrightarrow&\longrightarrow&\longrightarrow&\longrightarrow&\longrightarrow \\ 1&1&|&-1&-1\\ 1&-1&|&-1&1\end{array} \right]\]  
is the fourth-order Hadamard matrix,  
\[\mathbf{D}_{4} = diag(s_{0},s_{1},s_{2},s_{3}),\] \[\mathbf{W}_{4}^{(0)} = \mathbf{H}_{2}\otimes\mathbf{I}_{2}=\left[ \begin{array}{cccc}1 &|&1\\ &1&|&&1\\ \longrightarrow&\longrightarrow&\longrightarrow&\longrightarrow&\longrightarrow \\ 1&&|&-1&\\ &&1&|&&-1\end{array} \right],\]\[\mathbf{W}_{4}^{(1)} = \mathbf{I}_{2}\otimes\mathbf{H}_{2}=\left[ \begin{array}{cccc|cc}1&1& &|&0&0\\ 1&-1&|&0&0\\ \hline-&-&-&-&-&-\\ 0&0&|&1&1\\ 0&0&|&1&-1\end{array} \right],\]  
and \(\mathbf{I}_{N}\) is the order \(N\) identity matrix, \(\mathbf{H}_{2}=\left[ \begin{array}{cc}1&1\\ 1&-1\end{array} \right]\) is the second-order Hadamard matrix, and \(\otimes\), \(\oplus\) denote the Kronecker product and direct sum of two matrices, respectively. It is simple to verify that the entries of the matrix \(\mathbf{D}_{4}=diag(\mathbf{d}_{4})\) may be computed by applying the subsequent matrix-vector procedure, which minimizes the number of real additions involved:  
\[\mathbf{d}_{4}=\frac{1}{4}\mathbf{H}_{4}\mathbf{b}_{4}=\frac{1}{4}\mathbf{W}_ {4}^{(1)}\mathbf{W}_{4}^{(0)}\mathbf{b}_{4}, \tag{12}\]  
where  
\[\mathbf{d}_{4}=[s_{0},s_{1},s_{2},s_{3}]^{T},\ \ \ \mathbf{b}_{4}=[b_{0},b_{1},b_{2}, b_{3}]^{T}. \tag{13}\]  
Regretfully, there is no way to lessen the computational cost of the product \(2\mathbf{B}_{4}\mathbf{x}_{4}\); hence, it must be calculated directly without using any techniques.