Элементы высшей алгебры и теории кодирования

Description

Учебное пособие содержит алгебраическую основу и ее применение в теории кодирования. Сначала приводятся основные сведения по таким ал- гебраическим структурам, как группы, кольца, кольца многочленов, кольца матриц, системы линейных алгебраических уравнений, векторные пространства, пространства линейных операторов, билинейные и квадратичные формы, поля, конечные поля. Далее излагаются базовые разделы алгебраической теории кодирования: линейные коды, циклические коды, коды Боуза — Чоудхури — Хоквингема, коды Рида — Соломона, обобщенные коды Рида — Соломона, альтернативные коды, коды Гоппы, кодовые криптосистемы Мак-Элиса и Нидеррайтера. Особое внимание уделено алгоритмам декодирования, которые математически обосновываются и сопровождаются численными примерами. Также рассматриваются оптимальные алфавитные коды. Книга ориентирована на преподавателей, аспирантов, студентов математических специальностей, студентов специальностей по информационной безопасности. Введение Глава 1. Бинарные отношения. Группы 1.1. Множества 1.2. Отображения 1.3. Бинарные отношения 1.3.1. Отношение эквивалентности 1.3.2. Отношение частичного порядка 1.4. Алгебраические операции 1.5. Группы 1.6. Подгруппы 1.7. Циклические группы 1.8. Смежные классы. Теорема Лагранжа 1.9. Нормальная подгруппа 1.10. Факторгруппа 1.11. Морфизмы групп Глава 2. Кольца 2.1. Кольца 2.2. Подкольца 2.3. Идеалы кольца 2.4. Факторкольцо 2.5. Кольцо классов вычетов 2.6. Морфизмы колец 2.7. Кольца главных идеалов 2.8. Китайская теорема об остатках Глава 3. Комплексные числа 3.1. Поле комплексных чисел 3.2. Тригонометрическая форма комплексного числа 3.3. Сопряженные комплексные числа 3.4. Возведение в степень и извлечение корня Глава 4. Кольца многочленов 4.1. Кольцо многочленов от одной переменной 4.2. Делимость. Алгоритм Евклида 4.3. Неприводимые многочлены 4.4. Корни многочлена 4.5. Производная многочлена. Формула Тейлора 4.6. Интерполяционный многочлен 4.7. Отделение кратных множителей 4.8. Существование корней в поле C 4.9. Многочлены с действительными коэффициентами 4.10. Многочлены с рациональными коэффициентами 4.11. Алгебра классов вычетов многочленов 4.12. Кольцо многочленов от нескольких переменных 4.13. Симметрические многочлены 4.14. Степенные суммы Глава 5. Кольца матриц и системы линейных уравнений 5.1. Матрицы и действия над ними 5.2. Элементарные преобразования матриц 5.3. Перестановки и подстановки 5.4. Определитель матрицы 5.5. Матрицы Вандермонда и Коши 5.6. Обратная матрица 5.7. Обращение матрицы Вандермонда 5.8. Матрицы перестановок 5.9. Системы линейных алгебраических уравнений 5.10. Системы линейных уравнений общего вида Глава 6. Векторные пространства 6.1. Векторные пространства и подпространства 6.2. Линейная зависимость 6.3. Ранг матрицы. База системы векторов 6.4. Базис и размерность 6.5. Линейная оболочка 6.6. Системы линейных однородных уравнений 6.7. Сумма и пересечение векторных пространств 6.8. Прямая сумма подпространств 6.9. Факторпространство 6.10. Способы описания подпространств векторного пространства 6.12. Ортогональные векторы евклидова пространства 6.13. Ортогональное дополнение 6.11. Евклидовы пространства Глава 7. Линейные операторы 7.1. Линейные операторы 7.2. Векторные пространства и алгебры линейных операторов 7.3. Инвариантные подпространства 7.4. Собственные векторы и собственные значения 7.5. Треугольная форма матрицы линейного оператора над полем C 7.6. Корневые подпространства линейного оператора 7.7. Жорданова нормальная форма матрицы 7.8. Минимальный многочлен линейного оператора 7.9. Приведение матрицы к жордановой нормальной форме и вычисление ее минимального многочлена 7.10. Циклические векторы линейных операторов Глава 8. Билинейные и квадратичные формы 8.1. Билинейные формы 8.2. Квадратичные формы 8.3. Квадратичные формы над полем R Глава 9. Поля 9.1. Поле. Подполе 9.2. Простые идеалы 9.3. Поле частных 9.4. Простые поля. Характеристика поля 9.5. Расширение полей 9.6. Классификация простых расширений поля 9.7. Поля разложения многочлена 9.8. Автоморфизм Фробениуса. Совершенные поля 9.9. Трансцендентные расширения полей Глава 10. Конечные поля 10.1. Конечные поля 10.2. Образующие элементы конечного поля 10.3. Неприводимые многочлены над конечными полями 10.4. Число неприводимых многочленов фиксированной степени 10.5. Корни неприводимых многочленов 10.6. Критерий неприводимости многочлена над конечным полем 10.7. Алгоритм Берлекэмпа разложения многочленов на неприводимые множители 10.8. Еще один метод построения неприводимых многочленов над конечным полем 10.9. Автоморфизмы поля над подполем 10.10. След элемента. Нормальный базис поля 10.11. Решение квадратных уравнений над 𝐺𝐹(2𝑚) Глава 11. Алфавитные коды 11.1. Однозначно декодируемые и префиксные коды 11.2. Необходимые и достаточные условия префиксных и однозначно декодируемых кодов 11.3. Оптимальные коды 11.4. Построение оптимальных кодов Глава 12. Линейные коды 12.1. Вводные замечания 12.2. Линейные коды 12.3. Связь кодового расстояния с возможностью обнаружения и исправления ошибок 12.4. Порождающая матрица кода 12.5. Двойственный код. Проверочная матрица кода 12.6. Каноническая форма порождающей и проверочной матриц кода 12.7. Границы объемов кодов 12.8. Код Хэмминга 12.9. Декодирование линейного кода 12.10. Поэтапное декодирование 12.11. Операции над кодами 12.12. Теорема Глаголева 12.13. Мажоритарное декодирование линейного кода 12.14. Коды Рида–Маллера 12.15. Границы для кодов, исправляющих и обнаруживающих пакеты ошибок Глава 13. Циклические коды 13.1. Циклический код как идеал 13.2. Порождающая матрица циклического кода 13.3. Проверочная матрица циклического кода 13.4. Каноническая форма порождающей и проверочной матриц циклического кода 13.5. Декодирование циклического кода 13.6. Порождающий многочлен с заданными свойствами 13.8. Циклический код Хэмминга 13.9. Циклические коды, исправляющие две ошибки 13.10. Циклические коды, исправляющие пакеты ошибок 13.11. Циклические коды CRC 13.12. Укороченные циклические коды Глава 14. Коды Боуза —Чоудхури — Хоквингема 14.1. Определение кода БЧХ 14.2. Граница БЧХ 14.3. Декодирование кодов БЧХ 14.4. Декодирование двоичных кодов БЧХ 14.5. Декодирования кодов БЧХ для случая произвольного поля 14.6. Ключевое уравнение. Метод Форни для нахождения значений ошибок Глава 15. Алгоритм Берлекэмпа — Месси 15.1. Алгоритм Берлекэмпа — Месси 15.2. Взаимосвязь алгоритма Берлекэмпа — Месси и обобщенного алгоритма Евклида 15.3. Декодирование кодов БЧХ с использованием алгоритма Берлекэмпа — Месси 15.4. Алгоритм Берлекэмпа — Месси в случае поля характеристики два 15.5. Декодирование двоичных кодов БЧХ с использованием алгоритма Берлекэмпа — Месси Глава 16. Коды МДР. Коды Рида — Соломона 16.1. Свойства кодов МДР 16.2. Коды Рида—Соломона 16.3. Кодирование кода Рида—Соломона 16.4. Удлинение кодов Рида—Соломона 16.5. Декодирование кодов Рида—Соломона 16.6. Декодирование на основе алгоритма Сугиямы 16.7. Алгоритм декодирования Гао для кодов Рида—Соломона 16.8. Декодирование кодов БЧХ на основе алгоритма Гао 16.9. Построение каскадных кодов на основе кодов Рида — Соломона Глава 17. Обобщенные коды Рида — Соломона 17.1. Обобщенные коды Рида — Соломона 17.2. Декодирование обобщенных кодов Рида — Соломона 17.2.1. Декодирование ОРС кодов на основе алгоритма Гао 17.2.2. Декодирование ОРС кодов на основе алгоритма Сугиямы 17.2.3. Декодирование ОРС кодов на основе алгоритма Питерсона — Горенстейна — Цирлера 17.2.4. Декодирование ОРС кодов на основе алгоритма Берлекэмпа — Месси 17.3. Декодирование кодов РС и ОРС кодов на случай ошибок и стираний 17.3.1. Декодирование на основе алгоритма Гао (первый вариант) 17.3.2. Декодирование на основе алгоритма Гао (второй вариант) 17.3.3. Декодирование на основе алгоритма Сугиямы 17.3.4. Декодирование на основе алгоритма Питерсона — Горенстейна — Цирлера 17.3.5. Декодирование на основе алгоритма Берлекэмпа — Месси Глава 18. Альтернативные коды. Коды Гоппы 18.1. Альтернативные коды 18.2. Коды Гоппы 18.3. Двоичные коды Гоппы 18.4. Алгоритм декодирования Паттерсона двоичных кодов Гоппы 18.5. Алгоритмы декодирования кодов Гоппы на основе алгоритмов для ОРС кодов 18.6. Кодовые криптосистемы 18.6.1. Криптосистема Мак-Элиса 18.6.2. Криптосистема Нидеррайтера 18.6.3. Современный вариант криптосистемы Мак-Элиса Предметный указатель Литература