Р.Галлагер
ТЕОРИЯ ИНФОРМАЦИИ И НАДЕЖНАЯ СВЯЗЬ
М.: «Советское радио», 1974, 720 с.

В книге собраны, подытожены и заново переосмыслены все основные
результаты теории информации. Конструкция наиболее перспективных для
практического использования кодов, разнообразные методы декодирования,
выражения для вероятностей ошибки, пропускная способность реальных каналов
связи, методы сокращения избыточности — все это и многое другое изложено с
самых современных позиций. Предлагаемые читателю результаты (вместе с
изящными и полными их доказательствами) сведены в книге в единую систему.
Математические рассуждения удачно сочетаются с инженерными выводами и
техническими рекомендациями.
Книга предназначена для широкого круга инженеров и математиков,
специализирующихся по системам связи, системам управления, вычислительным
машинам и кибернетическим устройствам. Она также может служить хорошим
учебным пособием для аспирантов и студентов.
ОГЛАВЛЕНИЕ
Предисловие редакторов русского перевода
9
Предисловие к русскому изданию
13
Предисловие
14
1. СИСТЕМЫ СВЯЗИ И ТЕОРИЯ ИНФОРМАЦИИ
17
1.1. Введение
17
1.2. Модели источников и кодирование для источников
20
1.3. Модели каналов и кодирование для каналов
22
Исторические замечания и ссылки
28
2. МЕРА ИНФОРМАЦИИ
29
2.1. Дискретные вероятности; обзор и обозначения
29
2.2. Определение взаимной информации
32
2.3. Средняя взаимная информация и энтропия
39
2.4. Вероятность и взаимная информация для непрерывных ансамблей
42
2.5. Взаимная информация для произвольных ансамблей
49
Итоги и выводы
53
Исторические замечания и ссылки
53
3. КОДИРОВАНИЕ ДЛЯ ДИСКРЕТНЫХ ИСТОЧНИКОВ
54
3.1. Коды с фиксированной длиной
55
3.2. Неравномерные кодовые слова
60
3.3. Теорема кодирования для источника
66
3.4. Процедура выбора оптимального неравномерного кода
68
3.5. Дискретные стационарные источники
72
3.6. Марковские источники
80
Итоги и выводы
86
Исторические замечания и ссылки
87
4. ДИСКРЕТНЫЕ КАНАЛЫ БЕЗ ПАМЯТИ И ПРОПУСКНАЯ
88
СПОСОБНОСТЬ

4.1. Классификация каналов
4.2. Дискретные каналы без памяти
4.3. Обращение теоремы кодирования
4.4. Выпуклые функции
4.5. Нахождение пропускной способности дискретного канала без памяти
4.6. Дискретные каналы с памятью
Неразложимые каналы
Итоги и выводы
Исторические замечания и ссылки
Приложение 4А
5. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КАНАЛА С ШУМАМИ
5.1. Блоковые коды
5.2. Декодирование блоковых кодов
5.3. Вероятность ошибки для двух кодовых слов
5.4. Обобщенное неравенство Чебышева и граница Чернова
5.5. Случайные кодовые слова
5.6. Теорема кодирования для кода с числом слов, большим двух
Свойства показателя экспоненты случайного кодирования Er(R)
5.7. Вероятность ошибки для ансамбля кодов с выбрасыванием
5.8. Нижние границы для вероятности ошибки
Вероятность ошибки на блок при скоростях, больших пропускной
способности
5.9. Теорема кодирования для каналов с конечным числом состояний
Состояние известно на приемном конце
Итоги и выводы
Исторические замечания и ссылки
Приложение 5А
Приложение 5Б
6. МЕТОДЫ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ
6.1. Коды с проверкой на четность
Порождающие матрицы
Проверочные матрицы систематических кодов с проверкой на
четность
Таблицы декодирования
Коды Хэмминга
6.2. Теорема кодирования для кодов с проверкой на четность
6.3. Теория групп
Подгруппы
Циклические подгруппы
6.4. Поля и многочлены
Многочлены
6.5. Циклические коды
6.6. Поля Галуа
Коды максимальной длины и коды Хэмминга

88
90
93
99
107
113
122
127
128
128
132
132
136
138
142
147
152
157
166
172
188
191
197
202
203
203
208
211
211
214
215
217
218
222
225
226
228
229
231
237
243
248

