The Design of Fast Type-V Discrete Cosine Transform Algorithms for Short-Length Input Sequences

Abstract

Fast algorithms for type-five discrete cosine transform (DCT-V) for sequences of input data of short length in the range of two to eight are elaborated in the paper. A matrix–vector product representation of the DCT-V is the starting point for designing the algorithms. In each specific case, the DCT-V matrices have remarkable structural properties that follow from the localization of identical entries within the matrices. Each matrix of the DCT-V has only a few distinct entries that are repeated at different positions in its structure. Using simple transformations such as permutations of the rows and/or columns of this matrix or its favorable decomposition into two or more matrix components, it is possible to obtain efficient matrix structures that lead to useful factorization schemes. Based on the suitable factorization schemes we obtained, we developed fast algorithms that reduce the number of arithmetic operations when calculating the DCT-V. The correctness of the obtained algorithmic solutions was justified theoretically using a strict mathematical background of each of them. The developed algorithms were then further tested using MATLAB R2023b software to finally confirm their correctness. Finally, an evaluation of the computational complexity for each obtained solution is presented. The evaluation results were compared with the computational complexity of the direct calculation of matrix–vector products. The resulting factorizations of the matrices of the DCT-V reduce the average number of multiplications by 57% but increase the number of additions by 29%.

1. Introduction

Discrete cosine transform (DCT) [1,2,3] is widely applied in image compression [4,5], image denoising [6,7,8], healthcare systems [9,10], steganography and image encryption [11,12], image watermarking and image authentication [13,14], data analysis [15], image retrieval [16], video coding [17], audio signal enhancement [18]. The advantages of this transform are real-valued processing of data compared with discrete Fourier transform. This reduces the number of calculations required and simplifies further analysis of the transform results. In the literature, eight types of DCT have been proposed [1,2,3]. The most popular and researched transform is still DCT types I-IV [19,20,21]. DCT variant types V-VIII seem to be rarely used in practice [17,22,23]. One reason, perhaps, is that corresponding algorithms are generally more complicated than algorithms for DCT types I-IV. There are, however, several works concerning the efficient implementation of DCT types I-IV [24,25,26]. This paper is devoted to designing computationally efficient algorithms for small-size DCT-V.

The publication review shows that two approaches to the elaboration of fast algorithms for DCT can be found in the literature, specifically, structural and analytical ones. The first approach is structural [27,28,29,30]. It is usually employed to develop fast algorithms for small-size discrete orthogonal transforms. It is based on a deep analysis of the structures of base transform matrices, identifying individual features of the arrangement of identical entries and, if necessary, changing the matrix structures for subsequent use of certain matrix identities that lead to the suitable factorization of these matrices.

The structural approach does not limit the length of the original data sequence, for example, to a power of two or three. However, as the size of data sets increases, fast algorithms become more cumbersome and difficult to implement. The second approach is analytical and is based on the use of the most general patterns of factorization of the basic transformation matrices of arbitrary order [31,32,33]. It allows the development of efficient algorithms for long-length input sequences. However, in the case of short-length sequences, this approach does not always give good results. The effectiveness of this method in constructing a fast algorithm usually depends on the availability of an analytical representation of the transform’s coefficients. For the same reason, the length of the input data sequence is often limited to a power of two. Since short-length input sequences are considered in our research, the structural approach is selected to design computationally efficient algorithms. So, the aim of the article is the elaboration of reduced-complexity algorithms for DCT-V for short-length input sequences of length N = 2, 3, 4, 5, 6, 7, 8.

2. Materials and Methods

The DCT is one of the orthogonal transforms used, among other things, to analyze and process audio or other types of signals. DCT-V can be represented by the following expression [2,34]:

$$y_k={\displaystyle \frac{2}{\sqrt{2\left(N-1\right)+1}}}{\sum }_{n=0}^{N-1}{x}_n{\mathsf{ϵ}}_n{\mathsf{ϵ}}_k \cos {\displaystyle \frac{2n\mathsf{\pi }k}{2N-1}}, k=0, 1, \dots , N-1,$$

(1)

where $y_k$ is the output sequence after the DCT-V transform is performed; $x_n$ is the sequence of input data; and N is the number of signal samples,

$${{\mathsf{ϵ}}_n, \mathsf{ϵ}}_k=\left\{\begin{array}{c}{\displaystyle \frac{1}{\sqrt{2}}},n,k=0,\\ 1,\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}s\mathrm{e}.\end{array}\right.$$

DCT-V can be represented in matrix notation as follows:

$${\mathbf{Y}}_{N\times 1}={\mathbf{C}}_N{\mathbf{X}}_{N\times 1},$$

(2)

where ${\mathbf{Y}}_{N\times 1}={\left[y_0, y_1, \dots , y_{N-1}\right]}^{\mathbf{T}}$, ${\mathbf{X}}_{N\times 1}={\left[x_0, x_1, \dots , x_{N-1}\right]}^{\mathbf{T}}$, ${\mathbf{c}}_{\mathit{kl}}={\displaystyle \frac{2}{\sqrt{2\left(N-1\right)+1}}}{\mathsf{ϵ}}_n{\mathsf{ϵ}}_k \cos {\displaystyle \frac{2n\mathsf{\pi }k}{2N-1}}$, k, l = 0, …, N − 1.

In this paper, we use the following markings and signs:

• ${\mathbf{I}}_N$ is an order N identity matrix;
• ${\mathbf{H}}_2$ is a 2 × 2 Hadamard matrix;
• $1_{N\times M}$ is a N × M matrix of ones (a matrix where every entry is equal to one);
• ⊗ is the Kronecker product of two matrices;
• ⊕ is the direct sum of two matrices.

Voids in a matrix mean that the entries at those positions have a zero value. The multipliers were marked as $s_m^{\left(N\right)}$.

DCT-V in matrix notation is as follows:

$$\left[\begin{array}{c}\begin{array}{c}{y}_0\\ y_1\end{array}\\ \begin{array}{c}⋮\\ y_{N-1}\end{array}\end{array}\right]=\left[\begin{array}{ccc}\begin{array}{cc}{\mathbf{c}}_{0,0}& {\mathbf{c}}_{0,1}\\ {\mathbf{c}}_{1,0}& {\mathbf{c}}_{1,1}\end{array}& \cdots & \begin{array}{c}{\mathbf{c}}_{0,N-1}\\ {\mathbf{c}}_{1,N-1}\end{array}\\ ⋮& \ddots & ⋮\\ \begin{array}{cc}{\mathbf{c}}_{N-1, 0}& {\mathbf{c}}_{N-1, 1}\end{array}& \cdots & {\mathbf{c}}_{N-1,N-1}\end{array}\right]\left[\begin{array}{c}\begin{array}{c}{x}_0\\ x_1\end{array}\\ \begin{array}{c}⋮\\ x_{N-1}\end{array}\end{array}\right]$$

(3)

For a two-point DCT-V, the corresponding expression in matrix notation is represented as follows:

$${\mathbf{Y}}_{2\times 1}={\mathbf{C}}_2{\mathbf{X}}_{2\times 1},$$

(4)

where ${\mathbf{Y}}_{2\times 1}={ \left[y_0, y_1\right]}^{\mathbf{T}}$, ${\mathbf{X}}_{2\times 1}={\left[x_0, x_1\right]}^{\mathbf{T}}$, ${\mathbf{C}}_2=\left[\begin{array}{cc}{\mathrm{a}}_2& {\mathrm{b}}_2\\ {\mathrm{b}}_2& -{\mathrm{a}}_2\end{array}\right]$, $a_2$ = 0.5774, $b_2 =0.8165$.

Now, let us take into account the structural properties of the matrix ${\mathbf{C}}_2$ [18,27]. Then, the expression for DCT-V for N = 2 can be presented as follows:

$${\mathbf{Y}}_{2\times 1}={\mathbf{W}}_{2\times 3}{\mathbf{D}}_3{\mathbf{W}}_{3\times 2}{\mathbf{X}}_{2\times 1},$$

(5)

where ${\mathbf{D}}_3=\mathit{diag}\left(s_0^{\left(2\right)}, s_1^{\left(2\right)}, s_2^{\left(2\right)}\right)$, $s_0^{\left(2\right)}=a_2-b_2, s_1^{\left(2\right)}={-(a}_2+b_2), s_2^{\left(2\right)}=b_2,$ ${\mathbf{W}}_{2\times 3}=\left[\begin{array}{ccc}1& & 1\\ & 1& 1\end{array}\right],$ ${\mathbf{W}}_{3\times 2}=\left[\begin{array}{cc}1& \\ & 1\\ 1& 1\end{array}\right]$.

