The approach of computing the discrete cosine transforms based on cyclic convolutions requires an analysis of the block-cyclic structure of the core of the transform. A model of a compressed description of the block-cyclic structure of the core of a discrete cosine transform in the form of a cyclic decomposition of the substitution is considered. The cyclic decomposition of the substitution contains integer elements of the arguments of the basic function of the transform. In addition, the model are supplemented by a cyclic decomposition of the substitution with simplified values of the elements of the arguments of the basic function and a cyclic decomposition of substitution of signs. An analysis and determination of identical cyclic submatrices in the basic matrix of transform is performed with a variable step of the search, based on the parameters of the model of the discrete cosine transform. As a result of software implementation of the block-cyclic structure analysis, the use of cycles from the cyclic decomposition of the substitution allows us to speed up the process of analysis of the block-cyclic structure of the core of the transform, reduce the number of cyclic convolutions for computation of the discrete cosine transforms of arbitrary sizes. decomposition of substitution Discrete cosine transforms; model of transform core; analysis block-cyclic structure; cyclic
The use of a set of effective algorithms for information data processing provides compression, encoding and encryption of input data streams, increases the speed of formation and reliability of transmission of information and communication systems of compact, secure information packets. Thanks to fast algorithms of discrete Fourier class transforms, efficient storage, transmission and processing of multimedia data is achieved with a significant reduction of computational costs [1]. For wide practical application by international standardization organizations, ISO / IEC and ITU-T, 8 types of discrete cosine transforms (DCT I-VIII) are recommended [2]. DCT refers to orthogonal trigonometric transforms that correspond to the properties of DFT [3]. Orthogonal trigonometric basic systems of DCT I-VIII provide computation of direct and inverse transforms in the real domain, which is especially important for the effective solution of specific practical problems of audio and video data processing.
There are many algorithmic approaches, which can simplify digital transforms and reduce computational cost. For efficient computation of DCT, the various forms of recording the core of transform are used, including matrix multiplication with partial factorization [4], full factorization [5], recursive factorization [6] and other forms [7].
In many scientific fields and several problems, not only fast algorithms, block circulant matrices have been used [8]. Mathematical rules, linear algebra and graph theory have some techniques by which calculation cost and size of the structural matrices can be reduced in repetitive, regular and circulant
2023 Copyright for this paper by its authors. structures. Symmetry and regularity of structures or repetitive structures have been widely studied in details in book [9].
One of the approaches to the development of efficient algorithms is the ability to compute harmonic transforms through cyclic convolutions, which was first described for DFT in the publication by Charles Raider in 1968 [10]. A further development of this approach for the efficient computation of DCT is to bring a harmonic basis to block-cyclic matrix structures and computations of transforms using fast cyclic convolutions [11, 12]. The cyclic decomposition of the substitution is used to bring the harmonic basis of DCT to a set of cyclic submatrices [13]. Execution of the synthesis of fast DCT algorithms requires an analysis and research of the obtained block-cyclic structure of the core of the transform in order to reduce the computational complexity and efficient organization of its execution.
The approach of efficient computation of different types of DCT, based on block cyclic structuring and analysis of the matrix of arguments of basic functions, is considered in [14]. Among the existing eight types of DCT I-VIII [4], the first was DCT-II, which was simply called a discrete cosine transform. DCT-II is obtained on the basis of the DFT formula, in which the input sequence of transform is symmetrically extended to the half-sample [15]. This continuation with periodic symmetry of the HSHS type corresponds to DCT-II, where for each axis of symmetry the sequence of transform can be symmetrically extended to half-samples (HS) according to the systematization of trigonometric transforms in [16].
Direct and reverse DCT-II is described by expressions:
X c2 (k) = x(n) = 2 N −1
x(n) cos[
N n=0 2 N −1
X c2 (k) cos[ N k=0 (2n + 1)k
2N (2n + 1)k 2N ], ], k = 0,1,..., N −1 ; n = 0,1,..., N −1, where x(n), Xc2(k) are input and output sequences of transform.
Let's analyze the core of DCT-II in the matrix form:
X c2 (k ) = C NII (k, n) x(n),
(k, n = 0,1,..., N − 1) ,
(
To form a substitution, choose two columns of the base matrix CIIa. These columns are arbitrary, but should not have an index of n, which is an element of the decomposition of the size N of the transform. where CIIN is the basic matrix of dimension (N × N) with indices on rows k = 0,1,…, N-1 and indices on columns n = 0,1…, N-1.
The function cos [k (2n + 1) π / (2N)] is periodic in relation to 4N samples, so we can write the basic matrix CIІa (k,n) as integer arguments of the cosine function:
CaII (k, n) = [((2n + 1)k mod 4N ], (k, n = 0,1,..., N − 1) , without taking into account φ=π/(2N).
To obtain a model of the structure of the block-cyclic core DCT-II, according to [12], we analyze
the matrix CIIa twice as large for k, n = 0, 1,…, (2N-1) taking into account the periodicity (
The basic function cos[k(2n+1)π/(2N)] is symmetric in relation to the argument 2N, which corresponds to the value of π, so the values of the elements сk,n of the columns are reduced according to the properties of symmetry
CaII (k, n) = 4N − [ (ck ,n ) mod(4N )], if [(ck ,n ) mod 4N ] 2N ,
(k, n = 0,1,...2N − 1).
Therefore the model of the block-cyclic structure of the basis matrix of the DCT-II can be described
using a cyclic decomposition determined by the substitution of the corresponding columns in the matrix
CIIa (
H (L) = H1 (L1 ) H 2 (L2 )... H k (Lk ) = (h11, h12 ,...h1L1 ) (h21, h22 ,...h2L2 )...(hkL1, hkL2 ,...hkLk ) , where hij are integer elements of cycles Hi(Li) with size Li elements (i = 1,2,…, k; j = 1,2,…, Li), k is the number of cycles.
The elements hij of the cycle Hi(Li) correspond to the values from the matrix of arguments of the
basic harmonic transform function CIIa (
Due to the different expressions for the indexes of columns and rows included in the arguments of
the basis function (
For example of the DCT-II of size N = 7, we will form a substitution on the basis of two columns
CIIa. The first column of arguments of the basis function in the matrix CIIa with the index n = 0
corresponds to a natural series. The second substitution column is 3, which is the index (2n+1) for n =
1 and is not an element of the factorization of the size N of the transform. That is, the substitution will
contain elements сk,n , which are defined according to the properties of symmetry (
H(14)=H0(
In order to reduce the computational complexity of the transform [12], it is necessary to reformat the standard cyclic decomposition of substitution. For this provided that each subsequent cycle Hi+1(L i+1) begins with the first element equal to (2N-hi1), where hi1 is the first element of the previous cycle Hi (Li) , if it exists and Li+1 = Li. In each cycle, which is formed as a result of cyclic decomposition of the substitution, the cyclic shift of the elements is possible. The cyclic decomposition Hr(14) for indexing the rows of the base matrix DCT-II uses the cycles from the H(14) with the corresponding first elements, which corresponds to the described condition,
Hr(14) = (0)(
The cyclic decomposition Hc(
Hc(
Thus, as a result of rearrangements of sequences of rows, respectively Hr(14), and columns,
respectively Hc(
According to the properties of asymmetric (π) of DCT-II basis function the matrix (Fig. 1) consists
of the simplified elements ck,n of the arguments, which are determined by the consistent arithmetic
operations:
ck,n = 2N − {4N − [ (ck,n ) mod(4N )], if {4N - [(ck,n ) mod 4N ] N ,
(
ck,n = ck,n , (k, n = 0,1,...2N − 1).
The property of the symmetric/asymmetric of the basis functions of DCT-II proves efficient representation over less value of elements with the addition of corresponding signs Zc(n) in Figure 1 is denoted s_matrix[k][n]. The matrix of signs Zc(n) consists of the values of elements equal to +1, -1, 0 and has the same block cyclic structure with simplified arguments.
Based on the model (
For automatic synthesis of the fast algorithm DCT-II it is necessary to perform the analysis of the structure of the obtained block-cyclic matrix in order to determine identical blocks that are placed horizontally and vertically relative to each other. The presence of identical blocks reduces the computational complexity and provides an opportunity to organize the efficient computation of DCT.
The analysis of the structure and search for a set of elements in the matrix are tasks that are used in many subject areas in the formalization of the algebraic matrix approach. That is, the analysis of the structure of the matrix depends on the application, which imposes a number of requirements and criteria for analysis.
To synthesize efficient algorithms for computing DCT-II based on cyclic convolutions, the analysis
of the block-cyclic basis matrix CIIN is given for the search for identical cyclic submatrices. The criterion
and initial parameters of the analysis is a search for identical blocks with the corresponding indices of
placement in the basic matrix, the elements of which belong to one of the cycles of the model (
To research the structures of matrices a software analysis is used, which performs iterative scanning of the entire set of elements of the matrix. To find the specified fragments, a step-by-step scan of the matrix with the corresponding direction of movement is performed. The disadvantage of this scan is the large number of computations, which with increasing dimension of the matrix of size N × N has the order of computational complexity O(N4). The values of the elements of the matrix N × N can be determined in advance, but the large sizes of transforms require significant memory costs to save them.
For automatic synthesis of algorithms for computing DCT-II based on cyclic convolutions, it is necessary to provide efficient, in terms of speed, analysis of the structure of the block-cyclic core of transform. To do this, we apply the basic parameters of the model H(L) of the block-cyclic structure of the basic matrix DCT-II.
The model H(L) of the block-cyclic structure of the base matrix DCT-II complements its
representation in the form of a simplified cyclic decomposition H'(L), the simplified elements h’ij of
which are determined by formula (
= (h'11 , h'12 ,...h'1L1 ) (h'21 , h'22 ,...h'2L2 )...( h'kL1 , h'kL2 ,...h'kLk ) ,
Zc (L) = Z1 (L1 ) Z 2 (L2 )...Z k (Lk ) = (z11, z12 ,...z1L1 ) (z21, z22 ,...z2L2 )...(zkL1, zkL2 ,...zkLk ) , where zij =1, if hij < N, or zij =-1, if N < hij ≤ 2N, or hij =0 if hij =N; i=1,2,…,k; j=1,2,…,Li.
Therefore, accordance the model (
i,j is coordinates of the first elements of submatrices with the corresponding sign and value of zijcij in the matrix structure;
r is the number of repetitions of identical cyclic submatrices in the matrix structure horizontally/vertically;
r’ is the number of submatrices, starting not from the first cij = h’i1 but from the intermediate simplified element h’ij of the corresponding cycle Hi’(Li); m is the total number of submatrices in the block-cyclic structure.
The block-cyclic structure of a square matrix Ca (k,n) contains a set of cyclic submatrices of different size Li. These submatrices contain integers and are Latin squares. In addition, each square submatrix contains equal elements arranged parallel to the side diagonal or equal pairs of elements symmetrically arranged relative to the main diagonal. Such square submatrices are called Hankel or left-circulant, completely defined by their first row or first column.
The model of the block-cyclic structure of the core of the DCT-II of size N, which contains
leftcirculant submatrices, is determined by cyclic decompositions (
Taking into account the peculiarities of submatrices (square, left-circulant) in the block-cyclic structure of the basic matrix DCT-II is possible to analyze identical submatrices by different algorithms in the directions of search and comparison.
The search and analysis by sorting through the elements, starting from the top row or the first column, involves checking for cyclicity (the same values of elements with the next offset row or column). In the case of non-fulfillment of the requirement for cyclicity, we conclude that the size of the submatrix is complete, and the obtained size determines the dimension of the square submatrix. Next, we move from top to bottom and left to right (horizontally / vertically) to this defined size. We continue the analysis by searching the elements of the first rows or columns, determining a new submatrix, compare it with previously identified submatrices for identity.
The search and analysis by sorting through the elements on the lateral diagonal begins with the first element by checking for cyclicity (the same values of elements parallel to the side diagonal). If the requirement of cyclicity is not met or the maximum value of the number of elements in the lateral diagonal is determined, we conclude that the size of the submatrix is complete and determine its dimension. Next, move from top to bottom and left to right (horizontally/vertically) to this defined size. Continue the analysis by searching for elements in the lateral diagonal when determining a new submatrix, compare it with previously identified, determining the same separately for the same vertical and horizontal coordinates.
Mixed search for the values of elements in the row / column and the values of elements relative to the lateral diagonal, combining these two strategies, taking into account the peculiarities of the corresponding sizes of submatrices will also identify identical cyclic submatrices in the block-cyclic structure of the basic matrix DCT-II.
Identical cyclic submatrices are identical submatrices that have the same corresponding values of elements from the simplified cycle Hi’(Li) and the sign cycle Zc(Li). Quasi-identical cyclic submatrices have the same elements from the simplified cycle Hi’(Li), but opposite values in the cyclic decomposition of signs Zc(Li).
An important feature of the block-cyclic structure of the formed basic matrix DCT-II is presence of
square, left-circulant integer submatrices, the location coordinates, elements and dimensions of which
are determined by the corresponding cycles in (
The analysis of the matrix structure for the identity of the submatrices placed in it will be performed by coordinates (i, j), for which we will determine the values of zijci,j of the first elements of submatrices. Next, it is compared (ci,j) with the corresponding values h’ij of the first or other elements of the cycle Hi’(Li) and as a result of the correspondence, the dimension Li × Li of the square submatrix is determined. Further selection of identical horizontally and vertically placed matrices under the condition of equality of their first elements is performed by the coordinates of the column / row at offsets on the size Li.
The following coordinates (Table 1) of the first elements of submatrices are determined by (i+Li), (j+ Li), where the dimension Li is chosen according to the values of the first elements of submatrices in the matrix structure for the cycle Hi’(Li).
We define identical cyclic submatrices by selecting the coordinates (i+Li), (j+Li) of the first elements zi,jсi,j of identical submatrices horizontally (i+Li) = const in the block-cyclic structure of the basis matrix. For horizontally identical cyclic submatrices, cyclic convolution with element-wise addition/subtraction input data will be performed.
Similarly, identical cyclic submatrices are determined by selecting the coordinates (i+Li), (j+Li) of the first elements of identical submatrices vertically (j+Li) = const in the block-cyclic structure of the basis matrix. For vertically placed identical cyclic submatrices, one cyclic convolution will be performed with the corresponding input data.
For the remaining cyclic submatrices, that do not have identical block-cyclic structure of core of DCT-II in size N, one cyclic convolution will be performed.
The software implementation of analysis and search of identical matrices includes two main
functions: search and selection of cyclic matrices in the block-cyclic structure of the core of DCT-II
based on the model (
The analysis is the research of the obtained data set with values of сi,j of the first elements of cyclic blocks and their coordinates (i, j) in the structure of the block-cyclic matrix. The analysis is aimed at identifying identical blocks placed horizontally and vertically relative to each other. The block diagram of the algorithm for determining identical blocks and, accordingly, the minimum number of cyclic convolutions is given in Fig. 2.
No
Start
As a result of execution of the first function, a set of cyclic subarrays is determined in the form of an array of data containing the values of ci,j of the first elements of the blocks and their corresponding coordinates (i,j), which accordingly are the indices of the two-dimensional array. For example, as a result of the analysis for DCT-II, for size N = 14, we obtain an array of data shown in Table 2.
According to Table 2, the first elements of cyclic subarrays of the basis matrix, equal to, for example,
сi,j = 1, are located in the matrix at coordinates 1 (
For clarity of the results of the analysis in Table 2, in Figure 3, we show the block-cyclic structure of the arguments of the basic matrix DCT-II of size N = 14 with the coloring of the first elements and identical cyclic matrices, which in the analysis are not calculated, except for integer values of the first elements of submatrices.
The algorithm for determining the minimum number of convolutions (Figure 3) uses the result of the first search and selection of cyclic submatrices. In the next stage, the values of the first simplified elements of cyclic submatrices are selected and are compared in the structure of the basis matrix according to the formed coordinates. For each group of coordinates of the found first elements сi,j on the same coordinate yi (i = 0,1,…, 2N-1), a set of convolutions is formed using the function get_conv(v). After each iteration, the processed convolutions are added to the unique list.
As a result of definition of identical blocks horizontally and vertically by means of the software decision, the sequence of cyclic convolutions between a set of the simplified arguments and a set of the corresponding input data is formed. For example, for DCT-II of size N = 14, we obtain (Fig. 4) a conditionally written sequence of cyclic convolutions (X) for the corresponding values of the first elements with coordinates zi,jсi,j { i, j }.
To compute DCT-II of size N = 14 according to the formed block-cyclic structure (Fig. 2) it is necessary to perform 4 one-point and 8 three-point cyclic convolutions. Convolution number 5.c was determined to be opposite in sign to convolution number 2.c based on the analysis of identical cyclic submatrices vertically. At this stage of the analysis, the equals but opposite in sign of the convolutions are considered to be of the same type.
As a result of the analysis of the structure of the formed block-cyclic matrix for the identity of the blocks placed horizontally and vertically, we determine the reduced number and size of cyclic convolutions for the synthesis of the computation algorithm of DCT-II. A set of a reduced number of identical cyclic submatrices in the structure of the basic matrix determines the organization of the computations DCT-II of size N.
The formation of the basic matrix of DCT in the form of a set of cyclic submatrices and analysis of block structure with variable step allows us to speed up the process of analysis of the structure of the core of the transform, reduce the number of computations of cyclic convolutions and, consequently, reduce computational complexity.
The reduced number of cyclic submatrices in the structure of the basis matrix depends on the value
of the transform size N and model (
Identical cyclic submatrices placed vertically relative to each other lead to a one-time computation
of cyclic convolutions, the results of which are used in the process of combining for different X2c(k)
output values of the transform (
Identical cyclic submatrices placed horizontally relative to each other lead to the union of groups of
input values x(n) of the transform and a one-time computation of cyclic convolutions, the results of
which are used for one group X2c(k) of output values of the transform (
Depending on the specific size of the transform N, we have in the block-cyclic structures a corresponding number of cyclic convolutions, which is not constantly increasing with an increasing size N of transform.
In the process of analysis the block-cyclic structures of the DCT-II core for sizes N = pi, the regular increase of horizontal and vertical lines in the structure of transform basis with increasing size of degree is confirmed, which is shown in Fig. 5 for sizes N = 3i on the example of sizes of N = 9,27.
As it can be seen in the example for N = 3i (Fig. 5), for block-cyclic structures of the core of
DCTII for sizes of the integer N = pi is characterized by a regular increase of horizontal and vertical lines in
the structure of the basis. Similarly, this is confirmed by the corresponding increase in the number of
cycles in the model (
Depending on the specific value of the transform of the size N according to the corresponding value,
the choice of columns to form a substitution for the model (
This creates the possibility of choosing the structural diagrams of computers of DCT-II at the system (algorithmic) stage of design.
There are sizes of DCT-II, which have only one variant of the block-cyclic structure for any values of column indices. For example, one variant of the block-cyclic structure has simple values of sizes N = 11, 23, 47, 59, 83.
Computations of DCT-II for short sizes based on cyclic convolutions are characterized by the least time among other approaches to computing transforms and reducing the cost of implementing computers on VLSI [17, 18].
The synthesized DCT-II algorithms as a result of the analysis of the block-cyclic structures for short sizes are basic in the transition to large composite sizes of transform.
Thus, the analysis of the models of the block-cyclic structures of the core of the DCT-II allows us, in the process of synthesis of algorithms, to provide efficient software or hardware organization of transforms based on cyclic convolutions for each specific size N.
The analysis of model of the block-cyclic structures of the DCT-II core for the synthesis of fast algorithms is obtained in the work. The analysis of the block-cyclic structure of the basic matrix for identical blocks is performed using the variable search step, based on the models of the block-cyclic structures of the core of the DCT-II. Algorithmic support and software for analysis of the structure of the block-cyclic basis matrix have been developed, which is used to determine an array of parameters for the formal description of the structure of core of the DCT-II. As a result of the analysis of the models of the block-cyclic structures of core of the DCT-II, a reduced number of identical cyclic submatrices is determined, which allows us to reduce the number of cyclic convolutions for computing of the DCTII of arbitrary sizes N. A fast cosine transform algorithm implements in the form of a set of operations of cyclic convolutions over combined sequences of input data and coefficients of the basic function of transform.
The practical significance of the work lies in the fact that the obtained results of analysis of the block-cyclic structures for specific sizes of transform is important for the system engineering stage of designing a DCT-II based on cyclic convolutions, because clearly reflect the quantitative interactions of its parts on algorithmic level. These transforms are used in information technologies for various purposes, especially in convolutional neural networks [19].
Prospects for further research are the development the synthesis of fast algorithms of the DCT-II in parallel implementation of analysis the block-cyclic structures of the DCT-II core for large sizes.
[13] I. Prots’ko, Algorithm of Efficient Computation of DCT I-IV Using Cyclic Convolutions, Int. J.
Circuits, System and Signal Processing, 7 1 (2013) 1–9. [14] I. Prots’ko, M. Mishcuk, Block-Cyclic Structuring of the Basis of Fourier Transforms Based on
Cyclic Substitution, Cybernetics and Systems Analysis, 57 6 (2021) 1008–1016. [15] I. Prots’ko, V. Teslyuk, Relationship of Fast Computing DCT-II and DST-II Based on Cyclic Convolutions, International Journal of Condition Monitoring and Diagnostic Engineering Management (International Journal of COMADEM), 25 3 (2022) 9–19. [16] S. A. Martucci, Symmetric convolution and discrete sine and cosine transforms, IEEE Transactions on Signal Processing, 42 (1994) 1038–1051. [17] D. F. Chiper, L.-T. Cotorobai, An Efficient Algorithm for the VLSI Implementation of Inverse DCT Based on Quasi-Circular Correlation Structures, in: 15th International Conference on Advanced Technologies, Systems and Services in Telecommunications (TELSIKS), Nis, Serbia, 20-22 Oct. 2021, pp.197–201. doi:10.1109/TELSIKS52058.2021.9606373 [18] P.K, Meher, S. K. Lam, T. Srikanthan, D.H. Kim, S.Y. Park, Area-Time Efficient TwoDimensional Reconfigurable Integer DCT Architecture for HEVC, Electronics, 10 603 (2021). doi:10.3390/electronics10050603. [19] S. Ju, Y. Lee, S. Lee, Convolutional Neural Networks with Discrete Cosine transform features, IEEE Transactions on Computers, 71 12 (2022) 3389 – 3395. doi: 10.1109/TC.2022.3150574