Разработка методов и алгоритмов вейвлет-анализа для цифровой обработки сигналов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Ляхов, Павел Алексеевич

• Ляхов, Павел Алексеевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Ляхов, Павел Алексеевич

ПРИМЕНЯЕМЫЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ МЕТОДОВ И АЛГОРИТМОВ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ.

1.1 Аналитический обзор моделей и методов цифровой обработки сигналов

1.2 Анализ математических моделей фильтрации сигналов.

1.3 Обоснование целесообразности применения системы остаточных классов для решения задач цифровой обработки сигналов.

1.4 Анализ методов обеспечения отказоустойчивости цифровых фильтров, функционирующих в системе остаточных классов.

1.5 Постановка задачи исследования.

1.6 Выводы по главе 1.

ГЛАВА 2. РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ, МЕТОДОВ И АЛГОРИТМОВ РЕАЛИЗАЦИИ ЦИФРОВЫХ ФИЛЬТРОВ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ.

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

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

2.3 Синтез архитектуры вейвлетного фильтра в системе остаточных классов с использованием многофазной формы фильтров.

2.4 Алгоритм построения вейвлетов в конечном поле.

2.5 Метод многоканальной фильтрации сигнала в системе остаточных классов.

2.6 Выводы по главе 2.

ГЛАВА 3. РАЗРАБОТКА ОТКАЗОУСТОЙЧИВЫХ ФИЛЬТРОВ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ С МИНИМАЛЬНОЙ АППАРАТНОЙ СЛОЖНОСТЬЮ.

3.1 Математические модели и численные методы компьютерной и параллельной арифметики на основе СОК.

3.1.1 Методы точного вычисления позиционных характеристик модулярного кода.

3.1.2 Обоснование возможности применения приближенных характеристик для реализации немодульных процедур при модулярном представлении данных.

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

3.1.4 Использование дробных величин при реализации приближенного метода вычисления позиционной характеристики.

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

3.3 Создание программной среды моделирования вычислений в системе остаточных классов на основе приближенного метода и оценка эффективности разработанных алгоритмов.

3.4 Выводы по главе 3.

Введение диссертации (часть автореферата) на тему «Разработка методов и алгоритмов вейвлет-анализа для цифровой обработки сигналов»

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

Актуальность темы. Широкое и повсеместное распространение вычислительной техники приводит к необходимости постоянной обработки сигналов самой различной природы: изображений, видео, речи и др. Данная область современной науки является настолько важной и практически востребованной, что происходит непрерывный поиск новых, более качественных и надежных средств цифровой обработки сигналов (ЦОС), а также постоянно совершенствуются известные методы обработки. Во многих практических приложениях требуется обработка поступающей информации в режиме реального времени, а с учетом того, что развитие технических средств сбора и передачи информации требует постоянного роста производительности систем обработки, весьма актуальной является проблема увеличения производительности вычислительных структур, осуществляющих ЦОС - цифровых фильтров.

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

Стимулом быстрого развития дискретной математики является и то, что стоимость цифровой обработки данных ниже аналоговой и продолжает падать, а производительность вычислительных операций возрастает. Системы цифровой обработки сигналов отличаются высокой гибкостью, их можно дополнять новыми программами и перепрограммировать на выполнение различных функций без изменения оборудования. В последние годы цифровая обработка сигналов оказывает постоянно возрастающее влияние на ключевые отрасли современной промышленности: телекоммуникации, средства информации, цифровое телевидение и другие [103, 46, 51, 53, 82]. Следует ожидать, что в обозримом будущем интерес и к научным, и к прикладным вопросам цифровой обработке сигналов будет нарастать во всех отраслях науки и техники.

Необходимо отметить, что с развитием ЦОС аналоговая аппаратура обработки сигналов остается весьма актуальной, становится с каждым днем все более качественной и "интеллектуальной", например, многие современные аналоговые микросхемы имеют цифровое управление и в комплексе с цифровыми устройствами и вычислительными алгоритмами представляют собой мощнейший инструмент обработки сигналов [93, 100, 107, 23]. Стоит также отметить, что цифровая обработка сигналов на данном этапе развития техники не может напрямую охватить все частотные диапазоны без переноса на более низкую частоту, для которого используются различные аналоговые смесители, векторные модуляторы и демодуляторы и т.д., что, однако, не сильно уменьшает многочисленных достоинств цифровой обработки перед аналоговой.

Однако, несмотря на успехи в развитии науки и вычислительной техники за последние десятилетия, для решения многих практических задач достигнутой на сегодняшний день производительности устройств цифровой обработки сигналов явно недостаточно [10, 55, 81, 83].

