Теоремы кодирования для канала связи

 

Пусть – ансамбль равновероятных сообщений источника, – ансамбль соответствующих им кодовых слов длины n, поступающих на вход канала связи с выхода кодера, – множество векторов наблюдения на выходе канала, а – ансамбль решений, которые являются результатом преобразования векторов наблюдений. Данные условия означают, что предпринята попытка передавать по каналу

(3.20)

бит информации на каждый кодовый символ. Параметр R получил наименование скорость передачи или скорость кода. Именно соотношение между этим параметром и пропускной способностью кода C определяет потенциальную достоверность передачи данных по каналу. Данный факт является сущностью двух замечательных теорем Шеннона.

Теорема 3.5.1. (Обратная теорема канального кодирования). При скорости передачи R, большей информационной емкости канала связи C, никакой код не обеспечит произвольно малой вероятности ошибки декодирования, т.е. абсолютно надежной передачи сообщений.

Обратную теорему кодирования можно доказать в самой общей форме, не опираясь на какую-либо конкретную модель канала. Для этого можно воспользоваться неравенством Фано, связывающим остаточную энтропию и вероятность ошибки декодирования.

Доказательство. Пусть для передачи используется код со скоростью , где . Покажем, что при этом полная вероятность ошибочного декодирования больше некоторой положительной константы d.

В предположении, что между сообщениями и кодовыми словами существует взаимно однозначное соответствие, на основании следствия 3.2.2 . Учитывая, что ансамбль решений V есть отображение , на том же основании . Поэтому .

С другой стороны из (3.15) следует , т.е. . Из (3.7) вытекает , а при равной вероятности сообщений , поэтому с учетом (3.20) получаем

.

Рис. 3.3.

Отсюда и из (3.19) имеем , или

. (3.21)

График функции представлен на рис. 3.3, из которого видно, что при всех и вероятность ошибки декодирования не может быть сделана меньше d, где d - значение , обращающее в . Так как при , то , что и доказывает теорему.

Доказанный результат весьма многозначителен, свидетельствуя, что надежная связь при скоростях выше информационной емкости в принципе невозможна. Однако еще более важным окажется устанавливаемый ниже факт, что при скоростях, меньших информационной емкости, в принципе достижима сколь угодно высокая надежность передачи.

Теорема 3.5.2. (Прямая теорема кодирования для ДКБП.) Для дискретного канала без памяти при скоростях R, меньших информационной емкости C, всегда существует код, обеспечивающий сколь угодно малую вероятность ошибочного декодирования.

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

, (3.22)

где множитель в показателе, называемый функцией надежности, не зависит от длины кода и всегда положителен, если скорость кода ниже информационной емкости канала. Величина определяется только свойствами канала и увеличивается с ростом разности информационной емкости канала и скоростью передачи. Из соотношения (3.22) очевидным образом следует, что с ростом длины кода по крайней мере для некоторых лучших кодов вероятность ошибочного декодирования экспоненциально спадает и, следовательно, может быть сделана произвольно малой в обмен на увеличение длины кода.

Верхняя граница средней вероятности ошибки (иногда называемой экспонентой случайного кодирования) является экспоненциально строгой, означая, что для лучших кодов достаточно большой длины она дает очень точное приближение истинной вероятности ошибки декодирования. Следовательно, она может служить верным ориентиром, насколько хорош или плох некоторый конкретный код. Широко распространена практика сравнения вероятности ошибки декодирования подобных кодов с данной границей, чтобы оценить по достоинству характеристики кодов. Графики на рис. 3.4 демонстрируют типичную зависимость от в соответствии с соотношением (3.22), а также типичную форму функции надежности в зависимости от скорости .

Прямая теорема кодирования Шеннона представляет собой типичную математическую теорему существования. Она не дает рецепта построения даже одного подобного хорошего кода. Именно теория кодирования посвящена отысканию путей практической утилизации потенциального качества передачи, провозглашаемой прямой теоремой кодирования.

Отметим, что с учетом доказанного для любых каналов обратного утверждения (теорема 3.5.1) установленный результат говорит о том, что значение информационной емкости C является порогом, превышение которого скоростью R исключает возможность передачи с произвольно высокой надежностью, тогда как условие принципиально гарантирует такую возможность. Напомним в связи с этим уже появлявшееся ранее параллельное наименование для информационной емкости – пропускная способность.