Розглянуто програмну модель визначення еквівалентних циклічних секцій для матриці показників і матриці знаків дійсного базису дискретного гармонічного перетворення даних. Результати програмної моделі можна застосовувати для проектування розподілу завантаження ресурсів розподілених обчислювальних структур та створення ефективних алгоритмів виконання перетворень.

Розглянуто узагальнений підхід ефективного обчислення дискретного косинусного перетворення (ДКП) на основі циклічних згорток. Підхід грунтується на приведенні матриці аргументів і матриці знаків дійсного базису ДКП до еквівалентних циклічних секцій.

Розглянуто ефективне обчислення дискретних гармонічних перетворень. Обчислювальний алгоритм визначено за сформованою структурою дискретної базисної матриці. Зазначено, що симетричні циклічні згортки є основою ефективного обчислення дискретних гармонічних перетворень.

Дисертація присвячена аналізу та розробці алгоритмічних та спеціалізованих апаратних засобів швидкого обчислення дискретного перетворення Фур'є (ДПФ) послідовностей довільного обсягу на основі проведення декомпозиції експоненціального базису ДПФ на показники степенів та матриці знаків. Проаналізовано та одержано ганкелеві лівоциркулянтні матриці показників експоненціального базису ДПФ, доведено, що матриці показників степені і знаків косинусу, синусу мають еквівалентні структури, приведено узагальнену схему обчислення ШПФ, розглянуто спеціалізовані засоби та функціональні блоки для виконання ДПФ послідовностей довільного обсягу.

Проаналізовано аргументи дискретного перетворення класу Фур'є для простого обсягу, що задають частковий випадок алгебричної системи - абелеві групи. Визначено особливості та характер породжуючих елементів даної системи.

Розглянуто стратегію пошуку та визначення однотипових підматриць у базисній матриці дискретного гармонічного перетворення. Однотиповість визначають окремо за вертикального та горизонтального двовимірного положення підматриць. Базисна матриця задається твірним масивом, параметри якого спрощують пошук однотипних циклічних підматриць.

Розглянуто узагальнений підхід ефективного обчислення дискретних гармонічних перетворень для обсягів цілого степеня два на базі циклічних згорток. Проаналізовано твірний масив дискретної базисної матриці для гармонічних перетворень. Визначено взаємозв'язок твірних масивів і структур базисних матриць між дискретними гармонічними перетвореннями.

Розглянуто узагальнений підхід щодо ефективного обчислення дискретного перетворення Хартлі (ДПХ) на основі циклічних згорток. Підхід базується на приведенні матриці аргументів і матриці знаків дійсного базису ДПХ до еквівалентних циклічних секцій.

