# A Novel Low-Complexity and Parallel Algorithm for DCT IV Transform and Its GPU Implementation
## 3 Proposed DCT IV Algorithm for Parallel Implementation  
Due to the wide range of applicability of the DCT IV transform and the interest shown by the academic community, we present here the mathematical background of a novel implementation of this algorithm. \begin{table}
\begin{tabular}{c c c c c c} \hline  
For a real input sequence \(x(i):i=0,\;1,\;\ldots,\;N-1\), type IV DCT (DCT-IV) is defined using the following equation [44]:  
\[Y(k)=\sqrt{\frac{2}{N}}\cdot\sum_{i=0}^{N-1}x(i)\cdot cos[(2i+1)(2k+1)\,\alpha] \tag{1}\]  
where \(k=0,\;1\;,\ldots,\;N-1\;\) and  
\[\alpha=\frac{\pi}{4N} \tag{2}\]  
To simplify the presentation, we remove the constant coefficient \(\sqrt{\frac{2}{N}}\) from the DCT-IV equation, and we add this multiplication at the end of the algorithm. Equations (1) and (2) represent the classical definition of DCT IV and cannot be implemented efficiently in parallel with low complexity. In the following, we propose a new algorithm that, in addition to being an efficient parallel implementation, by braking the computation into four or eight computational structures that can be computed in parallel, has a low arithmetic complexity by using the sub-expression sharing technique, as evidenced below. In order to obtain an efficient parallel algorithm, we need to reformulate Equation (1) using some auxiliary input and output restructuring sequences, and we reordered them in an appropriate manner. In the following, we consider the transform length a prime number N = 17. The output sequence \(\{Y(k):\;k=1\;,2\;,\ldots,\;N-1\}\) can be recursively computed using the following equations:  
\[Y(0)=x_{C}(0)+\sum_{i=1}^{(N-1)/2}[x_{C}(i)+x_{C}(N-1-i)] \tag{3}\]  
\[Y(k)=\mathit{Tc}(k)-Y(k-1)\;\text{for}\;k=1\;,\;2,\;\ldots,\;N-1 \tag{4}\]  
where we used an auxiliary output sequence \(\{T_{c}(k):k=1,\;2\;,\;\ldots,\;N-1\}\) and the following auxiliary input sequence:  
\[x_{C}(i)=x(i)\cdot cos[(2i+1)\,\alpha]\;\text{for}\;i=0,1,\ldots,N-1 \tag{5}\]  
The input auxiliary sequence \(\{x_{a}(i):i=0,\;\ldots,\;N-1\}\) is recursively computed as follows:  
\[x_{a}(N-1)=x_{C}(N-1) \tag{6}\]  
\[x_{a}(i)=x_{C}(i)-x_{a}(i+1) \tag{7}\]  
for \(i=N-2,\;\ldots,\;1,\;0\). For a compact expression of the following relations, we note:  
\[A= \begin{bmatrix}1&1&1&0&-1\\ 1&-1&1&-1&0\\ 1&1&-1&0&1\\ 1&-1&-1&1&0\end{bmatrix}  \tag{8}\]  
\[B= \begin{bmatrix}1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&0&-1&0\\ 0&1&0&-1\end{bmatrix}  \tag{9}\]\[C= \begin{bmatrix}1/4&1/4&1/4&1/4\\ 1/4&-1/4&1/4&-1/4\\ 1/2&0&-1/2&0\\ 1/2&-1/2&-1/2&1/2\\ 1/2&1/2&-1/2&-1/2\end{bmatrix}  \tag{10}\]  
Using the above auxiliary input and output sequences and sub-expression sharing technique, we obtained the below equations that can be efficiently computed in parallel and have a reduced arithmetic complexity that allow for an efficient implementation on a GPU significantly faster than the classical algorithm. Thus, we have:  
\[ \begin{bmatrix}T(6)\\ -T(14)\\ T(10)\\ -T(12)\end{bmatrix}  \tag{11}\] \[= \begin{bmatrix}-[x_{a}(1)+x_{a}(16)]&x_{a}(8)+x_{a}(9)&-[x_{a}(4 )+x_{a}(13)]&x_{a}(2)+x_{a}(15)\\ x_{a}(2)+x_{a}(15)&-[x_{a}(1)+x_{a}(16)]&x_{a}(8)+x_{a}(9)&-[x_{a}(4)+x_{a}(13) ]\\ -[x_{a}(4)+x_{a}(13)]&x_{a}(2)+x_{a}(15)&-[x_{a}(1)+x_{a}(16)]\\ x_{a}(8)+x_{a}(9)&-[x_{a}(4)+x_{a}(13)]&x_{a}(2)+x_{a}(15)&-[x_{a}(1)+x_{a}(16 )]\\ \end{bmatrix} x \begin{bmatrix}-2 cos(12\alpha)\\ 2 cos(28\alpha)\\ -2 cos(20\alpha)\\ 2 cos(24\alpha)\end{bmatrix} \] \[+ \begin{bmatrix}x_{a}(3)+x_{a}(14)&-[x_{a}(7)+x_{a}(10)]&-[x_{a} (5)+x_{a}(12)]&x_{a}(6)+x_{a}(11)\\ -[x_{a}(6)+x_{a}(11)]&x_{a}(3)+x_{a}(14)&x_{a}(7)+x_{a}(10)&-[x_{a}(5)+x_{a}(1 2)]\\ x_{a}(5)+x_{a}(12)&-[x_{a}(6)+x_{a}(11)]&-[x_{a}(3)+x_{a}(14)]&x_{a}(7)+x_{a}(1 0)\\ -[x_{a}(7)+x_{a}(10)]&x_{a}(5)+x_{a}(12)&x_{a}(6)+x_{a}(11)&-[x_{a}(3)+x_{a}(1 4)]\end{bmatrix} x \begin{bmatrix}2 cos(32\alpha)\\ -2 cos(16\alpha)\\ -2 cos(8\alpha)\\ 2 cos(4\alpha)\end{bmatrix} \]  
Using sub-expression sharing to reduce the arithmetic complexity, we can reformulate the previous equation as follows:  
\[