Repeatability the block cyclic structures 
the basis matrices of DCT for sizes pn
Ihor Prots’ko1, Roman Rikmas2, Vasyl Teslyuk3

1. Lviv State University of Life Safety, UKRAINE, Lviv, S. Klaparivska 35,  E-mail: ioprotsko@gmail.com 
2. LtdC “Uniservice”, Lviv, UKRAINE, Lviv, S. Naukova 5, E-mail: roman.rikmas@gmail.com
3 . CAD Department, Lviv Polytechnic National University, UKRAINE, Lviv, S. Bandery street 12,    E-mail: vtesliuk@polynet.lviv.ua

	Abstract – The structures of basis matrices for efficient computation discrete cosine transforms (DCT) using cyclic convolutions for size the integer power of prime is considered. The structures of basis matrices of DCT are presented via the hashing arrays. Interconnection of the structures or hashing arrays of DCT for the sizes the integer power of prime are determined, what are simplified the analysis of the basis matrices on the stage of synthesis the fast algorithms.
	Keywords – Discrete cosine transform (DCT), block-circular structure, hashing array, cyclic convolution.

I. INTRODUCTION
The move towards low-power consumption and small area for embedded systems support the algorithms using cyclic convolution in digital signal processing.
The algorithms of discrete transform of Fourier class are extensively generalized and advanced for efficient computations [1]. The most common variant of discrete cosine transform is the type-II of DCT, which is often called simply "the DCT" its inverse the type-III of DCT. This is important transform in the area of processing and manipulation of images and video streams compressed in DCT-based methods, such as JPEG, MPEG, H.261, and others [1]. 
     The DCT is defined in matrix form:
                               X  = W* x ,                             (1)
where W(k,n) – a basis square matrix: ( n, k=0,(1),...,N-1); x(n) and X(k) – columns of input and output data, N– size of transform. The basis square matrix of DCT:
W(k,n)=c(n)x(n)cos[p(2k+1)n/2NT],           (2)
       c(n) =      2-1/2,   if n=0 ;
                        1,     otherwise, 
where n, k=0(1)N-1.
Many efficient algorithms and special-purpose structural means have been designed and wide use for sequence with value of size of transform equal integer power of prime, especially of two. Multivariate effective computing algorithms can be divided into: direct matrix factorization of DCT; indirect calculation by FFT or through discrete Hartley transform; algorithms based on the theory of complexity and others. One approach of efficient algorithms is the possibility to compute DCT through the cyclic convolutions. The fast DCT using cyclic convolution wide implement in embedded systems and other microelectronic structures [2]. 
To consider the common properties of block cyclic structures the basis matrices for efficient computation DCT using cyclic convolutions for sizes the integer power of prime.

II. The Parameters of the HASHING ARRAY 

The method using cyclic convolutions of efficient computation of DCT are proposed for arbitrary size of transform [3, 4]. It is based on the decomposition of discrete basis matrix of arguments into block-circular submatrices. In result, the structure of the basis matrix are determined by the hashing array 
                H(n)=H1(L1) H2(L2) … Hk(Lk),                   (3)
H(n)=(n11,n12,…,n1L1)(n21,n22,…,n2L2)…,(nkL1,nkL2,…,nkLk).(4) 
where n – size of hashing array, Li – number of nij elements  hashing subarrays Hi(Li), k – number of subarrays. 
	The size of the hashing arrays H(n) equals n=2N-1. The determination of the parameters of hashing array (n, k, Li) defines specific of the structures and the computational algorithm via cyclic convolutions.   