Figure 1 shows a data flow graph of the synthesized algorithm for the two-point DCT-V. As can be seen, the number of multiplication operations may be reduced from 4 to 3, but the number of addition operations is increased from 2 to 3.

Consider the elaboration of the algorithm for three-point DCT-V. The expression for three-point DCT-V is as follows:

$${\mathbf{Y}}_{3\times 1}={\mathbf{C}}_3{\mathbf{X}}_{3\times 1},$$

(6)

where ${\mathbf{Y}}_{3\times 1}={\left[y_0, y_1,y_2\right]}^{\mathbf{T}}$, ${\mathbf{X}}_{3\times 1}={\left[x_0, x_1, x_2\right]}^{\mathbf{T}}$, ${\mathbf{C}}_3=\left[\begin{array}{ccc}{b}_3& c_3& c_3\\ c_3& a_3& -d_3\\ c_3& -d_3& a_3\end{array}\right]$ with $a_3$ = 0.2764,$b_3$ = 0.4472, $c_3$ = 0.6325, $d_3$ = 0.7236.

The matrix ${\mathbf{C}}_3$ is decomposed into two components:

$${\mathbf{C}}_3={\mathbf{C}}_3^{\left(\mathrm{a}\right)}+{\mathbf{C}}_3^{\left(\mathrm{b}\right)},$$

(7)

where ${\mathbf{C}}_3^{\left(\mathrm{a}\right)}=\left[\begin{array}{ccc}{b}_3& c_3& c_3\\ c_3& & \\ c_3& & \end{array}\right]$, ${\mathbf{C}}_3^{\left(\mathrm{b}\right)}=\left[\begin{array}{ccc}& & \\ & a_3& -d_3\\ & -d_3& a_3\end{array}\right]$.

Taken into account properties of structural matrices [27,28], the computational procedure for the three-point DCT-V is represented by expression

$${\mathbf{Y}}_{3\times 1}={\mathbf{W}}_{3\times 5}{\mathbf{W}}_5{\mathbf{D}}_5{\mathbf{W}}_5{\mathbf{W}}_{5\times 6}{\mathbf{W}}_{6\times 3}{\mathbf{X}}_{3\times 1},$$

(8)

where ${\mathbf{D}}_5=\mathit{diag}\left(s_0^{\left(3\right)}, s_1^{\left(3\right)}, s_2^{\left(3\right)}, s_3^{\left(3\right)}, s_3^{\left(3\right)}\right)$, $s_0^{\left(3\right)}=b_3$, $s_1^{\left(3\right)}=(a_3-d_3)/2$, $s_1^{\left(3\right)}=(a_3+d_3)/2$, $s_3^{\left(3\right)}=c_3$, ${ \mathbf{W}}_5=1{\mathbf{H}}_2{\mathbf{I}}_2$,

$${\mathbf{W}}_{3\times 5}=\left[\begin{array}{ccccc}1& & & 1& \\ & 1& & & 1\\ & & 1& & 1\end{array}\right],{\mathbf{W}}_{6\times 3}=\left[\begin{array}{ccc}1& & \\ & 1& \\ & & 1\\ 1& & \\ & 1& \\ & & 1\end{array}\right],{\mathbf{W}}_{5\times 6}=\left[\begin{array}{cccccc}1& & & & & \\ & 1& & & & \\ & & 1& & & \\ & & & & 1& 1\\ & & & 1& & 1\end{array}\right].$$

A data flow graph of the proposed algorithm for the three-point DCT-V is shown in Figure 2. The number of multiplication operations can be reduced from 9 to 5, but the number of addition operations is increased from 6 to 8.

Let us design the algorithm for four-point DCT-V. The four-point DCT-V is expressed as follows:

$${\mathbf{Y}}_{4\times 1}={\mathbf{C}}_4{\mathbf{X}}_{4\times 1},$$

(9)

where ${\mathbf{Y}}_{4\times 1}={ \left[y_0, y_1,y_2, y_3\right]}^{\mathbf{T}}$, ${\mathbf{X}}_{4\times 1}={ \left[x_0, x_1, x_2, x_3\right]}^{\mathbf{T}}$, ${\mathbf{C}}_4=\left[\begin{array}{cccc}{b}_4& d_4& d_4& d_4\\ d_4& c_4& -a_4& -e_4\\ d_4& -a_4& -e_4& c_4\\ d_4& -e_4& c_4& -a_4\end{array}\right]$ with $a_4$ = 0.1682, $b_4$ = 0.3780,$c_4$ = 0.4713, $d_4$ = 0.5345, $e_4$ = 0.6811.

To change the order of columns of ${\mathbf{C}}_4$, the permutation

$${\mathsf{\pi }}_4=\left(\begin{array}{cc}1& 2\\ 1& 2\end{array}\begin{array}{cc}3& 4\\ 4& 3\end{array}\right)$$

is defined. After permutation of the columns of ${\mathbf{C}}_4$ according to ${\mathsf{\pi }}_4$, we obtain the matrix ${\mathbf{C}}_4^{\left(a\right)}=\left[\begin{array}{cccc}{b}_4& d_4& d_4& d_4\\ d_4& c_4& -e_4& -a_4\\ d_4& -a_4& c_4& -e_4\\ d_4& -e_4& a_4& -c_4\end{array}\right]$ with permutation matrix ${\mathbf{P}}_4=\left[\begin{array}{cccc}1& & & \\ & 1& & \\ & & & 1\\ & & 1& \end{array}\right]$.

The matrix ${\mathbf{C}}_4^{\left(a\right)}$ is decomposed into two components:

$${\mathbf{C}}_4^{\left(a\right)}={\mathbf{C}}_4^{\left(b\right)}+{\mathbf{C}}_4^{\left(c\right)},$$

(10)

where ${\mathbf{C}}_4^{\left(b\right)}=\left[\begin{array}{cccc}{b}_4& d_4& d_4& d_4\\ d_4& c_4& -e_4& -a_4\\ d_4& -a_4& c_4& -e_4\\ d_4& -e_4& a_4& -c_4\end{array}\right]$, ${\mathbf{C}}_4^{\left(c\right)}=\left[\begin{array}{cccc}{b}_4& d_4& d_4& d_4\\ d_4& c_4& -e_4& -a_4\\ d_4& -a_4& c_4& -e_4\\ d_4& -e_4& a_4& -c_4\end{array}\right]$.

To process the matrix ${\mathbf{C}}_4^{\left(a\right)}$, we use the expressions for calculating the entries of a circular convolution matrix ${\mathbf{H}}_3=\left[\begin{array}{ccc}{h}_0& h_2& h_1\\ h_1& h_0& h_2\\ h_2& h_1& h_0\end{array}\right]$ for N = 3 [28,29]:

$${\mathbf{H}}_3={\mathbf{T}}_3^{\left(1\right)}{\mathbf{T}}_{3\times 4}\mathit{diag}(s_0,s_1,s_2,s_3){\mathbf{T}}_{4\times 3}{\mathbf{T}}_3^{\left(0\right)},$$

(11)

where $s_0={(h}_0+h_1+h_2)/3, s_1=h_0-h_2,s_2=h_1-h_2, s_3={(h}_0+h_1-2h_2)/3$; ${\mathbf{T}}_3^{\left(1\right)}=\left[\begin{array}{ccc}1& 1& \\ 1& -1& -1\\ 1& & 1\end{array}\right]$, ${\mathbf{T}}_{3\times 4}=\left[\begin{array}{cccc}1& & & \\ & 1& & -1\\ & & 1& -1\end{array}\right]$, ${\mathbf{T}}_{4\times 3}=\left[\begin{array}{ccc}1& & \\ & 1& \\ & & 1\\ & 1& 1\end{array}\right]$, ${\mathbf{T}}_3^{\left(0\right)}=\left[\begin{array}{ccc}1& 1& 1\\ 1& & -1\\ & 1& -1\end{array}\right]$.

Taking into account the properties of structural matrices [28,29], the computational procedure for the four-point DCT-V is represented by the formula

$${\mathbf{Y}}_{4\times 1}={\mathbf{W}}_{4\times 6}{\mathbf{W}}_6^{\left(1\right)}{\mathbf{W}}_{6\times 7}{\mathbf{D}}_7{\mathbf{W}}_{7\times 6}{\mathbf{W}}_6^{\left(0\right)}{\mathbf{W}}_{6\times 8}{\mathbf{W}}_{8\times 4}{\mathrm{P}}_4{\mathbf{X}}_{4\times 1},$$

(12)

