Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Ляхов Павел Алексеевич
РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ВЕЙВЛЕТ-АНАЛИЗА ДЛЯ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ
05.13.18 - Математическое моделирование, численные методы и комплексы программ
АВТОРЕФЕРАТ
диссертации на соискание учёной степени кандидата физико-математических наук
Ставрополь - 2012
Работа выполнена на кафедре прикладной математики и информатики ФГБОУ ВПО Ставропольский государственный университет
Научный консультант: заслуженный деятель науки и техники РФ, доктор технических наук, профессор Червяков Николай Иванович
Официальные оппоненты: доктор физико-математических наук, доцент Наац Виктория Игоревна, доктор технических наук, профессор Финько Олег Анатольевич.
Ведущая организация: Поволжский государственный университет телекоммуникаций и информатики г. Самара
Защита состоится л20 июня 2012 г. в 11 часов 00 минут на заседании совета по защите диссертаций на соискание ученой степени кандидата наук, на соискание ученой степени доктора наук Д 212.256.08 при ФГБОУ ВПО Ставропольский государственный университет по адресу: 355009, г.Ставрополь, ул. Пушкина, 1а, ауд. 416.
С диссертацией можно ознакомиться в научной библиотеке Ставропольского государственного университета.
Автореферат разослан л мая 2012 года.
Ученый секретарь диссертационного совета Д 212.256.канд. физ.-мат. наук, доцент Копыткова Л.Б.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Современный уровень развития инфокоммуникационных технологий требует повсеместного применения цифровой обработки сигналов для решения различных практичеких задач: обработки изображений, распознавания речи, организацию мобильной связи, телеметрию и многих других. Важным средством цифрового преобразования сигналов являются цифровые фильтры дискретного вейвлет-преобразования.
Повышение производительности этих устройств является важной задачей, стоящей перед отечественными и зарубежными исследователями.
Одним из весьма перспекитвных путей увеличения производительности цифровых фильтров является параллельная организация вычислений. В настоящей работе исследована возможность реализации цифровых фильтров на базе непозиционной арифметики - системы остаточных классов. Система остаточных классов позволяет значительно ускорить работу приложений, основная доля вычислений в которых приходится на сложения и умножения. Цифровая фильтрация является именно таким приложением, так как математической основой работы фильтра является вычисление сверток - сумм произведений.
Еще одним весьма важным достоинством системы остаточных классов является ее способность к обеспечению отказоустойчивости системы без замедления вычислений - путем простого введения дополнительных, контрольных вычислительных каналов, работающих параллельно с основными.
Постоянный рост плотности элементной базы в современных микропроцессорах повышает вероятность сбоев отдельных элементов вычислительного устройства, при этом исчерпывающее тестирование всех компонентов микропроцессора является весьма долгим процессом, и потому не является целесообразным. Поэтому вопрос о повышении надежности и устойчивости вычислительных систем к различным программным и аппаратным сбоям, а также принципы построения надежных вычислительных структур, являются одним из важнейших направлений проектирования современной техники.
Применение системы остаточных классов для реализации цифровых фильтров позволяет не только увеличить быстродействие систем цифровой обработки сигналов, но и обеспечить их отказоустойчивость с минимальными аппаратурными затратами. Существенный вклад в развитие теории цифровой обработки сигналов внесли отечественные и зарубежные ученые В.М. Амербаев, А.И. Галушкин, В.П. Дьяконов, Е.К. Лебедев, Л.В. Новиков, А.Б. Сергиенко, А.Л. Стемпковский, Н.И. Червяков, М.К. Чобану, G.C. Cardarilli, U. Meyer-Base, A. Nannarelli, J. Ramrez, 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 приложения.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении показана практическая востребованность в построении высокопроизводительных и отказоустойчивых цифровых фильтров, использующих вейвлет-преобразование. Обоснована актуальность исследований по разработке моделей, методов и алгоритмов цифровой фильтрации сигнала на основе использования системы остаточных классов, которая позволяет значительно ускорить работу вычислительных устройств за счет параллельной обработки данных малой разрядности. Сформулирована цель работы, изложены основные результаты проведённых исследований, показана их научная новизна, практическая значимость, указаны основные положения, выносимые на защиту.
Первая глава посвящена литературному обзору основных моделей, методов и алгоритмов цифровой обработки сигналов.
Рисунок 1 - Каскадный набор фильтров дискретного вейвлет-преобразования.
Для отслеживания и обработки разнообразных особенностей сигналов на практике широко применяются методы вейвлет-анализа. Наиболее простым и эффективным способом вейвлетной обработки сигнала является его дискретное вейвлет-преобразование на основе набора фильтров, по схеме, изображенной на рисунке 1. Изображенный на рисунке 1 набор фильтров дискретного вейвлет-преобразования сигнала x[n] содержит высокочастотные h[n] и низкочастотные g[n] анализирующие фильтры, а также операторы децимации 2, удаляющие нечетные отсчеты сигнала. В результате получается набор аппроксимирующих и детализирующих коэффициентов сигнала, позволяющих осуществить его точное восстановление. Вычисление коэффициентов дискретного вейвлет-преобразования по схеме, изображенной на рисунке 1, требует интенсивных вычислений. Для решения многих задач, особенно функционирующих в режиме реального времени, требуется разработка максимально эффективных алгоритмов для про граммных или аппаратных вычислений. Развитие высокопроизводительных и надежных систем цифровой обработки сигналов, обладающих свойством отказоустойчивости, базируется на идеях создания вычислительных средств с параллельной структурой, использующих параллельное представление и обработку данных. К их числу относятся непозиционные коды - коды, основанные на модулярной арифметике, то есть коды, в которых данные представляются в системе остаточных классов (СОК).
Модель целочисленной модулярной арифметики можно задать сле+ дующей сигнатурой P, Х, МО, НО, где: P - полная система вычетов pi + по модулю полного динамического диапазона, Х - вычет чисел по модуpi лю pi, МО - множество модульных операций, к которым относятся арифметические операции сложения, вычитания, умножения и деления нацело или умножение на обратный элемент, НО - множество немодульных операций, к которым относятся операции определения знаков чисел и переполнения динамического диапазона, сравнение, определение интервалов чисел, определение и локализация ошибочного разряда и др.
Для реализации фильтров вейвлет-преобразования требуется выполнение лишь сложений и умножений, что позволяет использовать СОК для их реализации с максимальной эффективностью. Однако для обеспечения отказоустойчивости цифрового фильтра необходимо выполнение операций обнаружения, локализации и исправления ошибок, которые относятся к немодульным. Немодульные операции обусловлены знанием числового значения модулярной величины, которая определенным образом связана со значениями компонент модулярного представления. Для реализации немодульных операций используются специальные функционалы, которые определяют количественные характеристики отношения порядка над множеством модулярных векторов. Одно из устоявшихся названий функционалов - позиционная характеристика (ПХ) модулярной величины или числовой величины в модулярном коде. В основе алгоритмов выполнения немодульных операций лежат методы вычисления ПХ, сложность которых непосредственно влияет на скорость выполнения немодульных операций в модулярной алгебре. Поиск эффективных и универсальных ПХ важен для теоретических основ модулярных вычислительных структур и вычислительных средств на их основе.
В настоящее время известны следующие методы определения позиционных характеристик модулярного представления чисел: метод ортогональных базисов; метод интервальных оценок; метод с использованием коэффициентов обобщенной позиционной системы счисления (ОПСС).
Перечисленные методы используют точные вычисления. Общим недостатком для всех этих методов является необходимость обработки избыточной информации. Разработка новых методов рассчета ПХ числа в СОК, не содержащих избыточной информации, позволит значительно упростить выполнение немодульных операций и, в частности, позволит значительно сократить аппаратурные и временные затраты на обеспечение отказоустойчивости цифровых фильтров. В диссертационной работе вводится новое понятие о приближенном методе вычислений в СОК. Предлагается новый, приближенный метод вычисления позиционной характеристики числа в СОК, позволяющий устранить необходимость в обработке избыточной информации.
Вторая глава содержит теоретические исследования возможности реализации цифровых фильтров дискретного вейвлет-преобразования в системе остаточных классов, позволяющих сократить время вычисления отклика, за счет увеличения числа параллельных вычислительных каналов.
На рисунке 2а приведен M -канальный набор фильтров, на рисунке 2б - его многофазная форма. На вход изображенного на рисунке 2а набора фильтров подается сигнал - последоваа) тельность x(n), который обрабатывается M анализирующими фильтрами H (z) с последующей i децимацией. Децимация M означает сохранение для дальнейшей передачи каждого M -го элемента б) последовательности, осРисунок 2 - а) M -канальный набор фильтров, тальные M - 1 элементы б) его многофазная реализация.
отбрасываются. Разложение сигнала представляет собой M последовательностей yi (n), 0 i M - 1. Для восстановления сигнала используются M синтезирующих фильтров Fi(z) совместно с интерполяцией (прореживанием сигнала). В ходе интерполяции сигнала (на рисунке она обозначена M ), между последовательными элементами входной последовательности вставляются M -1 нулевое значение сигнала. Результатом работы набора фильтров является выходная последовательность x'(n). Многофазная реализация дискретного вейвлет-преобразования (рисунок 2б) позволяет сократить вычисления отклика, так как в этом случае обработка сигнала происходит после его децимации.
При переводе значений вейвлетных функций из множества действительных чисел в СОК неизбежно возникают ошибки округления. Построение наборов фильтров на основе вейвлетов конечного поля позволяет устранить это явление. Материнский вейвлет (x) и скейлинг-функция (x), определяющие вейвлет-преобразование в конечном поле GF(p), должны удовлетворять следующим соотношениям V0 = span{(n - 2 j)}, j Z, (5) W0 = span{ (n - 2 j)}, j Z, (6) и, кроме того, условиям ортонормированности базиса (n - 2m),(n - 2k) = (m - k), m,k Z, (n - 2m), (n - 2k) = (m - k), m,k Z, (7) (n - 2m), (n - 2k) = 0, m,k Z.
Вейвлет-преобразованием в конечном поле GF(p) является отображение, ставящее в соответствие вектору x(m) последовательность коэффициентов x(m), (m - 2k). Обратное преобразование осуществляется по формуле x(n) = x(m), (m - 2k) (n - 2k)+ x(m), (m - 2k) (n - 2k). (8) kZ kZ Многочлены E00 и E01 многофазной матрицы набора фильтров над полем GF(p), изображенного на рисунке 2, для случая M = 2 определяются следующими соотношениями:
M E00(z) = z-i, e00 0, e0i GF(p); (9) e 0i i=N E01(z) = z-i, e1N 0, e1i GF(p), (10) e 1i i=а многочлены E10(z) и E11(z) находятся по формулам E10(z) = z- N E01(z-1); E11(z) = -z- N E00(z-1), (11) где M - положительное число M N. Кроме того, эти многочлены должны удовлетворять условию точного восстановления сигнала E00(z)E00(z-1)+ E01(z)E01(z-1)= 1. (12) Фильтры H0 и H1 можно найти по формулам H0 = E00(z2)+ z-1E01(z-2); (13) H1 = E10(z2)+ z-1E11(z-2). (14) Фильтры G0 и G1 находятся из условий точного восстановления сигнала G0 = H1(- z), G1(z) = -Ho(- z). (15) Для построения всех возможных двухканальных ортогональных наборов фильтров, позволяющих осуществлять точное восстановление сигнала, разработан следующий алгоритм:
1. Положить M = 1.
M M 2. Найти все пары A(z)= z-i, a0 0 и B(z)= zi, bM 0 из кольца a b i i i=0 i=многочленов F(z), удовлетворяющие условию A(z)A(z-1)+ B(z)B(z-1)= 1. (16) Каждая такая пара многочленов определяет многочлены E00 и E01 по формулам ai = e0i, e1i = 0, для i = 0,..., N - M -1. (17) bi = e1,(N -M +i), для i = 0,..., M.
3. Увеличивать M на единицу и повторять шаг 2, до тех пор пока M N.
Одним из наиболее часто предъявляемых требований при проектировании набора фильтров, является свойство точного восстановления сигнала.
Наиболее распространенным способом добиться свойства точного восстановления сигнала является такое задание матрицы E(z), чтобы она удовлетворяла свойству параунитарности, то есть j j EЖ(e )E(e )= I для всех , (18) где символ Ж означает сопряженное транспонирование, I - единичная матj j рица. В этом случае полагают R(e )= EЖ(e ), и фильтр, определенный матрицами E(z) и R(z), удовлетворяет свойству точного восстановления сигнала. Для построения параунитарных матриц в конечном поле в диссертации доказано следующее утверждение:
Теорема 1. Возьмем вектор v в GF(pn), такой что lv = vTv 0. Тогда матрица s -го порядка -1 -Ds(z) = I - lv vvT + z- slv vvT (19) будет параунитарной в GF(pn).
Доказанная теорема позволяет строить параунитарные матрицы произвольного размера и порядка над полями GF(pn). Построенные параунитарные матрицы являются основой для построения многоканальных наборов фильтров со свойством точного восстановления сигнала в конечном поле.
Третья глава посвящена разработке вопросов обеспечения отказоустойчивости цифровых фильтров, функционирующих в системе остаточных классов.
Операции обнаружения, локализации и исправления ошибок в СОК являются вычислительно сложными, так как для их реализации необходимо наличие информации о величине числа в целом - позиционной харакеристики.
Для нахождения позиционных характеристик числа, представленного в модулярной форме обычно используются точные методы: метод ортогональных базисов, использование функций Эйлера, перевод числа в обобщенную позиционную систему счисления. Однако все эти методы обладают существенными недостатками при использовании на практике: высокие аппаратурные затраты и значительная вычислительная сложность.
Для преодоления данных недостатков был разработан приближенный метод нахождения позиционной характеристики числа в системе остаточных классов, основанный на использовании относительной величины исследуемого числа к полному диапазону системы:
n Pi -1 n A pi = i i, (20) K i P i=1 pi i=где: A - исследуемое число; pi - модули СОК; Pi -1 - мультипликативная pi Pi -P инверсия Pi относительно pi ; Pi = = p1 p2...pi-1 pi+1...pn ; Ki = - конpi pi станты выбранной системы; i - разряды числа, представленного в СОК.
Разработанный приближенный метод вычисления позиционной характеристики описывается следующей последовательностью действий:
Pi -pi 1. Вычисление констант СОК Ki = с требуемой точностью.
pi 2. Вычисление приближенных значений iKi и запись их в LUT-память вычислительной системы, где Ki - константы найденные в п. 1, 1 i pi -1.
Адресами выборки значений iKi являются разряды СОК i, где i = 1,..., n.
3. Вычисление приближенного значения позиционной характеристики n K i в интервале [0,1). Конечный результат определяется после суммиi i=рования и отбрасывания целой части числа с сохранением дробной части суммы. Тогда позиционная характеристика определяется в виде относиn Pi -1 n A pi тельного значения величины = i i.
K i P i=1 pi i=4. Конструируются некоторые правила i, i = 1,...,4 согласно которым вычисляется i -я немодульная операция (определение знака числа, сравнение чисел, обнаружение ошибки и переполнения, а также локализация ошибочного разряда).
A Правило 1. Определение знака числа, в случае, если p1 = 2 : если <, P A то число положительное; если >, то число отрицательное.
P A B Правило 2. Сравнение модулярных чисел A и B : если - = 0, то P P A B A B A = B ; если - > 0, то A > B ; если - < 0, то A < B.
P P P P Правило 3. Обнаружение ошибки и переполнения динамического диапаA M зона: ошибки нет, если <, где A - искаженное число, Pизб = pn+1 pn+2P Pизб Pизб - избыточный диапазон при двух избыточных модулях pn+1 и pn+2, n A M M = P = pi - рабочий диапазон; если , тогда есть ошибка и ус i=1 Pизб Pизб тановлено переполнение динамического диапазона.
Ai Mi Правило 4. Локализация неисправного канала: если <, то в разряде Pi Pi Ai Mi i нет ошибки; если , то в разряде i есть ошибка, где Pi Pi Ai = (1,2,...,i-1,i+1,...,n,n+1,n+2) - проекция искаженного числа A;
Mi = (m1,m2,...,mi-1,mi+1,...,mn,mn+1,mn+2) - проекция рабочего диапазона.
Блок-схема алгоритма обнаружения и локализации ошибки по правилам 3 и 4 изображена на рисунке 3. На основе данного алгоритма разработан блок контроля отказоустойчивого цифрового фильтра в СОК (рисунок 4). В состав фильтра входят: блок перевода входного сигнала из позиционной системы счисления в СОК; КИХ-фильтры по каждому из модулей;
блок контроля; обратный преобразователь сигнала из СОК в позиционную систему счисления. Поступивший на вход фильтра сигнал x(kT ) преобразуется из позиционной формы в остаточную, после чего происходит его обработка в СОК. Модулярная обработка сигнала происходит параллельно, при помощи КИХ-фильтров, по каждому из модулей, как информаРисунок 3 - Блок-схема алгоритма обнаружения ционных pi, i =1,2,...,n, и локализации ошибки с использованием так и контрольных pn+1 и приближенного метода pn+2. После завершения работы фильтра сигнал подается на вход блока преобразования из СОК в ПСС, результатом работы которого является выходная последовательность фильтра y(kT ). Отказоустойчивость фильтра реализуется путем введения в схему блока контроля, назначением которого является обнаружение, локализа-ция и коррекция ошибок. Обнаружение и локализация ошибки в блоке контроля реализуется при помощи устройства, функционирующего на основе алгоритма, изображенного на рисунке 3, использующего приближенный метод.
Применение блока обна- Рисунок 4 - Схема отказоустойчивого цифрового ружения и локализации фильтра в СОК ошибки позволяет установить факт наличия ошибки и локализовать неисправный вычислительный канал, в соответствии со свойствами СОК, независимо от сбоев в одном из каналов. В случае обнаружения ошибки для коррекции и получения верного значения происходит реконфигурация преобразователя СОКПСС с учетом локализованного неисправного канала. Для исправления ошибки используется приближенный метод с финальным шагом коррекции.
Анализ эффективности разработанного приближенного метода для создания отказоустойчивых цифровых фильтров в СОК был произведен при помощи разработанного комплекса программ моделирования вычислений в СОК на основе приближенного метода. Для оценки эффективности применения приближенного метода при реализации операции восстановления позиционной формы числа по его остаточному представлению было произведено его сравнение с методом ортогональных базисов. Для перевода числа из СОК в ПСС применяется приближенный метод с финальным шагом коррекции. Для моделирования перевода чисел из СОК в позиционную систему счисления был разработан комплекс программ в среде PARI/GP, который позволяет производить оценку требуемых аппаратурных затрат на осуществление восстановления позиционной формы числа. В таблице приведены результаты моделирования для СОК с диапазонами 16; 32 и бит. Анализ данных, приведенных в таблице 1 показывает, что применение приближенного метода для восстановления позиционной формы числа по его модулярному коду позволяет существенно сократить аппаратурные и временные затраты по сравнению с методом ортогональных базисов.
Таблица 1. Аппаратурные и временные затраты приближенного метода и метода ортогональных базисов перевода числа из СОК в ПСС Разрядность точного Такты восстановления синхронизации Модули СОК 16 {7, 17, 19, 29} 21 43 44 1{2, 3, 5, 11, 13, 19, 23, 32 38 81 154 429, 79} {2, 11, 17, 19, 23, 31, 41, 64 72 143 290 753, 59, 61, 71, 79, 83} Для СОК с диапазоном 16 бит аппаратурные затраты сокращаются в 2,0 раз, работа устройств ускоряется в 2,8 раз. В СОК с диапазоном 32 бит происходит сокращение временных затрат в 2,1 раз и увеличение быстродействия в 3,1 раз. Наконец, для СОК с диапазоном 64 бит происходит сокращение аппаратурных затрат в 2,0 раз, временных затрат в 2,5 раз (рисунок 5). Данный выигрыш объясняется тем, что при использовании приближенного метода не происходит работа над избыточной информацией, а также имеется возможность для использования табличной арифметики при работе с дробными величинами. Таким образом можно сделать вывод о преимуществе предложенного метода над ранее известными.
Приближенный метод Приближенный метод Метод ортогональных базисов Метод ортогональных базисов 81140 7120 6100 580 460 340 220 10 16 32 64 16 32 Диапазон СОК, бит Диапазон СОК, бит а) б) Рисунок 5 - Затраты методов перевода числа из СОК в ПСС а) аппаратурные, б) временные.
метод метод Метод Метод базисов базисов Диапазон СОК, бит ортогональных ортогональных Приближенный Приближенный Разряды Такты синхронизации В таблице 2 приведены значения разрядности приближенного метода и метода ОПСС для реализации операций определения знака числа, сравнения чисел, обнаружения и локализации ошибки в СОК с диапазонами 16, и 64 бит. Анализ данных, приведенных в таблице 2 показывает, что применение приближенного метода для реализации немодульных операций позволяет значительно сократить аппаратурные и временные затраты, по сравнению с методом перевода числа из СОК в ОПСС.
Таблица 2. Аппаратурные затраты приближенного метода выполнения немодульных операций в СОК.
Десятичные Двоичные Такты разряды разряды синхронизации 16 6 14 18 36 38 32 11 30 35 74 142 264 21 50 67 140 270 5При использовании десятичной записи чисел аппаратурные затраты сокращаются в 2,3; 2,7 и 2,4 раз для СОК с диапазонами 16; 32 и 64 бит, соответственно (рисунок 6а). При использовании двоичного кодирования информации происходит сокращение аппаратурных затрат в 2,0; 2,1 и 2,1 раз для СОК с диапазонами 16; 32 и 64 бит, соответственно (рисунок 6б).
Приближенный метод Приближенный метод Метод обобщенной позиционной Метод обобщенной позиционной системы счисления системы счисления 11120 10 16 32 64 16 32 Диапазон СОК, бит Диапазон СОК, бит а) б) Рисунок 6 - Аппаратурные затраты методов выполнения немодульных операций определения знака числа, сравнения чисел, обнаружения и локализации ошибки: а) десятичные разряды, б) двоичные разряды.
метод метод метод Диапазон СОК, бит Метод ОПСС Метод ОПСС Метод ОПСС Приближенный Приближенный Приближенный Двоичные разряды Десятичные разряды Для СОК с диапазоном Приближенный метод бит время выполнения немодульМетод обобщенной позиционной ных операций сокращается в 1,системы счисления 6раз. Скорость выполнения немодульных операций для СОК с диа5пазоном 32 бит увеличивается в 42,1 раз. Применение приближен3ного метода для СОК с диапазо2ном 64 бит позволяет сократить время вычислений в 2,1 раз (рису1нок 7). Результаты эксперимента показывают, что приближенный 16 32 метод позволяет получить выиг- Диапазон СОК, бит рыш с точки зрения временных и Рисунок 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.20Формат 60х84 1/16 Усл.печ.л. 1,0 Уч.-изд.л. 0,Бумага офсетная Тираж 150 экз. Заказ 1Отпечатано в Издательско-полиграфическом комплексе Ставропольского государственного университета.
355009, Ставрополь, ул.Пушкина, 1.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям