# 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  
To develop the algorithm for 5-point 1D DTT, we express this transform as follows:  
\[\mathbf{Y}_{5\times 1}=diag(\mathbf{s}_{5\times 1})\mathbf{C}_{5}\mathbf{X}_{5 \times 1}, \tag{13}\]  
\[\text{where}\ \mathbf{C}_{5}= \begin{bmatrix}\mathbf{1}&\mathbf{1}&\mathbf{1}& \mathbf{1}&\mathbf{1}\\ -\mathbf{2}&-\mathbf{1}&\mathbf{0}&\mathbf{1}&\mathbf{2}\\ \mathbf{2}&-\mathbf{1}&-\mathbf{2}&-\mathbf{1}&\mathbf{2}\\ -\mathbf{1}&\mathbf{2}&\mathbf{0}&-\mathbf{2}&\mathbf{1}\\ \mathbf{1}&-\mathbf{4}&\mathbf{6}&-\mathbf{4}&\mathbf{1}\end{bmatrix} , \mathbf{Y}_{5\times 1}= \begin{bmatrix}y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ y_{4}\end{bmatrix} ,\mathbf{X}_{5\times 1}= \begin{bmatrix}x_{0}\\ x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{bmatrix} .\]  
The vector \(\mathbf{s}_{5\times 1}= \begin{bmatrix}s_{0}^{(5)},s_{1}^{(5)},s_{2}^{(5)},s_{3}^{(5) },s_{4}^{(5)}\end{bmatrix} ^{\text{T}}\) is computed by expression (5) where \(s_{1}^{(5)}=\frac{2p_{1}}{\sqrt{d(1,\,N)}}\), \(s_{3}^{(5)}=\frac{2p_{3}}{\sqrt{d(3,\,N)}}\), \(s_{4}^{(5)}=\frac{p_{4}}{N\sqrt{d(4,\,N)}}\). As a result, we yield \(\mathbf{s}_{5\times 1}= \begin{bmatrix}\frac{1}{\sqrt{5}},\frac{1}{\sqrt{10}},\frac{1} {\sqrt{14}},\frac{1}{\sqrt{10}},\frac{1}{\sqrt{70}}\end{bmatrix} ^{\text{T}}\) or \(\mathbf{s}_{5\times 1}= \begin{bmatrix}0.4472,0.3162,0.2673,0.3162,0.1195\end{bmatrix} ^{ \text{T}}\). Denoting \(a_{5}=1\); \(b_{5}=2\); \(c_{5}=4\); \(d_{5}=6\), we obtain the matrix  
\[\mathbf{C}_{5}^{(a)}= \begin{bmatrix}a_{5}&a_{5}&a_{5}&a_{5}\\ -b_{5}&-a_{5}&\mathbf{0}&a_{5}&\mathbf{b}_{5}\\ b_{5}&-a_{5}&-b_{5}&-a_{5}&b_{5}\\ -a_{5}&b_{5}&\mathbf{0}&-b_{5}&a_{5}\\ a_{5}&-c_{5}&d_{5}&-c_{5}&a_{5}\end{bmatrix} . \tag{14}\]  
Figure 2: The data flow graph of the 4-point DTT algorithm. We again apply the structural approach [37; 38; 39; 40] to develop the algorithm for 5-point 1D real DTT. The permutations \(\pi_{3}\) and \(\pi_{4}\) are defined to alter the order of columns and rows of matrix \(\mathbf{C}_{5}\), respectively, as  
\[\pi_{3}= \begin{pmatrix}1&2&3&4&5\\ 1&2&3&5&4\end{pmatrix} \text{ and }\pi_{4}= \begin{pmatrix}1&2&3&4&5\\ 3&5&1&4&2\end{pmatrix} . \tag{15}\]  
After permutation, the obtained matrix \(\mathbf{C}_{5}^{(b)}= \begin{bmatrix}\mathbf{b}_{5}&-\mathbf{a}_{5}&-\mathbf{b}_{5}&\mathbf{b} _{5}&-\mathbf{a}_{5}\\ \mathbf{a}_{5}&-\mathbf{c}_{5}&\mathbf{c}_{5}&\mathbf{a}_{5}&-\mathbf{c}_{5}\\ \mathbf{a}_{5}&\mathbf{a}_{5}&\mathbf{a}_{5}&\mathbf{a}_{5}&\mathbf{a}_{5}\\ -\mathbf{a}_{5}&\mathbf{b}_{5}&\mathbf{0}&\mathbf{a}_{5}&-\mathbf{b}_{5}\\ -\mathbf{b}_{5}&-\mathbf{a}_{5}&\mathbf{0}&\mathbf{b}_{5}&\mathbf{a}_{5}\end{bmatrix} \) is decomposed into two components [37; 39]:  
\[\mathbf{C}_{5}^{(b)}=\mathbf{C}_{5}^{(c)}+\mathbf{C}_{5}^{(d)}, \tag{16}\]  
\[\text{where }\mathbf{C}_{5}^{(c)}= \begin{bmatrix}&-\mathbf{b}_{5}&\\ &\mathbf{d}_{5}&\\ \mathbf{a}_{5}&\mathbf{a}_{5}&\mathbf{a}_{5}&\mathbf{a}_{5}\\ &\mathbf{0}&\\ &\mathbf{0}&\end{bmatrix} \text{ and }\mathbf{C}_{5}^{(d)}= \begin{bmatrix}\mathbf{b}_{5}&-\mathbf{a}_{5}& \mathbf{b}_{5}&-\mathbf{a}_{5}\\ \mathbf{a}_{5}&-\mathbf{c}_{5}&\mathbf{a}_{5}&-\mathbf{c}_{5}\\ -\mathbf{a}_{5}&\mathbf{b}_{5}&\mathbf{a}_{5}&-\mathbf{b}_{5}\\ -\mathbf{b}_{5}&-\mathbf{a}_{5}&\mathbf{b}_{5}&\mathbf{a}_{5}\end{bmatrix} .\]  
The structure of matrix \(\mathbf{C}_{5}^{(c)}\) allows for reducing the number of operations without further transforms because the elements in the third row are identical except for the sign. After eliminating the rows and columns having only zero elements in matrix \(\mathbf{C}_{5}^{(d)}\), we yield matrix \(\mathbf{C}_{4}^{(d)}\):  
\[\mathbf{C}_{4}^{(d)}= \begin{bmatrix}\mathbf{b}_{5}&-\mathbf{a}_{5}&\mathbf{b}_{5}&-\mathbf{a }_{5}\\ \mathbf{a}_{5}&-\mathbf{c}_{5}&\mathbf{a}_{5}&-\mathbf{c}_{5}\\ -\mathbf{a}_{5}&\mathbf{b}_{5}&\mathbf{a}_{5}&-\mathbf{b}_{5}\\ -\mathbf{b}_{5}&-\mathbf{a}_{5}&\mathbf{b}_{5}&\mathbf{a}_{5}\end{bmatrix} . \tag{17}\]  
Matrix \(\mathbf{C}_{4}^{(d)}\) matches the template \(