# The Fast Discrete Tchebichef Transform Algorithms for Short-Length Input Sequences
## 3 Reduced Complexity DTT Algorithms for Short-Length Input Sequences
### Generalization of the Proposed Algorithms  
Let us describe a generalization for \(N>8\) regarding the proposed \(N\)-point DTT algorithms, where \(N\) ranges from 3 to 8. The \(N\)-point DTT with \(N>8\) is also expressed by Equation (4). Further, we consider the even and odd lengths of input sequences separately.  
At first, we suppose that \(N\) is even. Based on the symmetry of integer DTT, the following permutation of columns of the integer 1D DTT matrix \(\mathbf{C}_{N}\) can be used:  
\[\pi_{N}=\begin{pmatrix}1&2&3&4&5&6&\ldots&N-1&N\\ 1&N&2&N-1&3&N-2&\ldots&N/2&N/2+1\end{pmatrix}. \tag{59}\]  
Rearranging the rows is not necessary at all; however, if it is feasible to organize the rows such that pairs of equal-signed elements create \(2\times 2\) blocks, which can help minimize the number of additions and shifts required. This trick offers a reducing the number of integer multiplications.  
Next, we start designing the data flow graph from inputs to outputs by adding the permutation of inputs at the first computational level. Then, we pairwise combine the outputs from the first computational level into butterfly modules and the outputs of each such module are transmitted to a line of integer multipliers. Every multiplication by an integer can be implemented by additions and shifts. The results of the multiplications are added together to obtain the outputs of integer DTT, and permutation of outputs is performed. The outputs of real DTT are calculated using the outputs of integer DTT multiplied by the specific coefficients as described in Equation (4).  
Let us consider an odd \(N\). The order of the columns of the integer DTT matrix \(\mathbf{C}_{N}\) is changed using the permutation  
\[\pi_{N}=\begin{pmatrix}1&2&3&4&\ldots&[N/2]&[N/2]+1&[N/2]+2&\ldots\\ 1&N&2&N-1&\ldots&[N/2]&[N/2]+1&[N/2]+2&\ldots\end{pmatrix}, \tag{60}\]  
where \([N/2]\) denotes the whole part of \(N/2\). Columns \([N/2]\), \([N/2]+1\), and \([N/2]+2\) remain in their places, and the remaining columns are grouped in pairs as in Equation (60). The symmetry of DTT is taken into account again.  
The first and \([N/2]+1\) rows are swapped. The order of the remaining rows can be left unchanged, or they can be swapped to reduce the number of multiplications and shifts as in the case of even \(N\).  
Next, we represent the transform matrix \(\mathbf{C}_{N}^{(a)}\) after permutations as the sum of two matrices \(\mathbf{C}_{N}^{(b)}\) and \(\mathbf{C}_{N}^{(c)}\) of the same size as matrix \(\mathbf{C}_{N}^{(a)}\):  
\[\mathbf{C}_{N}^{(a)}=\mathbf{C}_{N}^{(b)}+\mathbf{C}_{N}^{(c)}. \tag{61}\]  
Matrix \(\mathbf{C}_{N}^{(b)}\) includes the \([N/2]+1\) row and the \([N/2]+1\) column of matrix \(\mathbf{C}_{N}^{(a)}\), and the rest of its elements are zero. In matrix \(\mathbf{C}_{N}^{(c)}\), the \([N/2]+1\) row and the \([N/2]+1\) column are filled with zeros, and the rest of the elements are the same as in matrix \(\mathbf{C}_{N}^{(a)}\). Then, matrix \(\mathbf{C}_{N}^{(b)}\) has identical entries in its \([N/2]+1\) row. This allows us to reduce the number of operations without further transformations. Next, we eliminate the row and column containing only zero entries in matrix \(\mathbf{C}_{N}^{(c)}\) and obtain matrix \(\mathbf{C}_{N-1}^{(c)}\). Matrix \(\mathbf{C}_{N-1}^{(c)}\) has an even size. Therefore, a data flow graph of the fast algorithm for the transform with matrix \(\mathbf{C}_{N-1}^{(c)}\) can be constructed similarly to the previous case.  
To obtain the data flow graph for the transform with matrix \(\mathbf{C}_{N}^{(a)}\), we add the path, corresponding to the \([N/2]+1\) output after the column permutation, to the data flow graph for the transform with matrix \(\mathbf{C}_{N-1}^{(c)}\). The edges of the resulting graph that enter thenode at this path immediately after column permutation are constructed using a structural approach similar to the case of \(N=7\). Again, for odd \(N\), the outputs of integer DTT after row permutation are multiplied by the specific coefficients to obtain the outputs of real DTT.