Основным средством цифрового преобразования сигналов являются цифровые фильтры. Цифровые фильтры на сегодняшний день применяются практически везде, где требуется обработка сигналов, в частности в спектральном анализе, обработке изображений, обработке видео, обработке речи и звука и многих других приложениях [88, 109, 31, 74]. Повышение производительности этих устройств является важной задачей, стоящей перед отечественными и зарубежными исследователями. Одним из весьма перспективных путей увеличения производительности цифровых фильтров является параллельная организация вычислений [10]. В настоящей работе исследована возможность реализации цифровых фильтров на базе непозиционной арифметики — системы остаточных классов. Система остаточных классов позволяет значительно ускорить работу приложений, основная доля вычислений в которых приходится на сложения и умножения [40, 41, 42]. Цифровая фильтрация является именно таким приложением, так как математической основой работы фильтра является вычисление сверток -сумм произведений.

Еще одним весьма важным достоинством системы остаточных классов является ее способность к обеспечению отказоустойчивости системы без замедления вычислений — путем простого введения дополнительных, контрольных вычислительных каналов, работающих параллельно с основными [110, 62, 72]. Постоянный рост плотности элементной базы в современных микропроцессорах повышает вероятность сбоев отдельных элементов вычислительного устройства, при этом исчерпывающее тестирование всех компонентов микропроцессора является весьма долгим процессом, и потому не является целесообразным. Поэтому вопрос о повышении надежности и устойчивости вычислительных систем к различным программным и аппаратным сбоям, а также принципы построения надежных вычислительных структур, являются одним из важнейших направлений проектирования современной техники [66]. Применение системы остаточных классов для реализации цифровых фильтров позволяет не только увеличить быстродействие систем цифровой обработки сигналов, но и обеспечить их отказоустойчивость с минимальными аппаратурными затратами. Таким образом, исследования, направленные на разработку высокопроизводительных и отказоустойчивых цифровых фильтров являются актуальными и практически значимыми.

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

Задачи диссертационной работы. Для достижения указанной цели в работе решаются следующие задачи:

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

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

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

4. Математическое моделирование цифровой фильтрации в системе остаточных классов с использованием вейвлет-преобразования и параллельных вычислений.

5. Создание системы компьютерного моделирования в форме комплекса программ для оценки эффективности предложенных методов и алгоритмов.

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

Объектом исследования в диссертации выступают цифровые фильтры, а предметом исследования - математические модели, методы и алгоритмы реализации фильтров цифровой обработки сигналов.

Методы исследования. Для решения поставленных в работе научных задач использованы методы теории цифровой фильтрации сигналов, теории вероятностей, математического моделирования, вейвлет-анализа, алгебры, линейной алгебры, теории чисел, теории модулярных вычислений в системе остаточных классов, теории алгоритмов, численные методы, методы математического и имитационного моделирования, а также системный анализ.

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

Моделирование и вычислительный эксперимент проводились с использованием математических пакетов МАТЬАВ 112008а и МаШетайса 8, системы компьютерной алгебры РАМАЗР, а также среды моделирования вычислений в системе остаточных классов на основе приближенного метода смвсокопм.

Теоретическая значимость работы заключается в следующем:

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

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

3. Разработана математическая модель многоканального набора фильтров в системе остаточных классов.

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

5. Создана модель отказоустойчивого цифрового фильтра с блоком обнаружения и локализации ошибок на основе приближенного метода.

6. Проведено моделирование предложенных методов и алгоритмов в разработанной программной среде, и выполнен сравнительный анализ с известными методами.

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

Положения, выносимые на защиту:

1. Математическая модель вейвлет-обработки сигналов в системе остаточных классов на основе цифровых фильтров в многофазной форме.

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

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

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

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

Апробация результатов работы. Результаты работы были представлены на научно-методических конференциях «Университетская наука - региону» (Ставрополь, 2010, 2012 гг.), на Всероссийской научной конференции «Параллельная компьютерная алгебра» (Ставрополь, 2010г.), в материалах участников международной научно-практической конференции «20 лет нового пути России» (Ставрополь, 2011 г.), в материалах участников VI Международной научно-практической конференции «Перспективы развития информационных технологий» (Новосибирск, 2011 г.), на СевероКавказском молодежном форуме «Машук-2011» (Пятигорск, 2011), на Всероссийском конкурсе научно-исследовательский работ студентов, аспирантов и молодых ученых «ЭВРИКА-2011» (Новочеркасск, 2011), на краевом научно-инновационном конкурсе «УМНИК-2011» (Ставрополь, 2011).

Публикации. Основные результаты работы отражены в 10 публикациях суммарным объёмом 5,75 п.л, из них 5 в журналах, рекомендованных ВАК РФ, 2 статьи - в трудах международных научных конференций.

