Курс раскрывает основные принципы и особенности системы остаточных классов рассмотрены способы перевода в позиционную систему и обобщенно-позиционную систему счислений. <...> Авторы-составители: д-р техн. наук, профессор Н. И. Червяков, канд. физ.-мат. наук, доцент П. А. Ляхов, канд. физ.-мат. наук, доцент Л. Б. Копыткова, ст. преподаватель А. В. Гладков Рецензенты: д-р техн. наук, профессор И. А. Калмыков, канд. техн. наук, доцент С. В. Аникуев («Ставропольский государственный аграрный университет») © ФГАОУ ВО «Северо-Кавказский федеральный университет», 2016 У че б н о е п о с о б и е 2 О б р а б о т к а инф о р м а ци и в си ст ем е о ст ат о ч н ы х к л ассо в СОДЕРЖАНИЕ Предисловие……………………………………………………… 6 1. <...> Введение знака в СОК с нечетными основаниями………. <...> Метод ортогональных базисов перевода ИЗ СОК в ПСС. <...> Методы цифровой фильтрации с использованием вейвлетов конечного поля………………………………………. <...> Применение модулярной арифметики в цифровой обработке изображений…………………………………………. <...> К числу задач освоения курса относятся: анализ и обобщение результатов научно-исследовательских работ в области модулярной арифметики с использованием современных достижений науки и техники, передового отечественного и зарубежного опыта; применение фундаментальных математических знаний и творческих навыков для быстрой адаптации к новым задачам, возникающим в процессе развития вычислительной техники и математических методов, к росту сложности математических алгоритмов и моделей; использование модулярного кодирования информации для решения теоретико-числовых задач, при нейросетевой обработке информации, в области цифровой обработки сигналов и в области защиты информации; умение применять <...>
Обработка_информации_в_системе_остаточных_классов_(СОК).pdf
УДК 004.942 (075.8)
ББК 22.19 я73
О 23
Печатается по решению
редакционно-издательского совета
Северо-Кавказского федерального
университета
О 23 Обработка информации в системе остаточных классов (СОК):
учебное пособие / авт.-сост.: Н. И. Червяков, П. А. Ляхов, Л. Б. Копыткова,
А. В. Гладков. – Ставрополь: Изд-во СКФУ, 2016. – 225 с.
Пособие представляет курс лекций и подготовлено в соответствии с
ФГОС ВО, одобрено на заседании кафедры прикладной математики и математического
моделирования 29 августа 2016 г. (протокол № 1). Курс раскрывает
основные принципы и особенности системы остаточных классов
рассмотрены способы перевода в позиционную систему и обобщенно-позиционную
систему счислений. Представляются способы расширения системы
оснований. Рассматриваются корректирующие особенности системы
остаточных классов, способы сравнения и представления комплексных
чисел. Разбираются возможности применения СОК для цифровой обработки
сигналов и методы обработки изображений.
Предназначено для студентов, обучающихся по направлению подготовки
01.04.01 – Математика (магистратура), а также может быть полезно
студентам направления «Прикладная математика и информатика» (магистратура)
при изучении дисциплины «Использование математических пакетов
для цифровой обработки сигналов».
Авторы-составители:
д-р техн. наук, профессор Н. И. Червяков,
канд. физ.-мат. наук, доцент П. А. Ляхов,
канд. физ.-мат. наук, доцент Л. Б. Копыткова,
ст. преподаватель А. В. Гладков
Рецензенты:
д-р техн. наук, профессор И. А. Калмыков,
канд. техн. наук, доцент С. В. Аникуев
(«Ставропольский государственный аграрный университет»)
© ФГАОУ ВО «Северо-Кавказский
федеральный университет», 2016
У че б н о е
п о с о б и е
2
Стр.2
О б р а б о т к а инф о р м а ци и
в си ст ем е о ст ат о ч н ы х к л ассо в
СОДЕРЖАНИЕ
Предисловие……………………………………………………… 6
1. ТЕОРЕТИКО-ЧИСЛОВОЕ ОБОСНОВАНИЕ
ПОСТРОЕНИЯ СИСТЕМЫ ОСТАТОЧНЫХ КЛАССОВ
(СОК) В ОБЛАСТИ ЦЕЛЫХ ЧИСЕЛ
1.1. Систематические числа……………………………………...
1.2. Обобщенно-позиционная система счисления……………..
1.3. Теоретико-числовые основы построения СОК. Китайская
теорема об остатках………………………………………………
1.4. Диапазоны представления чисел. Определение системы
остаточных классов. Выбор системы оснований СОК………...
1.5. Достоинства и недостатки СОК…………………………….
2. МОДУЛЬНЫЕ ОПЕРАЦИИ В СОК
2.1. Модульные операции в СОК……………………………….
2.2. Индексы и их применение для представления
информации в СОК………………………………………………
2.3. Введение знака в СОК при одном из оснований равном…
2.4. Правило сложения чисел разных знаков в СОК…………..
2.5. Правило умножения чисел разных знаков в СОК…………
2.6. Введение знака в СОК с нечетными основаниями………..
3. НЕМОДУЛЬНЫЕ ОПЕРАЦИИ В СОК. МЕТОДЫ
ПЕРЕВОДА ИЗ ПСС В СОК И ОБРАТНО
3.1. Определение вычета числа, как составная часть
операции перевода из ПСС в СОК……………………………...
3.2. Метод ортогональных базисов перевода ИЗ СОК в ПСС...
3.3. Перевод в ОПСС…………………………………………….
3.4. Интервальные методы перевода в ПСС……………………
4. РАСШИРЕНИЕ ДИАПАЗОНА
И ДЕЛЕНИЕ ЧИСЕЛ В СОК
4.1. Расширение системы оснований, опирающееся на ранг
и след числа……………………………………………………….
4.2. Расширение системы оснований с помощью
характеристик ОПС………………………………………………
3
К у р с ле к ц и й
8
13
15
22
28
32
34
39
41
44
47
56
61
64
74
85
90
Стр.3
4.3. Алгоритм деления чисел на основания СОК с помощью
перевода в ОПС…………………………………………………..
4.4. Алгоритм деления с помощью характеристик ранг
и след числа……………………………………………………….
4.5. Масштабирование чисел в СОК…………………………….
4.6. Общий случай деления……………………………………...
5. КОРРЕКТИРУЮЩИЕ СВОЙСТВА КОДОВ В СОК
5.1. Основные факты, характеризующие корректирующие
свойства кодов……………………………………………………
5.2. Корректирующие свойства кодов в СОК………………….
5.3. Корректирующие коды……………………………………...
5.4. Геометрическая модель избыточного кода в СОК………..
5.5. Обнаружение и локализация ошибок в СОК………………
6. СИСТЕМА ОСТАТОЧНЫХ КЛАССОВ
В КОМПЛЕКСНОЙ ОБЛАСТИ
6.1. Сравнение целых комплексных чисел……………………..
6.2. Фундаментальная теорема Гаусса…………………………
6.3. Построение СОК в комплексной области на основе
теоремы Гаусса…………………………………………………..
6.4. Отображение комплексного числа на пары
действительных чисел……………………………………………
6.5. Метод представления комплексных чисел В СОК,
опирающийся на их представление в виде матрицы…………..
7. ОСНОВЫ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ
(ЦОС). ПРИМЕНЕНИЕ СИСТЕМЫ ОСТАТОЧНЫХ
КЛАССОВ В ЦИФРОВОЙ ОБРАБОТКЕ СИГНАЛОВ
7.1. Аналоговые, дискретные и цифровые сигналы……………
7.2. Быстрые алгоритмы коротких сверток…………………….
7.2.1. Алгоритм перекрывания с суммированием……………...
7.2.2. Алгоритм перекрытия с накоплением……………………
7.2.3. Алгоритм Кука – Тоома…………………………………..
7.2.4. Алгоритм винограда вычисления коротких сверток……
7.3. Квантование чисел и сигналов……………………………..
7.4. Использование нейросетевых технологий в задачах
обработки сигналов………………………………………………
У че б н о е
п о с о б и е
97
113
114
117
123
126
128
133
140
144
146
151
157
160
166
168
168
170
171
171
173
174
4
Стр.4
О б р а б о т к а инф о р м а ци и
в си ст ем е о ст ат о ч н ы х к л ассо в
7.5. Приближение нейронной сети к СОК и алгоритмам
цифровой обработки сигналов………………………………….. 178
8. МЕТОДЫ ЦИФРОВОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ
В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ
8.1. Реализация алгоритмов вейвлет-анализа
в модулярном базисе……………………………………………..
8.2. Методы цифровой фильтрации с использованием
вейвлетов конечного поля……………………………………….
8.3. Применение модулярной арифметики в цифровой
обработке изображений………………………………………….
187
199
209
Литература……………………………………………………….. 223
5
К у р с ле к ц и й
Стр.5
ПРЕДИСЛОВИЕ
Учебное пособие (курс лекций) по дисциплине «Обработка информации
в системе остаточных классов (СОК)» подготовлено в соответствии
с Федеральным государственным образовательным стандартом
высшего образования.
Данная дисциплина имеет целью формирование профессиональных
компетенций (ПК-6) будущего магистра по направлению подготовки
01.04.01 – Математика.
К числу задач освоения курса относятся:
анализ и обобщение результатов научно-исследовательских работ
в области модулярной арифметики с использованием современных достижений
науки и техники, передового отечественного и зарубежного
опыта; применение фундаментальных математических знаний и творческих
навыков для быстрой адаптации к новым задачам, возникающим
в процессе развития вычислительной техники и математических
методов, к росту сложности математических алгоритмов и моделей; использование
модулярного кодирования информации для решения теоретико-числовых
задач, при нейросетевой обработке информации,
в области цифровой обработки сигналов и в области защиты информации;
умение применять полученные знания при изучении данной дисциплины
при написании магистерских диссертаций путем модификации
известных алгоритмов, улучшении их точностных и временных характеристик,
разработки математических моделей для исследования
отказоустойчивого функционирования модулярных нейрокомпьютеров,
использования теоретических основ модулярной нейроматематики
для решения прикладных задач в конечных кольцах и полях.
В ходе изучения дисциплины студенты получат навыки в использовании
системы остаточных классов для выполнения различных математических
операций. Кроме того, разбираются аспекты практического
применения системы остаточных классов для цифровой обработки
сигналов и обработки изображений.
Дисциплина «Обработка информации в системе остаточных классов
(СОК)» служит основой для следующих дисциплин: ««Модулярные
нейрокомпьютерные технологии», «Защита информации в распределенных
вычислительных сетях», «Применение системы остаточных
классов и вейвлет-анализа в цифровой обработке сигналов» а также
научно-исследовательской работы магистрантов и основой для выполУ
че б н о е
п о с о б и е
6
Стр.6
О б р а б о т к а инф о р м а ци и
в си ст ем е о ст ат о ч н ы х к л ассо в
нения выпускной квалификационной работы (магистерской диссертации),
предусмотренных учебным планом указанной магистерской программы.
Освоение
дисциплины позволит будущему магистру по направлению
подготовки «Математика» полноценно осуществлять свою профессиональную
деятельность, в частности, обладать следующими профессиональными
компетенциями:
– способность к собственному видению прикладного аспекта в
строгих математических формулировках (ПК-6).
7
К у р с ле к ц и й
Стр.7