Существование полей Галуа
6.7. БЧХ-коды
Итеративный алгоритм для нахождения σ(D)
6.8. Сверточные коды и пороговое декодирование
6.9. Последовательное декодирование
Сложность последовательного декодирования
Вероятность ошибки при последовательном декодировании
6.10. Кодирование в каналах с пакетами ошибок
Циклические коды
Сверточные коды
Итоги и выводы
Исторические замечания- и ссылки
Приложение 6А
Приложение 6Б
Случайные блуждания и доказательство леммы 6Б.1
7. ДИСКРЕТНЫЕ ПО ВРЕМЕНИ КАНАЛЫ БЕЗ ПАМЯТИ
7.1. Введение
7.2. Отсутствие ограничений на входе
7.3. Ограничения на входе
7.4. Аддитивный шум и аддитивный гауссов шум
Аддитивный гауссов шум и ограничение на энергию входного сигнала
7.5. Параллельные каналы с аддитивным гауссовым шумом
Итоги и выводы
Исторические замечания и ссылки
8. НЕПРЕРЫВНЫЕ КАНАЛЫ
8.1. Ортонормальные разложения сигналов и белый гауссов шум
Гауссовские случайные процессы
Взаимная информация для каналов с непрерывным временем
8.2. Белый гауссов шум и ортогональные сигналы
Вероятность ошибки для двух кодовых слов
Вероятность ошибки для ортогональных кодовых слов
8.3. Эвристическое изучение пропускной способности канала с аддитивным
гауссовым шумом и ограничениями на полосу частот
8.4. Представление линейных фильтров и небелый шум
Профильтрованный шум и разложение Карунена — Лоэва
Идеальные фильтры нижних частот
8.5. Каналы с аддитивным гауссовым шумом и сигналами на входе,
ограниченными по мощности и по частоте
8.6. Диспергирующие каналы с замираниями
Итоги и выводы
Исторические замечания и ссылки
9. КОДИРОВАНИЕ ИСТОЧНИКА С ЗАДАННЫМ КРИТЕРИЕМ
ВЕРНОСТИ
9.1 Введение

252
256
263
276
282
291
299
304
309
317
323
324
324
327
331
334
334
336
341
351
353
361
371
372
373
373
380
387
389
392
396
401
407
415
419
422
446
455
455
457
457

9.2. Дискретные источники без памяти и меры искажения отдельной буквы 458
9.3. Теорема кодирования для источников при заданном критерии верности 466
9.4. Вычисление R(d*)
472
9.5. Модификация обращения теоремы кодирования для канала с шумами
480
9.6. Дискретные по времени источники с непрерывными амплитудами
484
9.7. Гауссовские источники с квадратично-разностным искажением
490
Источники, порождающие гауссовские случайные процессы
496
9.8. Дискретные эргодические источники
504
Итоги и выводы
514
Исторические замечания и ссылки
516
Задачи и упражнения
517
Решения задач
575
Список обозначений
691
Примечания редакторов
693
Список использованной литературы и рекомендуемые книги
695
Именной указатель
709
Предметный указатель
711
ИМЕННОЙ УКАЗАТЕЛЬ
Возенкрафт (Wozencraft J. М.) 16,
Абель 226
280, 284, 324, 455, 569, 693
Ахиезер 377, 412
Вольфовиц (Wolfowitz J.) 76, 188,
Бабкин 692
203, 507
Берлекэмп (Berlekamp E.) 16, 142,
Габидулин 690
173, 176, 184, 203, 219, 263, 272,
Галлагер (Gallager R. G.) 11, 12, 16,
298, 319, 324, 348
128, 142, 173, 176, 184, 203, 219
Берман 693
Галуа 230, 243, 244, 245, 246, 247,
Берри 551, 631
251, 252, 253, 255, 256, 280
Бессель 375
Гантмахер 199
Биркгоф 225
Гёльдер 209, 533, 534, 539, 544, 607,
Блекуэлл (Blackwell D.) 84, 100, 128,
615
203
Гельфанд 53, 388, 693
Блюстейн (Bluestein) 296
Гилберт (Gilbert E.) 530, 547, 555,
Блэчмен (Blachman N. М.) 581
558, 693
Боуз 243, 256, 324
Гильберт 412, 455
Брейман (Breiman L.) 87, 128, 203
Гиршик (Girshick M. А.) 100
Бьюк (Buck R. С.) 91
Глазман 377, 412
Вагнер (Wagner Т.) 372
Гоблик (Goblick Т.) 515, 516
Вальд 332, 562
Голей (Golay M.) 220
Вайнер A. (Wyher A.) 16, 319, 456
Голомб (Golomb S. W.) 87
Варшамов 554, 558, 693
Гордон (Gordon В.) 87
Велч (Welch L. R.) 87
Гоппа 693
Венн 517, 575
Гренандер 432
Виленкин 693 Винер (Wiener N.) 28
Давенпорт (Davenport) 381 386, 455
Витерби (Viterbi A.) 303, 304, 397
Джелинек (Jelinek) 172, 549

Джекобе (Jacobs I.) 16, 28, 298, 324,
455
Добрушин 51, 692—694
Дуб (Doob J. L.) 455
Евклид 233, 234, 235, 237, 239, 242
Егармин 690
Ерохин 690
Жордан (Jordan) 296
Звонкий 692
Зеттенберг (Zettenberg L. H.) 456, 570
Зигангиров 12, 693, 694
Ивадари 317, 318, 319, 321
Истман (Eastman W. L.) 87
Кайлат (Kailath T.) 16, 495, 456
Казани (Kasami Т.) 312
Карунен 416, 418, 496
Каруш (Karush J.) 65
Кац (Каc) 432, 504
Келли (Kelly J. L.) 436, 520
Кендалл (Kendall) 87
Кеннеди (Kennedy R. S.) 16, 203, 446,
456, 569
Кириллов 692
Кокс 83, 330
Коленберг (Kohlenberg A.) 16, 319
Колесник 693
Колмогоров 9, 28, 516, 692, 694
Котельников 28, 693
Коутц (Kotz S.) 324
Кошелев 693
Коши 329, 330, 534
Крамер 355
Крафт 64, 65, 67, 70, 586, 587, 588
Кричевский 692
Кун 128
Курант 412, 455
Кэн 16
Лагранж 103, 227, 314, 347, 352
Левенштейн 692
Левин 692
Литтльвуд (Littlewood J. E) 340, 533,
596
Лоев (Loeve M.) 416, 418, 455, 496
Лопиталь 170, 175, 549, 625

