# The Fast Discrete Tchebichef Transform Algorithms for Short-Length Input Sequences
## 3 Reduced Complexity DTT Algorithms for Short-Length Input Sequences
### Algorithm for 4-Point DTT  
Let us construct the algorithm for 4-point real-valued DTT, which is expressed as  
\[\mathbf{Y}_{4\times 1}=diag(\mathbf{s}_{4\times 1})\ \mathbf{C}_{4}\mathbf{X}_{4 \times 1}, \tag{8}\]  
where \(\mathbf{Y}_{4\times 1}=[y_{0},\,y_{1},\,y_{2},y_{3}]^{\mathrm{T}}\), \(\mathbf{X}_{4\times 1}=[x_{0},\,x_{1},\,x_{2},\,x_{3}]^{\mathrm{T}}\), \(\mathbf{C}_{4}=\begin{bmatrix}\mathbf{1}&\mathbf{1}&\mathbf{1}&\mathbf{1}\\ -\mathbf{3}&-\mathbf{1}&\mathbf{1}&\mathbf{3}\\ \mathbf{1}&-\mathbf{1}&-\mathbf{1}&\mathbf{1}\\ -\mathbf{1}&\mathbf{3}&-\mathbf{3}&\mathbf{1}\end{bmatrix}\). Vector \(\mathbf{s}_{4\times 1}=\begin{bmatrix}s_{0}^{(4)},s_{1}^{(4)},s_{2}^{(4)},s_{3}^{(4)} \end{bmatrix}^{\mathrm{T}}\) was computed using expression (5) as \(\mathbf{s}_{4\times 1}{=}\begin{bmatrix}\frac{1}{2},\frac{1}{\sqrt{20}},\, \frac{1}{2},\frac{1}{\sqrt{20}}\end{bmatrix}^{\mathrm{T}}\) or \(\mathbf{s}_{4\times 1}{\approx}[0.5000,0.2236,0.5000,0.2236]^{\mathrm{T}}\).  
We use the structural approach [37; 38; 39; 40] to design the algorithm for 4-point real DTT. Let us define the permutations \(\pi_{1}=\begin{pmatrix}1&2&3&4\\ 1&3&2&4\end{pmatrix}\) and \(\pi_{2}=\begin{pmatrix}1&2&3&4\\ 1&2&4&3\end{pmatrix}\) for altering the order of the rows and columns of matrix \(\mathbf{C}_{4}\), respectively. The obtained matrix \(\mathbf{C}_{4}^{(a)}\) matches the matrix pattern \(\begin{bmatrix}\mathbf{A}_{2}&\mathbf{A}_{2}\\ \mathbf{B}_{2}&-\mathbf{B}_{2}\end{bmatrix}\) where \(\mathbf{A}_{2}=\mathbf{H}_{2}\), \(\mathbf{B}_{2}=\begin{bmatrix}-3&-1\\ -1&3\end{bmatrix}\). Therefore, \(\mathbf{C}_{4}^{(a)}=(\mathbf{A}_{2}\oplus\mathbf{B}_{2})(\mathbf{H}_{2} \otimes\mathbf{I}_{2})\). The matrix \(\mathbf{B}_{2}\) can be decomposed as [37; 38]:  
\[\mathbf{B}_{2}=\mathbf{T}_{2\times 3}^{(4)}diag(-2,4,-1)\mathbf{T}_{3\times 2}^{(3)}, \tag{9}\]  
where \(\mathbf{T}_{3\times 2}^{(3)}=\begin{bmatrix}1&0\\ 0&1\\ 1&1\end{bmatrix}\), \(\mathbf{T}_{2\times 3}^{(4)}=\begin{bmatrix}1&0&1\\ 0&1&1\end{bmatrix}\).  
Figure 1: The data flow graph of the three-point DTT algorithm.  
We give the matrix factorization for the algorithm of 4-point DTT as follows:  
\[\mathbf{Y}_{4\times 1}=diag(\mathbf{s}_{4\times 1})\mathbf{P}_{4}^{(1)}\mathbf{W }_{4\times 5}\mathbf{D}_{5}\mathbf{W}_{5\times 4}\mathbf{W}_{4}\mathbf{P}_{4}^{(0)} \mathbf{X}_{4\times 1}, \tag{10}\]  
where  
\[\mathbf{D}_{5}=diag(1,\ 1,\ -2,\ 4,\ -1);\ \mathbf{W}_{4\times 5}=\mathbf{I}_{2 }\oplus\mathbf{T}_{2\times 3}^{(4)},\mathbf{W}_{5\times 4}=\mathbf{H}_{2} \oplus\mathbf{T}_{3\times 2}^{(3)},\mathbf{W}_{4}=\mathbf{H}_{2}\otimes \mathbf{I}_{2}, \tag{11}\]  
\[\mathbf{P}_{4}^{(1)}=\begin{bmatrix}\mathbf{1}&&\\ &\mathbf{1}&\\ &\mathbf{1}&\\ &&\mathbf{1}\end{bmatrix},\ \mathbf{P}_{4}^{(0)}=\begin{bmatrix}\mathbf{1}&&\\ &\mathbf{1}&\\ &&\mathbf{1}\\ &&\mathbf{1}\end{bmatrix}. \tag{12}\]  
Figure 2 shows a data flow graph of the proposed four-point DTT algorithm. Note that for \(N=4\), the initial 4-point real DTT requires 8 real-valued multiplications, 8 shifts, and 12 additions. If we use the proposed four-point DTT algorithm, then the number of multiplications, additions, and shifts may be reduced from 8 to 2, from 12 to 9, and from 8 to 5, respectively.