DOI: https://doi.org/10.15588/1607-3274-2020-2-15

PECULIARITIES OF COMPUTATION THE HASHING ARRAYS FOR THE SYNTHESIS OF FAST ALGORITHMS OF DCT I–IV

I. O. Protsko

Abstract


Actuality. Discrete cosine transforms provide high efficiency of applications in modern information processing facilities. After all, the computation of forward and reverse transforms in the real field is especially important for the effective solution of specific practical problems in the field of information technology. The use of fast transforms with a significant reduction in computational cost requires the development of new efficient methods for synthesizing algorithms and performing them for different types of real discrete transforms.

The purpose of the work is to determine the differences and common features of computing hashing arrays for the synthesis of fast algorithms of four basic types of discrete cosine transforms based on cyclic convolutions.

Method. The paper analyzes the peculiarities of the computation of hashing arrays based on the cyclic decomposition of a substitution, which is determined from the rows/columns of arguments of the basic functions of the kernel of a discrete cosine transform.

Results. The result of the research is to determine and generalize the main differences and common features of the computation of hashing arrays for the formation of block-cyclic structures in the basis matrices of discrete cosine transforms of arbitrary sizes.

Conclusions. The research analyzes the peculiarities of computing hashing arrays for four main types of discrete cosine transforms. The basic idea of using a generalized mathematical apparatus to efficiently compute different types of discrete cosine transformations based on cyclic convolutions is to use hashing arrays containing a brief description of the block-cyclic structure of the transformation basis. Hashing arrays are determined by the cyclic decomposition of the substitution and ensure that the basic transformation matrix is reduced to a set of cyclic left submatrices. The analysis of the peculiarities of the choice of the substitution sequences, the execution of the cyclic decomposition of the substitution, the selection of arrays for the formation of hashing arrays provide the possibility of efficient organization of computations for different types and sizes of discrete cosine transforms. 


Keywords


Discrete cosine transformation, cyclic convolution, hashing array, cyclic decomposition of the substitution.

References


Britanak V., Yip P., Rao K. R. Discrete Cosine and Sine Transforms. New York, Academic Press, 2007, 368 p.

ITU-T Recommendations [Electronic resource]. Access mode: http://www.itu.int/net4/ipr/details_ps.aspx?sector= ITU-T&id=H262-48

Blahut R. E. Fast algorithms for signal processing. Cambridge, University Press, 2010. DOI: 10.1017/CBO9780511760921

Prots’ko I., Rykmas R. Becoming of Discrete Harmonic Transform Using Cyclic Convolutions, American Journal of Circuits, Systems and Signal Processing, 2015, Vol. 1, pp. 114–119.

Процько І. О. (Україна); Пат. 96540 Україна, МПК2006 G06F 17/16. Спосіб приведення дискретних гармонічних складових цифрових сигналів до циклічних згорток. Заявник Національний університет «Львівська політехніка». № a201014053; заявл. 25.11.2010; опубл. 10.11.2011, Бюл. №21.

Prots’ko I. The generalized technique of computation the discrete harmonic transforms, Perspective Technologies and Methods in MEMS Design, Polyana, Ukraine, May 2008, proceedings. Lviv, Veza & Cо, 2008, pp. 101–102. DOI: 10.1109/MEMSTECH.2008. 4558753

Rader С. М. Discrete Fourier Transforms When the Number of Data Samples is Prime, Proceedings of IEEE, 1968, Vol. 56, pp. 1107–1108. DOI: 10.1109/PROC.1968.6477

Eklundh J.-O., Huang T. S., Tyan S. G., Zohar S. Winograd’s discrete Fourier transform algorithm, Twodimensional Digital Signal Processing. Transforms and Median Filters. Berlin, Heidelberg, New York, SpringerVerlag, 1981, pp. 89–152.

Chan Y.-H., Siu W.-C. Generalized approach for the realization of discrete cosine transform using cyclic convolutions, IEEE international conference on Acoustics, Speech, and Signal processing: digital speech processing, Minneapolis, USA, 27–30 April 1993: proceedings. Washington, IEEE Computer Society, DC, 1993, Vol. III, pp. 277–280. DOI: 10.1109/ICASSP.1993. 319489

Yin R.-X., Siu W.-C. New Fast Algorithm for Computing Prime length DCT through Cyclic Convolutions, Signal Processing, May 2001, Switzerland, Vol. 81, pp. 895–906.

Chiper D. F. A New VLSI algorithm and Architecture for the hardware implementation of type IV discrete cosine transform using a pseudo-band correlation structure, Central European Journal of Computer Science, 2011, Vol. 1, No. 2, pp. 90–97. DOI: 10.2478/s 13537-011-0015-7

Prots’ko I. O., Teslyuk V. M Development of WFTA based on the hashing array, Radio Electronics, Computer Science, Control, 2018, No. 2, pp. 135–142.