Маклейн 225
Макмиллан (McMillan В.) 65, 77, 87,
692
Мардок (Murdock W. L.) 432, 504
Марков 80, 81, 82, 85, 86, 115, 122,
128, 530, 537, 692
Мартон 694
Макс (Max J.) 16, 515
Месси (Massey J. L.) 16, 263, 272, 280,
281, 317, 318, 319, 321, 324
Метцнер (Metzner) 280
Миллер 82
Минковский 194, 297, 340, 534, 535
Мирончиков 693
Морган (Morgan) 280
Морзе 20, 55
Надь 375, 412, 418, 455, 564, 666
Овсеевич 694
Отт (Ott G.) 87
Парсеваль (Parseval) 377, 379, 393
Паттерсон 61, 525
Пилк (Pile R.) 472, 515
Пинкстон (Pinkston J.) 16, 516, 573
Пинскер 12, 49, 51, 53, 456, 693—694
Пирс (Pierce J.) 456
Питерсон (Peterson W. W.) 220, 251,
275, 324, 693
Плоткин 182, 554
Полиа (Polya G.) 340, 533, 596
Прейндж (Prange E.) 324
Прелов 692
Препарата 16
Пятошин 694
Рейффен (Reiffen В. ) 128
Рид (Reed) 87, 276, 316, 559, 649
Риман 668
Рисе (Riesz) 375, 412, 418, 437, 437,
564, 566
Ричтерс (Richters J.) 456
Робинсон 653
Рут (Root) 381, 386, 436, 456
Сакрисон 16, 28
Сардинас (Sardinas) 61, 525
Севэдж (Savage J.) 298

Хорстейн 280
Сеге (Szego G.) 432, 504
Хэмминг (Hamming R. W.) 177, 217,
Сейдман 16 Сифоров 694
218, 219, 220, 248, 251, 285, 324,
Слепян (Slepian D.) 324, 372
541, 546, 553, 557, 558, 559, 560,
Соломон 316, 559, 649
572, 643, 644, 649, 654, 686
Стиглитц (Stiglitz I.) 516, 548
Цирлер (Zierler N.) 324
Стерлинг 141, 180, 538, 540, 602, 607
Цыбаков 12, 693, 694
Тейлор 532, 594, 612
Чоудхури 243, 356, 324
Титчмарш (Titchmars E. С.) 379
Чебышев 79, 142, 143, 156, 167, 190,
Толман 36
297, 468, 471, 502, 517, 524, 525,
Томасян (Thomasian A. J.) 128, 203
539, 551, 584, 585, 606, 607
Тюкер 128
Чень (Chien R. T.) 272
Файнстейн (Feinstein A.) 49, 203, 507
Чернов 142, 143, 147, 151, 190, 328,
Файр (Fire P.) 312, 324
539, 541, 543, 546, 548, 551, 560,
Фано (Fano R. M.)16, 53, 87, 128, 188,
606, 609, 631, 541, 658
203, 284, 287, 288, 298, 324 456,
Шварц 376, 412, 503, 534, 565, 667,
690
674
Феллер (Feller W.) 53, 57, 82, 206,
Шелквийк (Schalkwijk) 495, 694
207, 333, 348, 368, 383, 398
Шеннон (Shannon С. Е.) 9, 17, 53, 81,
Ферма (Fermat P.) 556
87, 128, 142, 171, 173, 176, 184,
Фитингоф 692
203, 219, 348, 357, 372, 391, 516,
Фишер 375, 437
542, 407, 692
Форни (Forney G. D.) 16, 276, 543
Шольц (Scholtz R. A.) 87
Фробениус 199
Шорт 312
Фурье (Fourie) 377, 378, 379, 380, 382,
Эберт (Ebert R.) 370, 371, 372
384, 387, 565
Эбрамсон (Abramson) 53, 87
Фэлконер (Falconer D.) 298
Эйзенберг (Eisenberg E.) 128
Халмош (Halmos P. R.) 50, 51
Элайс (Elias P.) 16, 203, 219, 220, 324,
Харди (Hardy D. W.) 340, 533, 596
495
Харкевич 692
Элспас 312
Хаффман (Huffman D.) 68, 87, 515,
Эссен 551, 631
527, 528, 529, 587, 588, 589
Эш (Ash R.) 53, 87, 319
Хегельбергер (Hagelbarger D. W.) 324
Юдкин (Yudkin H.) 16, 128, 203, 303,
Хинчин 76, 692
304, 551, 456
Хоквингем (Hocquenghem A.)
Яглом 53, 381, 388, 692
243,256, 324
Холзингер (Holsinger J.) 456
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
АЕР (Asymptotic equipartion
Автокорреляционная функция 381
property)-свойство 87
— — на выходе линейного фильтра,
Алфавитный двоичный код для
выраженная через сигнал на
источника 526
входе 382
Аналоговые и цифровые системы
Аддитивный шум 351
связи 28
— — гауссов 47, 351, 422

