LibRar.Org.Ua — Бібліотека українських авторефератів

Загрузка...

Головна Електроніка. Обчислювальна техніка → Універсальні алгоритми швидких ортогональних перетворень для паралельних інформаційних технологій

третьего видов. Получены их направленные графы и раскрыто структурное сходство, включая совпадение вычислительных затрат, между известными алгоритмами косинусного преобразования и полученными алгоритмами синусного преобразования второго и третьего видов.

Разработаны новые двухкаскадные быстрые алгоритмы вычисления дискретного преобразования Хартли (с прореживанием по времени и частоте), дискретного преобразования Фурье действительной или эрмитовой последовательностей. По сравнению с непосредственным применением известных косвенных алгоритмов быстрого вычисления преобразований Фурье -Хартли на основе быстрых алгоритмов косинусного преобразования второго-третьего видов они сокращают один этап поворотов вектора (на 5-7% вычислительные затраты). Показано, что их графы имеют одинаковую структуру, которая отличается только направлением вычислений и значениями фазовых множителей на отдельных этапах поворота вектора. Установлено, что первый каскад (каскад простых базовых операций) двукаскадных быстрых алгоритмов отображает быстрый алгоритм дискретного преобразования Уолша-Адамара.

Синтезированы двукаскадные быстрые алгоритмы косинусного и синусного преобразований четвертого вида. Для получения структурно однородных вычислительных структур проведена модификация схемы связей на этапах поворотов вектора в двукаскадных быстрых алгоритмах синусного преобразования второго вида, косинусного и синусного преобразований четвертого вида. В результате получены алгоритмы, которые на этапах выполнения базовых операций структурно совпадают с алгоритмом быстрого косинусного преобразования второго вида, структура которого (схема соединений базовых операций), в свою очередь, совпадает со структурой алгоритма БПФ по основанию два.

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

Предложен новый вариант дополнительной декомпозиции графов быстрых алгоритмов. С этой целью введен универсальный вычислительный блок, который реализует преобразование только одного каскада двухкаскадных универсальных алгоритмов и позволяет представить произвольный двухкаскадный быстрый алгоритм как последовательное двукратное обращение к универсальному блоку. В универсальном блоке базовые операции (поворот вектора) соединены по правилу графа алгоритма БПФ по основанию два. Здесь также выбор преобразования осуществляется только за счет выбора соответствующих фазовых множителей в двухточечных базовых операциях (на всех его этапах). Блок позволяет выполнять и дискретное преобразование Уолша-Адамара.

Разработаны эффективные быстрые алгоритмы реализации входных и выходных перестановок данных в полученных универсальных алгоритмах с количеством операций перемещения данных .

Развит алгоритмический подход к построению нейронных сетей фильтрации сигналов в частотной области. В рамках этого подхода на основании универсального вычислительного блока построена искусственная нейронная сеть, в которой по сравнению с общей сетью (реализующей дискретное преобразование) сокращено в раз количество весов (по аналогии замены дискретного преобразования быстрым алгоритмом). На примере решения задачи сжатия изображений установлено, что применение универсального блока и алгоритмического подхода позволяет существенно (в раз) ускорить обучение нейронной сети фильтрации сигналов.

Разработаны структуры потоковых универсального СБИС-процессора быстрых ортогональных преобразований и СБИС-процессора реализации универсального блока, а также получены оценки основных затрат оборудования на их реализацию. Установлено, что сравнительно с однотипным по структуре поточным СБИС-процессором БПФ по основанию два затраты оборудования сокращаются в 1.1-1.6 раз при одновременном обеспечении универсальности относительно видов преобразований. Для больших размерностей универсальный блок позволяет в 1.2 раза сократить затраты оборудования сравнительно с универсальными алгоритмами. Отмечено, что полученные универсальные алгоритмы могут быть эффективно использованы и при построении матричных процессоров, что реализуют один этап графа алгоритма с постоянной структурой.

Ключевые слова:параллельные информационные технологии, универсальныебыстрые алгоритмы ЦОС, ортогональные преобразования, нейронные сети.

Liskevych R. Universal algorithms of fast discrete orthogonal transformations for parallel information technologies. – Manuscript.

The dissertation for obtaining of a scientific degree of Candidate of Technical Science in a speciality 05.13.06 – automated control systems and advanced information technologies. State research institute of information infrastructure, Lviv, 2001.

The dissertation is dedicated to the development of universal orthogonal transformation algorithms for parallel information technologies. New universal fast bicascade algorithms of direct and inverse discrete Fourier transformations of real sequence, Hartley, second-fourth form cosine and sine transformations have been derived. The author shows, that aforecited algorithms could be implemented in a universal computational system. The transformation type in such a system could be chosen by selecting of corresponding phase factors for the two-point base operations only. The process of the phase factors groups assembling is governed by the general rule. Such an approach allows to reduce the expenses on algorithms realization in 1.2-1.6 times. The new algorithmic approach to neural networks of the signal filtration synthesis has been developed. It reduces the network training time essentially (in N/log2N times).

Key words: parallel information technologies, universal fast DSP algorithms, orthogonal transformations, neural networks.