ОГЛАВЛЕНИЕ
Предисловие
Гл. 1 Основные принципы кодирования и декодирования при передаче сообщений
§ 1.1 Блоковое и неблоковое кодирование
1.1.1 Блоковое кодирование
1.1.2 Неблоковое кодирование
§ 1.2 Математические модели каналов связи
§ 1.3 Основные принципы декодирования
1.3.1 Декодирование по максимуму правдоподобия (МП)
1.3.2 Декодирование по максимуму апостериорной вероятности (МАВ)
1.3.3 Декодирование по минимуму расстояния Хэмминга (МРХ)
1.3.4 Декодирование с помощью шаров Хемминга
§ 1.4 Объем шара Хэмминга
1.4.1 Асимптотика числа точек в шаре Хэмминга
§ 1.5 Способность кода обнаруживать и исправлять ошибки
§ 1.6 Границы для минимального расстояния
1.6.1 Граница Хемминга (граница плотной упаковки)
1.6.2 Асимптотическая форма границы плотной упаковки
1.6.3 Граница Варшамова-Гилберта
1.6.4 Асимтотическая форма границы Варшамова-Гилберта
1.6.5 Граница Бассалыго-Элайеса для двоичных кодов
Гл. 2 Линейные коды
§ 2.1 Линейные пространства
2.1.1 Линейные пространства над конечными полями
2.1.2 Линейные подпространства и ортогональные дополнения
2.1.3 Порождающая и проверочная матрицы линейного пространства
§ 2.2 Линейные коды
2.2.1 Определение и свойства линейных кодов
2.2.2 Построение линейных кодов с заданным минимальным расстоянием
2.2.2.1 Линейные коды с минимальным расстоянием d = 2
2.2.2.2 Линейные коды с минимальным расстоянием d = 3
2.2.2.3 Двоичные линейные коды с минимальным расстоянием d = 4
2.2.3 Коды, двойственные кодам Хемминга
2.2.4 Итеративные коды (коды-произведения)
§ 2.3 Синдромное декодирование линейных кодов
2.3.1. Алгоритм синдромного декодирования
2.3.2. Структурная схема синдромного декодера
§ 2.4 Вероятностные характеристики декодирования в каналах с независимыми ошибками
2.4.1 Вероятность ошибки декодирования
2.4.2 Распределение весов кодовых слов в линейных кодах
Гл. 3 Циклические коды
§ 3.1 Определение и свойства циклических кодов
3.1.1 Алгебраическое описание линейных циклических кодов
3.1.2 Порождающая и проверочная матрицы циклического кода
3.1.3 Прмеры нетривиальных циклических кодов
3.1.4 Циклические коды, исправляющие пакеты ошибок
§ 3.2 Многотактные линейные фильтры. Вычислители остатков
3.2.1 Алгебраическое описание многотактных линейных фильтров
3.2.2. Замечание о связи между вычислениями остатков и вычислениями в конечных полях
§ 3.3 Реализация операции кодирования для циклических кодов
§ 3.4 Синдромное декодирование циклических кодов
3.4.1 Алгоритм синдромного декодирования
3.4.2 Синдромный декодер двоичного циклического кода, исправляющего однократные ошибки и пакеты ошибок
3.4.3 Синдромный декодер укороченного циклического кода
3.4.4 Вычислительные затраты при синдромном декодировании циклических кодов
Гл. 4 Коды Боуза-Чоудхури-Хоквингхема (БЧХ-Коды)
§ 4.1 Алгебраическое декодирование циклических кодов
4.1.1 Алгебраическое декодирование циклических кодов с минимальным расстоянием 3
4.1.2 Алгебраическое декодирование циклических кодов с минимальным расстоянием 5
§ 4.2 Матрица Вандермонда
§ 4.3 Коды Боуза-Чоудхури-Хоквингхема
4.3.1 Определение БЧХ-кодов
4.3.2 Двоичные примитивные БЧХ-коды
4.3.3 Двоичные непримитивные циклические коды
4.3.4 Недвоичные БЧХ - коды, граница Синглтона и коды Рида-Соломона
§ 4.4 Декодирование БЧХ-кодов
4.4.1 Основное уравнение декодирования БЧХ кодов
4.4.2 Алгоритм декодирования Питерсона-Горенстейна –Цирлера
4.4.3 Исправление ошибок и стираний
4.4.4 Метод Форни вычисления величин ошибок и стираний
Гл. 5 Итеративное декодирование БЧХ-кодов
§ 5.1 Отыскание полинома локаторов ошибок
5.1.1 Ключевое уравнение
5.1.2 Решение ключевого уравнения с помощью алгоритма Евклида
5.1.3 Алгоритм Берлекэмпа-Месси
§ 5.2 Описание БЧХ-кодов в спектральной области
5.2.1 Преобразования Фурье в конечных полях
5.2.2 Спектральное описание БЧХ-кодов
§ 5.3 Декодирование в спектральной области
!Гл.6 Декодирование РС-кодов в каналах с мягким выходом
§ 6.1 Свойства кодов Рида-Соломона
6.1.1 Исправление пакетов ошибок
6.1.2 Спектр весов РС-кодов
6.1.3 Доля необнаруживаемых ошибок
!Гл.7 Низкоплотностные коды и «турбо»-декодирование
НЕ НАПИСАНО!
Приложение. ОСНОВЫ КОНЕЧНОЙ АЛГЕБРЫ И ТЕОРИИ
КОНЕЧНЫХ ПОЛЕЙ
§ П.1 Элементы теории чисел
П.1.1 Сравнения
П.1.2 Алгоритм Евклида
П.1.3 Китайская теорема об остатках
§ П.2 Элементы теории групп
П.2.1 Определения и примеры групп
П.2.2 Разложение группы по подгруппе
П.2.3 Циклические группы
§ П.3 Конечные поля
П.3.1 Определения, примеры полей
П.3.2 Алгебраические свойства конечных полей
П.3.3 Арифметические свойства конечных полей
§ П.4 Полиномы над конечными полями
П.4.1 Определения и основные свойства
П.4.2 Циклотомические классы
П.4.3 Структурное разложение двучлена 
П.4.4 Построение полиномов по заданным корням
§ П.5 Поля многочленов
П.5.1 Поле вычетов по модулю неприводимого полинома
П.5.2 Расширение полей
§ П.6 Вычисления в конечных полях
П.6.1 Комбинационные схемы умножения
П.6.1 Построение таблиц логарифмов и антилогарифмов
П.6.2 Логарифмы Цеха
§ П.7 Квадратичные расширения полей
П.7.1 Квадратичные расширения и формулы перехода
П.7.2 Вычисления в квадратичных расширениях
§ П.8 Следовые полиномы
П.8.1 Определение и свойства следовых полиномов
П.8.2 Факторизация двучлена 
с помощью следовых полиномов
§ П.9 Поиск корней полиномов
П.9.1 Табличный поиск корней полиномов второй степени
П.9.2 Табличный поиск корней полиномов третьей степени
П.9.3 Табличный поиск корней полиномов четвертой степени
НЕ ОКОНЧЕНО!
Задачи
З а д а ч и
9.1. Определите длину двоичного циклического кода, который порождается многочленом 
. Выпишите все слова этого кода и найдите минимальное расстояние.
9.2. Докажите, что порождающий полином любого двоичного циклического кода с четной длиной содержит квадраты.
9.3. Пусть 
- порождающий многочлен циклического кода над GF(q). Покажите, что 
. Покажите, что всякий многочлен вида 
, где с –ненулевой элемент GF(q), также обладает свойствами, указанными в теоремах 9.2 и 9.3.
9.4. Пусть С – двоичный код с порождающей матрицей
.
Покажите, что этот код – циклический. Найдите его порождающий многочлен и минимальное расстояние.
9.5. Пусть С – двоичный код с проверочной матрицей
.
(а) Покажите, что этот код – циклический. Найдите его порождающий многочлен и
минимальное расстояние.
(б) Покажите, что первые 3 строки этой матрицы задают 3 независимых уравнения (3
независимых проверки), выражающие первый кодовый символ в виде суммы остальных
символов. Покажите, что эти три уравнения позволяют правильно определить значение
первого символа при одиночных ошибках и сигнализировать о наличии двух ошибок,
если они произошли. Такое декодирование называется мажоритарным.
(в) Покажите, что любой из 7 кодовых символов этого кода допускает мажоритарное
декодирование при некотором выборе системы проверок.
(г) Покажите, что все кодовые символы могут быть мажоритарно продекодированы с
помощью одной и той же системы проверок.
9.6. Определите какой (какие) из следующих полиномов порождают циклический код длины 15 над GF(2):
9.7. Разработать вычислитель остатка от деления на полином 
. Убедиться, что построенный вычислитель правильно работает, подавая на его вход многочлен, для которого остаток был заранее вычислен. Исследовать полученный фильтр. Определить периодичность его состояний в автономном режиме. Показать, что имеются два различных цикла состояний одинаковой длины, показать также, что имеются два устойчивых состояния, переходящих сами в себя.
9.8. Разработать несистематический и систематический кодеры для кода с порождающим многочленом . Найти параметры кода. Описать работу ключей. Убедитесь, что этот код исправляет все пакеты ошибок длины 2, т. е. все комбинации одиночных ошибок и двойных ошибок, которые искажают пару стоящих рядом символов на длине 15. Постройте синдромный декодер, исправляющий пакетные ошибки.
9.9. В этой задаче будет построена граница Варшамова-Гилберта для укороченных двоичных циклических кодов, порождаемых неприводимыми многочленами. Заметим, что 
не порождает укороченный циклический (n,k)-код с расстоянием d, если найдется многочлен степени n-1 и веса 
, который делится на . Поэтому укороченный циклический (n,k)-код с расстоянием d существует, если количество неприводимых многочленов степени r=n-k больше количества всех неприводимых делителей степени r для всех многочленов степени n-1, вес которых меньше, чем d. Количество таких делителей можно оценивать сверху величиной 
. Выражение в фигурных скобках – это количество многочленов степени n-1 и меньше, вес которых не превышает d-1, а отношение n/r – это верхняя оценка числа неприводимых делителей степени r для каждого такого многочлена. Оценка для количества Ir неприводимых над полем GF(q) многочленов степени r получена в работах Э. Берлекэмпа и имеет следующий вид
.
При больших r это количество хорошо оценивается величиной 
.
(а) Покажите, что наибольшее значение k, для которого заведомо существует укороченный
циклический 
-код с расстоянием d это то, которое удовлетворяет неравенству
(б) Выведите отсюда, что при достаточно больших n и при 
имеет место граница Варшамова-Гилберта для скорости кода 
при данном относительном расстоянии 
.
Разд. 13.2
Рассмотрим двоичный циклический код длины 
с проверочной матрицей
,
где 
и имеет порядок 17, т. е. 
. Циклотомический класс, порождаемый 
, состоит из следующих элементов 
. Порождающий полином имеет 8-ю степень и набор корней, перечисленный в множестве I. Хотя конструктивное расстояние этого кода равно 3, минимальное расстояние равно 5 и этот код способен исправлять одиночные и двойные ошибки. Синдромные компоненты 
дают полную информацию о локаторах ошибок 
. Покажите, что 
и полином локаторов ошибок может быть вычислен по формуле 
. Опишите алгебраическую процедуру декодирования для этого кода.