Английский текст как марковский
источник 81
Ансамбли, статистически
независимые, 31
Ансамбль (вероятностное
пространство) 29
— блоковых кодов 148, 166, 344
— сверточных кодов 292, 300
— совместный 30, 31, 48, 128
Ансамбля разбиение 50
Ассоциативный закон 225
Белый гауссов шум 383
— — —, статистическая
независимость коэффициентов
разложения 385
Белый гауссовский случайный
процесс, см. белый гауссов шум
Берлекэмпа алгоритм 263
Бесконечный ряд функций,
сходимость 376
Бесселя неравенство 375
Биномиальная функция
распределения, ее границы 540
Биномиальные коэффициенты,
границы 540
Бит 32
Блок-схема системы связи 17
— — кодера для метода
декодирования Ивадари—
Месси 317
БЧХ-коды 256—276
— —, декодирование с помощью
итеративного алгоритма 263,
см. также Берлекэмпа алгоритм
— —, минимальное расстояние 258
— —, —, асимптотическое поведение
275
— —, синдром 260
Вальда тождество 332, 562
Варшамова—Гилберта граница 554,
558
Вектор вероятностей 100
Вероятности плотность 43
— — совместная 43

— — условная 43
Вероятностная мера 50
— модель канала связи 127
Вероятность 29—32
— дискретная 29
— — совместная 29
— — условная 30
— и информация 21
— и взаимная информация для
непрерывных ансамблей 42
— ошибки декодирования 137—138
— — —, верхняя граница 548
— — —, верхняя граница в терминах
(C-R)2 548
— — —, граница для ансамбля
случайных кодов 152.
— — —, граница сферической
упаковки 173
— — — для ансамбля кодов с
выбрасыванием 166—172
— — — для двух кодовых слов 138,
392
— — — для канала с белым
гауссовым шумом при
ортогональном коде 396
— — — — при ортогональном коде и
неизвестной фазе 572
— — — —, случай двух - кодовых
слов 392
— — — для кода источника 58
— — — для случайных кодовых слов
147
— — — на блок при скоростях,
больших пропускной
способности 188
— — — на символ источника 94
— — — , нижние границы 172
— — —, прямолинейная граница, см.
прямолинейная граница для
показателя вероятности ошибки
— — —, см. также теоремы
кодирования, показатель
экспоненты, показатель

экспоненты для процедуры с
выбрасыванием
Вес двоичной последовательности
217
Взаимная информация 32
— — выпуклость 105 535
— — для каналов с непрерывным
временем 387—389
— — — непрерывных ансамблей
44—45
— — — произвольных ансамблей
49—53
— —, средняя 34, 39—42, 51
— —, — и энтропия 39
— —, условная 37, 45, 52
— —, — средняя 37, 46, 52
Взаимно-простые числа 228
Вогнутая функция 101
Волновые функции вытянутого
сфероида 420
— — — —, асимптотическое
поведение собственных
значений 421—422
— — — —, свойства преобразования
Фурье 422
Вольфовица теорема 188
Воспроизведение выхода источника у
адресата при выполнении
заданного критерия верности
514
Время когерентности шума 382
Выборочное пространство 29
— — совместное 30, 31
Выпуклая область 100
Выпуклая функция 99—107
— — вверх 100
— — вниз 101
Гауссовский канал 353—361, 422—
446
— источник дискретный по времени
с квадратично-разностным
искажением 490—504
— случайный процесс, определение
383

— — —, представление в виде
отфильтрованного белого шума
418
— — —, стационарный 500
Гауссовская случайная величина 47
— — —, границы для функции
распределения 397
Гёльдера неравенство 533
Гилберта граница 547, см. также
Варшамова—Гилберта граница
Группа 225—229
— абелева (коммутативная) 226
—, порядок элемента 228
—, циклическая 228
Двоичный симметричный канал
(ДСК) 23
— — —, граница сферической
упаковки 179
— — —, показатель экспоненты
случайного кодирования 162—
163
— — —, пропускная способность 109
— — —, прямолинейная граница 187
— код алфавитный 526
— — Хаффмана 527
— сверточный кодер 282
Декодер 17
—, диффузный пороговый 320
— для исправления пакетов 318
— для разнесения пакетов по
времени 322
— пороговый 279
Декодирование 136, см. также коды,
последовательное
декодирование пороговое
декодирование
— блоковых кодов 136—138
— БЧX—кодов 262—276
— по максимуму правдоподобия 137
— — в белом гауссовом шуме 394
— — — в двоичном симметричном
канале 217
— — — в диспергирующем канале с
замираниями 571

— списком 181
— —, верхняя граница Pe 182, 547
Декодирования таблица 217—218
Демодулятор дискретных данных
(ДДД) 24
Дерево для префиксного кода 62—63
— принятых цен 286
Диспергирующий канал с
замираниями 446—455
— — —, оптимальный выбор
собственных значений 454
— — —, приемник максимального
правдоподобия 751
Дисперсия взаимной информации
522
— — —, связь с пропускной
способностью 537
Дисперсия суммы случайных
величин 517
ДКБП, см. канал
Диффузный пороговый декодер, см.
декодер, диффузный пороговый
Длина блокового кода 133
— кодового ограничения
сверточного кода 231
Добрушина теорема 51
Достаточный приемник 522
Дуальный код 241
Евклида алгоритм деления
многочленов 233
Единицы информации 32
Живые организмы как системы связи
19
Закон больших чисел 57, 518
Замирания в канале 89, 446
Защитный интервал 307
Значения ошибок, БЧХ-коды 260
Идеальные фильтры нижних частот,
см. фильтры идеальные нижних
частот
Импульсно-кодовая модуляция 493
Инвариантное множество
последовательностей 75

