Кларк Дж., мл., Кейн Дж.
Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. — М.: Радио и связь, 1987.— 392 с.: ил.— (Стат. теория связи).
В книге американских авторов впервые предпринята попытка проанализировать и обобщить результаты применения кодирования в системах связи. Описаны различные методы декодирования блоковых кодов и особенности реализации алгебраических декодеров в виде специализированных процессоров. Обсуждение сверточных кодов проиллюстрировано результатами численного моделирования. Даны конкретные рекомендации по использованию интегральных микросхем в устройствах кодирования.
Для инженерно-технических работников, связанных с разработкой и эксплуатацией систем цифровой связи.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Заметное расстояние отделяет сегодня уровень развития теории кодирования от практики ее применений. Теория ушла намного дальше того, что нашло использование. Традиционно теоретики объясняют это недостаточно высоким уровнем математических и теоретико-информационных знаний инженеров. Этр правда, но не вся. Дело в том, что в теории исследуются идеализированные модели каналов, при этом рассматриваются лишь два-три параметра, характеризующие кодовую систему, и не учитываются многие существенные технические, экономические и другие факторы. За пределами теоретического рассмотрения остаются вопросы выбора наилучших систем модуляции и демодуляции, синхронизации, ширины полосы частот, стоимости использования стандартных микросхем, расчета реальных вероятностей ошибок, возможности защиты от несанкционированного доступа и др. На практике решение именно этих вопросов оказывается определяющим для рекомендации применения кодов. Знание того, что данный код выбран из семейства с хорошим поведением кодового расстояния и линейно или алгебраически растущим с длиной кода усложнением кодирующих и декодирующих схем, является на самом деле не окончательным аргументом в пользу применения кода, а лишь начальным импульсом к исследованию такой возможности.
Предлагаемая советскому читателю книга американских разработчиков систем связи Кларка и Кейна направлена на то, чтобы сократить расстояние между теорией и практикой кодирования. Они пересматривают коды с позиции их применений. Это выполняется с помощью включения в рассмотрение модуляции, оценки эффективности кода показателем выигрыша по мощности, изучением поведения кодов в каналах с зависимыми ошибками и, наконец, обсуждением вопросов экономичного использования современных микросхем в кодирующих и декодирующих устройствах.
Для достижения поставленных целей авторы сознательно жертвуют математической строгостью изложения. При решении сложных вопросов упор делается на рассмотрение типичных примеров, разумный инженерный компромисс и накопленный опыт. Математически настроенному читателю следует принять это во внимание и при чтении сдерживать недовольство отходом от принятых в теории кодирования строгих канонов. Книга откроет читателю новые подходы и взгляды, которые не излагаются в других книгах по кодированию, но являются ключевыми для успеха применений.
Предисловие редактора перевода . Предисловие . • ' '
1. КОДИРОВАНИЕ. ОСНОВНЫЕ ПОНЯТИЯ
1.1. Основные принципы.......
1.2. Практические ограничения.........
.2.1. Источник данных..........
.2.2. Кодер.............
.2.3. Модулятор...........
.2.4. Физический канал.........
.2.5. Демодулятор или детектор.......
.2.6. Декодер............
1.2.7. Дискретный канал.........
1.3. Расчет характеристик...... ...
1.3.1. Точное вычисление вероятности ошибки
1.3.2. Аддитивная граница для вероятности ошибки .
1.3.3. Характеристики систем обнаружения ошибок .
1.3.4. Мягкое декодировоние........
1.3.5. Влияние квантования........
1.3.6. Повторение в некогерентных системах ....
1.3.7. Выигрыш от кодирования.......
1.4. Границы для кодов..........
1.4.1. Границы для кодового расстояния ....
1.4.2. Границы случайного кодирования.....
1.5. Замечания . ............
Задачи...............
2. ГРУППОВЫЕ КОДЫ . . . Коды с обобщенными проверками на четность .
2.1.1. Проверочная матрица.......
2.1.2. Исследовоние кодового расстояния
2.1.3. Коды Хемминга.........
2.1.4. Порождающая матрица.......
2.1.5. Дуальные коды.........
2.1.6. Синдром...........
2.1.7. Задача о взвешивании монет.....
2.1.8. Простой итеративный код......
2.2. Полиномиальные коды........
2.2.1. Арифметика конечных полей.....
2.2.2. Построение полиномиальных кодов
2.2.3. Циклические коды . •......
2.2.4. Другой метод кодирования циклических кодов
2.1.
5 6
9 15 16 16 18 19 19 22 23 25 26 30 31 33 37 41 41 43 44 46 51 52
53
54
56
57
58
60
61
62
63
65
66
67
71
75
76
387
2.2.5. Дополнительные свойства многочленов и элементов полей Галуа 78
2.2.6. Коды, задаваемые корнями........... 80
2.2.7. Синдромные многочлены........... 81
2.2.8. Модификации кодов............ 85
2.3. Важные классы групповых кодов.......... 87
2.3.1. Коды БЧХ............... 87
2.3.2. Коды Голея............... 89
2.3.3. Коды максимальной длины........... 90
2.3.4. Коды Рида—Маллера............ 91
2.3.5. Квадратично-вычетные коды.......... 93
2.3.6. Замечания............... 94
Задачи................... 94
3. ПРОСТЫЕ НЕАЛГЕБРАИЧЕСКИЕ МЕТОДЫ
ДЕКОДИРОВАНИЯ ГРУППОВЫХ КОДОВ 96
3.1. Декодеры Меггитта.............. 96
3.2. Перестановочное декодирование........... 101
3.2.1. Общий алгоритм декодировония......... 101
3.2.2. Перестановочное декодирование с помощью матрицы . . . 106
3.2.3. Заранее выбранные покрывающие множества . . . ... . 107
3.2.4. Метод случайного выбора........... 117
3.3. Пороговое декодирование............. 129
3.4. Замечания................. 134
Задачи................... 136
4. МЯГКОЕ ДЕКОДИРОВАНИЕ БЛОКОВЫХ
КОДОВ........... 137
4.1. Пороговое декодирование по апостериорной вероятности . . . . 140
4.1.1. Вывод правила декодирования АРР........ 141
4.1.2. Вычисление весов............. 142
4.1.3. Приближенное вычисление ш,-.......... 144
4.1.4. Реализация АРР-декодера........... 146
4.2. Оптимальное посимвольное декодирование........ 149
4.2.1. Вывод алгоритма Хартмана—-Рудольфа....... 150
4.2.2. Другая форма алгоритма Хартмана—Рудольфа..... 151
4.2.3. Пример................ 153
4.2.4. Приближение Гринбергера к алгоритму Хартмана—Рудольфа 155
4.3. Алгоритм Велдона............... 156
4.4. Алгоритм Чейза............... 160
4.4.1. Стандартные алгоритмы Чейза.......... 160
4.4.2. Варианты алгоритма Чейза........... 162
4.5. Алгоритмы перестановочного декодирования....... 165
4.5.1. Алгоритмы с использованием только информационных множеств 165
4.5.2. Алгоритмы типа алгоритма Омуры........ 168
4.5.3. Частичное синдромное декодирование........ 169
388
4.5.4. Некоторые предсказания о качестве декодирования . . . . 171
. . . . 172
5. АЛГЕБРАИЧЕСКИЕ МЕТОДЫ ИСПРАВЛЕ-
~.....--- . . . 173
радами
НИЯ КРАТНЫХ ОШИБОК
|5.1. Преобразования над конечным полем.........175
.5.2. Коды БЧХ ................177
5.3. Методы декодирования кодов БЧХ..........179
5.3.1. Декодирование в частотной области........180
5.3.2. Декодирование во временной области........182
5.4. Решение ключевого уравнения...........186
5.4.1. Алгоритм Евклида.............186
5.4.2. Алгоритм Берлекэмпа............191
5.5. Вопросы реализации..............197
5.6. Исправление ошибок и стираний........... 2021
5.7. Вычисление характеристик............ 206
5.8. Замечания................. 209
Задачи ..... ...... ........ 211
6. СТРУКТУРА СВЕРТОЧНЫХ КОДОВ И АЛГОРИТМ ДЕКОДИРОВАНИЯ ВИТЕРБИ . . 212
6.1. Двоичные сверточные коды со скоростью 1/2....... 213
6.2. Алгоритм декодирования Витерби.......... 216
6.3. Сверточные коды со скоростью т/я.......... 221
6.4. Описание сверточных кодов с помощью конечных автоматов и свойства расстояния............... 223
6.5. Характеристики сверточных кодов с алгоритмом декодирования Витерби.................. 227
6.5.1. Аддитивные границы............ 227
6.5.2. Оптимальные коды............. 230
6.5.3. Характеристики систем с когерентной ФМ...... 231
6.5.4. Характеристики систем с ортогональными сигналами и некогерентным приемом............. 233
6.6 Соображения о реализации............ 236
6.6.1. Синхронизатор.............. 237
6.6.2. Вычисление метрики ребер........... 239
6.6.3. Хранение и обновление метрик путей........ 241
6.6.4. Хранение и обновление гипотетических информационных последовательностей .............. 243
6.6.5. Выходное устройство............ 245
6.6.6. Квантование демодулятора и автоматическоя регулировка усиления ........,........ 246
6.7. Замечания . ................247
Задачи...................247
389
7. ДРУГИЕ МЕТОДЫ ДЕКОДИРОВАНИЯ ОБЕРТОЧНЫХ КОДОВ...... 248
7.1. Методы синдромного декодирования......... .,4;,
7.1.1. Основные понятия ............ 250
7.1.2. Декодирование с табличным поиском....... >>gy
7.1.3. Пороговое декодирование.......... .>gtj
7.2. Методы последовательного декодирования........ 279
7.2.1. Алгоритм Фано последовательного декодирования . . . 281
7.2.2. Выбор метрики последовательного декодирования .... 28 i
7.2.3. Выбор кода............... 28ц
7.2.4. Вычислительные сложности последовательного декодирования 28Л
7.2.5. Характеристики последовательных декодеров...... 2!) i
7.2.6. Вопросы реализации............ 29S
7.2.7. Стек-алгоритмы последовательного декодирования .... 3(н; Задачи................... ;ЮН
8. ПРИМЕНЕНИЯ......... .410
8.1. Каскадные коды............... .410
8.1.1. Основные принципы каскадного кодирования...... .410
8.1.2. Системы, использующие код Рида—Соломона и ортогональный
код.................. .412
8.1.3. Системы, использующие код Рида—Соломона и короткий блоковый код............... .414
8.1.4. Системы, использующие код Рида—Соломона и сверточный кол 317
8.2. Кодирование для канала с белым гауссовским шумом . . . . .419
8.3. Перемежение в системах с кодированием........ .42.i
8.3.1. Периодические устройства перемежения....... 324
8.3.2. Псевдослучайные устройства перемежения...... 32/
8.4. Кодирование для каналов с пакетами ошибок....... '^0
8.4.1. Процессы возникновения шумовых пакетов...... ЗЛ2
8.4.2. Характеристики сверточных кодов при наличии случайных стираний .................
8.4.3. Характеристики сверточных кодов при наличии периодических пакетов стираний.............
8.4.4. Ухудшение характеристик, вызываемое случайными пакетами стираний................ 3.59
8.4.5. Влияние перемежения............ 340
8.5. Кодирование для систем с расширенным спектром...... №3
8.5.1. Системы с псевдошумовым ФМ расширением...... 344
8.5.2. Системы с прыгающей частотой......... 3->2
8.6. Кодирование для каналов с ограниченной полосой ...... 35о
Задачи................... 366
Приложение А. Порождающие многочлены для кодов БЧХ .... Зсе
Приложение Б. Порождающие многочлены сверточных кодов .... 37-
Б.1. Декодирование Витерби............ 3/2
Б.2. Декодирование с табличным поиском ........ 375
390
. 375
Б.З. Пороговое декодирование......... yj-
Б4 Последовательное декодирование.........
.... 379
Список литературы.............. .384
Список работ, переведенных на русский язык...... ^ т
Дополнительный список литературы.........
385 Предметный указатель...........
Цена: 300руб.
