ИТОГИ И ВЫВОДЫ

Основным результатом этой главы была теорема кодирования для канала с шумами. Вначале была изучена простая задача проверки гипотез, в которой одно из двух кодовых слов передавалось по дискретному каналу без памяти, и затем был изучен случай большого числа кодовых слов. Для случая большого числа кодовых слов было установлено, что основная трудность состоит в том, что не ясно, как выбирать кодовые слова. Решение этой проблемы было найдено с помощью построения верхней границы для средней по ансамблю кодов вероятности ошибки и последующего указания на то, что, по крайней мере, один код из ансамбля должен иметь столь же малую вероятность ошибки, как и средняя вероятность. При исследовании этой верхней границы было найдено, что при любой скорости меньшей, чем пропускная способность канала, существуют коды с любой длиной блока для которых Скорость R здесь понимается как умноженное на число двоичных символов, поступающих на кодер за время передачи одного символа в канале. Также была найдена более точная граница вероятности ошибки при малых Затем было установлено, что имеется нижняя граница для вероятности ошибки наилучших кодов, с заданными для которой вероятность ошибки убывает экспоненциально по и было показано, что показатели этих экспонент совпадают при скоростях, близких к пропускной способности, и в пределе при Нижние границы были выведены только для случая двоичного симметричного канала. Наконец, было показано, что каналы с конечным числом состояний имеют того же типа экспоненциальную верхнюю границу для вероятности ошибки. Ни один из полученных здесь результатов не дает прямого указания на то, как строить кодеры и декодеры; это является предметом следующей главы. В гл. 7 и 8 полученные здесь результаты будут распространены на недискретные каналы.

ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ И ССЫЛКИ

Теорема кодирования для канала с шумами принадлежит Шеннону (1948) и, несомненно, является самым значительным результатом в теории информации. Первое строгое доказательство этой теоремы для дискретных каналов без памяти было дано Файнстейном (1954) и вскоре после этого более простые доказательства были предложены Шенноном (1957) и Вольфовицем (1957). Впервые Файнстейн (1955) показал, что стремится к нулю экспоненциально по N при фиксированной скорости Граница случайного кодирования, граница сферической упаковки и тот факт, что они экспоненциально совпадают при скоростях, близких к пропускной способности, были впервые получены Элайсом (1955) в частных случаях двоичного симметричного канала и двоичного канала со стиранием. Фано (1961) использовал методы случайного кодирования, развитые Шенноном, и производящих функций моментов, для получения показателя экспоненты случайного кодирования и для эвристического вывода границы сферической упаковки для общего дискретного канала без памяти. Граница случайного кодирования для процедуры с выбрасыванием и большинство свойств показателя экспоненты случайного кодирования были получены Галлагером (1965). Нижние границы для вероятности ошибки (рассмотренные в § 5.8) в дискретном канале без памяти были получены Шенноном, Галлагером и Берлекэмпом (1967). Теорема кодирования для каналов с конечным числом состояний была впервые доказана Галлагером (1958) при, в некотором отношении, более жестких условиях, а в более сильной форме она была доказана Блекуэллом, Брейманом и Томасяном (1958). Показатель экспоненты случайного кодирования для каналов с конечным числом состояний и его исследование, проведенное в § 5.9, принадлежат Юдкину (1967). Теорема 5.9.3 была доказана Галлагером (1964). Единственная граница сферической упаковки, которая пока что получена, для каналов с конечным числом состояний, принадлежит Кеннеди (1963) и относится к одному классу двоичных каналов.