Комплекс программ сжатия/восстановления сигналов на основе сплайн-вэйвлетов Дипломная работа студента 543 группы Ракчаева Владимира Аркадьевича Научный руководитель: проф. Демьянович Юрий Казимирович

Введение Современные потоки информации – последовательности битов огромной длины ( символов) Быстрая обработка требует больших компьютерных ресурсов Сокращение объемов цифровой информации за счет отбрасывания несущественных ее составляющих – актуальная задача!

Введение Группа кафедры параллельных алгоритмов занимается этими задачами уже на протяжении последних десяти лет Алгоритмы, описанные в этой работе, еще не применялись на практике, и для их последующего практического применения программно реализуются здесь впервые!

Вэйвлеты Эффективные алгоритмы обработки больших потоков информации (экономное разложение потока информации) Исходный поток Основной поток Вэйвлетный поток

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

Цель работы Создание программ сжатия и восстановления числовой информации, основанного на сплайн-вэйвлетных разложениях эрмитова типа Анализ возможностей распараллеливания указанного алгоритма

Сплайн-вэйвлетное разложение эрмитова типа Вэйвлетные (всплесковые) разложения пространств сплайнов, пригодных для решения интерполяционной задачи Эрмита (с производными первого порядка) Такие сплайны называем сплайнами эрмитова типа (первой высоты) Для сплайн-вэйвлетного разложения эрмитова типа верны следующие формулы декомпозиции и реконструкции

Формулы декомпозиции

Формулы реконструкции

Описание алгоритма Входные данные – числовой поток c Создание сетки x Этап декомпозиции Этап реконструкции Сравнение потоков

Этап декомпозиции Параллельные процессы одновременно вычисляют составляющие вэйвлетного потока, выбрасывая узел сетки, и после этого выполняется процесс пересчитывания основного потока Задается шаг h, с которым происходит выбрасывание узлов сетки процессами Из исходного потока c соответствующий процесс вычисляет вэйвлетные составляющие b j по формулам декомпозиции

Этап декомпозиции Основной процесс собирает с остальных процессов все данные в один массив вэйвлетного потока и вычисляет основной поток a по первой части формул декомпозиции После процесса декомпозиции, из исходного потока выделяется основной поток a и вэйвлетный b, состоящий из компонент, выделенных каждым процессом

Этап реконструкции Этап, обратный этапу декомпозиции Из выделенных потоков a и b восстанавливается исходный поток Все процессы параллельно пересчитывают восстанавливаемый поток по формулам реконструкции Собрав данные со всех процессов, основной процесс собирает данные в один поток, используя вычисленные компоненты восстанавливаемого потока с

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

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

Результаты Программа корректно работает для любого допустимого входного потока Программа была протестирована на 10 выполняющих процессорах кластера Результатом выполнения программы стала успешная реализация вышеописанного алгоритма, подтверждением чего является полученный результирующий разностный поток, состоящий из нулей (в случае вещественных чисел – близких к нулю из-за ошибок округления)

Результаты Net: Source flow: Start decomposition... End of decomposition. Result of decomposition. Main flow: Wave flow: Start reconstruction... End of reconstruction. Result of reconstruction. Reconstr. flow: Difference of source and reconstr. flows: Ok.

Результаты Net: Source flow: Start decomposition... End of decomposition. Result of decomposition. Main flow: Wave flow: Start reconstruction... End of reconstruction. Result of reconstruction. Reconstr. flow: Difference of source and reconstr. flows: Ok.

Результаты Net: Source flow: Start decomposition... End of decomposition. Result of decomposition. Main flow: Wave flow: Start reconstruction... End of reconstruction. Result of reconstruction. Reconstr. flow: Difference source and reconstr. flows: e e e e e Ok.

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

Список литературы Демьянович Ю.К., Ходаковский В.А. Введение в теорию вэйвлетов. Учеб. пособие. СПб.: Петербургский государственный университет путей сообщения, – 51 с. Демьянович Ю.К., Зимин А.В. О всплесковом разложении сплайнов эрмитова типа. Проблемы математического анализа, Т.35, С