Оригинално заглавие:

PRINCIPLES OF DIGITAL COMMUNICATION AND CODING
Andrew J. Viterbi
IINK ABIT Corporation
Jim K. Omura
University of California, Los Angeles
McGraw-Hill Book Company

*

Аннотация

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

*

Переводчики:

Александр Юрьевич Шевердяев, Александр Васильевич Кузнецов, Валерий Николаевич Кошелев

*

Оглавление

Предисловие редактора перевода . 5
Предисловие к русскому изданию 6
Предисловие 7

Часть I. Основы цифровой связи и блочного кодирования . . 10

Глава 1. Цифровые системы связи: фундаментальные концепции и параметры 10
1.1. Источники, энтропия и теорема кодирования без шума .... 14
1.2. Взаимная информация и пропускная способность канала .... 26
1.3. Обращение теоремы кодирования 35
1.4. Библиографические замечания и ссылки 41
Приложение 1А. Выпуклые функции 41
Приложение 1Б. Неравенство Иенсена для выпуклых функций ... 45
Задачи 47

Глава 2. Модели каналов и блочное кодирование . 51
2.1. Цифровая связь по каналу с аддитивным гауссовским шумом при блочном кодировании 51
2.2. Минимальная вероятность ошибки и декодер максимального правдоподобия 56
2.3. Вероятность ошибки и простая верхняя граница
2.4. Более точная граница для вероятности ошибки 66
2.5. Ортогональные сигналы с равной энергией в АБГШ канале ... 67
2.6. Ограничения на ширину полосы частот, межсимвольная интерференция и неопределенность при отслеживании 71
2.7. Ограничения на входе канала .77
2.8. Квантование выхода канала: дискретные каналы без памяти ... 79
2.9. Линейные коды 83
2.10. Систематические линейные коды и оптимальное декодирование в ДСК 91
2.11. Примеры характеристик линейных блочных кодов в АБГШ канале и в каналах, к которым он сводится квантованием 97
2.12. Другие каналы без памяти 101
2.13. Библиографические замечания и ссылки 115
Приложение 2А. Ортогонализация Грама—Шмидта и представление сигналов 116
Задачи 118

Глава 3. Анализ характеристик ансамбля блочных кодов .... 125
3.1. Средняя по ансамблю кодов вероятность ошибки: верхняя граница 125
3.2. Теорема кодирования для каналов и свойства показателя экспоненты вероятности ошибки в каналах без памяти 131
3.3. Средняя вероятность ошибки по ансамблю с выбрасыванием: верхняя граница при малых скоростях 141
3.4. Примеры. Двоичные по входу и симметричные по выходу каналы и каналы с очень большим шумом 149
3.5. Граница Чернова и лемма Неймана—Пирсона . 155
3.6. Нижняя граница сферической упаковки 162
3.7. Нижние границы при нулевой скорости 170
3.8. Нижние границы при малых скоростях 175
3.9. Гипотезы и обращения 179
3.10. Границы для ансамблей линейных кодов 183
3.11. Библиографические замечания и ссылки . ' 187
Приложение ЗА. Полезные неравенства и доказательства леммы 3.2.1 и теоремы 3.3.2 188
Приложение ЗБ. Условия Куна—Таккера и доказательства теорем 3.2.2 и 3.2.3
Приложение ЗВ. Алгоритм вычисления пропускной способности ... 198
Задачи 203

Часть II. Сверточное кодирование и цифровая связь 217

Глава 4. Сверточные коды 217
4.1. Введение. Структура кодов 217
4.2. Декодер максимального правдоподобия для сверточных кодов — алгоритм Витерби 225
4.3. Дистанционные свойства сверточных кодов для каналов с двоичным входом 230
4.4. Оценки характеристик конкретных сверточных кодов в каналах без памяти с двоичным входом и симметричным выходом 234
4.5. Некоторые случаи и примеры 238
4.6. Структура кодов со скоростью Ортогональные сверточные коды 244
4.7. Усечение указателей путей, квантование метрики и кодовая синхронизация в декодере Витерби 250
4.8. Декодирование с обратной связью 254
4.9. Каналы с межсимвольной интерференцией 266
4.10. Кодирование для каналов с межсимвольной интерференцией . . 275
4.11. Библиографические замечания и ссылки 277
Задачи 278

Глава 5. Характеристики ансамбля сверточных кодов 290
5.1. Теорема кодирования для канала меняющихся во времени сверточных кодов 290
5.2. Примеры: показатели экспоненты сверточного кодирования для каналов с большим шумом 302
5.3. Верхняя граница с выбрасыванием для симметричного по выходу канала с двоичным входом 304
5.4. Нижняя граница для вероятности ошибки 308
5.5. Критическая глубина распространения ошибочных событий . . . 311
5.6. Усечение указателей пути и ошибки начальной синхронизации . . 314
5.7. Границы вероятностей ошибок для систематических сверточных кодов 316
5.8. Изменяющиеся во времени сверточные коды в каналах с межсимвольной интерференцией 319
5.9. Библиографические замечания и ссылки 327
Задачи 328

Глава 6. Последовательное декодирование сверточных кодов . . . 333
6.1. Основные понятия и базовый стек-алгоритм 333
6.2. Распределение числа вычислений: верхняя граница 339
6.3. Верхняя граница вероятности ошибки 345
6.4. Распределение числа вычислений: нижняя граница 350
6.5. Алгоритм Фано и другие последовательные алгоритмы декодирования 354
6.6. Вопросы сложности, переполнения буфера и устройства других систем 359
6.7. Библиографические замечания и ссылки 364
Задачи 365

Часть III. Кодирование источников для цифровой связи .... 368

Глава 7. Теория передачи с погрешностью: основные концепции для источников без памяти 368
7.1. Задача кодирования источников 368
7.2. Дискретные источники без памяти. Блочные коды 372
7.3. Связь с кодированием для каналов 385
7.4. Дискретные источники без памяти. Решетчатые коды 393
7.5. Непрерывные по амплитуде источники без памяти 405
7.6. Вычисление Р(Д). Дискретные источники без памяти .... 413
7.7. Вычисление Р(Д). Непрерывные по амплитуде источники без памяти 425
7.8. Библиографические замечания и ссылки 432
Приложение 7А. Вычислительный алгоритм для Я(О) 432
Задачи 437

Глава 8. Теория передачи с погрешностью: источники с памятью, гауссовские источники и универсальное кодирование 444
8.1. Векторные источники без памяти 444
8.2. Источники с памятью 455
8.3. Границы для Я(й) 471
8.4. Гауссовские источники с квадратично-разностной погрешностью . . 475
8.5. Симметричные источники с балансной мерой погрешности и последовательности с фиксированной композицией 492
8.6. Универсальное кодирование 505
8.7. Библиографические замечания и ссылки 513
Приложение 8А. Границы Чернова для распределений погрешности . . 514
Задачи 519

Список литературы 524
Предметный указатель 529