where ${\mathbf{W}}_6^{\left(1\right)}={1\oplus \mathbf{T}}_3^{\left(1\right)}{\oplus \mathrm{I}}_2$, ${\mathbf{W}}_{6\times 7}={1\oplus \mathbf{T}}_{3\times 4}{\oplus \mathbf{I}}_2$, ${\mathbf{D}}_7=\mathit{diag}\left(s_0^{\left(4\right)}, s_1^{\left(4\right)}, s_2^{\left(4\right)}, s_3^{\left(4\right)}, s_4^{\left(4\right)}, s_5^{\left(4\right)}, s_5^{\left(4\right)}\right)$, $s_0^{\left(4\right)}=b_4$, $s_1^{\left(4\right)}=(c_4-a_4-e_4)/3$, $s_2^{\left(4\right)}=c_4+e_4$, $s_3^{\left(4\right)}=-a_4+e_4$, $s_4^{\left(4\right)}=(c_4-a_4+2e_4)/3$, $s_5^{\left(4\right)}=d_4$, ${\mathbf{W}}_{7\times 6}={1\oplus \mathbf{T}}_{4\times 3}{\oplus \mathbf{I}}_2$, ${\mathbf{W}}_6^{\left(0\right)}={1\oplus \mathbf{T}}_3^{\left(0\right)}{\oplus \mathbf{I}}_2$, ${\mathbf{W}}_{6\times 8}={\mathbf{I}}_4{\oplus \mathbf{P}}_{2\times 4}$, ${\mathbf{W}}_{4\times 6}=\left[\begin{array}{cccccc}1& & & & 1& \\ & 1& & & & 1\\ & & 1& & & 1\\ & & & 1& & 1\end{array}\right]$, ${\mathbf{P}}_{2\times 4}=\left[\begin{array}{cccc}& 1& 1& 1\\ 1& & & \end{array}\right]$, ${\mathbf{W}}_{8\times 4}=\left[\begin{array}{cccc}1& & & \\ & 1& & \\ & & 1& \\ & & & 1\\ 1& & & \\ & 1& & \\ & & 1& \\ & & & 1\end{array}\right].$ A data flow graph of the proposed algorithm for the four-point DCT-V is presented in Figure 3. In particularly, the number of multiplication operations may be reduced from 16 to 7, although the number of addition operations is increased from 12 to 17.

Let us obtain the algorithm for five-point DCT-V. The five-point DCT-V is expressed as follows:

$${\mathbf{Y}}_{5\times 1}={\mathbf{C}}_5{\mathbf{X}}_{5\times 1},$$

(13)

where ${\mathbf{Y}}_{5\times 1}={\left[y_0, y_1,y_2, y_3, y_4\right]}^{\mathbf{T}}$, ${\mathbf{X}}_{5\times 1}={\left[x_0, x_1, x_2, x_3, x_4\right]}^{\mathbf{T}}$, $a_5=0.1158,$ $b_5$= 0.3333, $c_5$ = 0.4714, $d_5$ = 0.5107, $e_5$ = 0.6265, $f_5$ = 0.6667, ${\mathbf{C}}_5=\left[\begin{array}{ccccc}{b}_5& c_5& c_5& c_5& c_5\\ c_5& d_5& a_5& -b_5& -e_5\\ c_5& a_5& -e_5& -b_5& d_5\\ c_5& -b_5& -b_5& f_5& -b_5\\ c_5& -e_5& d_5& -b_5& a_5\end{array}\right]$.

To change the order of columns and rows of ${\mathbf{C}}_5$, the permutations ${\mathsf{\pi }}_5$ and ${\mathsf{\pi }}_6$ are defined in the following form:

$${\mathsf{\pi }}_5=\left(\begin{array}{cc}1& 2\\ 1& 4\end{array}\begin{array}{ccc}3& 4& 5\\ 2& 5& 3\end{array}\right), {\mathsf{\pi }}_6=\left(\begin{array}{cc}1& 2\\ 1& 4\end{array}\begin{array}{ccc}3& 4& 5\\ 2& 3& 5\end{array}\right).$$

The columns of ${\mathbf{C}}_5$ are permutated according to ${\mathsf{\pi }}_5$, and the rows of ${\mathbf{C}}_5$ are permutated according to ${\mathsf{\pi }}_6$. After permutations, the matrix acquires the following structure:

$${\mathbf{C}}_5^{\left(a\right)}=\left[\begin{array}{ccccc}{b}_5& c_5& c_5& c_5& c_5\\ c_5& f_5& -b_5& -b_5& -b_5\\ c_5& -b_5& d_5& -e_5& a_5\\ c_5& -b_5& a_5& d_5& -e_5\\ c_5& -b_5& -e_5& a_5& d_5\end{array}\right]$$

Then, the matrix ${\mathbf{C}}_5^{\left(a\right)}$ is decomposed into two components:

$${\mathbf{C}}_5^{\left(a\right)}={\mathbf{C}}_5^{\left(b\right)}+{\mathbf{C}}_5^{\left(c\right)},$$

(14)

where ${\mathbf{C}}_5^{\left(b\right)}=\left[\begin{array}{ccccc}{b}_5& c_5& c_5& c_5& c_5\\ c_5& f_5& -b_5& -b_5& -b_5\\ c_5& -b_5& & & \\ c_5& -b_5& & & \\ c_5& -b_5& & & \end{array}\right]$ and ${\mathbf{C}}_5^{\left(c\right)}=\left[\begin{array}{ccccc}& & & & \\ & & & & \\ & & d_5& -e_5& a_5\\ & & a_5& d_5& -e_5\\ & & -e_5& a_5& d_5\end{array}\right]$.

Matrix ${\mathbf{C}}_5^{\left(b\right)}$ has the same entries except on the main diagonal in the first column and first row, and the second column and second row, which allows reducing the number of operations without the need for further transformations. After eliminating the rows and columns containing only zero entries in matrix ${\mathbf{C}}_5^{\left(c\right)}$, we obtain matrix ${\mathbf{C}}_3^{\left(d\right)}$:

$${\mathbf{C}}_3^{\left(d\right)}=\left[\begin{array}{ccc}{d}_5& -e_5& a_5\\ a_5& d_5& -e_5\\ -e_5& a_5& d_5\end{array}\right].$$

To process the matrix ${\mathbf{C}}_3^{\left(d\right)}$ we use the expressions for calculating the entries of a circular convolution matrix ${\mathbf{H}}_3$ for N = 3 (Equation (11)) [28,29]. Taking into account the properties of structural matrices [28,29], the computational procedure for the five-point DCT-V is represented by the matrix–vector procedure

$${\mathbf{Y}}_{5\times 1}={\mathbf{P}}_5^{\left(1\right)}{\mathbf{W}}_{5\times 9}{\mathbf{W}}_9^{\left(1\right)}{\mathbf{W}}_{9\times 10}{\mathbf{D}}_{10}{{\mathbf{W}}_{10\times 9}\mathbf{W}}_9^{\left(0\right)}{\mathbf{W}}_{9\times 10}{\mathbf{W}}_{10\times 5}{\mathbf{P}}_5^{\left(0\right)}{\mathbf{X}}_{5\times 1},$$

(15)

where

$${\mathbf{W}}_{9\times 10}={\mathbf{I}}_5{\mathbf{P}}_{2\times 5}^{\left(3\right)}, { \mathbf{W}}_9^{\left(1\right)}={\mathbf{I}}_2{\mathbf{T}}_3^{\left(1\right)}{\mathbf{I}}_4,{\mathbf{W}}_{9\times 10}={\mathbf{I}}_2{\mathbf{T}}_{3\times 4}{\mathbf{I}}_4,$$

$${\mathbf{W}}_{10\times 9}={\mathbf{I}}_2{\mathbf{T}}_{4\times 3}{\mathbf{I}}_4, { \mathbf{W}}_{9\times 9}^{\left(0\right)}={\mathbf{I}}_2{\mathbf{T}}_3^{\left(1\right)}{\mathbf{I}}_4,$$

$${\mathbf{D}}_{10}=\mathit{diag}(s_0^{\left(5\right)},s_1^{\left(5\right)},s_2^{\left(5\right)},s_3^{\left(5\right)}, s_4^{\left(5\right)}, s_5^{\left(5\right)},s_6^{\left(5\right)},s_7^{\left(5\right)},s_8^{\left(5\right)}, s_9^{\left(5\right)}),$$

$$s_0^{\left(5\right)}=b_5,s_1^{\left(5\right)}=f_5,s_2^{\left(5\right)}=(d_5+a_5-e_5)/3, s_3^{\left(5\right)}=d_5+e_5,{ s}_4^{\left(5\right)}=a_5+e_5,{ s}_5^{\left(5\right)}=(d_5+a_5+2e_5)/3,$$

$$s_6^{\left(5\right)}=c_5,s_7^{\left(5\right)}=c_5,s_8^{\left(5\right)}=-b_5,s_9^{\left(5\right)}=-b_5,$$

