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

На правах рукописи

005045281 Л^ЗР

Ляхов Павел Алексеевич

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ВЕЙВЛЕТ-АНАЛИЗА ДЛЯ ЦИФРОВОЙ ОБРАБОТКИ

СИГНАЛОВ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

- 7 ит гт

Ставрополь - 2012

005045281

Работа выполнена на кафедре прикладной математики и информатики ФГБОУ ВПО «Ставропольский государственный университет»

Научный руководитель: заслуженный деятель науки и техники РФ,

доктор технических наук, профессор Червяков Николай Иванович

Официальные оппоненты: доктор физико-математических наук, доцент

Наац Виктория Игоревна,

доктор технических наук, профессор Финько Олег Анатольевич.

Ведущая организация: Поволжский государственный университет

телекоммуникаций и информатики г. Самара

Защита состоится «20» июня 2012 г. в 11 часов 00 минут на заседании совета по защите диссертаций на соискание ученой степени кандидата наук, на соискание ученой степени доктора наук Д 212.256.08 при ФГБОУ ВПО «Ставропольский государственный университет» по адресу: 355009, г.Ставрополь, ул. Пушкина, 1а, ауд. 416.

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

Автореферат разослан «» мая 2012 года.

Ученый секретарь

диссертационного совета Д 212.256.08 канд. физ.-мат. наук, доцент

Копыткова Л.Б.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Применение системы остаточных классов для реализации цифровых фильтров позволяет не только увеличить быстродействие систем цифровой обработки сигналов, но и обеспечить их отказоустойчивость с минимальными аппаратурными затратами. Существенный вклад в развитие теории цифровой обработки сигналов внесли отечественные и зарубежные ученые В.М. Амербаев, А.И. Галушкин, В.П. Дьяконов, Е.К. Лебедев, JI.B. Новиков, А.Б. Сершенко, AJI. Стемпковский, Н.И. Червяков, М.К. Чобану, G.C. Cardarilli, U. Meyer-Base, A. Nannarelli, J. Ramírez, P.P. Vaidyanathan и др. Однако, несмотря на успехи в развитии науки и вычислительной техники за последние десятилетия, для решения многих практических задач достигнутой на сегодняшний день производительности устройств цифровой обработки сигналов явно недостаточно. Таким образом, исследования, направленные на разработку высокопроизводительных и отказоустойчивых цифровых фильтров являются актуальными и практически значимыми.

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

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

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

При этом были решены следующие частные задачи:

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

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

остаточных классов.

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

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

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

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

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

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

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

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 статьи - в трудах международных научных конференций.

Объем и структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 122 наименований и приложений. Работа содержит 209 страниц машинописного текста, включая 51 рисунок, 15 таблиц и 4 приложения.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении показана практическая востребованность в построении высокопроизводительных и отказоустойчивых цифровых фильтров, использующих вейвлет-преобразование. Обоснована актуальность исследований по разработке моделей, методов и алгоритмов цифровой фильтрации сигнала на основе использования системы остаточных классов, которая позволяет значительно ускорить работу вычислительных устройств за счет параллельной обработки данных малой разрядности. Сформулирована цель работы, изложены основные результаты проведённых исследований, показана их научная новизна, практическая значимость, указаны основные положения, выносимые на защиту.

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

f-HsMl—" коэффициенты

__ _ I - —. третьего vposss

—»j g[n] j—Ч^^Н—H Ka]|—......*

| . | козффидаенты

Г^Шге...........ПМЬ^ЗГ-» второго урони

—»Г^Т—.......* к^ФФ^3™

1—;—1 —' первого уровня Рисунок 1 - Каскадный набор фильтров дискретного вейвлет-преобразования.

