Теория кодирования

  

Касами, Токура, Ивадари. Теория кодирования. М.: Мир, 1978. - 576 с.

В книге систематически излагается теория кодов, исправляющих ошибки, и рассматривается их применение в системах связи и вычислительной технике. В последние годы интерес к вопросам использования кодовых методов защиты от ошибок значительно возрос в связи с развитием сетей передачи данных и особенно сетей с коммутацией пакетов. В книге рассматриваются важнейшие классы кодов: блоковые, сверточные и арифметические. Приводятся последние достижения теории кодирования. Подробно обсуждаются возможности использования кодов в практических системах.

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



Оглавление

Предисловие редакторов русского издания
1. Основные понятия теории кодирования
1.1. Коды, обнаруживающие и исправляющие ошибки
1.2. Блоковые коды. Систематические коды
1.3. Двоичный симметричный канал
1.4. Верхние границы для минимального расстояния кодов
1.4.1. Верхняя граница Хэмминга
1.4.2. Верхняя граница Плоткина
1.4.3. Верхняя граница Элайса
1.5. Теорема кодирования
1.5.1. Граница случайного кодирования
1.5.2. Свойства функции надежности
1.5.3. Граница сферической упаковки
1.5.4. Декодирование списком
2. Конечные поля
2.2. Кольца и поля
2.3. Векторные пространства
2.4. Многочлены
2.5. Конечные поля
2.6. Дополнительные сведения о конечных полях
2.6.1 Вычисления в конечных полях
2.6.2. Матрицы Адамара
2.6.3. Конечные геометрии
2.6.4. Разностные множества
2.6.5. Дополняющий базис
2.6.6. Некоторые понятия, необходимые для определения кодов Гоппы
3. Линейные и циклические коды
3.1. Линейные коды
3.2. Методы декодирования линейных кодов
3.3. Нижняя граница Варшамова — Гилберта
3.4. Распределение весов
3.5. Циклические коды (I)
3.6. Циклические коды (II)
3.7. Укороченные коды
4. Важнейшие коды
4.1. Коды Боуза — Чоудхури — Хоквингема
4.2. Декодирование БЧХ-кодов
4.2.2. Итеративный алгоритм Берлекэмпа
4.3. Методы мажоритарного декодирования
4.4. Многочлены Матсона — Соломона
4.5. Полиномиальные коды
4.5.1. Обобщенные коды Рида — Маллера
4.5.2. Полиномиальные коды и двойственные к ним коды
4.6. Каскадные коды и коды Юстесена
4.6.2. Коды Юстесена
4.7. Коды Гоппы
4.7.2. Метод декодирования
4.8. Коды, исправляющие пачки ошибок
5. Сверточные коды
5.1. Общий обзор сверточных кодов
5.1.2. Методы последовательного декодирования
5.1.3. Методы декодирования по максимуму правдоподобия
5.2. Представление сверточных кодов
5.3. Пример порогового декодирования
5.4. Принцип порогового декодирования
5.5. Самоортогональные коды
5.5.3. Коды, строящиеся с помощью простых совершенных разностных множеств
5.6. Ортогонализируемые коды
5.7. Распространение ошибок
5.7.2. Критерий устойчивости пороговой декодирующей логической схемы
5.7.3. Критерий, основанный на использовании функции Ляпунова [32]
5.7.4. Дефинитное декодирование
5.8. Сверточные коды, исправляющие пачки ошибок
5.9. Сверточные коды, исправляющие пачки ошибок и независимые ошибки (диффузные коды)
5.10. Равномерные сверточные коды
5.10.4. Перфорированные равномерные коды
6. Сверточные коды II. Последовательное декодирование
6.1. Древовидные коды и принцип последовательного декодирования
6.4. Коды, представляемые в виде кодового дерева, называются древовидными.
6.2. Алгоритм Фано
6.3. Среднее число операций при декодировании
6.3.2. Свойство независимости в древовидном коде
6.3.3. Верхняя граница для среднего числа операций
6.4. Распределение числа операций и вероятность переполнения буфера
6.5. Вероятность необнаружения ошибки
6.6. Границы Витерби и декодирование по максимуму правдоподобия
6.7. Гибридные методы кодирования
6.7.2. Характеристики гибридного кодирования
6.8. Стек-алгоритм
6.9. Структура расстояний сверточных кодов
6.9.2. Нижняя граница Гилберта для сверточных кодов при декодировании с обратной связью
6.9.3. Верхняя и нижняя границы минимального расстояния при дефинитном декодировании
6.10. Коды, используемые при декодировании с обратной связью
6.11. Коды, используемые при последовательном декодировании
7. Реализация и применение кодов, исправляющих ошибки
7.1.2. Кодеры циклических кодов
7.1.3. Декодеры циклических кодов
7.2. Реализация порогового декодирования
7.3. Обсуждение связи теории кодирования с реальными техническими проблемами
7.4. Различные предположения, используемые в теории кодирования
7.4.3. Расстояние Хэмминга
7.4.4. Положительные стороны теории кодирования
7.5. Применения в системах связи метода повторной передачи
7.6. Применения в системах связи кодов, исправляющих ошибки
7.6.2. Вероятность ошибки при использовании алгебраических кодов
7.6.3. Многоуровневая фазовая модуляция и кодирование
7.6.4. Применения кодов в космических и спутниковых системах связи
7.6.5. Основные понятия о проектировании систем связи с помехоустойчивым кодированием
7.6.6. Проблемы, возникающие при проектировании систем связи с помехоустойчивым кодированием информации
7.6.7. Пример применения порогового декодирования в спутниковой связи
7.7. Применение в системах обработки информации
7.7.2. Коды на основе ортогональных латинских квадратов
7.7.3. Коды, исправляющие пачки ошибок и допускающие быстрое декодирование [19]
8. Коды для арифметических устройств
8.1. Основные понятия теории чисел
8.2. Определение AN-кода
8.3. Арифметический вес и арифметическое расстояние
8.4. Минимальное расстояние и корректирующая способность AN-кода
8.5. Обнаружение и исправление независимых ошибок веса 1
8.6. AN-коды, исправляющие кратные ошибки
8.7. Синдромы и методы декодирования AN-кодов
9. Циклические AN-коды
9.1. Структура циклических AN-кодов
9.2. Минимальное расстояние циклических AN-кодов
9.2.2. Минимальное расстояние AN-кодов, удовлетворяющих специальным условиям
9.2.3. Минимальное расстояние циклических AN-кодов (В — простое число)
9.2.4. Минимальное расстояние циклических AN-кодов (В — составное число)
9.3. Декодирование циклических AN-кодов
9.4. Дополнение
Приложения
Приложение 1. Разложение чисел вида 2^n-1 на простые множители и таблица неприводимых многочленов
Приложение 2. Параметры двоичных БЧХ-кодов в узком смысле длины 1023 и менее
Литература