Интерпретация пропускной
способности с наполнением
водой 406— 407
Информационная плотность 388
— устойчивость 87
Информационные символы 213
Информация 20
— взаимная, 32
— собственная 21
— — для непрерывных ансамблей 46
— — средняя, см. энтропия
— — условная 35
Источник 20
— дискретный без памяти 54
— — периодический 73
— — стационарный 72
— дискретный по времени, без
памяти, с непрерывными
амплитудами 484
— порождающий гауссовский
случайный процесс 380
— эргодический 504
— и канал, теорема кодирования, см.
совместная теорема
кодирования для канала и
источника
—, коды, 20, 54—87
—, — мгновенные 62
—, — неравномерные 55, 60—66
— , — — оптимальные 68—72
—, —, обладающие свойством
префикса 61
— —, однозначно декодируемые 61,
525
—, — с критерием верности 457
—, — с фиксированной длиной 55—
60
— марковский 80—86
—, модель 20
— недискретный 22
— , порождаемый марковским
источником 530
—, теорема кодирования 21

—, — для дискретного источника без
памяти, код с фиксированной
длиной 59
—, — —, код неравномерный 68, 526
—, — — с бесконечным алфавитом,
код неравномерный 526
—, — для стационарного источника,
код неравномерный 20, 72—75
—, — для эргодического источника,
код с фиксированной длиной 76
—, — при заданном критерии
верности 466
—,— — для дискретного источника
без памяти 468
—, — — —9 обращение 464
—, — — — с бесконечным
искажением 470
— — —, скорость сходимости 471
—, — для дискретного по времени
источника без памяти 484—490
—, — — — —^ обращение 485
—, — — — — при передаче по
каналу с шумами 488
—,— — — эргодического источника
514
—, — — для источника
порождающего гауссовский
случайный процесс 500
—, — — для дискретных
эргодических 514
—, — — —, обращение 506—507
—, порождающий гауссовские
случайные процессы 496, 499
—, представление выхода
последовательностью двоичных
символов 457
— реальный 20
— с заданным критерием верности
457—516
— эргодический 75
— физический 20
— эргодический 75
—, —, конструкции кодов 511

Канал, дискретный без памяти
(ДКБП) 23, 90—99
—, — по времени без памяти 334—
372
—, — — с аддитивным шумом 351—
361
—, — — — гауссовым шумом 353—
361
—, — с памятью 113—127
—, дискретные по времени
параллельные каналы с
гауссовым шумом 361—371
—, диспергирующий с замираниями
446—454
—, —, математическая модель —
449, см. также диспергирующий
канал с замираниями
—, классификация 88
—--, непрерывный 89
—, «панический» 119
— с аддитивным гауссовым шумом и
отфильтрованным входом 402,
422—446
— — белым гауссовым шумом 389—
400
— — конечным числом состояний
(ККЧС) 113—127
— —, неразложимый 122—127
— — —, состояния которого
неизвестны на приемном конце
197
— — очень большим шумом 163
— — пакетами ошибок 304
— связи 88
— составной 191
Карунена—Лоэва разложение 416
Квадратная матрица, неприводимая
199
Квантование 458
ККЧС, см. каналы с конечным
числом состояний
Кодер 17, 133
— блоковый 26
— для дискретного канала 27

— для диффузного порогового
декодирования 319
— для кода максимальной длины 248
— с проверкой на четность 214
— для разнесения пакетов во
времени 321
— пороговый 279
— сверточный, см. сверточный кодер
— сверточный систематический 281
— циклического кода 242
Кодирование 19
— длин серий 528
— для источников 20
— — —, дискретных 54
— — —, с заданным критерием
верности 457
— — каналов 22
— — — дискретных 132
— — —, — по времени без памяти
336
— — —, непрерывных 373
— — — с пакетами ошибок 304
— корреляционное, см.
корреляционное декодирование
по Хаффману 68
— с перемежением 305
— и декодирование в теории
информации 19
Кодирования теорема, см. теорема
кодирования
Коды 132
— биортогональные 572
— блоковые 132
— — (N, R) 154
— БЧХ 256—276
— групповые 237
— для источника; см. источник, коды
— —, обладающие свойством
префикса 61
— —, обладающие свойством
синхронизации 87
— —, однозначно декодируемые 61
— — переменной длины
(неравномерные) 60—66

— — оптимальные 68—72
— — с критерием верности 463
— — фиксированной длины 55—60
— в каналах с пакетами ошибок
304—327
— в каскадной схеме 276
— линейные 237—238
— максимальной длины 248—252,
569
— мгновенные 62
— ортогональные 396
— Рида—Соломона 276, 559, 649
— сверточные 276, 282
— симплексные 396, 400
— совершенные 219
— с проверкой на четность 211
— сферически упакованные 219
— Хаффмана 62—72
— Хэмминга 219—220, 248, 654
— циклические 237, 309 См. также
указанные выше названия
рубрик
Конструирование большого кода из
малого 519
Корень многочлена 235
Корректирующая пакеты
способность 307
Корреляционное декодирование 394
Крафта неравенство 64
— для бесконечного счетного
алфавита 526
Критерий верности 460 см. также
Теоремы кодирования,
источник
— однозначного декодирования 61,
525
— Сардинаса—Паттерсона 525
Критерий оценки методов
кодирования в каналах с
пакетами ошибок 307
Корреляционная функция 382
Коэффициент занятости передачи
452

