3.5. Пропускная способность дискретных каналов

Среднее количество информации на символ, передаваемое по каналу, - скорость передачи информации по каналу, найдем из (2.8). Здесь и - множества символов на входе и выходе канала, соответственно. Энтропия зависит лишь от источника входных сигналов, а , и , а значит, - и , вообще говоря, зависят от источника и канала. Пусть - среднее время передачи символа. Максимальное (по всем возможным источникам входных символов с распределениями вероятностей ) количество информации, которое можно передать по каналу в единицу времени,

(3.9)

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

Пропускная способность канала в расчете на символ

(3.10)

Пример 3.5.1. Согласно (2.6) и (3.1), в -ичном симметричном канале без памяти условная энтропия не зависит от передаваемых символов: . Максимальное значение энтропии при равновероятных символах (см. (2.10)). Выражения для и подставим в (2.8). С учетом (3.10) пропускная способность изучаемого канала

(3.11)

Из (3.11) видно, что минимальное значение при . Тогда, согласно (3.1), , так что каждый входной символ равновероятно переходит в любой выходной. Наблюдая выходные символы, нельзя предпочесть ни один из входных. Это означает обрыв канала - передача информации по каналу бесполезна. Тот же результат следует при случайном угадывании входных символов в точке приема. Из (3.11) для двоичного канала максимальное значение бит и при , и при . Случай описывает состояние канала с обратной работой. Тогда при передаче по каналу все переходят в , а - в . Если это заранее известно, при сообщение декодируют по правилу: , .

Из (2.8), (2.10) и (3.10) найдем пропускную способность ичного канала с памятью и аддитивным шумом: . Величина - степень неопределенности в значениях (дополнительная информация в ) при известном . За счет памяти канала эта степень становится меньше, а пропускная способность – больше .

3.6. Теоремы кодирования для дискретного канала

Применим неравномерное кодирование с основанием кода для дискретного источника с объемом алфавита . Пусть - среднее число канальных (кодовых) символов на символ источника. Для неравномерного кода можно обобщить (2.10) и сформулировать как теорему .

Теорема кодирования источника I’. Есть способ кодирования, при котором средняя длина последовательности канальных символов в расчете на символ источника

(3.12)

Нет способа кодирования, при котором .

Согласно (3.12), чем больше (избыточность источника), тем большая скорость кодирования нужна для передачи сообщений без ошибок. Уменьшение этой скорости достижимо при уменьшении избыточности экономным кодированием сообщений. Эта теорема дает условие лишь для средней длины блока канальных символов. Мгновенные значения этой длины могут отличаться от среднего. Источнику с постоянной скоростью нужен буфер для поглощения задержки поступающих сообщений. Накопитель конечной емкости, в конце концов, переполнится. Произойдет потеря информации. Итак, для источников с постоянной скоростью информацию надо кодировать равномерно. Формулировка теоремы I’ изменится так.

Теорема кодирования канала без помех. Есть способ кодирования и декодирования в канале без помех, когда для длины последовательности канальных символов в расчете на символ источника справедливо (3.12), и вероятность ошибки не больше любого как угодно малого .

Здесь вероятность ошибки - вероятность отличия последовательности символов, выданной получателю, от таковой для символов источника. Несмотря на применение канала без помех ошибки в принятом сообщении могут быть из-за специального (равномерного) способа кодирования.

Для кодирования каналов с помехами применяют помехоустойчивые коды. Пусть сообщения источника передаются по каналу с помехами. Канал задан алфавитом ( ) входных (выходных) символов, распределением условных вероятностей и скоростью передачи информации . Длину кода с основанием обозначим через . Правило верного приема (декодирования) задано вероятностями , , где - число разрешенных слов кода. Событие означает, что при передаче слова принято слово из подмножества . Последнее состоит из разрешенного слова и запрещенных слов, соответствующих . Справедлива следующая теорема Шеннона для канала с помехами .

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

(3.13)

Если , то (3.13) неверно при любом и любом большом .

Интерпретируем эту теорему для каналов без памяти и широкого класса каналов с памятью. Сопоставим каждому кодовому слову длины последовательность символов источника длины с энтропией . Условие взаимной однозначности кодирования и декодирования - . Условие отсутствия задержек по времени - ( и - длительности символов источника и канала, соответственно). Найдем связь между скоростями выдачи символов источником и их передачи по каналу : . По теореме, при передаче без ошибок . Допустимая скорость такой передачи по каналу от источника с любой статистикой ограничена: .

Учтем еще и статистику источника, кодируя не только канал, но и источник. Согласно (2.10), информационная емкость алфавита источника . Взаимная однозначность кодирования и декодирования дает , а отсутствие задержек по времени - . Получим неравенство, составляющее основную теорему Шеннона:

(3.14)

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

Теоремы кодирования Шеннона как теоремы существования мало, что говорят о реализации процедур кодирования и декодирования.