Алгебраическая теория кодирования

Научная библиотека

Научная библиотека

Алгебраическая теория кодирования

Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971, пер. с англ.

Книга освещает основные вопросы общей теории линейных кодов, исследования циклических (двоичных и недвоичных) кодов для метрик Хэмминга и Ли, вычисление параметров оптимальных кодов, а также вопросы построения кодирующих и декодирующих устройств.

Оглавление

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Глава 1. Основные двоичные коды
1.1. Коды с повторением и коды с одной проверкой на четность
1.2. Линейные коды
1.3. Коды Хэмминга
1.4. Конструктивное введение в теорию БЧХ-кодов, исправляющих двойные ошибки
Глава 2. Арифметические операции по модулю неприводимого двоичного многочлена
2.1. Более подробно об алгоритме Евклида
2.2. Логические цепи
2.3. Мультипликативное обращение
2.4. Умножение
2.5. Решение систем линейных уравнений
2.6. Специальныё метод решения систем уравнениё, матрицы которых состоят почти сплошь из нулей
Глава 3. Число неприводимых q-ичных многочленов заданной степени
3.2. Производящие функции
3.3. Число неприводимых нормированных q-ичных многочленов заданной степени
3.4. Формула обращения Мёбиуса
Глава 4. Структура конечных полей
4.2. Мультипликативная структура конечных полей
4.3. Круговые многочлены
4.4. Алгебраическая структура конечных полей
4.5. Примеры
4.6. Алгебраическое замыкание
4.7. Определение минимальных многочленов
Глава 5. Двоичные циклические коды
5.2. Переупорядочение столбцов проверочной матрицы двоичных БЧХ-кодов, исправляющих двойные ошибки
5.3. Общие свойства циклических кодов
5.4. Процедура Ченя
5.5. Описание общей схемы декодера для произвольного циклического двоичного кода
5.6. Пример
5.7. Пример
5.8. Эквивалентность определений циклических кодов при помощи различных примитивных корней n-степени из единицы
Глава 6. Разложение многочленов над конечными полями
6.2. Определение периода многочлена
6.3. Трехчлены над GF(2)
6.4. Полное разложение многочлена x^n-1
6.5. Определение степеней неприводимых делителей круговых многочленов
6.6. Четно или нечетно число неприводимых делителей f(x) над GF(q)?
6.7. Квадратичный закон взаимности
Глава 7. Двоичные БЧХ-коды, исправляющие многократные ошибки
7.2. Ключевое уравнение для декодирования двоичных БЧХ-кодов
7.3. Эвристическое решение ключевого уравнения
7.4. Алгоритм решения ключевого уравнения над произвольным полем
7.5. Связь с матричными методами декодирования
7.6. Упрощение алгоритма 7.4 для двоичных БЧХ-кодов
7.7. Реализация декодеров для двоичных БЧХ-кодов
Глава 8. Недвоичное кодирование
8.2. Весовые функции
Глава 9. Негациклические коды для метрики Ли
9.2. Коды, исправляющие две ошибки
9.3. Негациклические коды
Глава 10. Недвоичное обобщение Горенстейна-Цирлера БЧХ-кодов в случае метрики Хэмминга
10.2. Примеры
10.3. БЧХ-коды общего типа и 1-удлиненные БЧХ-коды
10.4. Совместное декодирование стираний и ошибок
10.5. Декодирование более чем t ошибок
10.6. Примеры
Глава 11. Линеаризированные многочлены и аффинные многочлены
11.2. Наименьшее аффинное кратное
11.3. Общие свойства линеаризированных и аффинных многочленов
11.4. Преобразования функции f(z)
11.5. Подсчет корней
11.6. Кодовые слова с малым весом в некоторых кодах
Глава 12. Нахождение числа информационных символов в БЧХ-кодах
12.2. Сведение задачи для случая примитивных БЧХ-кодов к перечислению некоторых q-ичных последовательностей
12.3. Теоремы о числе последовательностей
12.4. Примеры
12.5. Определение числа информационных символов в непримитивных БЧХ-кодах
12.6. Асимптотические результаты
12.7. Истинные расстояния
Глава 13. Скорость передачи информации для оптимальных кодов
13.1. Граница сферической упаковки Хэминга — Рао для больших скоростей
13.2. Совершенные коды
13.3. Границы d <= n+1-k
13.4. Граница Плоткина для малых скоростей (граница среднего расстояния)
13.5. Эквидистантные коды
13.6. Граница Элайеса
13.7. Граница Гилберта
13.8. Асимптотические границы для вероятности ошибки и конечные частные случаи
Глава 14. Коды, полученные путем модификации и сочетания других кодов
14.2. 1-укорочение кода (выбрасывание проверочных символов)
14.3. Присоединение дополнительных кодовых слов
14.4. Выбрасывание кодовых слов
14.5. 2-удлинение кодов (добавление информационных символов)
14.6. 2-укорочение кода (вычеркивание информационных символов)
14.7. Подкоды над подполями
14.8. Прямое произведение кодов и его свойства
14.9. Каскадные коды
Глава 15. Другие основные методы кодирования и декодирования
15.1. Коды Сривэставы — нециклические коды с алгебраическим алгоритмом декодирования
15.2. Вычетные коды — хорошие коды с трудным декодированием
15.3. Коды Рида — Маллера — слабые коды с легким декодированием
15.4. Пороговое декодирование — лучший из известных алгоритмов декодирования некоторых кодов
15.5. Ортогонализируемые коды, основанные на конечных геометриях
15.6. Сверточные коды — обзор
Глава 16. Нумераторы весов
16.1. Соотношения между нумераторами весов и вероятностью отказа от декодирования
16.2. Уравнения Мак-Вильямс – Плесс для нумераторов весов дуальных кодов
16.3. Ограничения весов
16.4. Нумераторы весов Казами для некоторых подкодов РМ-кода второго порядка
16.5. Нумераторы весов для кодов Рида — Соломона
ЛИТЕРАТУРА