Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
201
рис. 5.9.1, в котором устранена память. Заметим, что пропускная способность С не изменяется при устранении памяти (см. задачу 5.39), однако показатель экспоненты возрастает. Это может быть качественно объяснено тем, что среднее время, проводимое в каждом состоянии, не изменяется при устранении памяти, а вероятность пребывания в плохом состоянии (состоянии 1) значительно дольше, чем среднее время, существенно уменьшается при устранении памяти. Например, в канале, представленном на рис. 5.9.3, при N = 100 вероятность пребывания в плохом состоянии в течение всего блока приближенно равна 1/(2е) при наличии памяти и равна 2~100 при отсутствии памяти.
В каналах, в которых состояние не известно на приемном конце, имеется другой качественный эффект, обязанный долгодействующей памяти. Приемник может оценить состояние по выходам канала, используя знание кода. Это увеличивает пропускную способность канала по сравнению с той, которая имеет место при отсутствии памяти (см. задачу 5.38).
ИТОГИ и выводы
Основным результатом этой главы была теорема кодирования для канала с шумами. Вначале была изучена простая задача проверки гипотез, в которой одно из двух кодовых слов передавалось по дискретному каналу без памяти, и затем был изучен случай большого числа кодовых слов. Для случая большого числа кодовых слов было установлено, что основная трудность состоит в том, что не ясно, как выбирать кодовые слова. Решение этой проблемы было найдено с помощью построения верхней границы для средней по ансамблю кодов вероятности ошибки и последующего указания на то, что, по крайней мере, один код из ансамбля должен иметь столь же малую вероятность ошибки, как и средняя вероятность. При исследовании этой верхней границы было найдено, что при любой скорости R, меньшей, чем пропускная способность канала, существуют коды с любой длиной блока N, для которых Ре^ехр[—NET(R)]. Скорость R здесь понимается как умноженное на In 2 число двоичных символов, поступающих на кодер за время передачи одного символа в канале. Также была найдена более точная граница вероятности ошибки при малых R. Затем было установлено, что имеется нижняя граница для вероятности ошибки наилучших кодов, с заданными N и R, для которой вероятность ошибки убывает экспоненциально по N, и было показано, что показатели этих экспонент совпадают при скоростях, близких к пропускной способности, и в пределе при R -> 0. Нижние границы были выведены только для случая двоичного симметричного канала. Наконец, было показано, что каналы с конечным числом состояний имеют того же типа экспоненциальную верхнюю границу для вероятности ошибки. Ни один из полученных здесь результатов не дает прямого указания на то, как строить кодеры и декодеры; это является предметом следующей главы. В гл. 7 и 8 полученные здесь результаты будут распространены на недискретные каналы.
202
ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ И ССЫЛКИ
Теорема кодирования для канала с шумами принадлежит Шеннону (1948) и, несомненно, является самым значительным результатом в теории информации. Первое строгое доказательство этой теоремы для дискретных каналов без памяти было дано Файнстейном (1954) и вскоре после этого более простые доказательства были предложены Шенноном (1957) и Вольфовицем (1957). Впервые Файнстейн (1955) показал, что Ре стремится к нулю экспоненциально по N при фиксированной скорости R < С. Граница случайного кодирования, граница сферической упаковки и тот факт, что они экспоненциально совпадают при скоростях, близких к пропускной способности, были впервые получены Элайсом (1955) в частных случаях двоичного симметричного канала и двоичного канала со стиранием. Фано (1961) использовал методы случайного кодирования, развитые Шенноном, и производящих функций моментов, для получения показателя экспоненты случайного кодирования Er (R) и для эвристического вывода границы сферической упаковки для общего дискретного канала без памяти. Граница случайного кодирования для процедуры с выбрасыванием и большинство свойств показателя экспоненты случайного кодирования Ет (R) были получены Галлагером (1965). Нижние границы для вероятности ошибки (рассмотренные в § 5.8) в дискретном канале без памяти были получены Шенноном, Галлагером и Берлекэмпом (1967). Теорема кодирования для каналов с конечным числом состояний была впервые доказана Галлагером (1958) при, в некотором отношении, более жестких условиях, а в более сильной форме она была доказана Блекуэллом, Брейманом и Томасяном (1958). Показатель экспоненты случайного кодирования для каналов с конечным числом состояний и его исследование, проведенное в § 5.9, принадлежат Юд-кину (1967). Теорема 5.9.3 была доказана Галлагером (1964). Единственная граница сферической упаковки, которая пока что получена, для каналов с конечным числом состояний, принадлежит Кеннеди (1963) и относится к одному классу двоичных каналов.
ПРИЛОЖЕНИЕ 5А