$${\mathbf{P}}_{2\times 5}^{\left(3\right)}=\left[\begin{array}{ccccc}& 1& 1& 1& 1\\ 1& & & & \\ & & 1& 1& 1\\ & 1& & & \end{array}\right], {\mathbf{P}}_5^{\left(0\right)}=\left[\begin{array}{ccccc}1& & & & \\ & & & 1& \\ & 1& & & \\ & & & & 1\\ & & 1& & \end{array}\right], {\mathbf{P}}_5^{\left(1\right)}=\left[\begin{array}{ccccc}1& & & & \\ & & 1& & \\ & & & 1& \\ & 1& & & \\ & & & & 1\end{array}\right],$$

$${\mathbf{W}}_{5\times 9}=\left[\begin{array}{ccccccccc}1& & & & & 1& & & \\ & 1& & & & & 1& 1& \\ & & 1& & & & 1& & 1\\ & & & 1& & & 1& & 1\\ & & & & 1& & 1& & 1\end{array}\right], {\mathbf{W}}_{10\times 5}=\left[\begin{array}{ccccc}1& & & & \\ & 1& & & \\ & & 1& & \\ & & & 1& \\ & & & & 1\\ 1& & & & \\ & 1& & & \\ & & 1& & \\ & & & 1& \\ & & & & 1\end{array}\right].$$

A data-flow graph of the proposed algorithm for the five-point DCT-V is presented in Figure 4. In particularly, the number of multiplication operations may be reduced from 25 to 10, but the number of addition operations is increased from 20 to 23.

Let us now synthesize an algorithm for a six-point DCT-V, which is expressed as follows:

$${\mathbf{Y}}_{6\times 1}={\mathbf{C}}_6{\mathbf{X}}_{6\times 1},$$

(16)

where ${\mathbf{Y}}_{6\times 1}={\left[y_0, y_1,y_2, y_3, y_4, y_5\right]}^{\mathbf{T}}$, ${\mathbf{X}}_{6\times 1}={ \left[x_0, x_1, x_2, x_3, x_4, x_5\right]}^{\mathbf{T}}$, $a_6=0.0858,$ $b_6$= 0.2505, $c_6$ = 0.3015, $d_6$ = 0.3949, $e_6$ = 0.4264, $f_6$ = 0.5073, $g_6$ = 0.5786,

$${\mathbf{C}}_6=\left[\begin{array}{cccccc}{c}_6& e_6& e_6& e_6& e_6& e_6\\ e_6& f_6& b_6& -a_6& -d_6& -g_6\\ e_6& b_6& -d_6& -g_6& -a_6& f_6\\ e_6& -a_6& -g_6& b_6& f_6& -d_6\\ e_6& -d_6& -a_6& f_6& -g_6& b_6\\ e_6& -g_6& f_6& -d_6& b_6& -a_6\end{array}\right].$$

To change the order of columns and rows of ${\mathbf{C}}_6$, the permutations ${\mathsf{\pi }}_7$ and ${\mathsf{\pi }}_8$ are defined in the following form:

$${\mathsf{\pi }}_7=\left(\begin{array}{cc}1& 2\\ 1& 2\end{array}\begin{array}{cccc}3& 4& 5& 6\\ 6& 4& 5& 3\end{array}\right), {\mathsf{\pi }}_8=\left(\begin{array}{cc}1& 2\\ 1& 2\end{array}\begin{array}{cccc}3& 4& 5& 6\\ 3& 5& 4& 6\end{array}\right).$$

The columns of ${\mathbf{C}}_6$ are permutated according to ${\mathsf{\pi }}_7$, and the rows of ${\mathbf{C}}_6$ are permutated according to ${\mathsf{\pi }}_8$. After permutations, the matrix acquires the following structure:

$${\mathbf{C}}_6^{\left(a\right)}=\left[\begin{array}{cccccc}{c}_6& e_6& e_6& e_6& e_6& e_6\\ e_6& f_6& -g_6& -a_6& -d_6& b_6\\ e_6& b_6& f_6& -g_6& -a_6& -d_6\\ e_6& -d_6& b_6& f_6& -g_6& -a_6\\ e_6& -a_6& -d_6& b_6& f_6& -g_6\\ e_6& -g_6& -a_6& -d_6& b_6& f_6\end{array}\right]$$

Then, the matrix ${\mathbf{C}}_6^{\left(a\right)}$ is decomposed into two components:

$${\mathbf{C}}_6^{\left(a\right)}={\mathbf{C}}_6^{\left(b\right)}+{\mathbf{C}}_6^{\left(c\right)},$$

(17)

where

$${\mathbf{C}}_6^{\left(b\right)}=\left[\begin{array}{cccccc}{c}_6& e_6& e_6& e_6& e_6& e_6\\ e_6& & & & & \\ e_6& & & & & \\ e_6& & & & & \\ e_6& & & & & \\ e_6& & & & & \end{array}\right], {\mathbf{C}}_6^{\left(c\right)}=\left[\begin{array}{cccccc}& & & & & \\ & f_6& -g_6& -a_6& -d_6& b_6\\ & b_6& f_6& -g_6& -a_6& -d_6\\ & -d_6& b_6& f_6& -g_6& -a_6\\ & -a_6& -d_6& b_6& f_6& -g_6\\ & -g_6& -a_6& -d_6& b_6& f_6\end{array}\right].$$

Matrix ${\mathbf{C}}_6^{\left(b\right)}$ has the same entries except on the main diagonal in the first column and first row, which allows reducing the number of operations without the need for further transformations. After eliminating the rows and columns containing only zero entries in matrix ${\mathbf{C}}_6^{\left(c\right)}$, we obtain matrix ${\mathbf{C}}_5^{\left(d\right)}$:

$${\mathbf{C}}_5^{\left(d\right)}=\left[\begin{array}{ccccc}{f}_6& -g_6& -a_6& -d_6& b_6\\ b_6& f_6& -g_6& -a_6& -d_6\\ -d_6& b_6& f_6& -g_6& -a_6\\ -a_6& -d_6& b_6& f_6& -g_6\\ -g_6& -a_6& -d_6& b_6& f_6\end{array}\right].$$

To process the matrix ${\mathbf{C}}_5^{\left(d\right)}$, we use the expressions for calculating the entries of a circular convolution matrix ${\mathbf{H}}_5=\left[\begin{array}{ccccc}{h}_0& h_4& h_3& h_2& h_1\\ h_1& h_0& h_4& h_3& h_2\\ h_2& h_1& h_0& h_4& h_3\\ h_3& h_2& h_1& h_0& h_4\\ h_4& h_3& h_2& h_1& h_0\end{array}\right]$ for N = 5 [29]. Then,

$$h_0=f_6,h_1=b_6,h_2=-d_6,h_3=-a_6,h_4=-g_6,$$

and the computational procedure for the six-point DCT-V is expressed by formula

$${\mathbf{Y}}_{6\times 1}={\mathbf{P}}_6^{\left(1\right)}{\mathbf{W}}_{6\times 8}{\mathbf{W}}_8^{\left(0\right)}{\mathbf{W}}_{8\times 10}{\mathbf{W}}_{10\times 13}{\mathbf{D}}_{13\times 13}{\mathbf{W}}_{13\times 10}{\mathbf{W}}_{10\times 8}{\mathbf{W}}_8^{\left(0\right)}{\mathbf{W}}_8^{\left(1\right)}{\mathbf{W}}_{8\times 12}{\mathbf{W}}_{12\times 6}{\mathbf{P}}_6^{\left(0\right)}{\mathbf{X}}_{6\times 1},$$

(18)

where

$${\mathbf{P}}_6^{\left(0\right)}=\left[\begin{array}{cccccc}1& & & & & \\ & 1& & & & \\ & & & & & 1\\ & & & 1& & \\ & & & & 1& \\ & & 1& & & \end{array}\right], {\mathbf{P}}_6^{\left(1\right)}=\left[\begin{array}{cccccc}1& & & & & \\ & 1& & & & \\ & & 1& & & \\ & & & & 1& \\ & & & 1& & \\ & & & & & 1\end{array}\right],$$

$${\mathbf{W}}_{8\times 10}=\left[\begin{array}{cccccccccc}1& & & & & & & & & \\ & 1& & & & & & & & \\ & & 1& & & & 1& & & \\ & & & 1& & & & 1& & \\ & & & & 1& & 1& & & \\ & & & & & 1& & 1& & \\ & & & & & & & & 1& \\ & & & & & & & & & 1\end{array}\right],$$