Лагранжа теорема о порядке группы
227
Линейные коды, см. коды линейные
— фильтры 381, см. также фильтры
линейные
—, выход которых определяется
входом 427—431
—, меняющиеся во времени 408—
409
Логарифм отношения правдоподобия
393
Локаторы ошибок для БЧХ кодов 260
Макмиллана АЕР теорема 77
Максимум выпуклой функции 102—
105
Маркова процесс 530
Маркова цепь конечная
неоднородная 122
— — — однородная 81
Марковский источник 80—86
— — порождаемый 530
Мерсера теорема 418
Межсимвольная интерференция
424, 537 Мера информации 29
— — (неопределенности) букв
алфавита источника 21
— искажения 458
Минимальное расстояние 182
Минимальный многочлен 245
— —, вычисление 558
Минковского неравенство 534
Многочлены 231—237
— единственность разложения 235
—, корни 235
—, неопределенный символ 232
— нормированные 234
—, остаток по модулю многочлена
234
— приводимые (неприводимые) 234
—, равенство 232
—, степень 232
—, сумма и произведение 232
Множество совместно гауссовских
случайных величин 384

— — —, совместная плотность
вероятности 384
— — —, совместная
характеристическая функция
384
— элементов, замкнутое 229
— эргодическое 82 Модели
источников 20
— каналов 22
— каналов с замираниями (с пачками
ошибок) 115
— — связи 89
— — с межсимвольной
интерференцией 115
Модулятор дискретных данных
(МДД) 24
Модуляция частотная 493
Морзе код 55
Надежная передача по
диспергирующим каналам 456
— — в канале с пакетами ошибок
304—305
Нат 32
Нейтральный элемент 225
Невозвратные состояния марковской
цепи 82
Неопределенность для канала 42
Неопределенный символ, см.
многочлены, неопределенный
символ
Непосредственные потомки см.
последовательное
декодирование,
непосредственные потомки
Неравенства в теории информации
533
Неравенство Гёдьдера 533
— Крафта 64, 526
— Минковского 534
—. Чебышева 142—147
— Шварца 503
Неравномерные кодовые слова 60
Неразложимое множество состояний
марковской цепи 82

Несущественность независимых
шумов 429
Нижние границы для вероятности
ошибки 172
Нормальные случайные величины,
см. Гауссовская случайная
величина
Нормированные функции 374
Нуль-пространство столбцов (строк)
матрицы 216
Обнаружение ошибок и переспрос
304, 543
— сигнала в небелом гауссовом
шуме 456
Обратная связь, влияние на
экспоненту вероятности
ошибки 543
— — , на границу сферической
упаковки 550
— —, двочный канал со стиранием
519—520
— —, использование при передаче
данных по каналам с
аддитивным гауссовым шумом
495
— —, для гауссовского источника
493
— —, каналы с пакетами ошибок
304—324
— —, отсутствие влияния на
величину пропускной
способности дискретных
каналов без памяти 531—532
Обобщенное неравенство Чебышева
143.
Обобщенный случайный процесс 383
Обратный элемент 226
Ограничения на входе для
непрерывных каналов 335
— — на математическое ожидание
341
Оптимальные декодеры, см. коды
циклические, декодирование по
максимуму правдоподобия,

декодирование с минимальной
стоимостью и декодирование с
минимальной вероятностью
ошибки
Ортогональное множество линейных
комбинаций шумовых символов
278
Ортогональные коды, см. коды
ортогональные
— функции 374 Ортонормальные
множества 374
— — полные 374
— разложения 373
— —, асимптотическое поведение
множества собственных
значений 432
— —, представление выхода
линейного фильтра 408
Отображение двоичных
последовательностей во
входные буквы канала 224
Отсчетные функции 379
Ошибка при блоковом
декодировании 135
— при декодировании списком 181
Пакет ошибок 300
— — для циклических кодов 310
— — корректирующая способность
307
— — относительно защитного
интервала 307
Панический канал, см. канал
панический
Парадоксы, связанные с пропускной
способностью ограниченного
по полосе гауссовского канала
407
Параллельные каналы 165, 361, 530
Парсеваля равенство 377
— —, связывающие преобразования
Фурье 379
Перекошенные случайные величины
204
Перемежение 305

Перемешивание 305
Периодические множества состояний
однородной цепи Маркова 82
Период неразложимого множества 82
Плоткина граница 182, 554, 558, см.
также энергию разности
Повисший суффикс 525
Подгруппы 226
— циклические 228
Подполя 244
Показатель экспоненты вероятности
ошибки, Eex(R), для процедуры
с выбрасыванием 169—172
— — —, дискретный канал без
памяти; вычисление Rx∞ 549
— — —, предел R → 0 548
— — — —, максимизация по Q 548
— — —, дискретный по времени
гауссовский канал 359
— — —, — канал без памяти 341,
349
— — —, канал с аддитивным
гауссовым шумом и с
отфильтрованным входом 445
— — —, параллельные дискретные
по времени гауссовские каналы
370
— —, Er (R), для случайного
кодирования 155—166
— —, Esp (R) — граница сферической
упаковки 173
— —, Esl (R), прямолинейная граница
176
См. также случайного кодирования
показатель экспоненты
Полное дерево 64
— кодовое дерево 70
Поля 229—230
— Галуа 230, 243
— —, действия в них 252—253
— —, изоморфность, см. поля
изоморфные
— —, минимальный многочлен 245