The hashing array H(n) efficient represents of less value of elements of arrays of H’(n) with the addition of a accordance arrays of signs Z(n), corresponding the properties of symmetry the basis matrix. The arrays of signs Z(n) consist values of elements equal +1,-1, 0. The examples of the hashing arrays H(n) and H’(n) with the addition the array of signs Z(n) for size of transform N=2n, 3n, 5n are presented the accordance form (4):
for N=8=23, k=4;
H(15)=(1,3,9,5,15,13,7,11)(2,6,14,10)(4,12)(0) ;
H’(15)=(1,3,7,5, 1, 3, 7, 5 ) (2, 6,  2, 6)(4,  4)(0),
Z(15)= (+,+,-,+,-,-,+,-)(+,+,-,-)(+,-)(+);                                                                              for N=16=24, k=5; 
H(31)= (1,3,9,27,17,13,25,11,31,29,23,5,15,19,7,21) (2,6,18,10,30,26,14,22)(4,12,28,20)(8,24)(0);
H’(31)= (1,3,9,5,15,13,7,11,1,3,9,5,15,13,7,11) (2,6,14,10,2,6,14,10)(4,12,4,12 )(8,8)(0),
Z(31)= (+,+,+,-,-,+,-,+,-,-,-,+,+,-,+,-)(+,+,-,+,-,-,+,-)(+,+,-,-)(+, -)(+).
for N=9=32, k=8;
H(17)=(1,5,11,17,13,7)(3,15)(9)(2,10,14)(4,16,8)(6)(12)(0);
H’(17)= (1,5,7,1,5,7)(3,3)(9) (2,8,4) (4,2,8)(6) (6)(0), 
Z(17)= (+,+,-,-,-,+) (+,-)(0)(+,-,-) (+,-,+)(+) (-)(+);
for N=51, k=5;
H(9)= (1,3,9,7) (5) (2,6)(4,8) (0);
H’(9)= (0)(1,3,1,3)(5)(2,4)(4,2) (0),
Z(9)= (+,+,-,-)(0)(+,-)(+,-) (+).
The subarrays of hashing array H(n) reproduce Hankel circular submatrices in the structure of a basis square matrix W, that lead to computation of cyclic convolutions for the values of submatrices of basis matrix W with arguments  Z(n)H’(n)) and input data (x) of sizes Li. The hashing array H(n) defines the order of input data x(i) in algorithms of computation of DCT via cyclic convolutions. 

III. Common Property of Structures of the Basis Matrices

Let analyze the distribution of cyclic structures for specific values of sizes of DCT on base hashing arrays. The imported stage of the synthesis the efficient algorithms of DCT is analyzes the structure of basis matrix, that defines the specifics of computational algorithm. In paper [4] propose to conduct horizontal/vertical analyses of repeatability of block-cyclic structures. That is calculated using the coordinates of the row and column values ​​of the first elements of submatrices and analyzed value of the first elements. To find of identical and quasi-identical circular submatrices (with the same index, but opposite sign)  among value first elements of requires significant amount of time costs.
	In case the efficient computation DCT using cyclic convolutions for size the integer power of prime, the sizes of each power of prime value has the common structure of the basis matrices.
Proposed algorithm of DCT on base cyclic convolutions for size of transform N=pn (n=2, 3,…) place submatrices accordance the hashing array H(n). Therefore the peculiarity algorithm of transforms of size N=2n is determining general distribution of the submatrices in basis matrix of DCT the accordance form (3): 
N=23    H(15)= H1(23) H2(22) H3(21)H4(20);
N=24   H(31)= H1(24) H2(23) H3(22)H4(21) H4(20);
…
N=2n   H(2n+1-1)=  H1(2n) H2(2n-1)H2(2n-2)... Hk(20).
The hashing subarray H1(2n) consists the set of odd elements to value 2N-1, are denoted bold in hashing array. A difference in the formula (2) of values in rows k and columns (2n+1) requires the transition from hashing array P(n) to the appropriate hashing array indices of the columns Hc(2n) and rows Hr(2n+1-1):
Hc(2n) = H1(2n);
Hr(2n+1-1)= H1(2n) H2(2n-1)H2(2n-2)... Hk(20).
The example of the matrix structure (N x 2N-1) of DCT using cyclic convolution for size N=8=23 (Fig.1) with the hashing array H(15), where each hashing subarray H1(23), H2(22), H3(21), H4(20) presents Hankel circular submatrices.