Для отслеживания и обработки разнообразных особенностей сигналов на практике широко применяются методы вейвлет-анализа. Наиболее простым и эффективным способом вейвлетной обработки сигнала является его дискретное вейвлет-преобразование на основе набора фильтров, по схеме, изображенной на рисунке 1. Изображенный на рисунке 1 набор фильтров дискретного вейвлет-преобразования сигнала х[п\ содержит высокочастотные к\п\ и низкочастотные g\n\ анализирующие фильтры, а также операторы децимации 4-2, удаляющие нечетные отсчеты сигнала. В результате получается набор аппроксимирующих и детализирующих коэффициентов сигнала, позволяющих осуществить его точное восстановление. Вычисление коэффициентов дискретного вейвлет-преобразования по схеме, изображенной на рисунке 1, требует интенсивных вычислений. Для решения многих задач, особенно функционирующих в режиме реального времени, требуется разработка максимально эффективных алгоритмов для про-

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

Модель целочисленной модулярной арифметики можно задать следующей сигнатурой • | * , МО, НО^, где: - полная система вычетов по модулю полного динамического диапазона, | • - вычет чисел по модулю р1, МО - множество модульных операций, к которым относятся арифметические операции сложения, вычитания, умножения и деления нацело или умножение на обратный элемент, НО - множество немодульных операций, к которым относятся операции определения знаков чисел и переполнения динамического диапазона, сравнение, определение интервалов чисел, определение и локализация ошибочного разряда и др.

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

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

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

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

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

На рисунке 2а приведен М -канальный набор фильтров, на рисунке 26 - его многофазная форма. На вход изображенного на рисунке 2а набора фильтров подается" сигнал - последовательность х(п), который обрабатывается М анализирующими фильтрами Н, (г) с последующей децимацией. Децимация 1 и означает сохранение для дальнейшей передачи каждого М -го элемента последовательности, остальные М -1 элементы отбрасываются. Разложение сигнала представляет собой М последовательностей у,(п), О <; < М -1. Для восстановления сигнала используются М синтезирующих фильтров /*](-) совместно с интерполяцией (прореживанием сигнала). В ходе интерполяции сигнала (на рисунке она обозначена Т М), между последовательными элементами входной последовательности вставляются М -1 нулевое значение сигнала. Результатом работы набора фильтров является выходная последовательность х' (и). Многофазная реализация дискретного вейвлет-преобразования (рисунок 26) позволяет сократить вычисления отклика, так как в этом случае обработка сигнала происходит после его децимации.

При переводе значений вейвлетных функций из множества действительных чисел в СОК неизбежно возникают ошибки округления. Построение наборов фильтров на основе вейвлетов конечного поля позволяет устранить это явление. Материнский вейвлет ц/(х) и скейлинг-функция

(") I-> I-1 J-1 I-

я.(*) Г.....ИЗ..................'

г11и)

л(»)

а)

- I-1 -1 J-1

//„.,(*) ~1 1м г............."[гми » ¡**-М I

1(я) л-1 J

"Я..........1

1м

б)

1м

УМ УМ

Е(г) т

УыЛ")

Таг

......1 Тмг.....

Рисунок 2 - а) М -канальный набор фильтров, б) его многофазная реализация.