Содержание работы. Диссертационная работа состоит из введения, 3-х глав, заключения, списка литературных источников и приложений. Содержит 51 рисунок, 15 таблиц и 4 приложения. Список используемой литературы содержит 122 источников. В диссертации принята двойная нумерация формул, рисунков и таблиц: первая цифра указывает номер главы, а вторая -порядковый номер рисунка, таблицы или формулы внутри данной главы.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Ляхов, Павел Алексеевич

Основные результаты третьей главы состоят в следующем:

1. Проведен анализ математических моделей обеспечения отказоустойчивости на основе использования контрольных вычислительных каналов системы остаточных классов.

2. Исследованы математические модели реализации немодульных операций в СОК. Показано, что известные точные методы определения позиционных характеристик числа в модулярном коде обладают существенными недостатками: значительными аппаратурными и временными затратами на их реализацию.

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

4. Разработаны эффективные алгоритмы и техническая реализация устройств для вычисления немодульных операций определения знака числа, сравнения чисел, локализации и исправления ошибок на основе предложенного приближенного метода определения позиционной характеристики числа в СОК

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

6. Разработана архитектура отказоустойчивого фильтра, функционирующего в СОК, на основе использования предложенных устройств выполнения немодульных операций при помощи приближенного метода.

7. Создан программный комплекс для моделирования вычислений в системе остаточных классов на основе приближенного метода.

8. Проведено моделирование предложенных методов и алгоритмов в разработанной программной среде, и выполнен сравнительный анализ с известными методами. Анализ данных, полученных в результате вычислительного эксперимента показал, что приближенный метод позволяет сократить временные и аппаратурные затраты для восстановления позиционной формы числа по его остаткам в 2,5 - 3,1 раз (в зависимости от диапазона системы остаточных классов) по сравнению с методом ортогональных базисов. В сравнении с наилучшим известным ранее методом вычисления немодульных операций определения знака числа, сравнения чисел, обнаружения и локализации ошибки - методом перевода в ОПСС, получен выигрыш в 2,0 - 2,7 раз.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

6. Создан программный комплекс моделирования вычислений в системе остаточных классов на основе приближенного метода.

7. Проведено моделирование предложенных методов и алгоритмов в разработанной программной среде, и выполнен сравнительный анализ с известными методами.

Разработанный приближенный метод позволяет значительно сократить временные и аппаратурные затраты при реализации немодульных операций сравнения чисел, определения знака числа, обнаружения и локализации ошибок. Аппаратурные затраты сокращаются в 2,0 - 2,7 раз, временные в 1,9 - 2,1 раз (в зависимости от выбранной системы счисления и диапазона системы остаточных классов), по сравнению с наилучшим из известных методов - методом перевода числа в обобщенную позиционную систему счисления. Применение приближенного метода для восстановления позиционной формы числа по его модулярной записи позволяет сократить время вычилений и аппаратные ресурсы. Анализ данных, полученных в результате вычислительного эксперимента показал, что приближенный метод позволяет сократить аппаратурные затраты в 2,0 — 2,1; время выполнения операций сокращается в 2,5 - 3,1 раз (в зависимости от диапазона системы остаточных классов), по сравнению с методом ортогональных базисов.

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

Список литературы диссертационного исследования кандидат физико-математических наук Ляхов, Павел Алексеевич, 2012 год

1. Амербаев В.М. Теоретические основы машинной арифметики. Алма-Ата: Наука, 1976. 324 с.

2. Бабенко М.Г. Методы и алгоритмы моделирования вычислительных структур на эллиптических кривых с параллелизмом машинных операций. Диссертация на соискание ученой степени кандидата физико-математических наук. Ставрополь, 2011. 198 с.

3. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: БИНОМ. Лаборатория знаний, 2007. 632 с.

4. Блаттер К. Вейвлет-анализ. Основы теории. М.: Техносфера, 2006. 272 с.

5. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. М.: Мир, 1989. 448 с.

6. Бородкин Е.А. Теоретические основы цифровой обработки сигналов / Е. А. Бородкин, М. К. Чобану. М.: МЭИ, 1994. 135 с.

7. Бухштаб A.A. Теория чисел. М.: Просвещение, 1966. 384 с.

8. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). М.:Наука, 1974. 415 с.

9. Виноградов И. М. Основы теории чисел: учебное пособие. 11-е изд. / И. М. Виноградов. СПб.: Изд-во «Лань», 2006. 176 с.

10. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб.: Изд-во «BHV», 2002. 608 с.

11. Воробьёв В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. СПб.: ВУС, 1999. 204 с.

12. Галанина, H.A. Непозиционные алгоритмы и устройства цифровой фильтрации и спектрального анализа / H.A. Галанина. Чебоксары: Изд-во Чуваш, ун-та, 2009.208 с.13.