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

Authors

  • I. O. Protsko Lviv Polytechnic National University, Lviv, Ukraine

DOI:

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

Keywords:

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

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. 

Author Biography

I. O. Protsko, Lviv Polytechnic National University, Lviv

Dr. Sc., Associate Professor, Department of Automated Control Systems

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.

How to Cite

Protsko, I. O. (2020). PECULIARITIES OF COMPUTATION THE HASHING ARRAYS FOR THE SYNTHESIS OF FAST ALGORITHMS OF DCT I–IV. Radio Electronics, Computer Science, Control, (2), 149–157. https://doi.org/10.15588/1607-3274-2020-2-15

Issue

Section

Progressive information technologies