Програмний аналіз структури блочно-циклічної базисної матриці ДКП

Abstract

UK: Актуальність. Використання матричного запису застосовується для формалізації предметної галузі в рамках алгебраїчного підходу. Ефективне обчислення дискретних косинусних перетворень використовує приведення гармонічного базису до блочно-циклічних матричних структур з подальшим обчисленням перетворень за допомогою швидких циклічних згорток. Детальний аналіз структури базисної блочної матриці перетворення забезпечує синтез ефективних алгоритмів дискретних косинусних перетворень довільних обсягів. Програмна реалізація проведення аналізу блочно-циклічних структур формує опис структури, що дозволяє зменшити обчислювальну складність алгоритму та виконати розпаралелення обчислень циклічних згорток. Мета роботи – визначення алгоритмічних особливостей проведення аналізу структури базисної блочно-циклічної матриці, яка містить цілочисельні аргументи базисних гармонічних функцій, що дозволить зменшити обчислювальну складність синтезованого алгоритму дискретного косинусного перетворення на основі циклічних згорток. Метод. Пошук і аналіз перебором елементів матриці зі змінним кроком, що враховує властивості блочності та циклічності сформованої базисної матриці дискретного косинусного перетворення, дозволяє швидше виконувати аналіз структури базисної блочної матриці перетворення в порівнянні з повним скануванням. Результати. Розроблено алгоритмічне та програмне забезпечення виконання аналізу структури блочно-циклічної базисної матриці, за допомогою якого визначається масив параметрів даних формального опису структури базису дискретного косинусного перетворення. Дані аналізу структури базисної матриці дозволяють визначити наявність ідентичних циклічних підматриць розміщених горизонтально або вертикально одна відносно іншої і, тим самим, зменшити кількість виконання циклічних згорток. Висновки. Ефективний аналіз блочно-циклічної структури базисної матриці на основі розробленого програмного забезпечення є важливою частиною процесу синтезу швидкого алгоритму, який забезпечує скорочення обчислювальної складності та можливість розпаралелення виконання дискретного косинусного перетворення. Розроблене алгоритмічне та програмне забезпечення виконання аналізу структури блочно-циклічної базисної матриці може застосовуватись і для аналізу структури та пошуку відповідних підматриць в будь-яких матрицях з цілими, дійсними та нульовими елементами. EN: 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.