# Structure and Principles of Operation of a Quaternion VLSI Multiplier
## 3 Algorithmic Aspect
Upon integrating the computations for both matrices into a solitary process, we ultimately derive the following:  
\[\mathbf{y}_{4}=\mathbf{S}_{4\times 8}(\mathbf{H}_{4}\oplus\mathbf{I}_{4}) \mathbf{D}_{8}(\mathbf{H}_{4}\oplus\mathbf{I}_{4})\mathbf{P}_{8\times 4}^{(0)} \mathbf{x}_{4}, \tag{14}\]  
\[\mathbf{P}_{8\times 4}^{(0)} = \mathbf{1}_{2\times 1}\otimes\mathbf{I}_{4}=\left[ \begin{array}{cccc |cc}1&&&\\ &&1&&\\ &&1&&\\ -&-&-&-&-\\ 1&&1&&\\ &&&1&\\ &&&1\end{array} \right],\ \ \mathbf{1}_{2\times 1}=[1,1]^{T},\]  
\[\mathbf{S}_{4\times 8} = \left[ \begin{array}{cccc|cc}-1&&&|&1&&&\\ &1&&|&-1&&\\ &&1&&|&&-1&\\ &&&1&|&&&-1\end{array} \right],\] \[\mathbf{D}_{8} = \frac{1}{4}\mathbf{D}_{4}\oplus\mathbf{D}_{4},\]  
\[\mathbf{D}_{4}=diag(s_{4},s_{5},s_{6},s_{7})=diag(2\mathbf{B}_{4}\mathbf{x}_{4}). \tag{15}\]  
Expression (14) describes a fast algorithm for quaternion multiplication. The data flow diagram of the processing block for calculating elements \(\{s_{m}\}\), \(m=0,1,2,3\), is depicted in Figure 1, whereas the data flow structure of the quaternion multiplication unit is shown in Figure 2. Figure 3 shows a data flow structure of the process for calculating elements \(\{s_{m+4}\}\), \(m=0,1,2,3\). The data flow diagrams in this paper are left-to-right-oriented. The data transfer operations in the diagrams are represented by straight lines. Points indicate summation where lines converge. The subtraction procedure is indicated by the dotted lines. To avoid overcrowding the image, we purposefully employ the standard lines without arrows. These figures' circles depict the process of multiplying by a number, either constant or variable, that is written inside a circle. In turn, the rectangles indicate the matrix-vector multiplications by the matrices inscribed inside rectangles. Let us consider the data flow diagrams shown in Figures 2-3. It can be seen that the implementation of the computations according to (12) and (14) requires only eight multiplications, 28 additions, four right shifts (multiplications by 1/4) and four left shifts (multiplications by 2). And since the left-right shift operations are very simple and do not require additional memory access, they are usually omitted when evaluating the computational complexity. Note that here we take into account the fact that the multiplication of a fourth-order Hadamard matrix by a vector requires only 8 additions instead of 12. Figure 4 shows a detailed schematic view of the matrix-vector multiplications of the corresponding vectors by the factorized matrix \(\mathbf{H}_{4}\). Furthermore, when assessing computational complexity, left-right shift operations are typically left out because they are fairly simple and do not call for additional memory access. Take note that in this case, we account for the fact that, as opposed to 12, only 8 additions are needed to multiply a fourth-order Hadamard matrix by a vector. A thorough schematic representation of the matrix-vector multiplications of the appropriate vectors by the factorized matrix \(\mathbf{H}_{4}\) is shown in Figure 4. This is the so-called four-point \"fast Hadamard transform\". Figure 1: The data flow diagram that represents the calculation of elements \(\{s_{m}\}\), \(m=0,1,2,3\), according to expression (12). Figure 3: The data flow diagram that represents the calculation of elements \(\{s_{m}\}\), \(m=0,1,2,3\), according to expression (15). Figure 2: The data flow diagram of the fast algorithm for the multiplication of two quaternions. It should be noted that in applications related to quaternion-valued DSPs, often one of the multiplied quaternions contains coefficients that are real constants. In this case, the coefficients can be calculated in advance and stored in the processor's memory. Therefore, the arithmetic complexity of the proposed algorithm can be further reduced and it requires only eight real multiplications and only 20 real additions.