(р(х), определяющие вейвлет-преобразование в конечном поле GF{p), должны удовлетворять следующим соотношениям

К = spg>i{<p{n-2j% \fjeZ, (5)

К = span{y/{n-2j)\, V/ g Z, (6)

и, кроме того, условиям ортонормированности базиса

{(р{п - 2т),<р{п - 2к)) = 8 (ni- к), \/т,к е Z, (ц/{п - 2т),у/(п - 2к)) = 5(т- к), Vm,к е Z, (7)

- 2т),ц/(п - 2к)) = 0, \/т,к е Z. Вейвлет-преобразованием в конечном поле GF(p) является отображение, ставящее в соответствие вектору х(т) последовательность коэффициентов (х(т), <// {т - 2к)). Обратное преобразование осуществляется по формуле

х(п)=^{х{т),у/(т-2к))(р(п-2к)+^(х(т),ц/(т-2к))у/(п-2к). (8)

*6Z tez

Многочлены Ет и Ет многофазной матрицы набора фильтров над полем GF(p), изображенного на рисунке 2, для случая М = 2 определяются следующими соотношениями:

(-) = £ еа,=- , ет Ф 0, e0l е GF(p); (9)

EÁ=)= í>„-- , ew *0, еи е GF(P), (10)

1=0

а многочлены El0(z) и находятся по формулам

ею(=) = -"X(.--); = (11)

где М - положительное число М < N . Кроме того, эти многочлены должны удовлетворять условию точного восстановления сигнала

Я«,(-КоИ + £сп(--К, Н = 1 • (12)

Фильтры Н„ и //, можно найти по формулам

Нп = Е^)+^Ет{=г)-, (13)

Ht=Ela{=2)+=-'Eu(=-2). (14)

Фильтры G„ и G, находятся из условии точного восстановления сигнала

g0 = hl(-:),g¡(:)=-h,x-:). (15)

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

1. Положить М = 1.

2. Найти все пары Л(-) = , ааФ 0 и B(:)=Y¿k- , Ъи *0 из кольца

многочленов F(z), удовлетворяющие условию

A{z)A(z-l)+B(Z)B(z-')= 1. (16)

9

Каждая такая пара многочленов определяет многочлены Еж и Ет по формулам

е„=0,дляг = 0 ,...,И-М-\. (17)

Л = е,, для г = 0,..., М.

3. Увеличивать Мна единицу и повторять шаг 2, до тех пор пока М < N.

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

Е1 (е")Е(е*°)= I для всех а, (18)

где символ | означает сопряженное транспонирование, I - единичная матрица. В этом случае полагают л(еуш)= и фильтр, определенный матрицами £(г) и Л(г), удовлетворяет свойству точного восстановления сигнала. Для построения параунитарных матриц в конечном поле в диссертации доказано следующее утверждение:

Теорема 1. Возьмем вектор V в Се(р"), такой что /у = Тогда

матрица 5 -го порядка

Д (г) = / - /;'ууг + (19)

будетпараунитарнойв С//Г(/з").

Доказанная теорема позволяет строить параунитарные матрицы произвольного размера и порядка над полями

Ср(р" ). Построенные параунитарные матрицы являются основой для построения многоканальных наборов фильтров со свойством точного восстановления сигнала в конечном поле.

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

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

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

А_ Р

„ \р-Ч

а,

(20)

где: А - исследуемое число; р, - модули СОК; 1/^1 - мультипликативная

1 1р,

р

инверсия Р относительно р ; Р. =— = рхр^...р ,р г..р ; К. =1-:—- - кон-

Р> ' Р.

станты выбранной системы; а1 - разряды числа, представленного в СОК.

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

1. Вычисление констант СОК К =-— с требуемой точностью.

Р,

2. Вычисление приближенных значений а.ЛГ и запись их в ИЛТ-память вычислительной системы, где К. - константы найденные в п. 1, 1 < а, < д - 1. Адресами выборки значений а,/С, являются разряды СОК а,, где / = 1,...,и.

3. Вычисление приближенного значения позиционной характеристики

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

■ \р,!"

тельного значения величины — =

Р

Р,

4. Конструируются некоторые правила / = 1,...,4 согласно которым вычисляется г-я немодульная операция (определение знака числа, сравнение чисел, обнаружение ошибки и переполнения, а также локализация ошибочного разряда).

А 1

Правило Ч^. Определение знака числа, в случае, если р1 =2: если -- < —,

А 1

то число положительное; если — > —, то число отрицательное.

А В

Правило . Сравнение модулярных чисел А и В: если — - — = 0, то

А В А В

А = В; если--->0,то А> В; если---< 0, то А<В.

РР РР

Правило У,. Обнаружение ошибки и переполнения динамического диапазона: ошибки нет, если где А - искаженное число, Ртв = Р„1,Р„,2Р - избыточный диапазон при двух избыточных модулях рп^ и р,|+2,

м = Р = П р, - рабочий диапазон; если — > —, тогда есть ошибка и установлено переполнение динамического диапазона. _

А М

Правило Ч^. Локализация неисправного канала: если — < —, то в разряде

I нет ошибки; если — > —

Р Р

то в разряде г есть ошибка, где

А, = (а1,а2,...,а:_,,ам,...,аг1,а^ ,аи+2) - проекция искаженного числа А; М, = (тпт2,...,т,_1 ,...,тп ,т„41 ,т,н1) - проекция рабочего диапазона.

Блок-схема алгоритма обнаружения и локализации ошибки по правилам (Р, и % изображена на рисунке 3. На основе данного алгоритма разработан блок контроля отказоустойчивого цифрового фильтра в СОК (рисунок 4). В состав фильтра входят: блок перевода входного сигнала из позиционной системы счисления в СОК; КИХ-фильтры по каждому из модулей; блок контроля; обратный преобразователь сигнала из СОК в позиционную систему счисления. Поступивший на вход фильтра сигнал х(кТ) преобразуется из позиционной формы в остаточную, после чего происходит его обработка в СОК. Модулярная обработка сигнала происходит параллельно, при помощи КИХ-фильтров, по каждому из модулей, как информационных р / = 12..., п, Рисунок 3-Блок-схема алгоритма обнаружения

и локализации ошибки с использованием так и контрольных р. и _

приближенного метода

рпг. После завершения

работы фильтра сигнал подается на вход блока преобразования из СОК в ПСС,

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

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

Анализ эффективности разработанного приближенного метода для создания отказоустойчивых цифровых фильтров в СОК был произведен при помощи разработанного комплекса программ моделирования вычислений в СОК на основе приближенного метода. Для оценки эффективности применения приближенного метода при реализации операции восстановления позиционной формы числа по его остаточному представлению было произведено его сравнение с методом ортогональных базисов. Для перевода числа из СОК в ПСС применяется приближенный метод с финальным шагом коррекции. Для моделирования перевода чисел из СОК в позиционную систему счисления был разработан комплекс программ в среде РАШЛЗР, который позволяет производить оценку требуемых аппаратурных затрат на осуществление восстановления позиционной формы числа. В таблице 1 приведены результаты моделирования для СОК с диапазонами 16; 32 и 64 бит. Анализ данных, приведенных в таблице 1 показывает, что применение приближенного метода для восстановления позиционной формы числа по его модулярному коду позволяет существенно сократить аппаратурные и временные затраты по сравнению с методом ортогональных базисов.

Таблица 1. Аппаратурные и временные затраты приближенного метода и _метода ортогональных базисов перевода числа из СОК в ПСС_

и к

ю «

О

и

о

3 с

си

Я «

16

32

64

Модули СОК

{7, 17, 19, 29}

{2,3,5, 11, 13, 19,23, 29, 79}

{2. 11. 17, 19.23,31,41, 53,59,61,71,79,83}

Разрядность точного восстановления

«

3 я к

<и

Й ю 8 Л

С

21

38

72

я

л и ц °

« а

I I

О

н р.

43

81

143

Такты синхронизации

'5

3 х

X

и

к

4 Ю К

а

1=1

44

154

290

><

Я аз

3 »

5 §

§ I

та

О

н Л о

122

480

732

Для СОК с диапазоном 16 бит аппаратурные затраты сокращаются в 2,0 раз, работа устройств ускоряется в 2,8 раз. В СОК с диапазоном 32 бит происходит сокращение временных затрат в 2,1 раз и увеличение быстродействия в 3,1 раз. Наконец, для СОК с диапазоном 64 бит происходит сокращение аппаратурных затрат в 2,0 раз, временных затрат в 2,5 раз (рисунок 5). Данный выигрыш объясняется тем, что при использовании приближенного метода не происходит работа над избыточной информацией, а также имеется возможность для использования табличной арифметики при работе с дробными величинами. Таким образом можно сделать вывод о преимуществе предложенного метода над ранее известными.

160 140 120

3 100

4

а. 80

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

-------------

г! 1

I 500

0

Э" 400

1

о 300

5 200

н 100

□ Приближенный метод 0 Метод ортогональных базисов

I

д | Диапазон СОК, бит

Рисунок 5

б)

Диапазон СОК, бит

Затраты методов перевода числа из СОК в ПСС а) аппаратурные, б) временные.

В таблице 2 приведены значения разрядности приближенного метода и метода ОПСС для реализации операций определения знака числа, сравнения чисел, обнаружения и локализации ошибки в СОК с диапазонами 16, 32 и 64 бит. Анализ данных, приведенных в таблице 2 показывает, что применение приближенного метода для реализации немодульных операций позволяет значительно сократить аппаратурные и временные затраты, по сравнению с методом перевода числа из СОК в ОПСС.

Таблица 2. Аппаратурные затраты приближенного метода выполнения немодульных операций в СОК._

Ё Десятичные Двоичные Такты

ю « О и я о а разряды разряды синхронизации

Приближенный метод и § § « 1 § 1 Й и в о § I ^ § § й и В О «

а к Ч Й 1В 2 я & 1 я а- Й

16 6 14 18 36 38 73

32 11 30 35 74 142 297

64 21 50 67 140 270 561

При использовании десятичной записи чисел аппаратурные затраты сокращаются в 2,3; 2,7 и 2,4 раз для СОК с диапазонами 16; 32 и 64 бит, соответственно (рисунок 6а). При использовании двоичного кодирования информации происходит сокращение аппаратурных затрат в 2,0; 2,1 и 2,1 раз для СОК с диапазонами 16; 32 и 64 бит, соответственно (рисунок 66).

□ Приближенный метод

□ Метод обобщенной позиционной системы счисления

О Приближенный метод

а Метод обобьцр«ной позиционной системы счисления

Я

а

а 75

1

I

Диапазон СОК, бит ^ Диапазон СОК, бит

Рисунок 6 - Аппаратурные затраты методов выполнения немодульных операций определения знака числа, сравнения чисел, обнаружения и локализации ошибки: а) десятичные разряды, б) двоичные разряды.

15

□ Приближенный метод

И Метод обобщенной позиционной системы счисления

16 32

Диапазон СОК, бит

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

Для СОК с диапазоном 16 бит время выполнения немодульных операций сокращается в 1,9 раз. Скорость выполнения немодульных операций для СОК с диапазоном 32 бит увеличивается в 2,1 раз. Применение приближенного метода для СОК с диапазоном 64 бит позволяет сократить время вычислений в 2,1 раз (рисунок 7). Результаты эксперимента показывают, что приближенный метод позволяет получить выигрыш с точки зрения временных и аппаратурных затрат по сравнению с методом ОПСС для реализации немодульных операций в СОК, в частности, для обнаружения и локализации вычислительных ошибок.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В РАБОТАХ В рецензируемых журналах из списка ВАК

1. Ляхов П.А., Червяков Н.И. Исследование параунитарных матриц для реализации цифровой обработки сигналов в конечных полях // Инфокомму-никационные технолог™. 2011. Т. 9. №1. С. 4-8.

2. Ляхов П.А., Червяков Н.И. Реализация многоканальных фильтров в системе остаточных классов // Инфокоммуникационные технологии. 2011. Т. 9. №2. С. 4-7.

3. Червяков НИ., Ляхов П.А. Реализация многофазных фильтров в системе остаточных классов // Научные Ведомости Белгородского государственного университета. История. Политология. Экономика. Информатика. 2011. №13. С. 204-209.

4. Червяков Н.И., Ляхов П.А. Реализация модулярного вейвлет-преобразования в нейросетевом базисе // Нейрокомпьютеры: разработка, применение. 2011. №11. С. 18-25.

5. Червяков Н.И., Бабенко М.Г., Ляхов П.А., Лавриненко И.Н. Приближенный метод ускоренного обнаружения и локализации неисправного вычислительного канала в ЭВМ, функционирующей в системе остаточных классов // Нейрокомпьютеры: разработка, применение. 2011. №10. С. 13-19.

В материалах международных конференций

6. Червяков Н.И., Ляхов П.А. Дискретное вейвлет-преобразование в системе остаточных классов специального вида // 20 лет нового пути России: политика, общество, экономика, международное сотрудничество / Сборник материалов международной научно-практической конференции; институт дружбы народов Кавказа. Ставрополь: РИО ИДНК, 2011. С. 451-455.

7. Червяков Н.И., Ляхов П.А. Многоканальные фильтры точного восстановления сигнала в системе остаточных классов // Перспективы развития информационных технологий / Сборник материалов VI Международной научно-практической конференции. Новосибирск: Издательство «СИБПРИНТ», 2011. С. 215-220.

В других изданиях

8. Ляхов П.А. Принцип очистки сигнала от шума с использованием вейв-лет-преобразования // Современное состояние и приоритеты развития фундаментальных и прикладных исследований в области физики, математики и компьютерных наук: Материалы 55-й научно-методической конференции «Университетская наука - региону». Ставрополь: Издательско-информационный центр «Фабула», 2010. С. 18-21.

9. Ляхов П.А. Дискретное вейвлет-преобразование в системе остаточных классов // Параллельная компьютерная алгебра: Всероссийская научная конференция с элементами научной школы для молодежи, г. Ставрополь, 11-15 октября 2010 г. Ставропольский государственный университет. Ставрополь: Издательско-информационный центр «Фабула», 2010. С. 167-175.

10. Червяков Н.И., Ляхов П.А. Приближенный метод перевода чисел из модулярного кода в позиционный // Современное состояние и приоритеты развития фундаментальных и прикладных исследований в области физики, математики и компьютерных наук: Материалы 55-й научно-методической конференции «Университетская наука - региону», часть I. Ставрополь: Издательско-информационный центр «Фабула», 2012. С. 220-223.

Свидетельство о государственной регистрации программ для ЭВМ

11. Червяков Н.И., Бабенко М.Г., Ляхов П.А. Среда моделирования вычислений в системе остаточных классов на основе приближенных методов. Свидетельство о государственной регистрации программы для ЭВМ № 2012610503. Зарегистрировано в Реестре программ для ЭВМ 10 января 2012 г.

Подписано в печать 14.05.2012 Формат 60x84 1/16 Усл.печ.л. 1,0 Уч.-изд.л. 0,98

Бумага офсетная_Тираж 150 экз._Заказ 114

Отпечатано в Ичдательско-полиграфическом комплексе Ставропольского государственного университета. 355009, Ставрополь, ул.Пушкина, 1.

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

ВВЕДЕНИЕ.

ГЛАВА 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 раз (в зависимости от диапазона системы остаточных классов), по сравнению с методом ортогональных базисов.

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

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.