# The Fast Discrete Tchebichef Transform Algorithms for Short-Length Input Sequences
## 3 Reduced Complexity DTT Algorithms for Short-Length Input Sequences
### Algorithm for 6-Point DTT  
Let us obtain the algorithm for 6-point 1D DTT, which is expressed as follows:  
\[\textbf{Y}_{6\times 1}=\textit{diag}(\textbf{s}_{6\times 1})\textbf{C}_{6} \textbf{X}_{6\times 1}, \tag{25}\]  
\[\text{where }\textbf{C}_{6}= \begin{bmatrix}\textbf{1}&\textbf{1}&\textbf{1}& \textbf{1}&\textbf{1}&\textbf{1}\\ -\textbf{5}&-\textbf{3}&-\textbf{1}&\textbf{1}&\textbf{3}&\textbf{5}\\ \textbf{5}&-\textbf{1}&-\textbf{4}&-\textbf{4}&-\textbf{1}&\textbf{5}\\ -\textbf{5}&\textbf{7}&\textbf{4}&-\textbf{4}&-\textbf{7}&\textbf{5}\\ \textbf{1}&-\textbf{3}&\textbf{2}&\textbf{2}&\textbf{2}&-\textbf{3}&\textbf{1} \\ -\textbf{1}&\textbf{5}&-\textbf{10}&\textbf{10}&-\textbf{5}&\textbf{1}\\ \end{bmatrix} ,\textbf{Y}_{6\times 1}= \begin{bmatrix}y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ y_{4}\\ y_{5}\end{bmatrix} ,\textbf{X}_{6\times 1}= \begin{bmatrix}x_{0}\\ x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ x_{5}\end{bmatrix} .\]  
The vector \(\textbf{s}_{6\times 1}= \begin{bmatrix}s_{0}^{(6)},s_{1}^{(6)},s_{2}^{(6)},s_{3}^{(6)},s_{4}^{(6)},s_{5}^{(6)}\end{bmatrix} ^{\mathrm{T}}\) is computed by expression (5), where \(s_{2}^{(6)}=\frac{2p_{2}}{3\sqrt{d(2,N)}},s_{3}^{(6)}=\frac{2p_{3}}{3\sqrt{d(3, N)}}\). As a result, we yield \(\textbf{s}_{6\times 1}{=} \begin{bmatrix}\frac{1}{\sqrt{6}},\frac{1}{\sqrt{70}}, \frac{1}{2\sqrt{21}},\frac{1}{2\sqrt{45}},\frac{1}{\sqrt{28}},\frac{1}{\sqrt{2 52}}\end{bmatrix} ^{\mathrm{T}}\) or \(\textbf{s}_{6\times 1}{\approx}[0.4082,0.1195,0.1091,0.0745,0.1890,0.0630]^{ \mathrm{T}}\). Let us denote \(a_{6}=1\); \(b_{6}=2\); \(c_{6}=3\); \(d_{6}=4\); \(e_{6}=5\); \(f_{6}=7\); \(g_{6}=10\); then, matrix \(\textbf{C}_{6}\) is represented as  
\[\textbf{C}_{6}^{(a)}= \begin{bmatrix}a_{6}&a_{6}&a_{6}&a_{6}&a_{6}&a_{6}\\ -e_{6}&-e_{6}&-a_{6}&a_{6}&c_{6}&e_{6}\\ e_{6}&-a_{6}&-d_{6}&-d_{6}&-a_{6}&e_{6}\\ -e_{6}&f_{6}&d_{6}&-d_{6}&-f_{6}&e_{6}\\ a_{6}&-e_{6}&b_{6}&b_{6}&-c_{6}&a_{6}\\ -a_{6}&e_{6}&-g_{6}&g_{6}&-e_{6}&a_{6}\\ \end{bmatrix} . \tag{26}\]  
The columns and rows of \(\textbf{C}_{6}\) are permutated according to \(\pi_{5}\) and \(\pi_{6}\), which are defined in the following form: \(\pi_{5}= \begin{pmatrix}1&2&3&4&5&6\\ 1&6&3&4&2&5\end{pmatrix} \) and \(\pi_{6}= \begin{pmatrix}1&2&3&4&5&6\\ 2&4&1&6&3&5\end{pmatrix} \). The permutation matrices are as follows:  
\[\textbf{P}_{6}^{(1)}= \begin{bmatrix}&\textbf{1}&&\\ \textbf{1}&&\\ &\textbf{1}&&\\ &\textbf{1}&&\\ &&&\textbf{1}\\ &&&\textbf{1}\\ &&&\textbf{1}\end{bmatrix} ,\textbf{P}_{6}^{(0)}= \begin{bmatrix}\textbf{1}&&&& \\ &&\textbf{1}\\ &&\textbf{1}&&\\ &\textbf{1}&&\\ &\textbf{1}&&\\ &&\textbf{1}\end{bmatrix} . \tag{27}\]  
The resulting matrix  
\[\textbf{C}_{6}^{(b)}= \begin{bmatrix}-e_{6}&e_{6}&-a_{6}&a_{6}&-c_{6}&c_{6}\\ -e_{6}&e_{6}&d_{6}&-d_{6}&f_{6}&-f_{6}\\ a_{6}&a_{6}&a_{6}&a_{6}&a_{6}&a_{6}\\ -a_{6}&a_{6}&-g_{6}&g_{6}&e_{6}&-e_{6}\\ e_{6}&e_{6}&-d_{6}&-d_{6}&-a_{6}&-a_{6}\\ a_{6}&a_{6}&b_{6}&b_{6}&-c_{6}&-c_{6}\end{bmatrix}  \tag{28}\]  
contains repeated elements that enable butterfly module extraction and construction of the data flow graph for 6-point 1D DTT calculation. A derived data flow graph of the proposed 6-point 1D DTT algorithm is shown in Figure 4.  
Further, we compose the factorization of the matrix of 6-point 1D DTT from the matrices for calculations at each layer of the graph. Thus, at the first layer, we obtain the matrix \(\mathbf{W}_{6}=\mathbf{W}_{2}\oplus\mathbf{W}_{2}\oplus\mathbf{W}_{2}\), where \(\mathbf{W}_{2}= \begin{bmatrix}-1&1\\ 1&1\end{bmatrix} \). The second layer of calculations is described by matrix \(\mathbf{W}_{16\times 6}\) which can be expressed via matrix \(\left(\mathbf{W}_{16\times 6}\right)^{\text{T}}\) as follows:  
\[\left(\mathbf{W}_{16\times 6}\right)^{\text{T}}=\left[ \begin{array}{ccccccccccccc }&1&1&&&&&&&&\\ &&1&1&&&&&&&&\\ 1&&&&1&1&&&&&&\\ &&&&&&&&1&1&&&&\\ &&&&&&&&1&1&&1&\\ &&&&&&&&-1&&&1\end{array} \right]. \tag{29}\]  
In this matrix and the matrices below, an empty cell indicates that it contains zero.