В книге систематически излагается теория кодов, исправляющих ошибки, и рассматривается их применение в системах связи и вычислительной технике. В последние годы интерес к вопросам использования кодовых методов защиты от ошибок значительно возрос в связи с развитием сетей передачи данных и особенно сетей с коммутацией пакетов. В книге рассматриваются важнейшие классы кодов: блоковые, сверточные и арифметические. Приводятся последние достижения теории кодирования. Подробно обсуждаются возможности использования кодов в практических системах. Книга полезна специалистам, работающим в области систем связи, вычислительной техники и автоматизированных систем управления, математикам и кибернетикам, интересующимся теорией кодирования, а также аспирантам и студентам соответствующих специальностей.
Author(s): К. Касами, Н. Токура, Е. Ивадари, Я. Инагаки
Publisher: Мир
Year: 1978
Language: Russian
Pages: 577
City: М.
Аннотация ......Page 4
Предисловие редакторов русского издания ......Page 6
Предисловие авторов ......Page 8
1.1. Коды, обнаруживающие и исправляющие ошибки ......Page 14
1.2. Блоковые коды. Систематические коды ......Page 22
1.3. Двоичный симметричный канал ......Page 27
1.4. Верхние границы для минимального расстояния кодов ......Page 29
1.4.1. Верхняя граница Хэмминга ......Page 31
1.4.2. Верхняя граница Плоткина ......Page 33
1.4.3. Верхняя граница Элайса ......Page 35
1.5. Теорема кодирования ......Page 39
1.5.1. Граница случайного кодирования ......Page 40
1.5.2. Свойства функции надежности ......Page 45
1.5.3. Граница сферической упаковки ......Page 51
1.5.4. Декодирование списком ......Page 53
2.1. Группы ......Page 55
2.2. Кольца и поля ......Page 70
2.3. Векторные пространства ......Page 79
2.4. Многочлены ......Page 83
2.5. Конечные поля ......Page 91
2.6.1. Вычисления в конечных полях ......Page 111
2.6.2. Матрицы Адамара ......Page 112
2.6.3. Конечные геометрии ......Page 116
2.6.4. Разностные множества ......Page 122
2.6.5. Дополняющий базис ......Page 123
Задачи ......Page 126
3.1. Линейные коды ......Page 129
3.2. Методы декодирования линейных кодов ......Page 135
3.3. Нижняя граница Варшамова — Гилберта ......Page 141
3.4. Распределение весов ......Page 143
3.5. Циклические коды (I) ......Page 149
3.6. Циклические коды (II) ......Page 156
3.7. Укороченные коды ......Page 162
4.1. Коды Боуза — Чоудхури — Хоквингема ......Page 164
4.2.1. Основные этапы ......Page 170
4.2.2. Итеративный алгоритм Берлекэмпа ......Page 175
4.3. Методы мажоритарного декодирования ......Page 179
4.4. Многочлены Матсона — Соломона ......Page 185
4.5.1. Обобщенные коды Рида — Маллера ......Page 189
4.5.2. Полиномиальные коды и двойственные к ним коды ......Page 196
4.6.1. Каскадные коды ......Page 201
4.6.2. Коды Юстесена ......Page 205
4.7.1. Определение ......Page 207
4.7.2. Метод декодирования ......Page 215
4.8. Коды, исправляющие пачки ошибок ......Page 219
5.1.1. Метод порогового декодирования ......Page 223
5.1.2. Методы последовательного декодирования ......Page 224
5.1.3. Методы декодирования по максимуму правдоподобия ......Page 226
5.2.1. Представление с помощью операторов задержки ......Page 227
5.2.2. Представление с помощью матриц ......Page 231
5.3. Пример порогового декодирования ......Page 237
5.4. Принцип порогового декодирования ......Page 240
5.5.1. Определение самоортогонального кода ......Page 243
5.5.2. Простой пример ......Page 245
5.5.3. Коды, строящиеся с помощью простых совершенных разностных множеств ......Page 249
5.5.5 Оптимальность кодов ......Page 252
5.6.1. Простейшие примеры ......Page 255
5.6.2. Способ построения кодов ......Page 256
5.6.4. Связь с блоковыми кодами ......Page 257
5.6.5. Сопоставление с циклическими кодами, построенными на основе разностных множеств ......Page 260
5.7. Распространение ошибок ......Page 261
5.7.1. Анализ глубины распространения ошибок ......Page 262
5.7.2. Критерий устойчивости пороговой декодирующей логической схемы ......Page 265
5.7.3. Критерий, основанный на использовании функции Ляпунова ......Page 267
5.8. Сверточные коды, исправляющие пачки ошибок ......Page 271
5.8.1. Методы чередования ......Page 272
5.8.2. Принцип построения кодов ......Page 274
5.8.3. Способ построения кодов ......Page 275
5.8.4. Конкретные коды ......Page 277
5.8.5. Оценки кодов и сравнение их параметров ......Page 278
5.9. Сверточные коды, исправляющие пачки ошибок и независимые ошибки (диффузные коды) ......Page 280
5.9.2. Корректирующая способность ......Page 281
5.9.3. Простой пример ......Page 282
5.9.4. Самоортогональные коды ......Page 283
5.10.1. Определение равномерного кода ......Page 285
5.10.2. Правило ортогонализации ......Page 286
5.10.3. Метод ортогонализации, обеспечивающий небольшую глубину распространения ошибок ......Page 289
5.10.4. Перфорированные равномерные коды ......Page 291
Задачи ......Page 294
6. Сверточные коды. II. Последовательное декодирование ......Page 299
6.1.1. Древовидные коды ......Page 300
6.1.2. Принцип последовательного декодирования ......Page 302
6.2.1. Цена пути ......Page 306
6.2.2. Поведение декодера ......Page 308
6.3.1. Среднее число операций ......Page 312
6.3.2. Свойство независимости в древовидном коде ......Page 316
6.3.3. Верхняя граница для среднего числа операций ......Page 318
6.4. Распределение числа операций и вероятность переполнения буфера ......Page 322
6.4.1. Структура и функционирование буфера ......Page 323
6.4.2. Нижняя граница для р[с ^ L] ......Page 324
6.4.3. Верхняя граница для р[с ^ L] ......Page 329
6.4.4. Связь с вероятностью переполнения буфера ......Page 330
6.5. Вероятность необнаружения ошибки ......Page 335
6.6. Границы Витерби и декодирование по максимуму правдоподобия ......Page 339
6.6.1. Верхняя граница для вероятности ошибки ......Page 340
6.6.2. Нижняя граница для вероятности ошибки ......Page 345
6.7.1. Системы гибридного кодирования ......Page 349
6.7.2. Характеристики гибридного кодирования ......Page 354
6.8. Стек-алгоритм ......Page 359
6.9. Структура расстояний сверточных кодов ......Page 363
6.9.1. Верхняя граница Плоткина при декодировании с обратной связью ......Page 364
6.9.2. Нижняя граница Гилберта для сверточных кодов при декодировании с обратной связью ......Page 368
6.9.3. Верхняя и нижняя границы минимального расстояния при дефинитном декодировании ......Page 371
6.10. Коды, используемые при декодировании с обратной связью ......Page 372
6.11. Коды, используемые при последовательном декодировании ......Page 377
Задачи и упражнения ......Page 380
7.1. Реализация кодов, исправляющих ошибки ......Page 384
7.1.1. Стандарные схемы ......Page 386
7.1.2. Кодеры циклических кодов ......Page 389
7.1.3. Декодеры циклических кодов ......Page 392
7.2.1. Кодеры ......Page 406
7.2.3. Схема преобразования параллельных слов в последовательные и обратная схема ......Page 411
7.2.4. Реализация сверточных кодов, исправляющих пачки ошибок ......Page 412
7.3. Обсуждение связи теории кодирования с реальными техническими проблемами ......Page 413
7.3.1. Задача теории кодирования ......Page 416
7.3.2. Стоимость и надежность ......Page 418
7.3.3. Применение в вычислительных системах ......Page 419
7.4. Различные предположения, используемые в теории кодирования ......Page 421
7.4.2. Методы принятия решений ......Page 422
7.4.3. Расстояние Хэмминга ......Page 425
7.4.4. Положительные стороны теории кодирования ......Page 426
7.5.1. Системы с полной обратной связью и системы с дублированием передачи ......Page 427
7.5.2. Обнаружение ошибок ......Page 428
7.6.1. Модуляция и кодирование ......Page 429
7.6.2. Вероятность ошибки при использовании алгебраических кодов ......Page 431
7.6.3. Многоуровневая фазовая модуляция и кодирование ......Page 433
7.6.4. Применения кодов в космических и спутниковых системах связи ......Page 438
7.6.5. Основные понятия о проектировании систем связи с помехоустойчивым кодированием ......Page 449
7.6.6. Проблемы, возникающие при проектировании систем связи с помехоустойчивым кодированием информации ......Page 451
7.6.7. Пример применения порогового декодирования в спутниковой связи ......Page 452
7.7. Применение в системах обработки информации ......Page 454
7.7.1. Применение кодов при общении человека с машиной ......Page 455
7.7.2. Коды на основе ортогональных латинских квадратов ......Page 458
7.7.3. Коды, исправляющие пачки ошибок и допускающие быстрое декодирование ......Page 462
Задачи ......Page 466
8. Коды для арифметических устройств ......Page 467
8.1.2. Наименьшее общее кратное и наибольший общий делитель ......Page 468
8.1.4. Функция Эйлера ......Page 469
8.1.5. Сравнимость и классы вычетов ......Page 470
8.1.7. Показатели экспоненты и примитивные корни ......Page 471
8.1.8. Мультипликативные группы и их разложение ......Page 474
8.1.9. Квадратичные вычеты и символ Лежандра ......Page 476
8.1.10. Круговые многочлены и их сомножители ......Page 477
8.1.11. Минимальное представление дроби ......Page 479
8.2. Определение AN-кода ......Page 480
Алгоритм нахождения представления, удовлетворяющего условию М ......Page 482
8.4. Минимальное расстояние и корректирующая способность AN-кода ......Page 490
8.5. Обнаружение и исправление независимых ошибок веса I ......Page 494
8.6. AN-коды, исправляющие кратные ошибки ......Page 500
8.7. Синдромы и методы декодирования AN-кодов ......Page 503
9.1.2. Кольцо целых чисел по модулю 2е— 1 и его идеалы ......Page 507
9.1.3. Задание циклических кодов ......Page 509
9.1.4. Разложение и структура циклических AN-кодов ......Page 510
9.2.1. Минимальное расстояние простых кодов ......Page 518
9.2.2. Минимальное расстояние ЛУУ-кодов, удовлетворяющих специальным условиям ......Page 522
9.2.3. Минимальное расстояние циклических AN-кодов (В —простое число) ......Page 525
9.2.4. Минимальное расстояние циклических AN-колов (В —составное число) ......Page 529
9.3.1. Вычеты по модулю А и конфигурации ошибок ......Page 532
9.3.2. Метод декодирования, основанный на циклических сдвигах вычетов ......Page 535
9.3.3. Метод декодирования, основанный на переборе ......Page 538
9.4. Дополнение ......Page 541
Приложение 1. Разложение чисел вида 2П — 1 на простые множители и таблица неприводимых многочленов ......Page 546
Приложение 2. Параметры двоичных БЧХ-кодов в узком смысле длины 1023 и менее ......Page 547
Литература ......Page 557
Предметный указатель ......Page 569
Оглавление ......Page 573