$${\mathbf{W}}_{10\times 8}=\left[\begin{array}{cccccccc}1& & & & & & & \\ & 1& & & & & & \\ & & 1& & & & & \\ & & & 1& & & & \\ & & & & 1& & & \\ & & & & & 1& & \\ & & 1& & 1& & & \\ & & & 1& & 1& & \\ & & & & & & 1& \\ & & & & & & & 1\end{array}\right], {\mathbf{W}}_8^{\left(0\right)}=\left[\begin{array}{cccccccc}1& & & & & & & \\ & 1& 1& 1& 1& 1& & \\ & 1& -1& & & & & \\ & 1& & -1& & & & \\ & 1& & & -1& & & \\ & 1& & & & -1& & \\ & & & & & & 1& \\ & & & & & & & 1\end{array}\right],$$

$${\mathbf{W}}_8^{\left(1\right)}=\left[\begin{array}{cccccccc}1& & & & & & & \\ & 1& & & & & & \\ & & & & & 1& & \\ & & & & 1& & & \\ & & & 1& & & & \\ & & 1& & & & & \\ & & & & & & 1& \\ & & & & & & & 1\end{array}\right],$$

$${\mathbf{W}}_{12\times 6}=\left[\begin{array}{cccccc}1& & & & & \\ & 1& & & & \\ & & 1& & & \\ & & & 1& & \\ & & & & 1& \\ & & & & & 1\\ 1& & & & & \\ & 1& & & & \\ & & 1& & & \\ & & & 1& & \\ & & & & 1& \\ & & & & & 1\end{array}\right], {\mathbf{W}}_{6\times 8}=\left[\begin{array}{cccccccc}1& & & & & & 1& \\ & 1& & & & & & 1\\ & & 1& & & & & 1\\ & & & 1& & & & 1\\ & & & & 1& & & 1\\ & & & & & 1& & 1\end{array}\right],$$

$${\mathbf{W}}_{10\times 13}={\mathbf{I}}_2{\mathbf{T}}_{2\times 3}{\mathbf{T}}_{2\times 3}{\mathbf{T}}_{2\times 3}{\mathbf{I}}_2, {\mathbf{W}}_{13\times 10}={\mathbf{I}}_2{\mathbf{T}}_{3\times 2}{\mathbf{T}}_{3\times 2}{\mathbf{T}}_{3\times 2}{\mathbf{I}}_2,{\mathbf{T}}_{2\times 3}=\left[\begin{array}{ccc}1& & 1\\ & 1& 1\end{array}\right],$$

$${\mathbf{T}}_{3\times 2}=\left[\begin{array}{cc}1& \\ & 1\\ 1& 1\end{array}\right], {\mathbf{W}}_{8\times 12}={\mathbf{I}}_6{\mathbf{P}}_{2\times 6}^{\left(2\right)},{\mathbf{P}}_{2\times 6}^{\left(2\right)}=\left[\begin{array}{cccccc}& 1& 1& 1& 1& 1\\ 1& & & & & \end{array}\right],$$

$${\mathbf{D}}_{13}=\mathit{diag}(s_0^{\left(6\right)},s_1^{\left(6\right)},s_2^{\left(6\right)},s_3^{\left(6\right)},s_4^{\left(6\right)},s_5^{\left(6\right)},s_6^{\left(6\right)},s_7^{\left(6\right)},s_8^{\left(6\right)},s_9^{\left(6\right)},s_{10}^{\left(6\right)},s_{11}^{\left(6\right)},s_{11}^{\left(6\right)}),$$

$$s_0^{\left(6\right)}=c_6,s_1^{\left(6\right)}={(h}_0+h_1+h_2+h_3+h_4)/5,s_2^{\left(6\right)}=h_2-h_4+h_0-h_3,s_3^{\left(6\right)}=-h_1+h_4+h_0-h_3,s_4^{\left(6\right)}=h_3-h_0,$$

$$s_5^{\left(6\right)} {=h}_1-h_4+h_0-h_2,s_6^{\left(6\right)}=h_3-h_1+h_0-h_2,s_7^{\left(6\right)}{=h}_2-h_0,s_8^{\left(6\right)}=h_4-h_0,s_9^{\left(6\right)}=h_1-h_0,s_{10}^{\left(6\right)}=h_0-s_0^{\left(6\right)},$$

$$s_{11}^{\left(6\right)}=e_6.$$

A data-flow graph of the proposed algorithm of the six-point DCT-V is presented in Figure 5. We are able to reduce the number of multiplication operations from 36 to 13, but the number of addition operations is increased from 30 to 41.

The seven-point DCT-V transform in matrix notation can be represented by the following expression:

$${\mathbf{Y}}_{7\times 1}={\mathbf{C}}_7{\mathbf{X}}_{7\times 1},$$

(19)

where ${\mathbf{Y}}_{7\times 1}={ \left[y_0, y_1,y_2, y_3, y_4, y_5, y_6\right]}^{\mathbf{T}}$, ${\mathbf{X}}_{7\times 1}={\left[x_0, x_1, x_2, x_3, x_4, x_5, x_6\right]}^{\mathbf{T}}$, $a_7$ = 0.0669, $b_7$ = 0.1967, $c_7$ = 0.2774, $d_7$ = 0.3151, $e_7$ = 0.3922, $f_7$ = 0.4152, $g_7$ = 0.4912, $h_7$ = 0.5386,

$${\mathbf{C}}_7=\left[\begin{array}{ccccccc}{c}_7& e_7& e_7& e_7& e_7& e_7& e_7\\ e_7& g_7& d_7& a_7& -b_7& -f_7& -h_7\\ e_7& d_7& -b_7& -h_7& -f_7& a_7& g_7\\ e_7& a_7& -h_7& -b_7& g_7& d_7& -f_7\\ e_7& -b_7& -f_7& g_7& a_7& -h_7& d_7\\ e_7& -f_7& a_7& d_7& -h_7& g_7& -b_7\\ e_7& -h_7& g_7& -f_7& d_7& -b_7& a_7\end{array}\right].$$

Now, we need to change the order of columns and rows. Let us define the permutations ${\mathsf{\pi }}_9,{\mathsf{\pi }}_{10}$ in the following form:

$${\mathsf{\pi }}_9=\left(\begin{array}{cc}1& 2\\ 1& 2\end{array}\begin{array}{ccccc}3& 4& 5& 6& 7\\ 7& 4& 6& 5& 3\end{array}\right), {\mathsf{\pi }}_{10}=\left(\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ 1& 2& 3& 5& 6& 4& 7\end{array}\right).$$

Permute columns and rows of ${\mathbf{C}}_7$ according to ${\mathsf{\pi }}_9,{\mathsf{\pi }}_{10}$. After permutations, the matrix acquires the following structure:

$${\mathbf{C}}_7^{\left(a\right)}=\left[\begin{array}{ccccccc}{c}_7& e_7& e_7& e_7& e_7& e_7& e_7\\ e_7& g_7& -h_7& a_7& -f_7& -b_7& d_7\\ e_7& d_7& g_7& -h_7& a_7& -f_7& -b_7\\ e_7& -b_7& d_7& g_7& -h_7& a_7& -f_7\\ e_7& -f_7& -b_7& d_7& g_7& -h_7& a_7\\ e_7& a_7& -f_7& -b_7& d_7& g_7& -h_7\\ e_7& -h_7& a_7& -f_7& -b_7& d_7& g_7\end{array}\right].$$

Then, the matrix ${\mathbf{C}}_7^{\left(a\right)}$ is decomposed into two components:

$${\mathbf{C}}_7^{\left(a\right)}={\mathbf{C}}_7^{\left(b\right)}+{\mathbf{C}}_7^{\left(c\right)},$$

(20)

where

$${\mathbf{C}}_7^{\left(b\right)}=\left[\begin{array}{ccccccc}{c}_7& e_7& e_7& e_7& e_7& e_7& e_7\\ e_7& & & & & & \\ e_7& & & & & & \\ e_7& & & & & & \\ e_7& & & & & & \\ e_7& & & & & & \\ e_7& & & & & & \end{array}\right]{,\mathbf{C}}_7^{\left(c\right)}=\left[\begin{array}{ccccccc}& & & & & & \\ & g_7& -h_7& a_7& -f_7& -b_7& d_7\\ & d_7& g_7& -h_7& a_7& -f_7& -b_7\\ & -b_7& d_7& g_7& -h_7& a_7& -f_7\\ & -f_7& -b_7& d_7& g_7& -h_7& a_7\\ & a_7& -f_7& -b_7& d_7& g_7& -h_7\\ & -h_7& a_7& -f_7& -b_7& d_7& g_7\end{array}\right].$$

Matrix ${\mathbf{C}}_7^{\left(b\right)}$ has the same entries in the first column and first row, which allows us to reduce the number of operations without the need for further transformations. After eliminating the rows and columns containing only zero entries in matrix ${\mathbf{C}}_7^{\left(c\right)}$, we obtain matrix ${\mathbf{C}}_7^{\left(d\right)}$:

$${\mathbf{C}}_6^{\left(d\right)}=\left[\begin{array}{cccccc}{g}_7& -h_7& a_7& -f_7& -b_7& d_7\\ d_7& g_7& -h_7& a_7& -f_7& -b_7\\ -b_7& d_7& g_7& -h_7& a_7& -f_7\\ -f_7& -b_7& d_7& g_7& -h_7& a_7\\ a_7& -f_7& -b_7& d_7& g_7& -h_7\\ -h_7& a_7& -f_7& -b_7& d_7& g_7\end{array}\right].$$

The obtained matrix acquires the structure of the expressions for calculating the entries of a circular convolution matrix ${\mathbf{H}}_6=\left[\begin{array}{cccccc}{h}_0& h_5& h_4& h_3& h_2& h_1\\ h_1& h_0& h_5& h_4& h_3& h_2\\ h_2& h_1& h_0& h_5& h_4& h_3\\ h_3& h_2& h_1& h_0& h_5& h_4\\ h_4& h_3& h_2& h_1& h_0& h_5\\ h_5& h_4& h_3& h_2& h_1& h_0\end{array}\right]$ for N = 6 [29].

Then, denote

$$s_0^{\left(7\right)}={c_7;s}_1^{\left(7\right)}=(g_7{+b}_7{-f}_7+h_7)/6; s_2^{\left(7\right)}={(d}_7+b_7+a_7+h_7)/6;$$

$$s_3^{\left(7\right)}=(d_7{+a}_7-g_7+f_7)/6; s_4^{\left(7\right)}=(g_7{+b}_7+f_7-h_7)/6; s_5^{\left(7\right)}=(d_7-b_7-a_7+h_7)/6;$$

$$s_6^{\left(7\right)}=(g_7+f_7{-a}_7+d_7)/6; s_7^{\left(7\right)}=(g_7-d_7-{b_7+f}_7+a_7+h_7)/6; s_8^{\left(7\right)}=(g_7+d_7-{b_7-f}_7+a_7-h_7)/6; s_9^{\left(7\right)}=e_7.$$

Based on properties of structural matrices [28,29], the computational procedure for the seven-point DCT-V is represented by expression

$${\mathbf{Y}}_{7\times 1}={\mathbf{P}}_7^{\left(1\right)}{\mathbf{W}}_{7\times 9}{\mathbf{W}}_{9\times 11}^{\left(1\right)}{\mathbf{W}}_{11}^{\left(0\right)}{\mathbf{W}}_{11}^{\left(1\right)}{\mathbf{D}}_{11}{\mathbf{W}}_{11\times 9}^{\left(1\right)}{\mathbf{W}}_{9\times 11}^{\left(0\right)}{\mathbf{W}}_{11\times 9}^{\left(0\right)}{\mathbf{W}}_{9\times 14}{\mathbf{W}}_{14\times 7}{\mathbf{P}}_7^{\left(0\right)}{\mathbf{X}}_{7\times 1},$$

(21)

where

$${\mathbf{D}}_{11}=\mathit{diag}(s_0^{\left(7\right)},s_1^{\left(7\right)},s_2^{\left(7\right)},s_3^{\left(7\right)},s_4^{\left(7\right)},s_5^{\left(7\right)},s_6^{\left(7\right)},s_7^{\left(7\right)},s_8^{\left(7\right)},s_9^{\left(7\right)},s_9^{\left(7\right)}),$$

$${\mathbf{W}}_{9\times 11}^{\left(0\right)}=1{\mathbf{T}}_{6\times 8}^{\left(0\right)}{\mathbf{I}}_2, {\mathbf{W}}_{9\times 11}^{\left(1\right)}=1{\mathbf{T}}_{6\times 8}^{\left(1\right)}{\mathbf{I}}_2, {\mathbf{W}}_{11\times 9}^{\left(0\right)}=1{\mathbf{T}}_{8\times 6}{\mathbf{I}}_2, {\mathbf{W}}_{11}^{\left(0\right)}=1{\mathbf{T}}_3^{\left(2\right)}{\mathbf{T}}_3^{\left(2\right)}{\mathbf{I}}_4,$$

$${\mathbf{W}}_{11}^{\left(1\right)}=1{\mathbf{T}}_3^{\left(3\right)}{\mathbf{T}}_3^{\left(4\right)}{\mathbf{H}}_2{\mathbf{I}}_2, {\mathbf{W}}_{11\times 9}^{\left(1\right)}=1{\mathbf{T}}_{6\times 4}{\mathbf{I}}_4, {\mathbf{W}}_{9\times 14}={\mathbf{I}}_7{\mathbf{T}}_{2\times 7},$$

$${\mathbf{P}}_7^{\left(0\right)}=\left[\begin{array}{ccccccc}1& & & & & & \\ & 1& & & & & \\ & & & & & & 1\\ & & & 1& & & \\ & & & & & 1& \\ & & & & 1& & \\ & & 1& & & & \end{array}\right],{\mathbf{P}}_7^{\left(1\right)}=\left[\begin{array}{ccccccc}1& & & & & & \\ & 1& & & & & \\ & & 1& & & & \\ & & & & & 1& \\ & & & 1& & & \\ & & & & 1& & \\ & & & & & & 1\end{array}\right],$$

$${\mathbf{T}}_{6\times 8}^{\left(0\right)}=\left[\begin{array}{cccccccc}& & 1& & & 1& & \\ & & & 1& & & 1& \\ & & 1& & & -1& & \\ & 1& & & & & & -1\\ 1& & & & -1& & 1& \\ 1& & & & 1& & & 1\end{array}\right],{\mathbf{T}}_{8\times 6}=\left[\begin{array}{cccccc}1& & 1& & & \\ & 1& 1& & & \\ 1& & -1& & & \\ & 1& -1& & & \\ & 1& & 1& & \\ & & & 1& & -1\\ & & & & 1& -1\\ & & & & 1& 1\end{array}\right],$$

$${\mathbf{T}}_{6\times 8}^{\left(1\right)}=\left[\begin{array}{cccccccc}1& & & 1& & & 1& \\ & 1& & & -1& & & -1\\ & & -1& & & -1& 1& \\ 1& & & -1& & & & -1\\ & 1& & & 1& & 1& \\ & & -1& & & 1& & -1\end{array}\right], {\mathbf{T}}_{6\times 4}=\left[\begin{array}{cccc}1& & & \\ & 1& & \\ 1& -1& & \\ & & 1& \\ & & & 1\\ & & 1& 1\end{array}\right],$$

$${\mathbf{T}}_3^{\left(2\right)}=\left[\begin{array}{ccc}1& & -1\\ & 1& 1\\ 1& 1& \end{array}\right],{\mathbf{T}}_3^{\left(3\right)}=\left[\begin{array}{ccc}1& -1& \\ 1& & 1\\ & 1& 1\end{array}\right], {\mathbf{T}}_3^{\left(4\right)}=\left[\begin{array}{ccc}1& -1& \\ 1& & -1\\ & 1& -1\end{array}\right],$$

$${\mathbf{T}}_{2\times 7}=\left[\begin{array}{ccccccc}& 1& 1& 1& 1& 1& 1\\ 1& & & & & & \end{array}\right],$$

$${\mathbf{W}}_{14\times 7}=\left[\begin{array}{ccccccc}1& & & & & & \\ & 1& & & & & \\ & & 1& & & & \\ & & & 1& & & \\ & & & & 1& & \\ & & & & & 1& \\ & & & & & & 1\\ 1& & & & & & \\ & 1& & & & & \\ & & 1& & & & \\ & & & 1& & & \\ & & & & 1& & \\ & & & & & 1& \\ & & & & & & 1\end{array}\right]{,\mathbf{W}}_{7\times 9}=\left[\begin{array}{ccccccccc}1& & & & & & & 1& \\ & 1& & & & & & & 1\\ & & 1& & & & & & 1\\ & & & 1& & & & & 1\\ & & & & 1& & & & 1\\ & & & & & 1& & & 1\\ & & & & & & 1& & 1\end{array}\right].$$

Figure 6 shows a data flow graph of the synthesized algorithm for the seven-point DCT-V. As can be seen, we were able to reduce the number of multiplications from 49 to 11, although the number of additions increased from 42 to 55.

Let us design the algorithm for eight-point DCT-V. The eight-point DCT-V is expressed as follows:

$${\mathbf{Y}}_{8\times 1}={\mathbf{C}}_8{\mathbf{X}}_{8\times 1},$$

(22)

where ${\mathbf{Y}}_{8\times 1}={\left[y_0, y_1,y_2, y_3, y_4, y_5, y_6, y_7\right]}^{\mathbf{T}}$, ${\mathbf{X}}_{8\times 1}={ \left[x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7\right]}^{\mathbf{T}}$,

