Галлагер Р. Теория информации и надёжная связь
Подождите немного. Документ загружается.
Р.Галлагер
ТЕОРИЯ ИНФОРМАЦИИ И НАДЕЖНАЯ СВЯЗЬ
М.: «Советское радио», 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. Классификация каналов 88
4.2. Дискретные каналы без памяти 90
4.3. Обращение теоремы кодирования 93
4.4. Выпуклые функции 99
4.5. Нахождение пропускной способности дискретного канала без памяти 107
4.6. Дискретные каналы с памятью 113
Неразложимые каналы 122
Итоги и выводы 127
Исторические замечания и ссылки 128
Приложение 4А 128
5. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КАНАЛА С ШУМАМИ 132
5.1. Блоковые коды 132
5.2. Декодирование блоковых кодов 136
5.3. Вероятность ошибки для двух кодовых слов 138
5.4. Обобщенное неравенство Чебышева и граница Чернова 142
5.5. Случайные кодовые слова 147
5.6. Теорема кодирования для кода с числом слов, большим двух 152
Свойства показателя экспоненты случайного кодирования E
r
(R)
157
5.7. Вероятность ошибки для ансамбля кодов с выбрасыванием 166
5.8. Нижние границы для вероятности ошибки 172
Вероятность ошибки на блок при скоростях, больших пропускной
способности
188
5.9. Теорема кодирования для каналов с конечным числом состояний 191
Состояние известно на приемном конце 197
Итоги и выводы 202
Исторические замечания и ссылки 203
Приложение 5А 203
Приложение 5Б 208
6. МЕТОДЫ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ 211
6.1. Коды с проверкой на четность 211
Порождающие матрицы 214
Проверочные матрицы систематических кодов с проверкой на
четность
215
Таблицы декодирования 217
Коды Хэмминга 218
6.2. Теорема кодирования для кодов с проверкой на четность 222
6.3. Теория групп 225
Подгруппы 226
Циклические подгруппы 228
6.4. Поля и многочлены 229
Многочлены 231
6.5. Циклические коды 237
6.6. Поля Галуа 243
Коды максимальной длины и коды Хэмминга 248
Существование полей Галуа 252
6.7. БЧХ-коды 256
Итеративный алгоритм для нахождения σ(D)
263
6.8. Сверточные коды и пороговое декодирование 276
6.9. Последовательное декодирование 282
Сложность последовательного декодирования 291
Вероятность ошибки при последовательном декодировании 299
6.10. Кодирование в каналах с пакетами ошибок 304
Циклические коды 309
Сверточные коды 317
Итоги и выводы 323
Исторические замечания- и ссылки 324
Приложение 6А 324
Приложение 6Б 327
Случайные блуждания и доказательство леммы 6Б.1 331
7. ДИСКРЕТНЫЕ ПО ВРЕМЕНИ КАНАЛЫ БЕЗ ПАМЯТИ 334
7.1. Введение 334
7.2. Отсутствие ограничений на входе 336
7.3. Ограничения на входе 341
7.4. Аддитивный шум и аддитивный гауссов шум 351
Аддитивный гауссов шум и ограничение на энергию входного сигнала 353
7.5. Параллельные каналы с аддитивным гауссовым шумом 361
Итоги и выводы 371
Исторические замечания и ссылки 372
8. НЕПРЕРЫВНЫЕ КАНАЛЫ 373
8.1. Ортонормальные разложения сигналов и белый гауссов шум 373
Гауссовские случайные процессы 380
Взаимная информация для каналов с непрерывным временем 387
8.2. Белый гауссов шум и ортогональные сигналы 389
Вероятность ошибки для двух кодовых слов 392
Вероятность ошибки для ортогональных кодовых слов 396
8.3. Эвристическое изучение пропускной способности канала с аддитивным
гауссовым шумом и ограничениями на полосу частот
401
8.4. Представление линейных фильтров и небелый шум 407
Профильтрованный шум и разложение Карунена — Лоэва 415
Идеальные фильтры нижних частот 419
8.5. Каналы с аддитивным гауссовым шумом и сигналами на входе,
ограниченными по мощности и по частоте
422
8.6. Диспергирующие каналы с замираниями 446
Итоги и выводы 455
Исторические замечания и ссылки 455
9. КОДИРОВАНИЕ ИСТОЧНИКА С ЗАДАННЫМ КРИТЕРИЕМ
ВЕРНОСТИ
457
9.1 Введение 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
ИМЕННОЙ УКАЗАТЕЛЬ
Абель 226
Ахиезер 377, 412
Бабкин 692
Берлекэмп (Berlekamp E.) 16, 142,
173, 176, 184, 203, 219, 263, 272,
298, 319, 324, 348
Берман 693
Берри 551, 631
Бессель 375
Биркгоф 225
Блекуэлл (Blackwell D.) 84, 100, 128,
203
Блюстейн (Bluestein) 296
Блэчмен (Blachman N. М.) 581
Боуз 243, 256, 324
Брейман (Breiman L.) 87, 128, 203
Бьюк (Buck R. С.) 91
Вагнер (Wagner Т.) 372
Вальд 332, 562
Вайнер A. (Wyher A.) 16, 319, 456
Варшамов 554, 558, 693
Велч (Welch L. R.) 87
Венн 517, 575
Виленкин 693 Винер (Wiener N.) 28
Витерби (Viterbi A.) 303, 304, 397
Возенкрафт (Wozencraft J. М.) 16,
280, 284, 324, 455, 569, 693
Вольфовиц (Wolfowitz J.) 76, 188,
203, 507
Габидулин 690
Галлагер (Gallager R. G.) 11, 12, 16,
128, 142, 173, 176, 184, 203, 219
Галуа 230, 243, 244, 245, 246, 247,
251, 252, 253, 255, 256, 280
Гантмахер 199
Гёльдер 209, 533, 534, 539, 544, 607,
615
Гельфанд 53, 388, 693
Гилберт (Gilbert E.) 530, 547, 555,
558, 693
Гильберт 412, 455
Гиршик (Girshick M. А.) 100
Глазман 377, 412
Гоблик (Goblick Т.) 515, 516
Голей (Golay M.) 220
Голомб (Golomb S. W.) 87
Гордон (Gordon В.) 87
Гоппа 693
Гренандер 432
Давенпорт (Davenport) 381 386, 455
Джелинек (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
Сеге (Szego G.) 432, 504
Сейдман 16 Сифоров 694
Слепян (Slepian D.) 324, 372
Соломон 316, 559, 649
Стиглитц (Stiglitz I.) 516, 548
Стерлинг 141, 180, 538, 540, 602, 607
Тейлор 532, 594, 612
Титчмарш (Titchmars E. С.) 379
Толман 36
Томасян (Thomasian A. J.) 128, 203
Тюкер 128
Файнстейн (Feinstein A.) 49, 203, 507
Файр (Fire P.) 312, 324
Фано (Fano R. M.)16, 53, 87, 128, 188,
203, 284, 287, 288, 298, 324 456,
690
Феллер (Feller W.) 53, 57, 82, 206,
207, 333, 348, 368, 383, 398
Ферма (Fermat P.) 556
Фитингоф 692
Фишер 375, 437
Форни (Forney G. D.) 16, 276, 543
Фробениус 199
Фурье (Fourie) 377, 378, 379, 380, 382,
384, 387, 565
Фэлконер (Falconer D.) 298
Халмош (Halmos P. R.) 50, 51
Харди (Hardy D. W.) 340, 533, 596
Харкевич 692
Хаффман (Huffman D.) 68, 87, 515,
527, 528, 529, 587, 588, 589
Хегельбергер (Hagelbarger D. W.) 324
Хинчин 76, 692
Хоквингем (Hocquenghem A.)
243,256, 324
Холзингер (Holsinger J.) 456
Хорстейн 280
Хэмминг (Hamming R. W.) 177, 217,
218, 219, 220, 248, 251, 285, 324,
541, 546, 553, 557, 558, 559, 560,
572, 643, 644, 649, 654, 686
Цирлер (Zierler N.) 324
Цыбаков 12, 693, 694
Чоудхури 243, 356, 324
Чебышев 79, 142, 143, 156, 167, 190,
297, 468, 471, 502, 517, 524, 525,
539, 551, 584, 585, 606, 607
Чень (Chien R. T.) 272
Чернов 142, 143, 147, 151, 190, 328,
539, 541, 543, 546, 548, 551, 560,
606, 609, 631, 541, 658
Шварц 376, 412, 503, 534, 565, 667,
674
Шелквийк (Schalkwijk) 495, 694
Шеннон (Shannon С. Е.) 9, 17, 53, 81,
87, 128, 142, 171, 173, 176, 184,
203, 219, 348, 357, 372, 391, 516,
542, 407, 692
Шольц (Scholtz R. A.) 87
Шорт 312
Эберт (Ebert R.) 370, 371, 372
Эбрамсон (Abramson) 53, 87
Эйзенберг (Eisenberg E.) 128
Элайс (Elias P.) 16, 203, 219, 220, 324,
495
Элспас 312
Эссен 551, 631
Эш (Ash R.) 53, 87, 319
Юдкин (Yudkin H.) 16, 128, 203, 303,
304, 551, 456
Яглом 53, 381, 388, 692
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Автокорреляционная функция 381
— — на выходе линейного фильтра,
выраженная через сигнал на
входе 382
Аддитивный шум 351
— — гауссов 47, 351, 422
АЕР (Asymptotic equipartion
property)-свойство 87
Алфавитный двоичный код для
источника 526
Аналоговые и цифровые системы
связи 28
Английский текст как марковский
источник 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
— —, верхняя граница P
e 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