Prots’ko I. Algorithm of Efficient Computation of DCT I– IV Using Cyclic Convolutions, International Journal of Circuits, Systems and Signal Processing, 2013, Vol. 7, Issue 1, pp. 1–9.

Knuth D. E. The Art of Computer Programming; Seminumerical Algorithms. 3rd ed., t.1. New York, AddisonWesley Publishing Co., 1997, 784 p.

Math Kernel Library Homepage [Electronic resource]. Access mode: URL: https://software.intel.com/en-us/intel-mkl

Jridi M., Alfalou A., Meher PK A generalized algorithm and reconfigurable architecture for efficient and scalable orthogonal approximation of DCT, IEEE Transactions on Circuits and Systems I: Regular Papers, 2014, Vol. 62, No 2, pp. 449–457.


GOST Style Citations


1. Britanak V. Discrete Cosine and Sine Transforms / V. Britanak, P. Yip, K. R. Rao.  – New York : Academic Press, 2007.

2. ITU-T Recommendations [Electronic resource]. – Access mode: http://www.itu.int/net4/ipr/details_ps.aspx?sector= ITU-T&id=H262-48

3. Blahut R. E. Fast algorithms for signal processing / R. E. Blahut. – Cambridge : University Press, 2010. DOI: 10.1017/CBO9780511760921

4. Prots’ko I. Becoming of Discrete Harmonic Transform Using Cyclic Convolutions / I. Prots’ko, R. Rykmas // American Journal of Circuits, Systems and Signal Processing. – 2015. – Vol. 1. – P. 114–119.

5. Пат. 96540 Україна, МПК2006 G06F 17/16. Спосіб приведення дискретних гармонічних складових цифрових сигналів до циклічних згорток / І. О. Процько (Україна); Заявник Національний університет «Львівська політехніка». – № a201014053; заявл. 25.11.2010; опубл. 10.11.2011, Бюл. №21.

6. Prots’ko I. The generalized technique of computation the discrete harmonic transforms / I. Prots’ko // Perspective Technologies and Methods in MEMS Design, Polyana, Ukraine, May 2008 : proceedings. – Lviv : Вежа і Ко, 2008. – P.101–102. DOI: 10.1109/MEMSTECH.2008. 4558753

7. Rader С. М. Discrete Fourier Transforms When the Number of Data Samples is Prime / C. M. Rader // Proceedings of IEEE. – 1968. – Vol. 56. – P. 1107–1108. DOI: 10.1109/PROC.1968.6477

8. Winograd’s discrete Fourier transform algorithm // Twodimensional Digital Signal Processing. Transforms and Median Filters / [J.-O. Eklundh, T. S. Huang, S. G. Tyan, S. Zohar]. – Berlin, Heidelberg, New York: SpringerVerlag, 1981. – P. 89–152.

9. Chan Y.-H. Generalized approach for the realization of discrete cosine transform using cyclic convolutions / Y. H. Chan, W.-C. Siu // IEEE international conference on Acoustics, Speech, and Signal processing: digital speech processing, Minneapolis, USA, 27–30 April 1993: proceedings. – Washington: IEEE Computer Society, DC, 1993. – Vol. III. – P. 277–280. DOI: 10.1109/ICASSP.1993. 319489

10. Yin R.-X. New Fast Algorithm for Computing Prime length DCT through Cyclic Convolutions / R.-X. Yin, W.-C. Siu // Signal Processing. – May 2001, Switzerland. – Vol. 81. – P. 895–906. 

11. Chiper D. F. A New VLSI algorithm and Architecture for the hardware implementation of type IV discrete cosine transform using a pseudo-band correlation structure / D. F. Chiper // Central European Journal of Computer Science. – 2011. – Vol. 1, No. 2. – P. 90–97. DOI: 10.2478/s 13537-011-0015-7

12. Prots’ko I. O. Development of WFTA based on the hashing array / I. O. Prots’ko, V. M. Teslyuk // Radio Electronics, Computer Science, Control. – 2018. – № 2. – P. 135–142.

13. Prots’ko I. Algorithm of Efficient Computation of DCT IIV Using Cyclic Convolutions / I. Prots’ko // International Journal of Circuits, Systems and Signal Processing. – 2013. – Vol. 7, Issue 1. – P. 1–9.

14. Knuth D. E. The Art of Computer Programming; Seminumerical Algorithms. 3rd ed., t.1 / D. E. Knuth. – New York : Addison-Wesley Publishing Co., 1997.

15. Math Kernel Library Homepage [Electronic resource]. – Access mode: URL: https://software.intel.com/en-us/intelmkl

16. Jridi M. A generalized algorithm and reconfigurable architecture for efficient and scalable orthogonal approximation of DCT / M. Jridi, A. Alfalou, PK Meher // IEEE Transactions on Circuits and Systems I: Regular Papers. – 2014. – Vol. 62, No 2, – P. 449–457.







Copyright (c) 2020 I. O. Protsko

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.