$${\mathbf{C}}_8=\left[\begin{array}{cccccccc}{c}_8& e_8& e_8& e_8& e_8& e_8& e_8& e_8\\ e_8& g_8& d_8& b_8& -a_8& -c_8& -f_8& {-h}_8\\ e_8& d_8& -a_8& -f_8& {-h}_8& -c_8& b_8& g_8\\ e_8& b_8& -f_8& -f_8& b_8& q_8& b_8& -f_8\\ e_8& -a_8& {-h}_8& b_8& g_8& -c_8& -f_8& d_8\\ e_8& -c_8& -c_8& {\mathrm{q}}_8& -c_8& -c_8& q_8& -c_8\\ e_8& -f_8& b_8& b_8& -f_8& q_8& -f_8& b_8\\ e_8& {-h}_8& g_8& -f_8& d_8& {-c}_8& b_8& -a_8\end{array}\right]$$

with $a_8$ = 0.0540, $b_8$ = 0.1596, $c_8$ = 0.2582, $d_8$ = 0.3455, $e_8$ = 0.3651, $f_8$ = 0.4178, $g_8$ = 0.4718, $h_8$ = 0.5051, $q_8$ = 0.5164.

Let us define the permutations

$${\mathsf{\pi }}_{11}=\left(\begin{array}{cc}1& 2\\ 1& 6\end{array}\begin{array}{cccccc}3& 4& 5& 6& 7& 8\\ 4& 7& 2& 8& 5& 3\end{array}\right), {\mathsf{\pi }}_{12}=\left(\begin{array}{cc}1& 2\\ 1& 6\end{array}\begin{array}{cccccc}3& 4& 5& 6& 7& 8\\ 7& 4& 2& 3& 5& 8\end{array}\right)$$

to change the order of columns and rows, respectively. As a result of the permutations, the matrix ${\mathbf{C}}_8^{\left(a\right)}$ is obtained:

$${\mathbf{C}}_8^{\left(a\right)}=\left[\begin{array}{cccccccc}{c}_8& e_8& e_8& e_8& e_8& e_8& e_8& e_8\\ e_8& -c_8& q_8& q_8& -c_8& -c_8& -c_8& {-c}_8\\ e_8& q_8& b_8& -f_8& {-f}_8& b_8& {-f}_8& b_8\\ e_8& q_8& -f_8& b_8& b_8& {-f}_8& b_8& -f_8\\ e_8& -c_8& b_8& -f_8& g_8& -h_8& -a_8& d_8\\ e_8& -c_8& -f_8& b_8& d_8& g_8& -h_8& -a_8\\ e_8& -c_8& b_8& -f_8& -a_8& d_8& g_8& -h_8\\ e_8& {-c}_8& -f_8& b_8& -h_8& -a_8& d_8& g_8\end{array}\right].$$

Further, the matrix ${\mathbf{C}}_8^{\left(a\right)}$ is decomposed into two components:

$${\mathbf{C}}_8^{\left(a\right)}={\mathbf{C}}_8^{\left(b\right)}+{\mathbf{C}}_8^{\left(c\right)},$$

(23)

where

$${\mathbf{C}}_8^{\left(b\right)}=\left[\begin{array}{cccccccc}{c}_8& e_8& e_8& e_8& e_8& e_8& e_8& e_8\\ e_8& -c_8& q_8& q_8& -c_8& -c_8& -c_8& {-c}_8\\ e_8& q_8& b_8& -f_8& {-f}_8& b_8& {-f}_8& b_8\\ e_8& q_8& -f_8& b_8& b_8& {-f}_8& b_8& -f_8\\ e_8& -c_8& b_8& -f_8& & & & \\ e_8& -c_8& -f_8& b_8& & & & \\ e_8& -c_8& b_8& -f_8& & & & \\ e_8& {-c}_8& -f_8& b_8& & & & \end{array}\right]{,\mathbf{C}}_8^{\left(c\right)}=\left[\begin{array}{cccccccc}& & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & g_8& -h_8& -a_8& d_8\\ & & & & d_8& g_8& -h_8& -a_8\\ & & & & -a_8& d_8& g_8& -h_8\\ & & & & -h_8& -a_8& d_8& g_8\end{array}\right].$$

Matrix ${\mathbf{C}}_8^{\left(b\right)}$ has the repeated entries in the first, second, third, and fourth columns and rows, which allows us to reduce the number of operations without the need for further transformations. After eliminating the rows and columns containing only zero entries in matrix ${\mathbf{C}}_8^{\left(c\right)}$, we obtain matrix ${\mathbf{C}}_4^{\left(e\right)}$:

$${\mathbf{C}}_4^{\left(e\right)}=\left[\begin{array}{cccc}{g}_8& -h_8& -a_8& d_8\\ d_8& g_8& -h_8& -a_8\\ -a_8& d_8& g_8& -h_8\\ -h_8& -a_8& d_8& g_8\end{array}\right].$$

To process the matrix ${\mathbf{C}}_4^{\left(e\right)}$, we use the expressions for calculating the entries of a circular convolution matrix ${\mathbf{H}}_4=\left[\begin{array}{cccc}{h}_0& h_3& h_2& h_1\\ h_1& h_0& h_3& h_2\\ h_2& h_1& h_0& h_3\\ h_1& h_2& h_1& h_0\end{array}\right]$ for N = 4 [29]:

$${\mathbf{H}}_3={\mathbf{T}}_4^{\left(1\right)}{\mathbf{T}}_{4\times 5}\mathit{diag}(s_0^{\left(0\right)},s_1^{\left(0\right)},s_2^{\left(0\right)},s_3^{\left(0\right)},s_4^{\left(0\right)}){\mathbf{T}}_{5\times 4}{\mathbf{T}}_4^{\left(0\right)},$$

(24)

where

$$s_0^{\left(0\right)}={(g}_8+d_8 -{ a}_8 -{ h}_8)/4, s_1^{\left(0\right)}={(g}_8 - d_8 -{ a}_8+{ h}_8)/4, s_2^{\left(0\right)}={(g}_8+a_8)/2, s_3^{\left(0\right)}={(g}_8 - d_8+{ a}_8 -{ h}_8)/2;$$

$$s_4^{\left(0\right)}={(g}_8+d_8+a_8+h_8)/2;$$

$${\mathbf{T}}_4^{\left(1\right)}=\left[\begin{array}{cccc}1& & & 1\\ & 1& 1& \\ 1& & & -1\\ & 1& -1& \end{array}\right],{\mathbf{T}}_4^{\left(0\right)}=\left[\begin{array}{cccc}1& & 1& \\ & 1& & 1\\ 1& & -1& \\ & 1& & -1\end{array}\right], {\mathbf{T}}_{4\times 5}=\left[\begin{array}{ccccc}1& 1& & & \\ 1& -1& & & \\ & & 1& -1& \\ & & 1& & -1\end{array}\right], {\mathbf{T}}_{5\times 4}=\left[\begin{array}{cccc}1& 1& & \\ 1& -1& & \\ & & 1& 1\\ & & 1& \\ & & & 1\end{array}\right].$$

Based on properties of structural matrices [29], the computational procedure for the eight-point DCT-V is represented by expression

$${\mathbf{Y}}_{8\times 1}={\mathbf{P}}_8^{\left(1\right)}{\mathbf{W}}_{8\times 18}{\mathbf{W}}_{18}^{\left(1\right)}{\mathbf{W}}_{18\times 19}{\mathbf{D}}_{19}{\mathbf{W}}_{19\times 18}{\mathbf{W}}_{18}^{\left(0\right)}{\mathbf{W}}_{18\times 16}{\mathbf{W}}_{16\times 8}{\mathbf{P}}_8^{\left(0\right)}{\mathbf{X}}_{8\times 1},$$

(25)

where

$${\mathbf{W}}_{18\times 16}={\mathbf{I}}_8{\mathbf{T}}_{10\times 8}, {\mathbf{W}}_{18}^{\left(1\right)}={\mathbf{I}}_2{{\mathbf{H}}_2\mathbf{T}}_4^{\left(1\right)}{{\mathbf{H}}_2{\mathbf{H}}_2\mathbf{I}}_6, {\mathbf{W}}_{18}^{\left(0\right)}={\mathbf{I}}_2{{\mathbf{H}}_2\mathbf{T}}_4^{\left(0\right)}{{\mathbf{H}}_2{\mathbf{H}}_2\mathbf{I}}_6, {\mathbf{W}}_{19\times 18}={\mathbf{I}}_4{\mathbf{T}}_{5\times 4}{\mathbf{I}}_{10}, {\mathbf{W}}_{18\times 19}={\mathbf{I}}_4{\mathbf{T}}_{4\times 5}{\mathbf{I}}_{10},$$