— —, многочленов по модулю
многочлена 234
— —, порядок, см. порядок для поля
Галуа
— —, примитивные элементы, см.
примитивный элемент поля
Галуа
— —, существование 255
— —, целые элементы 244
Поля изоморфные 247
Попарная независимость, см.
статистическая независимость,
попарная
Пороговое декодирование 279—282
— — диффузное 319
— —, коды максимальной длины 560
Пороговый декодер, см. декодер
пороговый Порождающие матрицы
214—215, 239
— —, эквивалентные 220
Порождающий многочлен
циклического кода 240
Порядок группы 227
— поля Галуа 231
Последовательное декодирование
282—304
— —, вероятность ошибки
декодирования 299
— — движения вперед, вбок и назад
286
— —, доказательство того, что
Wn < ∞ при R < Rвыч = E0 (1, Q)
297
— —, непосредственные потомки
узла 289
— —, порог T 287
— —, потомки узла 289
— —, F — проверки 289
— —, путь порогов 289
— —, — правильный 290
— —, — узлов 289
— —, — цен 289
— —, смещение 285

— —, статистическая независимость
правильного и неправильного
путей 561
— —, Фано алгоритм 287
— —, цена узла 285
— —, число вычислений и
вероятность ошибки при
ограниченной глубине поиска
560—561
— —, — вычислений на
декодированный подблок Wn
291, 295, 297
Последовательные каналы 41, 522,
537
Построение двоичных кодовых слов
для ансамбля сообщений 526
Правило декодирования с
минимальной вероятностью
ошибки 136
Правый (левый) смежный класс 227
Предел в среднем 375
Представление непрерывного канала
как дискретного 24
Преобразование алфавита в
двоичные символы 20
— аналог — цифра 458
Префикса свойство кодирования
источников, см. источника
коды, обладающие свойством
префикса
Прием с отрицательной задержкой
(предсказание) 28
Примитивный многочлен 248
— элемент поля Галуа 244
Проверка на четность 211
— —, коды 211
— —, —, в произвольном ДКБП
224—225
— —, — матрица 215 _. __, __ 214
— —, — систематические 214
см. также линейные коды
Проверочная матрица, см. проверка
на четность, коды, матрица

Проверочные матрицы
систематических кодов 215
Проверочный многочлен
циклического кода 240
Производная Радона—Никодима, 53
Пропускная способность 25
— гауссовского канала с аддитивным
шумом и с отфильтрованным
входом 401
— — —, эвристический вывод 401—
407
— — с белым шумом без
ограничения на полосу частот
389—392
— — — и ограниченным числом
степеней свободы 391
— двоичного симметричного канала
109
— дискретного канала без памяти 91
— — —, верхняя оценка и
минимаксная интерпретация
535
— — —, вычисление 107—113
— дискретного по времени канала
без памяти 336
— — с аддитивным шумом 353
— — — с гауссовым аддитивным
шумом 353—361
— — — с входными ограничениями
342
— диспергирующих каналов с
замираниями 453
— каналов с конечным числом
состояний 113—127
— — —, неразложимых 122
— — —, нижние и верхние
пропускные способности 116—
117
— — — без межсимвольной
интерференции 552
— параллельных каналов,
дискретных без памяти 530
— — — гауссовских 361

— —- каналов с непрерывным
временем 389
— с нулевой ошибкой 171
— связь с принятием решений 537
Простая модель канала с
замираниями 197
Пространство строк (столбцов)
матрицы 215
Профильтрованный белый гауссовый
шум 415
Прямолинейная граница для
показателя вероятности ошибки
Esl (R) 176
Псевдошумовая последовательность
250
Радона—Никодима производная 53
Разложение по выборочным
функциям 379—380
Разложения отфильтрованного
белого шума 415—418
— функции в бесконечный ряд 376
Расстояние Хэмминга, см. Хэмминга
расстояние
Расширение поля 244
Регистры сдвига с линейной
обратной связью максимальной
длины 250
— — —, алгоритм построения 264
— — — —, нахождения самого
короткого регистра 265
Редукция данных 458
Редуцированный ансамбль для кодов
источника 69
Решетчатая случайная величина 146
Речевой сигнал 458
Рида—Соломона коды 276, 559, 649
— —, наименьшее расстояние 559
Рисса—Фишера теорема 375
Рост капитала в азартной игре 520
Сверточные коды 276, 282
— —, длина кодового ограничения
281
— —, древовидная структура 282

— —, исправление пакетов ошибок
317
— — систематические 281
Семиинвариантная производящая
функция моментов 203
Сверточный кодер 276
Сжатие полосы частот 458
Симметричный дискретный канал без
памяти 110
Симплексные коды 396
— —, вероятность ошибочного
декодирования 400
Синдром 216
— для БЧХ-кодов 260
— для сверточных-кодов 277
Синхронизация кодов 87
Система связи 17
— —, блок-схема 17
Систематические линейные коды 238
Систематический код с проверкой
на четность 213
Скорость блоковых кодов 134
— как функция искажения 459— 460
— —, выпуклость 460
— —, вычисление 472
— — для гауссовского дискретного
по времени источника 492
— — для дискретного по времени
источника без памяти 484
— — для дискретного эргодического
источника 504—505
— —, нижняя граница 474
— сверточных кодов 285
Слабое обращение теоремы
кодирования 188
Случайного кодирования показатель
экспоненты 155—156
— — для двоичного симметричного
канала 162—163
— — для дискретного канала без
памяти 155—166
— — для дискретных параллельных
каналов 166

