# The Fast Discrete Tchebichef Transform Algorithms for Short-Length Input Sequences
## 3 Reduced Complexity DTT Algorithms for Short-Length Input Sequences
### Algorithm for 7-Point DTT  
To design the algorithm for the 7-point 1D DTT we represent this transform as follows:  
\[\mathbf{Y}_{7\times 1}=diag(\mathbf{s}_{7\times 1})\ \mathbf{C}_{7}\mathbf{X}_{7 \times 1}, \tag{33}\]  
\[\text{where}\ \mathbf{C}_{7}= \begin{bmatrix}\mathbf{1}&\mathbf{1}&\mathbf{1}& \mathbf{1}&\mathbf{1}&\mathbf{1}&\mathbf{1}\\ \mathbf{-3}&\mathbf{-2}&\mathbf{-1}&\mathbf{0}&\mathbf{1}&\mathbf{2}& \mathbf{3}\\ \mathbf{5}&\mathbf{0}&\mathbf{-3}&\mathbf{-4}&\mathbf{-3}&\mathbf{0}&\mathbf{ 5}\\ \mathbf{-1}&\mathbf{1}&\mathbf{1}&\mathbf{0}&\mathbf{-1}&\mathbf{-1}&\mathbf{ 1}\\ \mathbf{3}&\mathbf{-7}&\mathbf{1}&\mathbf{6}&\mathbf{1}&\mathbf{-7}&\mathbf{ 3}\\ \mathbf{-1}&\mathbf{4}&\mathbf{-5}&\mathbf{0}&\mathbf{5}&\mathbf{-4}&\mathbf{ 1}\\ \mathbf{1}&\mathbf{-6}&\mathbf{15}&\mathbf{-20}&\mathbf{15}&\mathbf{-6}& \mathbf{1}\\ \end{bmatrix} ,\mathbf{Y}_{7\times 1}= \begin{bmatrix}y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ y_{4}\\ y_{5}\\ y_{6}\end{bmatrix} ,\mathbf{X}_{7\times 1}= \begin{bmatrix}x_{0}\\ x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ x_{5}\\ x_{6}\end{bmatrix} .\]  
Vector \(\mathbf{s}_{7\times 1}= \begin{bmatrix}5_{0}^{(7)},s_{1}^{(7)},s_{2}^{(7)},s_{3}^{(7) },s_{4}^{(7)},s_{5}^{(7)},s_{6}^{(6)}\end{bmatrix} ^{\text{T}}\) is computed by expression (5), where \(s_{1}^{(7)}=\frac{2p_{1}}{\sqrt{d(1,\,N)}}\), \(s_{3}^{(7)}=\frac{5p_{3}}{\sqrt{d(3,\,N)}}\), \(s_{5}^{(7)}=\frac{3p_{5}}{\sqrt{d(5,\,N)}}\), \(s_{6}^{(7)}=\frac{p_{6}}{N\sqrt{d(6,\,N)}}\). As a result, we yield \(\mathbf{s}_{7\times 1}=[\frac{1}{\sqrt{7}},\frac{1}{\sqrt{28}},\frac{1}{2\sqrt{21}}, \frac{1}{\sqrt{6}},\frac{1}{\sqrt{154}},\frac{1}{2\sqrt{21}},\frac{1}{\sqrt{ 924}}]^{\text{T}}\) or \(\mathbf{s}_{7\times 1}\approx[0.3780,\,0.1890,\,0.1091,\,0.4082,\,0.0806,\,0.1091,\,0.03 29]^{\text{T}}\). If we denote \(a_{7}=1;b_{7}=2;c_{7}=3;d_{7}=4;c_{7}=5;f_{7}=6;g_{7}=7;h_{7}=15;k_{7}=20;\) matrix \(\mathbf{C}_{7}\) can be represented as  
\[\mathbf{C}_{7}= \begin{bmatrix}\mathbf{a}_{7}&\mathbf{a}_{7}&\mathbf{a}_{7}&\mathbf{a}_{7}&\mathbf{a }_{7}&\mathbf{a}_{7}&\mathbf{a}_{7}\\ -c_{7}&-b_{7}&-a_{7}&\mathbf{0}&\mathbf{a}_{7}&\mathbf{b}_{7}&\mathbf{c}_{7}\\ \mathbf{e}_{7}&\mathbf{0}&-c_{7}&-d_{7}&-c_{7}&\mathbf{0}&\mathbf{e}_{7}\\ -a_{7}&\mathbf{a}_{7}&\mathbf{a}_{7}&\mathbf{0}&-a_{7}&-a_{7}&\mathbf{a}_{7}\\ c_{7}&-g_{7}&\mathbf{a}_{7}&f_{7}&\mathbf{a}_{7}&-g_{7}&c_{7}\\ -\mathbf{a}_{7}&\mathbf{d}_{7}&-e_{7}&\mathbf{0}&\mathbf{e}_{7}&-d_{7}&\mathbf{a}_{7}\\ \mathbf{a}_{7}&-f_{7}&\mathbf{h}_{7}&-k_{7}&\mathbf{h}_{7}&-f_{7}&\mathbf{a}_{7}\\ \end{bmatrix} . \tag{34}\]  
We developed the 7-point real DTT algorithm using a sparse matrix factorization [8; 28; 29; 41] and the structural approach [37; 40]. The structural approach was used to decompose the initial DTT matrix into submatrices. Sparse matrix factorization allows for the design of the data flow graph of the algorithm. To change the order of columns and rows, we define permutations \(\pi_{7}\) and \(\pi_{8}\) as follows:  
\[\pi_{7}= \begin{pmatrix}1&2&3&4&5&6&7\\ 1&7&2&4&6&3&5\end{pmatrix} ,\;\pi_{8}= \begin{pmatrix}1&2&3&4&5&6&7\\ 2&4&6&1&3&5&7\end{pmatrix} . \tag{35}\]  
The permutation matrices are expressed as:  
\[\mathbf{P}_{7}^{(1)}= \begin{bmatrix}&&&1&&&\\ 1&&&&\\ &&&1&&\\ &1&&&&\\ &1&&&1&\\ &&&1&&&1\end{bmatrix} ;\mathbf{P}_{7}^{(0)}= \begin{bmatrix}1&&&&\\ &1&&&&\\ &&1&&\\ &&1&&\\ &&&1&\\ &&&1\end{bmatrix} . \tag{36}\]  
After permutation, matrix \(\mathbf{C}_{7}\) acquires the following structure:  
\[\mathbf{C}_{7}^{(a)}= \begin{bmatrix}-c_{7}&c_{7}&-\mathbf{b}_{7}&\mathbf{0}&\mathbf{b}_{7}& -\mathbf{a}_{7}&\mathbf{a}_{7}\\ -a_{7}&\mathbf{a}_{7}&\mathbf{a}_{7}&\mathbf{0}&-a_{7}&\mathbf{a}_{7}&-a_{7}\\ -a_{7}&\mathbf{a}_{7}&\mathbf{d}_{7}&\mathbf{0}&-a_{7}&-e_{7}&e_{7}\\ \mathbf{a}_{7}&\mathbf{a}_{7}&\mathbf{a}_{7}&\mathbf{a}_{7}&\mathbf{a}_{7}&\mathbf{a}_{7}\\ e_{7}&e_{7}&\mathbf{0}&-\mathbf{d}_{7}&\mathbf{0}&-c_{7}&-c_{7}\\ c_{7}&c_{7}&-\mathbf{g}_{7}&f_{7}&-g_{7}&a_{7}&a_{7}\\ a_{7}&\mathbf{a}_{7}&-f_{7}&-k_{7}&-f_{7}&\mathbf{h}_{7}&\mathbf{h}_{7}\\ \end{bmatrix} .