Введение к работе
з
Актуальность темы. В настоящее время интенсивно развиваются исследования в области ортогональных преобразований (ОП) для цифровой обработки сигналов (ЦОС). ОП используются для обработки сигналов, представляющих сейсмические, акустические, биомедицинские данные, а также данные обработки изображений, речевых сигналов, анализа и проектирования систем связи и др. К наиболее часто применяемым относятся преобразования Фурье, Хаара, Уолша, а также вейвлет- и пилообразное преобразования. При этом актуальны задачи сокращения времени и объёма вычислений в процессе выполнения преобразований. В частности, при обработке изображений возникают трудности, связанные с тем, что изображение представляется двумерным массивом, содержащим большой объем информации. Изображение часто выступает как особый сигнал, предназначенный для визуального восприятия, требуется, чтобы обработка выполнялась в реальном масштабе времени. Проблема снижения временной сложности пилообразного преобразования обусловлена тем, что оно применяется для выделения характерных признаков изображений, с помощью этого преобразования обеспечивается высокая степень концентрации энергии изображения, помимо того, оно используется для обработки водяных знаков и кодирования сигналов. Преобразование Уолша ориентировано на цифровую обработку сложных сигналов, на применении которых основана технология кодового разделения каналов для сотовой связи третьего и четвертого поколений. Наличие многоканальности наряду с обработкой сложных сигналов обусловливает необходимость сокращения времени преобразования. Вейвлет-преобразование является базовой техникой компьютерной графики, используется при редактировании и сжатии изображений, поиска изображений по запросу, автоматического контроля уровня детальности при редактировании и создании кривых и поверхностей по контурам, в быстрых методах решения задач физического моделирования в анимации и глобальном освещении. Отсюда актуальна задача снижения временной сложности вейвлет-преобразования. Для современных цифровых систем передачи, синтеза речи, верификации, в которых используются алгоритмы дискретного преобразования Фурье (ДПФ), требуется осуществлять распознавание слов, словосочетаний и фраз в реальном масштабе времени. Аналогичные требования предъявляются для ЦОС в системах радио- и гидролокации, а также в синтетической телефонии. Алгоритмической основой построения таких систем является цифровой динамический спектральный анализ, который позволяет получать оценку текущего спектра сигнала в реальном масштабе времени. Динамический спектральный анализ в различных частотных диапазонах одного и того же сигнала дает возможность наблюдать спектр как во всем частотном диапазоне (панорамный режим), так и детальный анализ спектра в выбранных частотных диапазонах. Это влечет необходимость выполнять ОП при условии динамического изменения числа отсчетов в строго ограниченное время или в режиме реального времени, поэтому схемы вычисления ОП должны быть минимизированы по временной сложности. Таким образом, тема работы актуальна.
Цель диссертационной работы заключается в разработке и исследовании компьютерно-ориентированных алгоритмов построения и вьгаисления ОП с минимизацией временной сложности при динамическом изменении числа отсчетов.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
1. Построить распараллеливаемые схемы пилообразного преобразования с
минимизацией временной сложности, включающие в себя алгоритмы вьгаисления
коэффициентов и формирования матрицы преобразования, с помощью которой
можно выполнять преобразование в режиме реального времени при динамическом
изменении отсчетов.
2. На основе схем Стоуна и кусочно-полиномиальной аппроксимации
синтезировать алгоритмы параллельного вьгаисления функций Радемахера, с
минимальной оценкой временной сложности.
3. Синтезировать схемы параллельного формирования матрицы
преобразования Уолша с минимизацией временной сложности до значений
о (log 2 log 2 n) и о (і) для формирования матрицы в реальном времени при динамическом изменении числа отсчетов.
4. Синтезировать алгоритмы параллельного преобразования Уолша с
минимизацией временной сложности до значения o(log2w) для выполнения
преобразования в реальном времени при переменном количестве отсчетов.
Разработать модификации быстрого вейвлет-преобразования, на их основе построить параллельные схемы преобразования, позволяющие вычислять одновременно все вейвлет-коэффициенты и выполнять преобразование в реальном времени при динамическом изменении отсчетов.
Разработать схему параллельного преобразования Хаара, включающую алгоритм формирования матрицы преобразования с минимальной временной сложностью о (і), для выполнения преобразования в реальном времени при динамически меняющемся количестве отсчетов.
На основе кусочно-полиномиальной аппроксимации элементов базиса и редукции аргумента синтезировать параллельный алгоритмы вьгаисления базиса ДПФ за время о (і) и выполнения преобразования за время o(log2w) при динамическом изменении отсчетов.
Методы исследования опираются на методы теоретической информатики и прикладной информатики, численного анализа, теории сложности, а также на методы компьютерного моделирования ЦОС.
Достоверность результатов вытекает из их математического обоснования, подтверждается оценками временной сложности, а также результатами программного и численного эксперимента.
Научная новизна
1. Предложены схемы параллельного вьгаисления матрицы пилообразного преобразования с временной сложностью o(log2log2w) и о (і), на этой основе синтезированы параллельные алгоритмы выполнения преобразования, отличающиеся от известных временной сложностью o(log2w) и позволяющие
5 выполнять преобразование в режиме реального времени при динамическом изменении отсчетов.
2. Предложены параллельные схемы вычисления функций Радемахера с
использованием схем Стоуна с временной сложностью o(hg2N) при количестве
процессоров N2 и кусочно-полиномиальной аппроксимации тригонометрических функций - с временной сложностью o(i) при количестве процессоров JVlog2iV , которые улучшают известные оценки за счет увеличения числа процессоров и объема постоянной памяти.
3. На основе предложенных схем вычисления функций Радемахера
разработаны алгоритмы построения матрицы преобразования Уолша с временной
сложностью o(hg2hg2N) при количестве процессоров N2hg2N и o(i) - с
использованием счетчика одноразрядных единиц, - что отличается от известной оценки алгоритма афинной формы и позволяет в реальном времени формировать матрицу преобразования при динамическом изменении числа отсчетов.
4. Построены схемы параллельного преобразования Уолша с временной
сложностью О (log 2 N) при количестве процессоров N2, улучшающие известную
оценку на основе квантовых вычислений и позволяющие выполнять преобразование в реальном времени при переменном количестве отсчетов за счет динамического пересчета матрицы преобразования.
5. Предложены две модификации быстрого вейвлет-преобразования, первая
из которых позволяет параллельно вычислять все коэффициенты вейвлет-
преобразования за время o(tog2\og2Nx\og2N) при количестве процессоров #3;
вторая позволяет подмножество коэффициентов, определяемое конкретным
разрешением, ВЫЧИСЛЯТЬ За время O(l) при количестве процессоров LxN , где L -
длина вейвлет-фильтра, что улучшает известные оценки алгоритма Малла и позволяет выполнять вейвлет-преобразование в реальном времени при динамическом изменении отсчетов.
6. Разработано параллельное видоизменение преобразования Хаара,
выполняемое с временной сложностью О (log 2 n), которое включает динамическое
формирование матрицы преобразования с временной сложностью о (і), что отличается от оценок алгоритмов Эдрюса и Кули-Тьюки, позволяя выполнять преобразование в реальном времени при динамически меняющемся количестве отсчетов.
7. Синтезированы параллельные алгоритмы вычисления всех элементов
базиса ДПФ на основе кусочно-полиномиальной аппроксимации и редукции
аргумента с временной сложностью о(і), инвариантные относительно числа
отсчетов ДПФ, без избыточных затрат памяти, что в сочетании с минимальной
оценкой времени отличает их от известных и позволяет построить параллельную
схемы ДПФ, применимые для вычисления ДПФ при условии динамического
изменения числа отсчетов. Параллельные схемы ДПФ отличается от известных по
построению, по способу адресации к данным, инвариантностью относительно
динамически меняющегося числа отсчетов и временной СЛОЖНОСТЬЮ О (log 2 N) в
условиях произвольно заданной границы погрешности вычислений. Основные положения, выносимые на защиту
1. Предложены схемы параллельного вычисления матрицы пилообразного
преобразования с временной сложностью o(log2log2w) и o(i), синтезированы
параллельные алгоритмы выполнения преобразования с временной сложностью
o(log2iv), позволяющие выполнять преобразование в режиме реального времени при динамическом изменении отсчетов.
Предложены параллельные схемы вычисления функций Радемахера с использованием схемы Стоуна с временной сложностью o(log2w) и на основе кусочно-полиномиальной аппроксимации тригонометрических функций - с временной сложностью о (і) при количестве процессоров JVlog2iV .
Синтезированы алгоритмы построения матрицы преобразования Уолша с временной сложностью О (log 2 log 2 N) при количестве процессоров N2 log 2 N и о{\) -
с использованием счетчика одноразрядных единиц - для формирования матрицы преобразования в реальном времени.
4. Построены схемы параллельного преобразования Уолша с временной
сложностью О (log 2 n) при количестве процессоров n2 , которые позволяют
выполнять преобразование в реальном времени при переменном количестве отсчетов за счет динамического пересчета матрицы преобразования.
5. Предложены две модификации быстрого вейвлет-преобразования, первая
из которых позволяет параллельно вычислять все коэффициенты преобразования за
время о (log 2 log 2 Nx log 2 n) при количестве процессоров w3; вторая - позволяет
подмножество коэффициентов, определяемое конкретным разрешением, вычислять за время О (1) при количестве процессоров ь х n , где ь - длина вейвлет-фильтра.
6. Разработано параллельное видоизменение преобразования Хаара,
выполняемое с временной сложностью o(log27VJ, которое включает динамическое
формирование матрицы преобразования за время o(i), позволяя выполнять преобразование в реальном времени при динамически меняющемся количестве отсчетов.
7. Синтезированы инвариантные относительно числа отсчетов параллельные
алгоритмы вычисления всех элементов базиса ДПФ на основе кусочно-
полиномиальной аппроксимации и редукции аргумента за время о (і) без
избыточных затрат памяти. На этой основе параллельные схемы ДПФ инвариантны
относительно динамически меняющегося числа отсчетов и позволяют выполнять
преобразование с временной сложностью o{hg2N) в условиях произвольно
заданной границы погрешности вычислений.
Практическая ценность диссертационного исследования заключается в прикладном характере предложенных параллельных схем ортогональных преобразований в условиях минимизации временной сложности. Разработанная в диссертации параллельная схема ДПФ доведена до практической программной реализации. На основе совокупности предложенных схем ортогональных
7 преобразований могут создаваться новые системы ЦОС, ориентированные на практическое применение с повышенным быстродействием в последовательных и параллельных вычислительных системах.
Внедрение и использование результатов работы. Полученные в работе результаты использованы в ОАО «Таганрогский завод «Прибой» при обработке плоского отображения сигналов гидроакустической локации, при выполнении интегральных преобразований гидроакустических сигналов, а также при оценке скорости их изменений для сокращения времени обработки при одновременном увеличении ее точности; в учебном процессе факультета информатики и управления Таганрогского государственного педагогического института в курсах «Основы информатики», «Теоретические основы информатики», «Теоретические основы нейроинформатики», «Информационные технологии в математике», «Численные методы», «Программирование», «Компьютерное моделирование», а также в курсах по выбору и практикуме решения задач на ЭВМ, что подтверждено соответствующими актами об использовании, приведенными в приложении 2 к диссертационной работе.
Апробация работы были представлены на Всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, ЮФУ, 2008); Всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, ЮФУ, 2009); XIII Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов» (ВК-95-90) (Пенза, ПДЗ, Пензенская государственная технологическая академия, 2010); VIII Региональной научно-практической конференции «Аспекты модернизации образования и развития промышленности» (Таганрог, ДГТУ, 2010); XI Всероссийском симпозиуме по прикладной и промышленной математике, осенняя открытая сессия (Сочи-Дагомыс, 2010).
Публикации. По материалам диссертационной работы опубликовано 11 печатных работ, в том числе 4 статьи в журналах из списка допущенных ВАК РФ.
Структура и объем работы. Диссертационная работа состоит из введения, 3 глав основного раздела, заключения, списка литературы и приложений. Основное содержание работы изложено на 155 страницах, включая 12 таблиц, 24 рисунка и список литературы из 109 наименований.