— — для дискретных по времени
каналов без памяти 336—337,
349
— — — с аддитивным гауссовым
шумом 358—359
— — _. —j параллельных 366—377
— — — — с отфильтрованным
входом 441—442
— — для каналов с конечным числом
состояний 195
— — для каналов с очень большим
шумом 165—166
Случайные блуждания 331
— величины 34
— кодовые слова 147—148
Случайный процесс, определения 380
— — с нулевым средним 381
— — стационарный 381 _ — — в
широком смысле 382
Случайный гауссовский процесс с
нулевым средним 383
— — —, обобщенный 383
— код 222
Смежный класс 227
Собственная информация,
содержащаяся в событии 34—
35
Совершенные коды 219
Совместная теорема кодирования для
источника и канала 544
Совместные гауссовские величины
384
— —, плотность вероятности 384
— —, характеристическая функция
384
Согласованные фильтры 394
Составной канал 191
Спектральная плотность мощности
382
Средняя вероятность ошибки в
последовательности из L
символов 94
Статистическая независимость 31
— — ансамблей 31

— — попарная 223, 517
Степени свободы 378
Стирлинга формула 540, 602, 607
Сумма каналов, пропускная
способность 536
— —, показатель экспоненты
случайного кодирования 544
Суперисточники 509
Суффикса свойство 527
Сферическая упаковка, показатель
экспоненты, Esp(R) 173
Сферически упакованные коды 219
Таблица декодирования 217
Таблица используемого материала 15
Телефонная линия 17
Теорема кодирования 25—28, 132—
152
— для источников, см. источник,
теорема кодирования
— для каналов двоичных
симметричных 162, 541
— — дискретных 152
— — —, без памяти 155, 160
— — —, —, альтернативный вывод с
использованием пропускной
способности 543
— — — —, обращение 93
— — — —, обращение для
блокового кодирования 188
— — — —, сильное обращение 188
— — — —, слабое обращение 188
— — — —, упрощенный вывод с
более слабым показателем
экспоненты 543
— — — по времени без памяти 337
— — — —, 338
— — — —, с ограничениями на
входе 349
— — — — —, обращение 342
—- — — — диспергирующих с
замираниями 54
— — непрерывных по времени,
обращение 441

— — с конечным числом состояний
191—201
— — — —, обращение, 118—125
— — — —, с шумом, не зависящим
от ввода 551
— — — —, состояния известны на
приемнике 20
— — с шумами, обращение 480
— — для кодов с проверкой на
четность 222—225
Теорема Макмиллана 77, см.
Макмиллана АЕР теорема
— Мерсера, см. Мерсера теорема
— переработки информации 97 „
— Рисса—Фишера, см. теорема
Рисса—Фишера Теория информации
9, 17
Тест—канал 466
— — прямой и обращенный 493, 500
Тождество Вальда для блужданий с
одним барьером, см. " Вальда
тождество
Условная взаимная информация 37,
45
— — — средняя 37
Фазовая модуляция 493
Ферма теорема 556
Фильтры идеальные нижних частот
419—422
— линейные 381
— — меняющиеся, во времени 408—
409
— — с выходом, определяемый
входом 427—431
Формула Шеннона для пропускной
способности канала 391
Функции выпуклые, см. выпуклая
функция
— вогнутые, см. вогнутая функция
Функция E(R) 27
— из L2 374
— конечной энергии 374
— надежности 176—177

— нормированные, см.
нормированные функции
— ограниченные по времени и
частоте 378
— ортогональные 374
— разложение в ряд Фурье 377
— распределения 42
— —. совместная 43
— рассеивания 447
Фурье преобразование усеченной
синусоиды 378
— ряды 378
Характеристики поля Галуа 243—256
Хаффмана коды 68—72
Хэмминга граница 553, 558
— коды 219, 248
— — в циклической форме 557
— —, символы в произвольном поле
572
— расстояние 177, 217
Цена гипотезы 285
Центральная предельная теорема 206,
539
Циклические коды 237
— — для исправления пакетов
ошибок 309
— — —, построение оптимального
декодера 310
— —, порождающий многочлен 240
— —, проверочный многочлен 240,
557
— —, реализация кодирования 241—
242
Частотная модуляция 493
Чебышева неравенство 142—147
Чернова неравенства 144
Шварца неравенство 503
Шеннона теорема о пропускной
способности ограниченных по
полосе каналов с белым
гауссовым шумом 407
Шум 28
Шумовая последовательность 216
Энергетическое уравнение 377, 385

Энергия разности, оценка среднего
значения 395
Энтропия 21, 36, 39—42
— ансамбля 36
— буквы источника 21
—, выпуклость 102
— в термодинамике 36
— дискретного стационарного
источника 72
— — источника без памяти 86

— — марковского источника 83
— на букву марковского источника
86
— непрерывного ансамбля 47
— — —, условная 47
— P относительно Q 521
Эргодические компоненты 511
Эргодическое множество состояний
марковской цепи 83
Эргодичность 76