Fast Algorithms for Small-Size Type VII Discrete Cosine Transform

This paper presents new fast algorithms for the type VII discrete cosine transform (DCT-VII) applied to input data sequences of lengths ranging from 3 to 8. Fast algorithms for small-sized trigonometric transforms enable the processing of small data blocks in image and video coding with low computational complexity. To process the information in image and video coding standards, the fast DCT-VII algorithms can be used, taking into account the relationships between the DCT-VII and the type II discrete cosine transform (DCT-II). Additionally, such algorithms can be used in other digital signal processing tasks as components for constructing algorithms for large-sized transforms, leading to reduced system complexity. Existing fast odd DCT algorithms have been designed using relationships among discrete cosine transforms (DCTs), discrete sine transforms (DSTs), and the discrete Fourier transform (DFT); among different types of DCTs and DSTs; and between the coefficients of the transform matrix. However, these algorithms require a relatively large number of multiplications and additions. The process of obtaining such algorithms is difficult to understand and implement. To overcome these shortcomings, this paper applies a structural approach to develop new fast DCT-VII algorithms. The process begins by expressing the DCT-VII as a matrix-vector multiplication, then reshaping the block structure of the DCT-VII matrix to align with matrix patterns known from the basic papers in which the structural approach was introduced. If the matrix block structure does not match any known pattern, rows and columns are reordered, and sign changes are applied as needed. If this is insufficient, the matrix is decomposed into the sum of two or more matrices, each analyzed separately and transformed similarly if required. As a result, factorizations of DCT-VII matrices for different input sequence lengths are obtained. Based on these factorizations, fast DCT-VII algorithms with reduced arithmetic complexity are constructed and presented with pseudocode. To illustrate the computational flow of the resulting algorithms and their modular design, which is suitable for VLSI implementation, data-flow graphs are provided. The new DCT-VII algorithms reduce the number of multiplications by approximately 66% compared to direct matrix-vector multiplication, although the number of additions decreases by only about 6%.