# The Fast Discrete Tchebichef Transform Algorithms for Short-Length Input Sequences
## 1 Introduction
### State of the Art of the Problem  
To design fast DTT algorithms, the polynomial algebraic approach, sparse matrix factorization, and different heuristics are applied [22; 25; 26; 27; 28; 29; 30; 31; 32; 33]. Recursive expressions for obtaining the entries for DTT matrices do not facilitate the development of fast radix-type algorithms, although such algorithms are efficiently and widely employed for orthogonal trigonometric transforms [36]. Thus, in [30], the polynomial algebraic approach is used to construct the fast algorithm for the 2D 4 \(\times\) 4 real DTT. The expressions for transform matrix entries were regrouped to determine the products of Tchebichef polynomials via the linear combinations of new basis functions. These results reduce multiplications by 50% and additions by 31% compared to the naive product bearing in mind the separability and symmetry of the DTT matrix. However, very cumbersome mathematical calculations of the algebraic approach are an obstacle to obtaining fast algorithms for DTTs with other input sequence lengths.  
In [1], multiplier-less algorithms were proposed for one-dimensional (1D) and 2D integer \(8\times 8\) DTTs. These algorithms were obtained heuristically, although they used butterfly architecture. The sparse matrix factorization or data flow graphs are not presented for them. Despite this, these algorithms are considered to be among the most effective. In the 1D case, the number of additions was reduced by 50% compared to a naive method when considering the separability and symmetry properties of the DTT. In addition, 29 shifts were required in the 1D case. However, the above heuristics were proposed to construct an algorithm specifically for the case of an \(8\times 8\) integer DTT. Generalization of it to cases of other lengths of data sequence was not considered.  
The primary way to obtain fast DTT algorithms is sparse matrix factorization and/or construction of data flow graphs with butterfly architecture [28; 29; 30; 31; 32; 33]. For example, in [28; 29], sparse matrix factorization was proposed for a \(4\times 4\) real 2D DTT. Although an additional 20 shifts were required, it reduced multiplications by 81% and additions by 17% compared with the naive product bearing in mind the separability and symmetry of the DTT matrix. Proposed in [10], a fast algorithm with butterfly architecture for a 1D DTT approximation required only 20 additions, reducing operations by 55% compared to [1]. In [8], fast algorithms for \(4\times 4\) and \(8\times 8\) integer 1D DTTs were presented for data flow graphs based on butterfly architecture. The algorithms for \(4\times 4/8\times 8\) 2D DTTs were also implemented using Verilog HDL [8].  
Hence, efficient fast DTT algorithms are developed via sparse matrix factorization or data flow graphs with butterfly architecture. In general, such an approach is appropriate for designing fast DTT algorithms for even lengths of input sequences, including lengths different from 4 and 8. However, when dealing with odd lengths, problems arise in constructing butterflies, and thus the choice of an approach for constructing fast DTT algorithms for odd lengths remains open. Thus, the above short review of existing fast DTT algorithms allowed us to determine unsolved parts of the general problem of developing fast DTT algorithms for short-length input sequences.