$${\mathbf{D}}_{19}=\mathit{diag}(s_0^{\left(8\right)},s_1^{\left(8\right)},s_2^{\left(8\right)},s_3^{\left(8\right)},s_4^{\left(8\right)},s_5^{\left(8\right)},s_6^{\left(8\right)},s_7^{\left(8\right)},s_8^{\left(8\right)},s_2^{\left(8\right)},s_9^{\left(8\right)},s_2^{\left(8\right)},s_3^{\left(8\right)},s_{10}^{\left(8\right)},s_{10}^{\left(8\right)}{,s}_{11}^{\left(8\right)},s_{11}^{\left(8\right)},s_1^{\left(8\right)},s_1^{\left(8\right)}),$$

$$s_0^{\left(8\right)}=c_8,s_1^{\left(8\right)}={-c}_8,s_2^{\left(8\right)}={(b}_8-f_8)/2,s_3^{\left(8\right)}={(b}_8+f_8)/2,s_4^{\left(8\right)}=s_0^{\left(0\right)},$$

$$s_5^{\left(8\right)}=s_1^{\left(0\right)},s_6^{\left(8\right)}=s_2^{\left(0\right)},s_7^{\left(8\right)}=s_3^{\left(0\right)},s_8^{\left(8\right)}=s_4^{\left(0\right)},s_9^{\left(8\right)}={-(b}_8+f_8)/2,s_{10}^{\left(8\right)}{=e}_8,s_{11}^{\left(8\right)}{=q}_8.$$

$${\mathbf{P}}_8^{\left(0\right)}=\left[\begin{array}{cccccccc}1& & & & & & & \\ & & & & & 1& & \\ & & & 1& & & & \\ & & & & & & 1& \\ & 1& & & & & & \\ & & & & & & & 1\\ & & & & 1& & & \\ & & 1& & & & & \end{array}\right],{\mathbf{P}}_8^{\left(1\right)}=\left[\begin{array}{cccccccc}1& & & & & & & \\ & & & & 1& & & \\ & & & & & 1& & \\ & & & 1& & & & \\ & & & & & & 1& \\ & 1& & & & & & \\ & & 1& & & & & \\ & & & & & & & 1\end{array}\right],$$

$${\mathbf{W}}_{8\times 18}=\left[\begin{array}{cccccccccccccccccc}1& & & & & & & & & & & & 1& & & & & \\ & 1& & & & & & & & & & & & 1& 1& & 1& \\ & & 1& & & & & & 1& & & & & 1& & 1& & \\ & & & 1& & & & & & 1& & & & 1& & 1& & \\ & & & & 1& & & & & & 1& & & 1& & & & 1\\ & & & & & 1& & & & & & 1& & 1& & & & 1\\ & & & & & & 1& & & & 1& & & 1& & & & 1\\ & & & & & & & 1& & & & 1& & 1& & & & 1\end{array}\right],$$

$${\mathbf{T}}_{10\times 8}=\left[\begin{array}{cccccccc}& & & & 1& & 1& \\ & & & & & 1& & 1\\ & & 1& & & & & \\ & & & 1& & & & \\ & 1& 1& 1& 1& 1& 1& 1\\ 1& & & & & & & \\ & & 1& 1& & & & \\ & 1& & & & & & \\ & & & & 1& 1& 1& 1\\ & 1& & & & & & \end{array}\right]{,\mathbf{W}}_{16\times 8}=\left[\begin{array}{cccccccc}1& & & & & & & \\ & 1& & & & & & \\ & & 1& & & & & \\ & & & 1& & & & \\ & & & & 1& & & \\ & & & & & 1& & \\ & & & & & & 1& \\ & & & & & & & 1\\ 1& & & & & & & \\ & 1& & & & & & \\ & & 1& & & & & \\ & & & 1& & & & \\ & & & & 1& & & \\ & & & & & 1& & \\ & & & & & & 1& \\ & & & & & & & 1\end{array}\right],$$

A data-flow graph of the proposed algorithm of the eight-point DCT-V is presented in Figure 7. Based on this algorithm, the number of multiplications can be reduced from 64 to 19, but the number of additions is increased from 56 to 61.

3. Discussion of Computational Complexity

The computational complexity of the proposed algorithms is evaluated in this section. The proposed algorithms significantly reduce the number of multiplications in DCT-V algorithms for a 1D signal with the number of samples in the range from two to eight. At the same time, the number of additions was increased by an average of 29%. The number of multiplications was reduced by an average of 57% in the range of number of samples from two to eight. The results obtained based on the elaborated algorithms are shown in

Table 1. The number of additions and multiplications of the direct method against the proposed algorithms.

N	Direct Method		Proposed Algorithms
	Additions	Multiplications	Additions	Multiplications
2	2	4	3 (+33%)	3 (−25%)
3	6	9	8 (+33%)	5 (−44%)
4	12	16	17 (+42%)	7 (−56%)
5	20	25	23 (+15%)	10 (−60%)
6	30	36	41 (+37%)	13 (−64%)
7	42	49	55 (+31%)	11 (−78%)
8	56	64	61 (+9%)	19 (70%)

. In parentheses, the percentage difference in the number of operations is indicated: plus means that the number of operations has risen compared to the direct method, and minus means that it has reduced.

The reduction in multiplications significantly contributes to speeding up the signal processing since the multiplications are more expensive to use than additions. As a result, the amount of resources used on the signal processor is significantly reduced, while allowing for easier operation in real time. The correctness of each proposed algorithm is verified by implementation in the MATLAB environment.

Analyzing the obtained results, we note the following. First, it is necessary to emphasize that the number of arithmetic operations in proposed algorithms depends on how successfully the transform matrix can be factorized. And success closely depends on the structural properties of this matrix. That is why often, in such algorithms, the reduction in the number of multiplications is achieved by increasing the number of additions. For example, in the DCT-V algorithms proposed by the authors, the number of additions increases, and not always delicately. However, if the structure of the transform matrix is “suitable”, we obtain a reduction in both multiplications and additions. For example, this is the case with the developed in [28] fast DST-II algorithms.

Secondly, designers usually try to reduce the number of multiplications as much as possible, even at the expense of a small increase in the number of additions. The problem of reducing the number of multiplications is especially relevant when designing parallel VLSI processors. This is because, compared to a hardware adder, a hardware multiplier occupies a significantly larger area in VLSI, consumes more energy, emits more heat, and creates a very large delay.

Thirdly, this paper considers DCT-V algorithms for short-length input sequences. Processing short-length blocks of signals requires less memory to save temporary data, which is critical for mobile phones and other resource-constrained devices [35]. Fast DCT algorithms for short-length block handling allow detailed signal processing and reduce overall system complexity and delay, which is especially useful for real-time applications such as voice control systems and video conferencing [35].

The development of fast algorithms based on structural properties of transform matrices may be extended to larger input sequences processing in two ways. The first one is applying fast algorithms for short-length sequences as typical modules in synthesizing more complex algorithms [1]. Once constructed, the fast algorithms for short-length sequences can be successfully applied in various projects to unify the process of developing the final algorithm. The second way is designing the intelligent system to obtain the “suitable” matrix structure, for example, with a genetic algorithm applied [36].

4. Conclusions

In this paper, fast type-V DCT algorithms designed for processing short input data sequences were developed and investigated. Fast algorithms for short input data sequences are of particular interest because they are subsequently used as building blocks for developing fast algorithms of large-sized discrete transforms.

As a result of the literature review, two main approaches were identified for designing fast algorithms for DCT. The structural approach analyzes and considers the compositions of identical entries, using heuristic tricks to find successful transformation base matrix factorization schemes [27]. The search for successful factorization schemes largely depends on the intuition and experience of the designer of such algorithms. The analytical approach is based on searching and identifying general principles for factorizing the base transform matrix for arbitrary lengths of the input data sequences. To obtain the fast algorithms for short-length data processing, we use a structural approach. With its help, we analyzed the structural properties of the type-V DCT coefficient matrix and found algorithmic solutions that allow us to reduce the computational complexity of implementing the DCT-V transform. The calculations we carried out, as well as the comparison of the obtained solutions with naive calculation methods, prove the usefulness and cost-effectiveness of the developed algorithms. The resulting factorizations of the DCT-V matrix reduce the number of multiplications by 57% but increase the number of additions by 29% on average in the range of signal sample numbers from two to eight.

As the future development of the research might be the implementation of the designed algorithms to elaboration of time–frequency dictionaries of functions [37,38]. Such dictionaries allow obtaining a compact representation of signals and images to increase the performance of their processing [39,40].