# The Fast Discrete Tchebichef Transform Algorithms for Short-Length Input Sequences
## 3 Reduced Complexity DTT Algorithms for Short-Length Input Sequences
### Algorithm for 5-Point DTT
\begin{bmatrix}\mathbf{A}_{2}^{(0)}&\mathbf{A}_{2}^{(0)}\\ \mathbf{B}_{2}^{(0)}&-\mathbf{B}_{2}^{(0)}\end{bmatrix} \), where \(\mathbf{A}_{2}^{(0)}= \begin{bmatrix}b_{5}&-\mathbf{a}_{5}\\ \mathbf{a}_{5}&-\mathbf{c}_{5}\end{bmatrix} \) and \(\mathbf{B}_{2}^{(0)}= \begin{bmatrix}-\mathbf{a}_{5}&\mathbf{b}_{5}\\ -\mathbf{b}_{5}&-\mathbf{a}_{5}\end{bmatrix} \). Hence, matrix \(\mathbf{C}_{4}^{(d)}\) can be factorized as [37; 38]:  
\[\mathbf{C}_{4}^{(d)}=(\mathbf{A}_{2}^{(0)}\oplus\mathbf{B}_{2}^{(0)})(\mathbf{ H}_{2}\otimes\mathbf{I}_{2}). \tag{18}\]  
Let us swap the rows of matrix \(\mathbf{A}_{2}^{(0)}\) and alter the sign of the second row of matrix \(\mathbf{B}_{2}^{(0)}\). Then, the obtained matrices \(\mathbf{A}_{2}^{(1)}= \begin{bmatrix}\mathbf{a}_{5}&-\mathbf{c}_{5}\\ \mathbf{b}_{5}&-\mathbf{a}_{5}\end{bmatrix} \) and \(\mathbf{B}_{2}^{(1)}= \begin{bmatrix}-\mathbf{a}_{5}&\mathbf{b}_{5}\\ \mathbf{b}_{5}&\mathbf{a}_{5}\end{bmatrix} \) match the templates \( \begin{bmatrix}\mathbf{a}&\mathbf{b}\\ \mathbf{c}&-\mathbf{a}\end{bmatrix} \) and \( \begin{bmatrix}\mathbf{c}&\mathbf{d}\\ \mathbf{d}&-\mathbf{e}\end{bmatrix} \), where \(\mathbf{a}\)\(=\mathbf{a}_{5}\); \(\mathbf{b}\)\(=\mathbf{-}_{5}\); \(\mathbf{c}\)\(=\mathbf{b}_{5}\); \(\mathbf{d}\)\(=\mathbf{b}_{5}\); \(\mathbf{e}\)\(=\mathbf{-}_{5}\). Then [37; 40],  
\[\mathbf{C}_{4}^{(d)}=\mathbf{P}_{4}(\mathbf{T}_{2\times 3}^{(3)}\oplus\mathbf{T}_{2 \times 3}^{(4)})\text{ diag}(\mathbf{b}_{5}-\mathbf{a}_{5},\ -\mathbf{c}_{5}+\mathbf{a}_{5},\ -\mathbf{a}_{5},\mathbf{-a}_{5}-\mathbf{b}_{5},\ \mathbf{b}_{5})(\mathbf{T}_{3\times 2}^{(4)} \oplus\mathbf{T}_{3\times 2}^{(3)})(\mathbf{H}_{2}\otimes\mathbf{I}_{2}), \tag{19}\]  
\[\text{where }\mathbf{P}_{4}= \begin{bmatrix}\mathbf{1}&\\ \mathbf{1}&\\ &\mathbf{1}&\\ &&-\mathbf{1}\end{bmatrix} ,\mathbf{T}_{2\times 3}^{(3)}= \begin{bmatrix} \mathbf{0}&\mathbf{1}&\mathbf{1}\\ \mathbf{1}&\mathbf{0}&\mathbf{1}\end{bmatrix} \text{, }\mathbf{T}_{3\times 2}^{(4)}= \begin{bmatrix} \mathbf{1}&\mathbf{0}\\ \mathbf{0}&\mathbf{1}\\ -\mathbf{1}&\mathbf{1}\end{bmatrix} \text{. Matrices }\mathbf{T}_{2\times 3}^{(4)}\text{ and }\]  
\(\mathbf{T}_{3\times 2}^{(3)}\) are defined as in expression (9). Based on Equations (16) and (19), we derive the factorization of the 5-point DTT matrix:  
\[\mathbf{Y}_{5\times 1}=diag(\mathbf{s}_{5\times 1})\mathbf{P}_{5}^{(1)}\mathbf{W}_ {5\times 6}\mathbf{W}_{6}^{(1)}\mathbf{W}_{6\times 8}\mathbf{D}_{8}\mathbf{W}_{8 \times 6}\mathbf{W}_{6}^{(0)}\mathbf{W}_{6\times 5}\mathbf{P}_{5}^{(0)}\mathbf{X}_{5 \times 1}, \tag{20}\]  
where  
\[\mathbf{W}_{6\times 8}=\mathbf{T}_{2\times 3}^{(3)}\oplus\mathbf{I}_{2} \oplus\mathbf{T}_{2\times 3}^{(4)},\ \mathbf{W}_{8\times 6}=\mathbf{T}_{3\times 2}^{(4)} \oplus\mathbf{I}_{2}\oplus\mathbf{T}_{3\times 2}^{(3)},\ \mathbf{D}_{8}=diag(1,-3,-1,2,1,-3,-1,2), \tag{21}\]  
\[\mathbf{P}_{5}^{(0)}= \begin{bmatrix}\mathbf{1}&&\\ &\mathbf{1}&&\\ &&\mathbf{1}&&\\ &&&\mathbf{1}\end{bmatrix} ,\ \mathbf{P}_{5}^{(1)}= \begin{bmatrix}\mathbf{1}&&\\ &\mathbf{1}&&\\ \mathbf{1}&&\\ &&\mathbf{1}\end{bmatrix} , \tag{22}\]  
\[\mathbf{W}_{6}^{(0)}= \begin{bmatrix}\mathbf{1}&&\mathbf{1}&&\\ &\mathbf{1}&&\\ &&\mathbf{1}&&\\ &&\mathbf{1}&&\\ \mathbf{1}&&-\mathbf{1}&\\ &\mathbf{1}&&-\mathbf{1}\end{bmatrix} ,\ \mathbf{W}_{6}^{(1)}= \begin{bmatrix} \mathbf{1}&&\\ \mathbf{1}&&\\ &\mathbf{1}&&\\ &&\mathbf{1}&&\\ &&\mathbf{1}&\\ &&\mathbf{1}&\\ &&\mathbf{-1}\end{bmatrix} , \tag{23}\]  
\[\mathbf{W}_{6\times 5}= \begin{bmatrix}\mathbf{1}&&\\ &\mathbf{1}&&\\ &\mathbf{1}&&\\ \mathbf{1}&\mathbf{1}&\mathbf{1}&\\ &&\mathbf{1}&\\ &&&\mathbf{1}\end{bmatrix} ,\ \mathbf{W}_{5\times 6}= \begin{bmatrix} \mathbf{1}&-\mathbf{1}&&\\ &\mathbf{1}&\mathbf{3}&&\\ &&\mathbf{1}/2&\mathbf{1}&\\ &&\mathbf{1}&\\ &&\mathbf{1}\end{bmatrix} . \tag{24}\]  
As was mentioned in Section 2, an empty cell in matrices means it contains zero.