И. А. Калмыков, Я. В. Емарлукова, Т. А. Гиш,
А. В. Дунин, А. В. Макарова, Д. В. Гостев
УДК 004.032.26.519.7
ББК 32.818
М 34
М 34 Математические модели и схемные решения отказоустойчивых
непозиционных вычислительных систем: коллективная монография
/ И. А. Калмыков, Я. В. Емарлукова, Т. А. Гиш, А. В. Дунин,
А. В. Макарова, Д. В. Гостев. – Ставрополь: Изд-во СКФУ, 2016. –
216 с.
ISBN 978-5-9296-0869-8
В монографии рассмотрены вопросы использования полиномиальной системы
классов вычетов (ПСКВ) расширенных полей Галуа для разработки математических
моделей отказоустойчивых вычислительных средств цифровой обработки сигналов.
Изложены основы применения методов системного анализа при построении высокоскоростных
спецпроцессоров с параллельно-конвейерной реализацией, функционирующих
в полиномиальной системе классов вычетов.. Рассмотрены методы и алгоритмы
построения. устойчивых к отказам спецпроцессоров ЦОС, способных сохранять
работоспособное состояние во время отказов за счет снижения в допустимых
пределах основных показателей качества функционирования, а также вопросы применения
нейроинформатики для реализации математических моделей отказоустойчивых
систем цифровой обработки сигналов.
Адресована научным работникам, аспирантам, специализирующимся в области
построения корректирующих кодов и цифровой обработки сигналов; может быть
использована студентами, обучающимися по специальностям «Инфокоммуникационные
технологии и системы связи», «Информационные системы и технологии»,
«Информационная безопасность».
Авторы:
д-р техн. наук, профессор И. А. Калмыков,
ст. преподаватель Я. В. Емарлукова,
ассистент Т. А. Гиш,
аспиранты А. В. Дунин, А. В. Макарова,
ассистент Д. В. Гостев
Рецензенты:
д-р техн. наук, профессор О.А. Финько
(Краснодарское высшее военное училище им. С.М. Штеменко),
д-р техн. наук, профессор В.В. Копытов (ООО «Инфоком-С»)
© Коллектив авторов, 2016
ISBN 978-5-9296-0869-8
© ФГАОУ ВО «Северо-Кавказский
федеральный университет», 2016
2
Стр.2
Математические модели и схемные решения
отказоустойчивых непозиционных вычислительных систем
ВВЕДЕНИЕ
Цифровая обработка сигналов (ЦОС) относится к числу
наиболее динамически развивающихся областей инженерной деятельности.
Медицина, системы сотовой связи, телекоммуникации,
Internet-технологии, обработка звука и изображений, навигация –
вот далеко неполный перечень приложений, в которых активно
используются методы ЦОС.
Поиск новых путей повышения эффективности применения
задач ЦОС привели к активизации работ по разработке математических
моделей систем цифровой обработки сигналов, обладающих
свойством кольца или поля, и их реализации в нейросетевом
базисе. Обладая параллельной структурой, которая является
наиболее приспособленной для цифровой обработки сигналов,
нейросетевые спецпроцессоры (СП) ЦОС позволяют создавать
эффективные системы обработки сигналов в реальном масштабе
времени.
В то же самое время аппаратная реализация нейросетевых
процессоров ЦОС насыщена и сложна. Поэтому отказы в таких
нейронных сетях (НС) практически неизбежны, и обеспечение отказоустойчивости
должно быть неотъемлемой частью разработки
НС, особенно для применений в реальном масштабе времени.
Проблема обеспечения надежного функционирования сложных
вычислительных систем приобретает в настоящее время первостепенное
значение. Это объясняется увеличением сложности
аппаратной реализации нейросетевых процессоров, расширением
сферы их применения и важностью решаемых с их помощью задач.
Кроме того, расширяются области применения СП ЦОС,
в которых техническое обслуживание затруднено либо совсем исключено,
и поэтому обеспечение их правильного функционирования
при наличии неисправностей является главным и обязательным
требованием.
Одним из эффективных и перспективных путей достижения
высоких показателей отказоустойчивости нейросетевых СП ЦОС
является их построение на базе использования избыточности и
корректирующих способностей алгебраической системы, которая
3
Стр.3
И. А. Калмыков, Я. В. Емарлукова, Т. А. Гиш,
А. В. Дунин, А. В. Макарова, Д. В. Гостев
положена в основу математической модели цифровая обработки
сигнала. Применение полиномиальной системы классов вычетов
(ПСКВ) позволяет не только повысить скорость обработки данных,
но и обеспечить требуемый уровень надежности функционирования
нейросетевого вычислительного устройства цифровой
обработки сигналов.
В первой главе рассмотрены основные требования, предъявляемые
к ЦОС в различных областях применения. Показано, что
выбор метода ЦОС и его схемотехническая реализация являются
сложной задачей, эффективность решения которой зависит от
множества факторов. Предложено использование методологического
аппарата системного анализа для решения данной задачи.
Осуществлен системный анализ типовой системы цифровой обработки
сигналов. Разработана модель такой системы. Показана
необходимость повышения эффективность работы подсистемы
первичной обработки сигналов. Осуществлен выбор критериев
качества и постановка задачи исследования.
Во второй главе на основе исследований основных методов
системного проектирования осуществляется постановка задачи
системного анализа для разработки высокоскоростного устройства
первичной обработки сигнала. В качестве основного метода системного
анализа выбрана декомпозиция. Определены основные
модели, используемые в задаче системного анализа, осуществлено
математическое описание последних. Проведены исследования
параллельно-конвейерных вычислений в задачах ЦОС. Представлена
математическая модель ортогональных преобразований сигналов,
реализуемых в ПСКВ. Осуществлена разработка математической
модели систолической организации цифровой обработки
сигналов в полиномиальной системе классов вычетов. Определены
основные показатели качества функционирования систолического
вычислительного устройства.
В третьей главе рассматриваются вопросы применения
нейросетевого базиса для повышения скорости реализации ортогональных
преобразований сигналов в кольце полиномов. Рассмотрены
основные нейросетевые алгоритмы базовых операций –
суммирования по модулю два и умножения по модулю. Определены
схемные и временные затраты необходимые на построение
4
Стр.4
Математические модели и схемные решения
отказоустойчивых непозиционных вычислительных систем
многовходовых сумматоров по модулю два. На основе проведенных
исследований были выбраны основные алгоритмы выполнения
основных немодульных операций, которые характеризуются
минимальными временными затратами. Показаны схемные решения
для осуществления прямого преобразования из позиционного
кода в непозиционный код. Также разработаны нейросетевые реализации
для блока, осуществляющего обратное преобразование из
кода ПСКВ в модулярный код.
В четвертой главе рассмотрена разработаная методика построения
высокоскоростных спецпроцессоров первичной ЦОС.
Показана реализация данной методики. Произведена разработка
нейросетевых устройств, реализующих модульные и немодульные
операции. Показано, что применение системного анализа позволило
разработать структуру нейросетевого систолического спецпроцессора
первичной цифровой обработки сигналов, функционирующего
в полиномиальной системе классов и характеризующегося
минимальными временными затратами на выполнение ортогональных
преобразований.
В пятой главе рассмотрены алгоритмы реализация крупномасштабного
анализа в конечном поле Галуа. Показана возможность
выполнения дискретного вейвлет-преобразования Хаара в
конечном поле Галуа. Рассмотрена реализация ДВП Хаара в поле
GF (17). Представлена схемная реализация разработанного алгоритма
выполнения дискретного вейвлет-преобразования в конечном
поле. Проведен анализ основных методов обеспечения отказоустойчивости
для устройств цифровой обработки сигналов. Рассмотрены
вопросы использования структурной и временной избыточности.
Показана целесообразность использования корректирующих
арифметических кодов для обнаружения и коррекции ошибок.
Представлены разработанные алгоритмы поиска и исправления
ошибок в модулярных избыточных кодах путем параллельной
нулевизации кода, а также на основе вычисления старших коэффициентов
обобщенной полиадической системы. Рассмотрен алгоритм,
позволяющий корректировать ошибки при минимальной
избыточности кода ПСКВ.
В заключении обобщены итоги и результаты проведенных исследований.
5
Стр.5
И. А. Калмыков, Я. В. Емарлукова, Т. А. Гиш,
А. В. Дунин, А. В. Макарова, Д. В. Гостев
В приложениях приведены программные реализации выполнения
крупномасштабного анализа в конечных полях.
В большинстве глав приводятся примеры, предназначенные
для самостоятельной проработки материала. Основная часть их
иллюстрирует приведенный материал и не вызывает затруднений
при решении. Возможно, что решение таких упражнений обусловят
ряд задач, которые могут послужить читателю основой для
научных исследований.
6
Стр.6
И. А. Калмыков, Я. В. Емарлукова, Т. А. Гиш,
А. В. Дунин, А. В. Макарова, Д. В. Гостев
СОДЕРЖАНИЕ
Введение……………………………………………………….. 3
1. СИСТЕМНЫЙ АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ.
ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЙ
1.1. Цифровая обработка сигналов. Требования,
предъявляемые к цифровой обработке сигналов…………….
1.2. Базовые модели и методы системного анализа………….
1.3. Системный анализ типовой системы цифровой
обработки сигналов…………………………………………….
1.4. Постановка задачи исследования…………………………
Выводы………………………………………………………….
2. СИСТЕМНЫЙ АНАЛИЗ ПЕРВИЧНОЙ ОБРАБОТКИ
СИГНАЛОВ ДЛЯ СИСТЕМ ПЕРЕДАЧИ
И ОБРАБОТКИ ИНФОРМАЦИИ
2.1. Постановка задачи системного анализа цифровой
обработки сигналов…………………………………………….
2.2. Разработка математической модели цифровой
обработки сигнала с параллельно-конвейерной
организацией вычислительного процесса…………………….
2.3. Разработка математической модели систолической
организации цифровой обработки сигналов в ПСКВ………..
Выводы………………………………………………………….
3. РАЗРАБОТКА СТРУКТУРНЫХ РЕШЕНИЙ
ДЛЯ ПОСТРОЕНИЯ ВЫСОКОСКОРОСТНОГО
СПЕЦПРОЦЕССОРА ЦОС
3.1 Применение нейросетевого логического базиса
для реализации модульных операций…………………………
3.2. Реализация немодульных операций в нейросетевом
логическом базисе……………………………………………...
Выводы………………………………………………………….
214
7
17
25
30
32
34
42
54
76
77
89
103
Стр.214
Математические модели и схемные решения
отказоустойчивых непозиционных вычислительных систем
4. РЕШЕНИЕ ЗАДАЧИ СИСТЕМНОГО АНАЛИЗА
И РАЗРАБОТКА СИСТОЛИЧЕСКОГО
СПЕЦПРОЦЕССОРА ЦОС, ФУНКЦИОНИРУЮЩЕГО
В КОЛЬЦЕ ПОЛИНОМОВ
4.1. Методика разработки высокоскоростного
спецпроцессора цифровой обработки сигналов……………...
4.2. Решение задачи системного анализа при разработке
структуры высокоскоростного спецпроцессора ЦОС……….
Выводы………………………………………………………….
5. ПРИМЕНЕНИЕ МОДУЛЯРНОЙ АРИФМЕТИКИ
В ДИСКРЕТНЫХ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯХ
5.1. Математические основы вейвлет-преобразования………
5.2. Вычисление дискретного вейвлет преобразования
Хаара в конечном поле Галуа………………………………….
5.3. Схемная реализация дискретного вейвлет
преобразования Хаара в конечном поле………………………
5.4. Алгоритмы и методы обеспечения устойчивости
к отказам на основе модулярных кодов………………………
Выводы………………………………………………………….
105
108
131
133
143
151
158
180
Заключение……………………………………………………... 181
Литература……………………………………………………… 185
Приложение…………………………………………………….. 201
215
Стр.215