level 0		         H1(23)			
level 1	H2(22) 	                H2(22) 		
H3(21)
level 3		H3(21)		H3(21)	H3(21)	
H4(20)
level 4	…	…    …   …   …   …   …	H4(20)	

Fig. 1 The structure of basis matrix of DCT for size N=8.
Accordance the structure of basis matrix of DCT for size N=2n on each level has 2i - number of Hankel circular submatrices Hi+1(2n-i), where i=0(1),…, n+1 number of level.
The matrix structure (Nx2N-1) of DCT using cyclic convolution for size N=3n (n=2,3,…) is determined the general distribution of formed hashing arrays:
N= 32, H(17)= H1(6) H2(2) H3(1) H4(3) H5(3) H6(1)H7(1);                N= 33, H(53)= H1(18)H2(6)H3(2)H4(1)
                                H5(9)H6(9)H7(3)H8(3)H9(1) H10(1);
N=34, H(80)= H1(54) H2(18) H3(6) H4(2)H5(1) 
H6(27)H7(27)H8(9) H9(9)H10(3)H1(3)H12(1)H13(1);
…
N=3n, H(2n+1-1)=H1(2∙3n/31)H2(2∙3n/32)H3(2∙3n/33)…  
            Hn(2∙3n/3n)Hn+1(1) Hn+2(3n/31)Hn+3(3n/31)Hn+4(3n/32)Hn+5(3n/32) Hn+6(3n/33)  Hn+7(3n/33)… Hn+2n-3(3n/3n-1) Hn+2n-2(3n /3n-1) Hn+2n-1(3n/3n) Hn+2n(3n/3n).
The example of the matrix structure (N x 2N-1) of DCT using cyclic convolution for size N=32 (Fig.2), where H’1(6)=(1,5,7,1,5,7), H’2(2)=(3,3), H’3(1)=(9), H’4(3)=(2,8,4), H’5(3) =(4,2,8), H’6(1)=(6), H’7(1)=(6). 

 (+1  +5  -7  -1  -5  +7)  (+3  -3)	(0)  
 (+3  -3)	(+3  -3)	(+3  -3) (0)   (0)   (0)  
 (0)   (0)  (0)  (0)   (0)   (0)  (0)  (0)  (0)
 (+2  -8  -4) (+2  -8  -4)  (+6) (+6)   (-0) 
 (+4  -2  +8) (+4  -2  +8)(-6) (-6)    (+0) 
 (+6)(+6)(+6)(+6)(+6)(+6)(-0)(-0) (-0)  
 (-6) (-6)(-6)(-6)(-6)(-6) (+0) (+0) (+0) 	
Fig. 2 The structure of basis matrix of DCT for size N=32 with simplified elements and corresponding signs.
The matrix structure (N x 2N-1) of DCT on base cyclic convolutions for size N=5n (n=2, 3, …) is determined the general distribution of formed hashing arrays:
N=51, H(9)= H1(4) H2(1) H3(2) H4(2) ;           
N=52, H(49)=H1(20) H2(4)H3(1)H4(10)H5(10)H6(2)H7(2);
N=53, H(249)=H1(100) H2(20) H3(4) H4(1) H5(50)H6(50) H7(10)H8(10)H9(2)H10(2);
…
N=5n, H(2n+1-1)= H1(4∙5n/51) H2(4∙5n/52) H3(4∙5n/53)… Hn(4∙5n/5n) Hn+1(1) Hn+2(2∙5n/51) Hn+3(2∙5n/51) Hn+4(2∙ 5n/52)  Hn+5(2∙5n /52) Hn+6(2∙5n/53) Hn+7(2∙5n/53)… Hn+2n-2(2∙5n/5n-1) Hn+2n-1(2∙5n/5n-1) Hn+2n(2∙5n/5n) H n+2n+1(2∙ 5n /5n).
The example of the matrix structure (N x 2N-1) of  DCT using cyclic convolutions for size N=51 (Fig.3) with  hashing array H(9), where Hc(5)= H1(4) H2(1), Hr(9)= H1(4) H2(1), H3(2) H4(2).
		H1(4)			H2(1)	
	H2(1)	H2(1)	H2(1)	H2(1)	H2(1)	
	H3(2)		H3(2)		0	
	H4(2)		H4(2)		0	
   
Fig.3 The structure of basis matrix of DCT for size N=5.

+1	+3	-1	-3	0	
+3	-1	-3	+1	0	
-1	-3	+1	+3	0	
-3	+1	+3	-1	0	
+5	+5	+5	+5	+5	
+2	-4	+2	-4	-0	
-4	+2	-4	+2	-0	
+2	-4	+2	-4	+0	
-4	+2	-4	+2	+0	
Fig.4 The basis matrix of DCT for size N=5 with simplified elements and corresponding signs.
Analysis structure of basis matrices (Fig. 3) is equivalent the structure of indexes matrix (Fig. 4) for simplified hashing array H’(9) with the supplement respective the array Z(9) of cosine signs.
	Analysis structure of submatrices in basis matrices of DCT defines, that many circular submatrices are
      .                           (5)
 Because the sequence of elements nij of subarrays in simplified hashing array of H’(n) the reiterate  
 H’(nk)=(a, a)= (nkL1, nkL2, …, nkLj,   nkL1, nkL2, …, nkLj),   (6)
which reduces the size by 2 times the cyclic convolutions.
Corresponding [4], the process of synthesis of efficient algorithms of DCT includes: 
1) the definition of elements and form of the hashing array H(n);
2) the definition of elements of simplified hashing array H'(n) and matrix signs Z(n);
3) the analyses (horizontal/vertical) of reiteration of the cyclic submatrices in the matrix structure that allows:
a) to determine the order of combination  of input data x(n) for identical horizontal submatrices;
b) to determine the  number and order of cyclic convolutions;
c) to combine the intermediate results of cyclic convolutions to output data X(k).
The analyses of the structures of basis matrices is main and elaborate stage in the process of synthesis of efficient algorithms of DCT using cyclic convolutions. 

REFERENCES
[1] N. L. Tsitsas, “On block matrices associated with discrete trigonometric transforms and their use in theory of wave propagation,” Journal of Computational Mathematics, vol. 28, pp. 1-15, 2010. 
[2] C. Cheng and K. K. Parhi, “Hardware efficient fast DCT based on novel cyclic convolution structures,” IEEE Trans. Signal Process., vol. 54, no. 11, pp. 4419–4434, Nov. 2007.
[3] I. Prots’ko, The generalized technique of computation the discrete harmonic transforms. Proceedings International Conference MEMSTECH’2008, Poljana, 21-24 may 2008. pp.101-102.
[4] I. Prots’ko, “Algorithm of efficient computation of DCT I-IV using cyclic convolutions,” Intl. J. of Circuits, Systems and Signal Processing, vol. 1, no. 7, pp. 1-9, 2013. 
[5] J. Vasyliuk, V. Teslyuk, Architecture Design of Cooperation Program Module with Ontology. Proceedings International Conference MEMSTECH’ 2014, Poljana, june 2014. pp.4-5.

IV. CONCLUSION
	The process of synthesis analyzes the structure of basis matrix that defines the specific character of computational algorithm. The finding of identical and quasi-identical submatrices is based on the values of parameters of hashing array H(n) and hashing array H’(n), supplemented array Z(n) of cosine signs. Searching for identity cyclic submatrices among value elements of basis matrix may be done in advance, but a large search of all elements requires significant amount of memory to store and associated time costs.
	Repeatability the block cyclic structures the basis matrices of DCT for sizes pn eliminates 3) third stage of synthesis of efficient algorithms. Automatic generation the algorithms for computation DCT using cyclic convolutions for size the integer power of prime apply the repeatability of the structure of the basis matrices. Structured according to this approach of the basis matrix of DCT makes the proposed algorithms for implementation in parallel systems, where are performed the separate computations of cyclic convolutions and the combinations of their results.
The concurrency and low complexity of the algorithms are well suited for software implementations and applying in embedded systems and other microelectronic devices [5].