# The Fast Discrete Tchebichef Transform Algorithms for Short-Length Input Sequences
## 3 Reduced Complexity DTT Algorithms for Short-Length Input Sequences
### Algorithm for 8-Point DTT  
Let us design the algorithm for 8-point DTT. Eight-point DTT is expressed as follows:  
\[\mathbf{Y}_{8\times 1}=diag(\mathbf{s}_{8\times 1})\ \mathbf{C}_{8}\mathbf{X}_{8 \times 1}, \tag{47}\]  
\[\text{where}\ \mathbf{C}_{8}= \begin{bmatrix}\mathbf{1}&\mathbf{1}&\mathbf{1}& \mathbf{1}&\mathbf{1}&\mathbf{1}&\mathbf{1}&\mathbf{1}\\ \mathbf{-7}&\mathbf{-5}&\mathbf{-3}&\mathbf{-1}&\mathbf{1}&\mathbf{3}& \mathbf{5}&\mathbf{7}\\ \mathbf{7}&\mathbf{1}&\mathbf{-3}&\mathbf{-5}&\mathbf{-5}&\mathbf{-3}& \mathbf{1}&\mathbf{7}\\ \mathbf{-7}&\mathbf{5}&\mathbf{7}&\mathbf{3}&\mathbf{-3}&\mathbf{-7}&-\mathbf{ 5}&\mathbf{7}\\ \mathbf{7}&\mathbf{-13}&\mathbf{-3}&\mathbf{9}&\mathbf{9}&\mathbf{-3}&\mathbf{ -13}&\mathbf{7}\\ \mathbf{-7}&\mathbf{23}&\mathbf{-17}&\mathbf{-15}&\mathbf{15}&\mathbf{17}& \mathbf{-23}&\mathbf{7}\\ \mathbf{1}&\mathbf{-5}&\mathbf{9}&\mathbf{-5}&\mathbf{-5}&\mathbf{9}&\mathbf{ -5}&\mathbf{1}\\ \mathbf{-1}&\mathbf{7}&\mathbf{-21}&\mathbf{35}&\mathbf{-35}&\mathbf{21}&- \mathbf{7}&\mathbf{1}\\ \end{bmatrix} ,\ \mathbf{Y}_{8\times 1}= \begin{bmatrix}y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ y_{4}\\ y_{5}\\ y_{6}\\ y_{7}\end{bmatrix} ,\mathbf{X}_{8\times 1}= \begin{bmatrix}x_{0}\\ x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ x_{5}\\ x_{6}\\ x_{7}\end{bmatrix} .\]  
The vector \(\mathbf{s}_{8\times 1}= \begin{bmatrix}s_{0}^{(8)},s_{1}^{(8)},s_{2}^{(8)},s_{3}^{(8)},s_{4}^{(8)},s_{5}^{(8)},s_{6}^{(8)},s_{7}^{(8)}\end{bmatrix} ^{\mathsf{T}}\) is computed by expression (5). As a result, we obtain \(\mathbf{s}_{8\times 1}=[\frac{1}{2\sqrt{2}},\frac{1}{\sqrt{168}},\frac{1}{\sqrt{168}},\frac{1}{\sqrt{264}},\frac{1}{\sqrt{616}},\frac{1}{\sqrt{2184}},\frac{1}{ \sqrt{264}},\frac{1}{\sqrt{3432}}]^{\mathsf{T}}\) or \(s_{8\times 1}\approx[0.3536,\,0.0772,\,0.0772,\,0.0615,\,0.0403,\,0.0214,\,0.0615, \,0.017]^{\mathsf{T}}\). If we denote \(a_{8}=1;\,b_{8}=3;\,c_{8}=5;\,d_{8}=7;\,f_{8}=13;\,g_{8}=21;h_{8}=35;\,k_{8}=23 ;\,l_{8}=17;\,m_{8}=15\); then matrix \(\mathbf{C}_{8}\) can be represented as  
Matrix \(\mathbf{C}_{8}^{(a)}\) acquires the following structure:  
\[\mathbf{C}_{8}^{(b)}= \begin{bmatrix}a_{8}&a_{8}&a_{8}&a_{8}&a_{8}&a_{8}&a_{8}&a_{8 }\\ d_{8}&d_{8}&a_{8}&a_{8}&-b_{8}&-b_{8}&-c_{8}&-c_{8}\\ -d_{8}&d_{8}&-c_{8}&c_{8}&-b_{8}&b_{8}&-a_{8}&a_{8}\\ -d_{8}&d_{8}&c_{8}&-c_{8}&d_{8}&-d_{8}&b_{8}&-b_{8}\\ d_{8}&d_{8}&-f_{8}&-f_{8}&-b_{8}&-b_{8}&e_{8}&e_{8}\\ a_{8}&a_{8}&-e_{8}&-e_{8}&e_{8}&e_{8}&-c_{8}&-c_{8}\\ -d_{8}&d_{8}&k_{8}&-k_{8}&-l_{8}&l_{8}&-m_{8}&m_{8}\\ -a_{8}&a_{8}&d_{8}&-d_{8}&-g_{8}&g_{8}&h_{8}&-h_{8}\end{bmatrix} . \tag{50}\]  
The repeated elements are contained in matrix \(\mathbf{C}_{8}^{(b)}\). They facilitate the design of butterfly modules in the data flow graph for the 8-point 1D DTT calculation. An obtained data flow graph of the developed 8-point 1D DTT algorithm is presented in Figure 6.  
Let us derive the factorization of the matrix of 8-point 1D DTT. We consider the matrices for computations on each layer of the graph. The matrices  
Figure 6: The data flow graph of the eight-point 1D DTT algorithm. \[\mathbf{W}_{8}=\mathbf{H}_{2}\oplus\mathbf{H}_{2}\oplus\mathbf{H}_{2}\oplus \mathbf{H}_{2}\oplus\mathbf{H}_{2}\text{ and }\mathbf{W}_{18\times 8}=\mathbf{1}_{2\times 1}\oplus\mathbf{1}_{2 \times 1}\oplus\mathbf{1}_{3\times 1}\oplus\mathbf{1}_{3\times 1}\oplus\mathbf{1}_{2 \times 1}\oplus\mathbf{1}_{2\times 1}\oplus\mathbf{1}_{2\times 1} \tag{51}\]  
are obtained at the first and second layers of the graph, respectively. We have the diagonal matrix  
\[\mathbf{D}_{18}=diag(1,\,7,\,7,\,1,\,1,\,1,\,4,\,5,\,2,\,1,\,2,\,1,\,4,\,1,\,1, \,4,\,1,\,2) \tag{52}\]  
at the third layer of calculation. The fourth, fifth and sixth layers of computations of the data flow graph in Figure 6 are implemented with the matrices \(\mathbf{W}_{22\times 18}\), \(\mathbf{W}_{23\times 22}\), and \(\mathbf{D}_{23}\):  
\[\mathbf{W}_{22\times 18}=\mathbf{I}_{5} \begin{bmatrix}1&1\\ &1\end{bmatrix} \oplus \begin{bmatrix}1\\ &1\end{bmatrix} \oplus 1\oplus \begin{bmatrix}1\\ &1\\ &1\end{bmatrix} \oplus