Розглянуто обчислення адаптивного до обсягу перетворення класу ШПФ (швидке перетворення класу Фур'є або дискретні гармонічні перетворення) на базі циклічних згорток. Дискретну базисну матрицю перетворення представлено циклічними підматрицями, що задають ефективну модель обчислення. Запропоновано обчислювальні структури на базі потоку команд і потоку даних для цього підходу виконання дискретних гармонічних перетворень.

Розглянуто особливість ефективного обчислення згорток для послідовностей, що містять повторення ідентичних груп елементів. Проаналізовано зменшення обчислювальної складності для швидких алгоритмів згортки цих послідовностей.

Розглянуто узагальнену блок-схему синтезу ефективного обчислення дискретних гармонічних перетворень, що здійснюється на базі циклічних згорток. Параметри твірного масиву базисної квадратної матриці використано в алгоритмі синтезу.

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

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

Розглянуто підхід до ефективного обчислення основних чотирьох типів дискретного перетворення Хартлі на базі циклічних згорток. Параметри твірного масиву базисної квадратної матриці використано для синтезу алгоритму.

Розглянуто паралельну модель обчислення швидких гармонічних перетворень на основі циклічних згорток. Цей підхід проаналізовано з погляду розпаралелення обчислення через підзадачі з можливістю ефективного обміну даними між ними.

Розглянуто підходи ефективного обчислення дискретних перетворень класу Фур'є (ДПФ) на основі циклічних згорток. Описано сутність переформулювання базисних матриць перетворення ДПФ на блочно-циклічні структури для кожного підходу. Проаналізовано переваги та недоліки алгоритмів для кожного підходу.

Індекс рубрикатора НБУВ: З973-018

Рубрики:

Комп'ютери та програмування

Шифр НБУВ: Ж29409/А Пошук видання у каталогах НБУВ 

Розглянуто програмну реалізацію дискретного косинусного перетворення другого типу (ДКП-II) на основі циклічних згорток. Визначено етапи автоматичного генерування ефективних алгоритмів для обчислення ДКП-II довільного обсягу N. Алгоритм ДКП-II має швидшу програмну реалізацію для коротких обсягів у порівнянні з відомою бібліотекою FFTW.

Забезпечення результативності та багатофункціональності сучасних засобів оброблення візуальної інформації вимагає розробки різноманітних методів ефективного виконання дискретних косинусних перетворнь. Відповідно вимог сучасних відео стандартів, забезпечення високої чіткості стисненої візуальної інформації досягається на основі адаптивно блочно-розмірних перетворень, що потребує ефективних обчислювальних схем виконання дискретних косинусних перетворень змінних обсягів. Мета роботи - створення узагальненої структурної схеми ефективного обчислення цілочисельного дискретного косинусного перетворення на основі циклічних згорток обсягів рівних цілій степені двійки, що забезпечує низьку обчислювальну складність і можливість застосування в системах стиснення візуальної інформації на основі адаптивно блочно-розмірних перетворень. Запропоновано використання твірних масивів для ефективного синтезу алгоритмів та структурних схем обчислення цілочисельного дискретного косинусного перетворення на основі циклічних згорток. Підсумком дослідження є розроблення узагальненої структурної схеми виконання цілочисельного дискретного косинусного перетворення обсягів рівних цілій степені двійки для систем стиснення візуальної інформації на основі адаптивно блочно-розмірних перетворень. Висновки: у проведеному дослідженні застосовано підхід приведення базису цілочисельного дискретного косинусного перетворення до набору циклічних зліва підматриць, що дозволяє обчислювати перетворення на основі циклічних згорток. Основна ідея застосування належного математичного апарату полягає у використанні твірних масивів, що містять стислий опис блочно-циклічної структури базису перетворення. На основі одержаного набору циклічних підматриць ядра перетворення розроблено узагальненну структурну схему ефективного виконання цілочисельного дискретного косинусного перетворення коротких обсягів рівних цілій степені двійки. Обчислення відповідного набору циклічних згорток та об'єднання їх результатів за структурною схемою забезпечує виконання адаптивно блочно-розмірних перетворень для систем стиснення візуальної інформації.

Забезпечення високої швидкодії обчислення комп'ютерними системами класичної задачі факторизації цілочисельного значення на прості множники вимагає розробки ефективних алгоритмічних методів з використанням новітніх інформаційних технологій. Швидке обчислення факторизації чисел для забезпечення високої криптостійкості інформаційних даних, для переходу до багатовимірного подання одновимірних послідовностей інформаційних даних та інших застосувань є достатньо затребуваним в багатьох практичних завданнях. Мета роботи - вдосконалення методу пробних ділень для обчислення факторизації цілочисельного значення з використанням розпараралелення обчислень та ефективного використання обчислювальних ресурсів комп'ютерних систем, що забезпечить швидше обчислення значень простих множників розкладу. Запропоновано використання залишків кожного розряду бінарного представлення числа факторизації з метою перевірки на подільність в підході виконання пробних ділень на прості числа. Підсумком дослідження є розроблення програми паралельного виконання факторизації цілочисельного значення в комп'ютерних системах з багатоядерними процесорами. Висновки: у проведеному дослідженні застосовано метод проведення перевірки на подільність з використанням залишків кожного розряду бінарного представлення числа факторизації, що дозволяє в мультипотоковому режимі виконувати розклад числа на множники. Основна ідея застосування належного математичного апарату полягає у використанні залишків цілого показника степеня числа два від простих чисел. В результаті цього виконується операція накопичення значень залишків, яке перевіряється на рівність з відповідним простим числом та його степенів. Можливість мультипотокової програмної організації факторизації числа забезпечує її паралельне виконання в багатоядерних процесорах комп'ютерних систем.