Содержание к диссертации
Введение
Глава I. Анализ методов распознавания и классификации образов 15
1.1. Введение 15
1.2. Общая характеристика проблемы распознавания и классификации образов 15
1.3. Основные задачи, решаемые в процессе синтеза систем распознавания и классификации образов 18
1.4. Этап экстракции классообразующих признаков в обобщённой системе распознавания образов 27
1.5. Аналитический обзор методов экстракции классообразующих признаков из изображений 30
1.5.1. Преобразование Фурье 38
1.5.2. Косинусное преобразование 39
1.5.3. Вычисление градиента изображения 41
1.5.4. Вейвлет-преобразование 42
1.5.5. Вычисление моментов изображения 45
1.6. Сравнительный анализ методов экстракции классообразующих признаков для систем распознавания и классификации образов .47
1.7. Обоснование целесообразности применения системы остаточных классов для вычисления 'дискретного вейвлет-преобразования в системах распознавания и классификации образов, функционирующих в реальном режиме времени 51
1.8. Выводы по первой главе 53
1.9. Постановка задачи исследования 54
Глава 2. Разработка математических моделей вейвлет-анализа и модулярных вычислений для задач распознавания образов 57
2.1. Введение 57
2.2. Вейвлет-анализ в системах распознавания изображений 57
2.2.1. Кратномасштабиый анализ и вейвлеты 58
2.2.2. Развитие методов быстрого вейвлет-преобразования с помощью фильтров Добеши D4 65
2.3. Разработка математических моделей непозиционного кодирования для цифровой фильтрации 68
2.3.1. Модели параллельных вычислений в системе остаточных классов.. 74
2.3.2. Разработка методов повышения скорости вычислений в модулярных вычислительных каналах 77
2.4. Развитие методов КИХ-фильтрации для ПЛИС 92
2.5. Выводы по второй главе 100
Глава 3. Разработка модулярных алгоритмов вейвлет-анализа 101
3.1. Введение 101
3.2. Разработка методов дискретного вейвлет-преобразования на основе битовой арифметики 106
3.3. Модулярный сдвиговый сумматор с накоплением 109
3.4. Разработка рекурсивного алгоритма дискретного вейвлет-преобразования на основе модулярной арифметики 112
3.5. Разработка двуфазного рекурсивного модулярного алгоритма дискретного вейвлет-преобразования 115
3.6. Разработка параллельного модулярного алгоритма дискретного вейвлет-преобразования с экстенсивным использованием LUT-таблиц 117
3.7. Выводы по третьей главе 119
Глава 4. Моделирование и синтез высокоскоростных модулярных структур цифровой вейвлет-фильтрации на ПЛИС 122
4.1. Введение 122
4.2. Разработка архитектуры цифрового сигнального процессора для модулярной вейвлет-фильтрации 123
4.3. Методы организации вычислений в модулярных каналах 127
4.3.1. Алгоритмы, основанные на технике быстрой КИХ-фильтрации... 127
4.3.2. Алгоритмы с техникой демультиплексирования 130
4.3.3. Вычислительные архитектуры на основе битовой арифметики 141
4.4. Методы организации вычисления двумерного дискретного вейвлет-преобразования 143
4.5. Моделирование модулярных вычислительных элементов на ПЛИС 148
4.6. Выбор набора оснований СОК для вейвлет-фильтрации 151
4.7. Исследование производительности разработанных алгоритмов 157
4.8. Выводы по четвёртой главе 164
Заключение 166
Список литературы
- Основные задачи, решаемые в процессе синтеза систем распознавания и классификации образов
- Развитие методов быстрого вейвлет-преобразования с помощью фильтров Добеши D4
- Разработка методов дискретного вейвлет-преобразования на основе битовой арифметики
- Алгоритмы, основанные на технике быстрой КИХ-фильтрации...
Введение к работе
Диссертация посвящена разработке модулярных алгоритмов дискретного вейвлет-преобразования в системе остаточных классов для задач распознавания и классификации образов.
Актуальность темы. На данном этапе развития информационных технологий не вызывает сомнений важная и даже первостепенная роль подсистемы распознавания образов в кибернетических системах следующих поколений и роботов, самостоятельно ориентирующихся в пространстве и осваивающих его [78, 99]. За прошедшие 30-40 лет искусство распознавания образов уже выделилась во вполне самостоятельное направление, причисляемое к проблематике искусственного интеллекта [12, 21, 30, 73, 77]. Вместе с тем, в значительной мере оно основывается на исследованиях в области цифровой обработки сигналов, методах принятия решений, нейроинформатике и других инженерных дисциплинах.
В 80-х годах прошлого столетия появилось новое направление в области цифровой обработки сигналов - вейвлет-анализ [95]. В отличие от традиционно применяемого при анализе данных преобразования Фурье, результаты, полученные с помощью вейвлет-аиализа, обладают большей информативностью и способны выявлять такие особенности данных, которые при стандартных подходах анализировать-затруднительно [106]. Не отвергая значимости анализа Фурье, вейвлет-преобразоваиие его успешно дополняет и зачастую способно полностью заменить в решениях многих задач. Успешное применение вейвлет-преобразования, к примеру, в таких приложениях, как анализ сигналов и сжатие информации, стимулирует поиск новых идей и решений его использования в различных научно-технических' областях знаний, в том числе и в задачах распознавания изображений.
Одним из наиболее актуальных направлений использования устройств распознавания изображений является анализ статических изображений. В связи с этим, перед многими исследователями стоит задача совершенствования методов обработки изображений [19, 96, 97]. Один из путей повышения эффективности обработки является использование алгоритмов обработки и методов оценки изображений, основанных на кратномасштабном вейвлет-преобразовании [130]. С его помощью может быть решён широкий круг задач синтеза, анализа и обработки изображений. Кроме того, кратномасштабное представление обеспечивает сокращение объёмов обрабатываемых изображений за счёт удаления избыточной информации, тем самым снижая вычислительные затраты на последующую обработку [168, 178]. Оптические приборы и человеческое зрение обладают возможностями кратиомасштабности, позволяя расфокусироваться и сфокусироваться при необходимости рассмотреть мелкие детали либо всю картину целиком. Изображению с индексом масштаба J соответствует сумма всех полученных представлений изображения от самого первого (самого низкочастотного) до представления изображения уровня J включительно. Система распознавания может использовать для анализа изображения любой масштаб, переходя с одного уровня на другой и, возможно, приходить к необходимости вычисления следующего уровня мелких подробностей [59, 86].
Описанные возможности вейвлет-анализа позволяют говорить о нем как о перспективном и заслуживающем дальнейшего изучения инструменте для систем распознавания и классификации образов в реальном режиме времени.
До недавней поры получение вейвлет-коэффициентов было затруднительно, т.к. было связано с необходимостью вычисления большого количества интегралов с необходимой точностью и работой с очень малыми величинами [51]. Быстрое вейвлет-преобразование, предложенное Малла в 1989 году [ 149], позволило вычислять коэффициенты вейвлет-разложения без
интегрирования, используя алгебраические операции на основе свёртки. Поскольку свёртка осуществляется только операциями умножения и сложения, открывается возможность применения модулярных вычислений в системе остаточных классов, где эти операции могут быть реализованы крайне эффективно. Современное развитие технологий программируемых логических интегральных схем позволяет эффективно реализовывать модулярные алгоритмы вычислений с помощью однотактовых выборок из ШТ-таблиц [46, 47, 90].
Таким образом, исследования, проведённые в диссертационной работе, являются актуальными и практически значимыми.
Целью работы является повышение эффективности систем распознавания и классификации образов путём разработки эффективных модулярных алгоритмов дискретного вейвлет-преобразования в непозиционной системе остаточных классов.
Задачи диссертационной работы. Для достижения указанной цели решаются следующие задачи:
Анализ методов выделения классообразующих признаков в системах распознавания и классификации образов.
Исследование и развитие подходов и методов, применяемых для повышения эффективности модулярных вычислений.
Построение математической модели вейвлет-анализа, пригодной для её реализации в непозиционной системе остаточных классов.
Развитие эффективных методов КИХ-фильтрации для программируемых логических интегральных схем.
Разработка модулярных алгоритмов выполнения дискретного вейвлет-преобразования с оптимизацией по производительности и по количеству вентилей.
Разработка модулярного сдвигового сумматора с накоплением для повышения скорости работы модулярного алгоритма дискретного вейвлет-преобразования.
Компьютерное моделирование и экспериментальное исследование разработанных алгоритмов.
Объектом исследования в данной диссертации выступает система распознавания и классификации образов, а предметом исследования -эффективные методы . реализации этапа экстракции классообразующих признаков методами частотного вейвлет-анализа.
Методы исследования. Для решения поставленных в работе научных задач использованы методы теории цифровой фильтрации сигналов, теории вероятностей, математического моделирования, вейвлет-анализа, алгебры, теории чисел, теории модулярных вычислений в системе остаточных классов, а также математический и системный анализ.
Достоверность и обоснованность полученных в диссертационной работе теоретических результатов и формулируемых на их основе выводов обеспечивается строгостью производимых математических выкладок. Справедливость выводов' относительно эффективности предложенных методов подтверждена компьютерным моделированием.
Моделирование и вычислительный эксперимент проводились с использованием математического пакета Mathworks MATLAB v7.0 R14, интегрированной среды проектирования ПЛИС Xilinx ISE v8.1 и среды симуляции, отладки и исследования характеристик ПЛИС ModelSim ХЕ III 6.0 Xilinx Edition.
Теоретическая значимость работы заключается в следующем; 1. Разработана математическая модель и алгоритмы модулярного вейвлет-преобразования для выполнения экстракции в системах распознавания и классификации образов.
2. Разработаны и исследованы методы реализации модулярного вейвлет-преобразования на вычислительной базе ПЛИС.
Практическая значимость работы состоит в том, что разработанные методы и алгоритмы могут быть с успехом применены в автономных системах распознавания образов, в том числе, в виде модулей SoC (System-on-Chip, вся система на одном чипе), а также при проектировании специализированных высокопроизводительных СОК-архитектур цифровой обработки сигналов в реальном режиме времени.
Положения, выносимые на защиту:
Обобщённая система распознавания и классификации образов.
Обоснование целесообразности применения методов кратномасштабного вейвлет-анализа для извлечения классообразугощих признаков на этапе экстракции.
Математическая модель вейвлет-преобразования по алгоритму Малла с помощью ортогональных вейвлет-фильтров Добеши.
Математическая модель модулярных вычислений.
Алгоритм модулярного вейвлет-преобразования и его двуфазная модификация для уменьшения размеров используемых ШТ-таблиц.
Параллельный алгоритм модулярного дискретного вейвлет-преобразования с экстенсивным использованием LUT-таблиц.
Алгоритм и схема работы модулярного сдвигового сумматора с накоплением для повышения скорости работы модулярного алгоритма дискретного вейвлет-преобразования.
Результаты моделирования разработанных алгоритмов.
Алгоритм двумерного вейвлет-преобразования изображений и метод симметричного расширения границ изображений.
Личный вклад соискателя. Все изложенные в работе результаты исследований получены при непосредственном участии автора. Автору
принадлежат: разработка математической модели, методов и алгоритмов
модулярной фильтрации, разработка принципов повышения
производительности ПЛИС-вычислений в системе остаточных классов, создание специализированного вычислительного элемента «модулярный сдвиговый сумматор с накоплением»; выбор и проведение экспериментальных исследований; интерпретация результатов; формулирование научных положений и выводов.
Реализация результатов. Теоретические и практические разработки диссертационной работы использованы при выполнении НИР по гранту Федерального агентства по образованию А04-2.8-755 и реализованы в 000 «МОБИ» и 000 «РР-ИКС», а также в учебном процессе Ставропольского государственного университета.
Апробация результатов работы. Результаты работы были представлены в журнале «Инфокоммуникациониые технологии» (Самара, 2005 г.), в журнале «Нейрокомпьютеры: разработка и применение» (Москва, 2005 г.), в трудах участников 50-й юбилейной научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука - региону», посвященной 60-летию Победе в Великой Отечественной войне (Ставрополь, 5-25 апреля 2005 г.), на 51-й научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука - региону» (Ставрополь, 3-24 апреля 2006 г.), на международной научно-технической конференции «50 лет модулярной арифметике» (Зеленоград, 2005 г.) и на постоянно действующем межвузовском семинаре «Моделирование и нейросетевые технологии» (СГУ, Ставрополь, 2005-2006 гг.).
Публикации. Основные результаты работы отражены в 6 публикациях суммарным объёмом 37 страниц, из них четыре в журналах, одобренных ВАК.
Содержание работы. Диссертационная работа состоит из введения, 4-х глав, заключения, списка литературных источников и приложений. Содержит 45 рисунков, 7 таблиц, 4 приложения. Список используемой литературы содержит 205 источников. В диссертации принята двойная нумерация формул, рисунков и таблиц; первая цифра указывает номер главы, а вторая - порядковый номер рисунка, таблицы или формулы внутри данной главы.
Первая глава посвящена литературному обзору методов выделения классообразующих признаков для систем распознавания изображений по отечественным и зарубежным источникам. Показано, что этап экстракции вектора признаков является одним из важнейших в обобщённой системе распознавания образов. Приводится обзор наиболее популярных методов частотного анализа. На основе анализа частотно-временных характеристик рассматриваемых преобразований и возможности кратномасштабного представления информации делается вывод о преимуществах вейвлет-анализа для задач распознавания и классификации образов. Сформулирована постановка задачи исследования, а именно, разработка эффективного алгоритма получения коэффициентов вейвлет-преобразования для современных средств организации высокопроизводительных ПЛИС-вычислений.
Вторая глава содержит развитие теоретических исследований интегрального вейвлет-анализа непрерывных сигналов и вейвлет-анализа дискретных сигналов. Приводятся принципы и возможности кратномасштабного разложения изображений. Описан синтез алгоритма быстрого вейвлет-разложения дискретных сигналов - каскадный алгоритм Малла. Для алгоритма Малла на примере фильтров Добыли показаны примеры построения вейвлет-фильтров для прямого и обратного вейвлет-преобразования. Рассмотрены вопросы двумерного дискретного вейвлет-преобразования для разложения изображений. Для эффективной реализации операций вейвлет-преобразования по алгоритму Малла на основе свёртки
разработан теоретический аппарат системы остаточных классов и принципы организации модулярных вычислений. Обобщаются и развиваются методы синтеза специализированных вычислителей по модулю в модулярных вычислительных каналах. Отмечены основные подходы реорганизации вычислений для получения максимальной сквозной пропускной способности модулярных каналов. Завершает главу разработка и применение эффективного подхода к реализации на программируемых логических интегральных схем банков фильтров с конечной импульсной характеристикой (КИХ).
В третьей главе на основе теоретических разработок предыдущей главы проводится синтез алгоритмов модулярного дискретного вейвлет-анализа для систем распознавания и классификации изображений. Для возможности оценки производительности разработанных в этой главе алгоритмов синтезирован также алгоритм обычного дискретного вейвлет-преобразования для чисел, представленных в обыкновенной позиционной системы счисления (в дополнительном двоичном коде). Обосновывается необходимость и разрабатывается алгоритм работы специализированного модулярного вычислителя - модулярного сдвигового сумматора с накоплением. Синтезируется двуфазный алгоритм модулярного вейвлет-анализа для уменьшения требований к вентильным ресурсам ПЛИС. Реорганизация последовательности вычислений в схемах фильтрации позволяет синтезировать ещё один высокопроизводительный алгоритм модулярного вейвлет-преобразования с экстенсивным использованием LUT-таблиц.
В четвёртой главе предлагаются методы реализации на ПЛИС разработанных в предыдущей главе методов и алгоритмов. Анализируются требования, предъявляемые параллельным вычислительным структурам для цифровой фильтрации и строится обобщённая схема цифрового сигнального процессора для модулярной вейвлет-фильтрации. Обобщены и получают дальнейшее развитие методы организации вычислений в модулярных
вычислительных каналах, в том числе, методы на основе техники быстрой КИХ-фильтрации, множественного доступа с разделением каналов по времени и на основе битовой (сериализоваш-юй) арифметики. Предлагается подход к выбору набора оснований СОК. Для двумерных сигналов, которыми, в частности, являются изображения, подаваемые на вход системы распознавания и классификации образов, алгоритм выполнения дискретного вейвлет-преобразования аналогичен одномерному. Для устранения граничных искажений разрабатывается метод расширения границ обрабатываемого массива. Для оценки преимуществ и недостатков было проведено компьютерное моделирование при различных длинах входных значений, коэффициентов фильтров и выходных результатов.
В заключении содержится краткая сводка основных результатов работы и выводы.
В приложениях представлены основные фрагменты программного кода MATLAB и VHDL, используемые для расчёта количественных характеристик разработанных алгоритмов; акты внедрения результатов диссертационног'о исследования.
Автор выражает искреннюю благодарность научному руководителю -доктору технических наук, заслуженному деятелю науки и техники РФ, академику МАИ, создателю и руководителю научной школы «Модулярные нейрокомпьютеры», почётному профессору Ставропольского государственного университета Николаю Ивановичу Червякову, а также сотрудникам кафедры алгебры и кафедры прикладной математики Ставропольского государственного университета за советы и критические замечания, высказанные при обсуждении работы. Хотелось бы также поблагодарить Федеральное агентство по образованию РФ за финансовую поддержку по гранту А04-2.8-755 «Разработка нейросетевых методов и алгоритмов для решения задач распознавания и классификации образов».
Основные задачи, решаемые в процессе синтеза систем распознавания и классификации образов
Каждая система распознавания приспособлена для распознавания только данного вида объектов или явлений. Так, система предназначенная для диагностики заболеваний, не умеет диагностировать отказы сложной аппаратуры, а система, ориентированнаая на распознавание слов и предложений русского языка, будет беспомощна перед китайскими иероглифами или нотными знаками.
Рассмотрим основные задачи, возникающие в процессе синтеза систем распознавания. Необходимо иметь в виду следующее. Процесс разработки систем распознавания и классификации требует построения математической или физико-математической модели системы. Только наличие подобной модели позволяет реализовать итерационный процесс построения прообразов системы распознавания, всё более и более приближающихся по своим характеристикам (точности, временным, габаритным, весовым, стоимостным и т.д.) к требуемым, задаваемым на стадии разработки технического задания на создание системы. Рассматриваемые ниже- задачи в той или иной мере, с одной стороны, обеспечивают построение модели системы, а с другой стороны, могут быть решены только с помощью модели [30, 71, 67,75, 76].
Задача 1. Задача заключается в том, чтобы определите полный перечень признаков (параметров), характеризующих объекты или явления, для распознавания которых разрабатывается данная система. Эта совокупность признаков должна быть сформирована безотносительно каких-либо ограничений, связанных как с получением априорной информации, необходимой для исходного описания классов объектов, так и с получением апостериорной информации о конкретных объектах, подлежащих распознаванию. Наоборот, первоначально необходимо определить все признаки, хотя бы в малейшей мере характеризующие объекты или явления.
Задача 2. Задача заключается в проведении первоначальной классификации распознаваемых объектов или явлений, в составлении оприорного алфавита классов. Основное в данной задаче - выбор надлежащего принципа классификации, последний определяется требованиями, предъявляемыми к системе распознавания, которые, в свою очередь, зависят от того, какие решения могут приниматься системой управления по результатам распознавания неизвестных объектов или явлений. При решении последующих задач априорный алфавит классов уточняется, в результате чего формируется рабочий алфавит классов системы распознавания и классификации образов [14].
Задача 3. Задача состоит в разработке априорного словаря признаков. Словарь разрабатывается на основе результатов решения первой задачи с учётом того, что в априорный словарь признаков включаются только те признаки, относительно которых может быть получена априорная информация, необходимая для описания классов на языке этих признаков.
Задача 4. Задача состоит в описании всех классов априорного алфавита классов на языке признаков, включённых в априорный словарь признаков. Эта задача не имеет однозначного решения, и в зависимости от объёма исходной информации для её решения могут быть использованы методы непосредственной обработки исходных данных, обучения или самообучения. Если признаки распознаваемых объектов - детерминированные, то описаниями классов объектов на языке этих признаков являются их эталоны, т.е. точки, равноудалённые от точек, описывающих объекты, принадлежащие каждому данному классу.
Выработка сведений о распознаваемых объектах и априорное описание классов - весьма трудоёмкая часть в решении классификационных задач, требующая глубокого изучения свойств этих объектов.
Задача 5. Задача заключается в разбиении априорного пространства признаков на области, соответствующие классам априорного алфавита классов.
Подобное разбиение должно быть выполнено в некотором смысле оптимальным образом, например, так, чтобы при этом обеспечивалось минимальное значение ошибок, неизбежно сопровождающих распознавание поступающих на вход системы распознавания неизвестных объектов или явлений.
Пусть в априорном словаре признаков содержится упорядоченный набор объектов или явлений x[}...,xN, где X; можно рассматривать как составляющие вектора ха - [xv...,xN], описывающее априорное пространство признаков систем распознавания (априорное признаковое пространство) размерности N; конкретные точки этого пространства представляют собой распознаваемые объекты. Помимо геометрической существует и алгебраическая трактовка задачи: требуется построить разделяющие функции Ft [х{,..., xv ], і = 1,..., т, обладающие следующим свойством [1, 4, 23, 33]: если объект, имеющий признаки х,0,.--, , относится к классу Qp то величина { ,,...,} должна быть наибольшей. Такой же она должна быть и для всех других значений признаков объектов, относящихся к классу П;. Если х обозначить вектор признаков объекта, принадлежащего к Qg-My классу, то для всех значений вектора xgFg[xg) Fg[xs), g = 1,...,т.
Развитие методов быстрого вейвлет-преобразования с помощью фильтров Добеши D4
На уровне таких формальных рядов децимация производится совершенно просто: нужно обратить в нуль коэффициенты при нечётных степенях, а для этого достаточно взять iXH(z) + XH(-z)\ 2, затем в полученном выражении нужно сделать замену z2=w. Тогда массиву {4,}, А - Хл z х2 к соответствует степенной ряд A(w), определённый равенством: )=!«НЬ . (2-5) Аналогично, высокочастотный массив [Dn], Dn = 2ІшІкх2п-к соответствует ряду D(w), определённому равенством: D 2 XG(z) + XG(-z) (2.6) 2 На этапе восстановления сигнала производим обратную децимацию и ищем новые фильтры Я(й)) = У]Нпе ",а" и G(z) = y gne ir,l с коэффициентами \h ,\ и \gH\i которые дадут точную реконструкцию по формуле: =25 4 + 1.-2 - (2-7)
Последнюю формулу записываем в виде свёртки, сделав обратную децимацию массивов Дг] и {&„} \Акі если.и = 2&; - [DA., ссли« = 2; (2.8) [О, еслии = 2 + 1 " [О, если л = 2k +1 Тогда формула (2.7) принимает вид: xn=2Y(h»-ak + gri_kDk). (2-9)
Запись формулы восстановления в виде свёртки позволяет решить задачу нахождения фильтров реконструкции \1гЛ и \g„}, используя преобразование Фурье. Однако, здесь удобнее работать с z -преобразованием.
Если у нас имеются массивы [Ап\ и {Ц,}, то им соответствуют ряды A{w) = Y,Ar!-w" и D(w) = У]DnW,. На уровне формальных степенных рядов обратная децимация - это замена w = z . Тогда ряды, соответствующие массивам А„ и D», есть A(z2) и D{z2). Теперь наша цель заключается в нахождении фильтров H(z) и G(z), таких, чтобы выполнялось X{Z) 2{H{Z)A{Z2) + G{Z)D{Z1)). (2Л) Подставляя в (2,10) выражения для A(z2) и D(z2) из формул (2.4) -(2.6), получаем: X(z) = (#( )# (z) + G(z)G(z))X(z) + (2-11) +[H(Z)H( Z) + G(z)G(-z))x(rz). В силу произвольности X(z) из последнего равенства мы видим, что искомые фильтры #(z) и G(z) должны удовлетворять системе уравнений rH(z)H(z) + G(z)G(z) = 1 (2-12) [H(z)H(-z) + G(z)G( z) = 0 В матричном виде: (2.13) Ї r H(z) ( H(z) G(z) Щ-z) G(-z) G(z)J \P)
Решая систему (2.12), мы находим фильтры H(z) и G(z). Условия существования решения вполне очевидны - определитель системы должен быть отличен от нуля: АНС= H{z)G( z) - H( z)G{z) 0. (2.14) всюду на единичной окружности z = е 1Ш.
Таким образом, если фильтры H(z) и G(z) выбрать удовлетворяющими уравнению (2.14), то фильтры восстановления H{z) и G(z) находятся единственным образом из системы (2.12). Проблема заключается в том, что нам нужно найти не только функции H(z) и G(z), не менее важно, чтобы были получены хорошие выражения для их коэффициентов через коэффициентов фильтров #(z) и G(z) [5].
Эта проблема решается с помощью сопряжённых квадратурных фильтров из хорошо разработанной теории субполосного кодирования [60].
Выбираем фильтр H(z) с вещественными коэффициентами {hn}. Остальные фильтры определяем так: G(z) = -z-lH(-z-x); (2.15) H(z) = H(z-1); G(z) = G(z-l) = -zH(-z).
Тогда очевидно, что второе соотношение из (2.12) выполнено, а первое принимает вид: H(z l)H(z) + H{-z)H{ z-x) = 1. (2-16)
Вернёмся к частотной переменной а?, полагая z-e ,a . Напомним, что Н(а ) есть H(z) при z = е №. Поскольку z 1 = z в случае, когда z = e lta, и поскольку коэффициенты {кп) - вещественные, имеем H(z l) =Н(0)). Далее, -z = -е ш = г (й)+ж). Поэтому Я(-г) = Я(й) + я-). Тогда условие (2.16) принимает вид: \H(cof +\H( + xf = \, (2-17) а оставшиеся фильтры будут следующие: G(a ) = -ela,H(a + 7c); (2-18) Н(Ф) = Я(й ); ед = -е-івЯ(й) + я). Система (2.12) сводится к одному уравнению (2.17), которое даёт условие для выбора фильтра Н(а ).
Разработка методов дискретного вейвлет-преобразования на основе битовой арифметики
Битовая арифметика в дополнительном коде (БАДК) может быть успешно применена для реализации КИХ-фильтров и других линейных дискретных преобразований. Как было отмечено выше (параграф 2.4), в БАДК операции обычного умножения заменены на табличное умножение с помощью ШТ-таблиц. БАДК является последовательной на уровне битов, и в большинстве случаев быстрее традиционных умножителей/сумматоров. В добавок, по сравнению с программируемыми АЛУ, БАДК приводит к меньшему накоплению ошибок округления [187]. Преимущества БАДК могут быть использованы для организации вычислений в ПЛЙС-процессорах для цифровой обработки сигналов, у которых возможности быстрого сложения/умножения традиционно являются слабым местом (по сравнению с непрограммируемыми СБИС-процессорами).
Схема вычислений БАДК подразумевает, что сигнал на входе процессора цифровой обработки сигналов (в частности, интересующего нас КИХ-фильтра) является -битовым словом (в дополнительном коде): = -2 + 2 , (3.6) где а[ 1) - бит с номером / входного сигнала Й М), Подставив выражение (3.6) в (3.3). получим: JV-I N-l B,-2 Zvftn+M C
По описанной в параграфе 2,4 методике назначим БАДК-ШТ-таблицы в виде функций LUT (/) и ШТА(/) по формулам: LUT Z) = Ze -in LUT,(/) = IVa. (18) благодаря чему уравнения (3.7) можно переписать в виде: ef - LUT -lJ + LUT O; (3 9) rff = -2 - ШТ, (Я, -1) + JT2 LUTA(/) Вычисление аппроксимирующих а и детализирующих J r) коэффициентов /-го уровня (і 1, 2, . . . , J) производится с помощью двух ШТ-таблиц размером 2N xW, содержащих функции ШТ (/) и LUTft(/), адресуемые W-битовым вектором {4 fl -V --- -«+u} W b + \\og2(N)], где b обозначает ширину коэффициентов фильтра. Видно, что при вычислении выражения (3.4) необходимо произвести повторные запросы к LUT-таблицам ШТ (/) и LUTb (7), которые следуют за накапливающим сдвиговым сумматором (реализующим фрагменты -25г1ШТ(Д.-1)).
Схема тактируется сигналом bCLK, а на уровне слов - sCLK. Понятно, что bCLK и sCLK связаны соотношением sCLK = bCLK/i?,.. Регистры сдвига имеют ширину Д и сдвигают влево, так что первым будет обработан самый старший бит (MSB).
Размеры БАДК-ШТ будут увеличиваться экспоненциально с ростом длины фильтра. Нивелировать это можно с помощью многофазных фильтров разложения, что повлечёт за собой уменьшение адресного пространства БАДК-ШТ. Определим многофазные фильтры следующим образом; g0(k)=-glk, К(Ю = Кк gx(k) = gik,i и M ) = Az +i. гДе ( = 0Л JV/2-1). Многофазная БАДК-архитектура будет состоять из четырёх независимых фильтров, параллельно оперирующих чётными и нечётными индексами входного вектора (ЗЛО): Af/2-l N12-]) -2S-1 і=0 (3.10) =0 4=0 i=0 k=li
Таким образом, многофазные фильтры обрабатывают два разных подмножества входных данных. Входные данные вектора cf! !) с чётными номерами сворачивается фильтрами g0(k) и 1%{к\ а с нечётными - g k) и hi(k). LUT-таблицы, соответствующие такой схеме вычислений, рассчитываются по формулам: и выходы банка фильтров будут определяться как (3,12): ві-2 вгг a j) = -lLUTgQ№-l)+ ШТ О Ш Д -1)+ 2 ШТД(/); Гі Л (ЗЛ2) rf«=-2 - LUTJ5f-l) + f;VLm (0-24-,LUT (5,-1) + 2 (0 1=0 1=0 Алгоритм вычисления выражения 3.12 предусматривает четыре LUT-таблицы размером 2N/2 xW\ где w 6 +[log2(N/2)] и by - ширина коэффициентов многофазных фильтров.
Для корректной работы многофазного алгоритма необходимо ввести задержку в нечетно-нумерованную последовательность. Выходы с$ и d вьгчисляются путём слияния выходов низкочастотного и высокочастотного многофазного фильтра, соответственно,
Модулярная арифметика в системе остаточных классов (СОК) является очень эффективньш инструментом реализации высокопроизводительных процессоров цифровой обработки сигналов на основе ПЛИС, Одной из основных проблем, довлеющих над разработчиками вычислительных ПЛИС, является опасность выйти за пределы вычислительного диапазона в промежуточных вычислениях [154]. Как было разобрано в параграфе 2,3, вычисления в СОК происходят параллельно по L вычислительным каналам малой размерности (обычно т-, 5 2 ), с помощью которых можно эффективно реализовать необходимый динамический диапазон вычислений.
Для применения модулярных вычислений в архитектурах, аналогичных описанным ранее БАДК, необходим специально спроектированный сдвиговый сумматор по модулю т; с накоплением, производящий вычисление \у(п)\ = р-УІп -1) + х(п)\ по следующим правилам:
Алгоритмы, основанные на технике быстрой КИХ-фильтрации...
Одним из наиболее преспективных путей повышения производительности цифровой фильтрации в устройствах различного назначения является внедрение новых высокоэффективных параллельных структур, ориентированных на широкое использование СБИС и ПЛИС [101, 137,143 ,145, 164, 176].
Благодаря параллелизму СОК, вычислительное устройство разбивается на вычислительные каналы по количеству модулей принятой системы оснований. Обеспечиваемая при этом однородность модулярных вычислительных устройств идеально согласуется с принципами конвейерной обработки информации [46, 47].
Анализ применения алгоритмов арифметики СОК в устройствах цифровой фильтрации показывает, что звенья имеют одинаковую обобщённую структуру, типовым элементом которой является последовательность операций сложения, сдвига, умножения и задержки, при этом значительная часть операций может быть эффективно реализована с помощью операций табличной выборки.
В работах [6, 72, 90,] представлена общая структура специализированного цифрового сигнального процессора, основными элементами которого являются: 1. Модулярные вычислительные каналы, количество которых определяется выбранной для вычислений системой остаточных классов. 2. Устройство согласования позиционных вычислительных устройств с модулярным вычислительным устройством. 124 3. Устройство согласования модулярного вычислительного устройства с позиционным вычислительным устройством. 4. Устройство обнаружения и коррекции ошибок (УОКО). 5. Блок вычисления позиционных характеристик.
Разработанные способы реализации модульных и немодульных процедур и их аппаратные структуры позволяют синтезировать общую параллельную струкгуру цифровых фильтров в системе остаточных классов для реализации на ПЛИС, которая представлена на рис. 4.1.
Вычислительный канал цифровой фильтрации в СОК по модулю т1 включает в себя звенья фильтра, реализованные в виде блоков операций в кольце целых чисел и элементов задержек на сигнальных линиях, LUT-таблиц для ускорения выполнения операций суммирования и умножения, а таюке демультиплексоры, сдвиговые регистры и FIFO-буферы для хранения промежуточных результатов.
Процесс функционирования параллельных структур цифровой фильтрации в СОК определяется выбранной структурой модулярного вычислительного канала, способом выполнения арифметических операций в звене, формой реализации фильтра, заданной точностью вычислений, допустимыми аппаратурными (вентильными для ПЛИС) затратами и способом реализации алгоритма фильтрации [90, 177].
Основными этапами организации функционирования цифрового фильтра в СОК являются [38]: 1. Подготовительный этап. 2. Этап выбора характеристик СОК. 3. Этап синтеза структуры и оценки эффективности цифровой модулярной фильтрации. К первому этапу следует отнести решение следующих задач: і выбор прототипа аналогового фильтра и решение апроксимационной задачи; определение диапазона входных данных, оценка использования данного фильтра в конкретной аппаратуре; на основе решения предыдущих задач делается вывод о возможности использования модулярной цифровой фильтрации, форме его реализации, организации звеньев, способе реализации алгоритма фильтрации.
Второй этап подготовки организации вычисления модулярной фильтрации в СОК включает решение следующих задач: определение диапазона представления чисел в СОК; анализ исходных данных на предмет наличия в их составе отрицательных чисел; выбор способов представления числа в СОК и преобразования ПСС-СОК и обратно; выбор позиционной характеристики СОК и числа дополнительных модулярных каналов, используемых для обнаружения и коррекции ошибок; оценка обеспечиваемой точности вычислений и корректирующих возможностей СОК. На последнем этапе организации вычислений цифровыми модулярными фильтрами необходимо решить следующие задачи: выбор способа выполнения арифметических операций в модулярных каналах; синтез структуры модулярного канала цифровой фильтрации в СОК; оценка показателей качества цифрового фильтра в СОК и сравнение их с предъявляемыми требованиями и накладываемыми ограничениями.
Необходимо отметить, что в отдельных случаях в системах передачи информации требуется применение рекурсивных цифровых фильтров, которые могут быть эффективно реализованы с применением системы остаточных классов [183], а организация их функционирования будет включать решение практически тех же задач, что представлены выше с незначительными изменениями.
В работах [46, 47, 87-90] обосновывается, что наиболее эффективным подходом к реализации цифровых фильтров в СОК на ПЛИС является подход, суть которого заключается в создании специализированных по назначению устройств цифровой обработки сигналов в СОК. Такой подход обеспечивает наилучшее соотношение производительность/стоимость по сравнению с другими подходами [46].
