SOFTWARE ANALYSIS OF STRUCTURE BLOCK-CYCLIC BASIC MATRIX OF DCT

Authors

  • I. O. Protsko Lviv Polytechnic National University, Lviv, Ukraine
  • M. V. Mishchuk Lviv Polytechnic National University, Lviv, Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2020-3-16

Keywords:

Matrix analysis, search algorithm, hashing array, block-cyclic submatrices, discrete cosine transforms.

Abstract

Context. The matrix notation is used to formalize the subject area within the framework of the algebraic approach. Effective computation of the discrete cosine transforms uses the reduction of a harmoniс basis to a block-cyclic matrix structure with the subsequent calculation of the transform using fast cyclic convolutions. An analysis of the structure of the basic block matrix of transforms provides a synthesis of algorithms of effective discrete cosine transforms of arbitrary sizes. The software implementation of the analysis of block-cyclic structures generates a description of the structure, which allows to reduce the computational complexity of the algorithm of effective discrete cosine transform and to perform parallelization of computation the cyclic convolutions.

Objective. The work is to determine the algorithmic features of the analysis of the structure of a block-cyclic matrix containing integer arguments of basic harmonic functions, which will reduce the computational complexity of the synthesized discrete cosine transform algorithm based on cyclic convolutions.

Method. Search and analysis by enumerating elements of the matrix with a variable step, taking into account the blockiness and cyclicity of the formed basis matrix of the discrete cosine transform, allows you to quickly analyze the structure of the block matrix of transform in comparison with full scanning.

Results. Algorithmic and software for analyzing the structure of a block-cyclic basis matrix have been developed, with the help of which an array of data parameters for a formal description of the basis matrix structure of a discrete cosine transform is determined. The analysis of the structure of the base matrix allows us to determine the presence of identical cyclic submatrices placed horizontally or vertically relative to each other and, thereby, reduce the number of cycles of convolutions.

Conclusions. An effective analysis of the block-cyclic structure of the basis matrix based on the developed software is an important part of the fast algorithm synthesis process, which provides a reduction in computational complexity and the ability to parallelize the implementation of the discrete cosine transform. The developed algorithmic and software for performing the analysis of the structure of a block-cyclic matrix can also be used to analyze the structure and search for the corresponding submatrices in any matrices with integer, real, and zero elements. 

Author Biographies

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

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

M. V. Mishchuk, Lviv Polytechnic National University, Lviv

Student, Department of Automated Control Systems

References

Horn R. A., Johnson C. R. Matrix analysis. New York, Cambridge university press, 1985, 561 p. DOI: 10.1017/CBO9780511810817

Trott M. The Mathematica GuideBook for Programming. New York, Springer-Verlag, 2004, 1028 p. DOI 10.1007/978-1-4419-8503-3

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

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.

Prots’ko I., Rikmas R., Mashevska M. Performance evaluation of the program of DCT-II using cyclic convolutions, Computer Sciences and Information Technologies (CSIT’2017): International scientific and technical conference, Lviv, Ukraine, 5–8 September 2017: proceedings. Lviv, Lvivska polytechnika Press, 2017, pp. 276–278. DOI: 10.1109/STC-CSIT.2017.8098785

Prots’ko I. O. Peculiarities of computation the hashing arrays for the synthesis of fast algorithms of DCT I–IV, Radio Electronics, Computer Science, Control, 2020, No. 2, pp. 149–157.

Prabhune O., Sabale P., Sonawane D. N., Prabhune C. L. Image processing and matrices, Data Management, Analytics and Innovation (ICDMAI): International conference, Pune, India, 24–26 Feb. 2017: proceedings. Pune, Curran Associates, Inc., 2017, pp. 166–171. DOI: 10.1109/ICDMAI.2017.8073504

Zhang F., Liu W., Feng N., Zhai J., Du X. Performance evaluation and analysis of sparse matrix and graph kernels on heterogeneous processors, CCF Transactions on High Performance Computing, 2019, Vol. 1, pp. 131–143.

Duff I. S., Heroux M. A., Pozo R. An overview of the sparse basic linear algebra subprograms: the new standard from the BLAS technical forum, ACM Transactions on Mathematical Software, 2002, Vol. 28, No. 2, pp. 239–267.

Pichel J. C., Pateiro- B. Lopez Sparse Matrix Classification on Imbalanced Datasets Using Convolutional Neural Networks, EEEI Access, 2019, Vol. 7, pp. 82377–82389. DOI: 10.1109/ACCESS.2019.2924060

Prots’ko I. The Algorithm and Structures for Efficient Computation of Type II/III DCT/ DST/ DHT Using Cyclic Convolutions, International Journal of Signal Processing Systems, 2014, Vol. 2, No. 2, pp. 119–127. DOI: 10.12720/ijsps.2.2.119–127

Prots’ko I., Rykmas R., Teslyuk V. Repeatability the block cyclic structures the basis matrices of DCT for sizes pn, International conference Perspective Technologies and Methods in MEMS Design (MEMSTECH’2015), PolyanaSvalyava, Ukraine, 2–4 September 2015: proceedings. Lviv, Veza & Cо, 2015, pp. 107–109.

Downloads

How to Cite

Protsko, I. O., & Mishchuk, M. V. (2020). SOFTWARE ANALYSIS OF STRUCTURE BLOCK-CYCLIC BASIC MATRIX OF DCT. Radio Electronics, Computer Science, Control, (3), 173–180. https://doi.org/10.15588/1607-3274-2020-3-16

Issue

No. 3 (2020): Radio Electronics, Computer Science, Control

Section

Progressive information technologies

License

Copyright (c) 2020 I. O. Protsko, M. V. Mishchuk

Creative Commons License

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.