PECULIARITIES OF COMPUTATION THE HASHING ARRAYS FOR THE SYNTHESIS OF FAST ALGORITHMS OF DCT I–IV
DOI:
https://doi.org/10.15588/1607-3274-2020-2-15Keywords:
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.
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.
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2020 I. O. Protsko
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
