Підвищення ефективності обчислення дійсних гармонічних перетворень на основі циклічних згорток

Abstract

Дисертаційна робота присвячена питанням дослідження та розвитку ефективного підходу обчислення дійсних дискретних гармонічних перетворень (дискретних косинусних, синусних і перетворень Хартлі) на основі циклічних згорток. Вирішено актуальну науково-прикладну проблему підвищення ефективності обчислювальних характеристик дійсних дискретних гармонічних перетворень шляхом розроблення узагальненої методології, що вирішує завдання формування й аналізу структури дискретних гармонічних складових базису перетворення у вигляді набору ганкелевих циркулянтів і виконання обчислення перетворень на основі циклічних згорток. У результаті розроблення узагальненої методології одержано систематизовану сукупність принципів, методів, алгоритмів, способів для синтезу ефективних алгоритмів обчислення дійсних дискретних гармонічних перетворень на основі циклічних згорток. Для синтезу алгоритмів застосовано твірний масив, який визначається циклічним розкладом підстановки рядків/стовпців аргументів функції базису перетворення. Розвинуто метод цілочисельного пошуку ідентичних підматриць у блочно- циклічній структурі ядра перетворення, що використовує твірні масиви. Досліджено особливості синтезу алгоритмів для виконання обчислення чотирьох основних видів кожного з ДКП, ДСП, ДПХ перетворень на основі циклічних згорток. Показано, що замість примітивних елементів циклічних груп для формування блочно-циклічної структури базису перетворення простіше застосовувати твірні масиви, за якими формується базис перетворення з ганкелевими підматрицями. Обчислення циклічних згорток для послідовностей гармонічних коефіцієнтів з повторенням групи елементів, що зустрічаються в запропонованих алгоритмах, зменшує обсяг виконання циклічних згорток і, відповідно, обчислювальну складність дійсних дискретних гармонічних перетворень. Розроблено ефективні структури обчислювальних систем прямого і зворотнього виконання ДГП, що містять систолічні конвольвери виконання циклічних згорток. На основі узагальненої методології синтезу розроблено програмне забезпечення для швидкого обчислення ДГП довільного обсягу на основі циклічних згорток.

Разработан ряд методов эффективного вычисления дискретных преобразований класса Фурье, которые основываются на различных теоретических принципах. Метод, который использует для эффективного вычисления дискретных преобразований циклическую свертку, имеет низкие показатели вычислительной сложности, экономен при реализации в интегральных микросистемах, обобщается на разные виды преобразований. Диссертационная работа посвящена разработке обобщенной методологии синтеза эффективных алгоритмов вычисления вещественных преобразований с косинусными, синусными, касинусными базисными функциями на основании циклических сверток. Решена актуальная научно-прикладная проблема повышения эффективности вычислительных характеристик действительных ДГП путем разработки обобщенной методологии которая решает задачи формирования и анализа структуры дискретных гармонических составляющих базиса преобразования в виде набора ганкелевых циркулянтов и выполнения вычисления преобразований на основании циклических сверток. Для синтеза алгоритмов предложено использовать хэш массив, который определяется циклическим разложением подстановки строк/столбцов аргументов базисной функции ДГП. В результате разработки обобщенной методологии получена систематизированная совокупность принципов, методов, алгоритмов, способов для синтеза эффективных алгоритмов вычисления действительных дискретных гармонических преобразований на основании циклических сверток. Исследованы особенности синтеза алгоритмов для выполнения вычисления четырех видов каждого с ДКП, ДСП, ДПХ преобразований. Показано, что вместо поиска примитивных элементов для формирования перестановки, проще использовать хэш массивы, с помощью которых формируется базис преобразования с ганкелевыми подматрицами. Доказано эффективное использование для синтеза алгоритмов и анализа блочно- циклической структуры ядра ДГП хэш массива по сравнению с использованием примитивных элементов циклических групп. Вычисление циклических сверток для последовательностей данных с повторением группы элементов, которые встречаются в разработанных алгоритмах, уменьшает вычислительную сложность алгоритма. Разработаны эффективные структурные схемы содержащие систолические конвольверы для вычисления прямого и обратного ДГП на основании циклических сверток. Описана программная реализация синтеза быстрых алгоритмов вычисления ДГП произвольной длины на основании циклических сверток

The thesis is devoted to the research and development of an efficient approach to the computation of real discrete harmonic transforms based on cyclic convolutions and to the solution of the problems related to the analysis and synthesis of multiversion efficient algorithms for the computation of real transforms with cosine, sine, casine basis functions. The scientific and technical problems of the analysis and synthesis of efficient algorithms for computation of DCT, DST, DHT and their types using cyclic convolutions is resolved; the usage of a hashing array, which is formed via the cyclic of substitution of the basis matrix arguments, is proposed; the technique of the analysis of block cyclic structure of basis discrete harmonic transform using hashing arrays is developed. In result of analysis the efficient methods of the computation of the discrete transforms of Fourier class based on cyclic convolutions, the general approach to the synthesis of efficient algorithms for the computation of real harmonic transforms and their types is developed. The peculiarities of synthesis algorithms for efficient computation of each of the four types of DCT, DST, DHT are determined. The efficient usage for the synthesis of a hashing array compared with the primitive elements of cyclic groups is proved. The computations of cyclic convolutions for sequences of data with the repetitive groups of the harmonic coefficients, which occur in the proposed algorithms, reduce computational complexity of the algorithms. The computing structures that perform real discrete harmonic transforms based on cyclic convolution and the components of the efficient computation of fast cyclic convolutions are developed. The software implementation of the synthesis of fast algorithms for the computation of real discrete harmonic transforms based on cyclic convolutions is described.