Для дискретных каналов без помех Шенноном была доказана следующая теорема: если производительность источника , где ε — сколь угодно малая величина, то всегда существует способ кодирования, позволяющий передавать по каналу все сообщения источника. Передачу всех сообщений при осуществить невозможно.

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

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

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

(6.34)

а скорость передачи информации в канале определяется на основании (6.29) отношением

(6.35)

Здесь — средняя длительность кодовой комбинации, которая в общем случае неравномерного кода записывается по аналогии с выражением (6.26) как

(6.36)

где — длительность одного элемента кода и, — число элементов в комбинации, присваиваемой сообщению .

Подстановка в ф-лу (6.35) выражений (6.6) и (6.36) приводит к соотношению

(6.37)

в котором числитель определяется исключительно статистическими свойствами источника, а величина — характеристиками канала. При этом возникает вопрос, можно ли так закодировать сообщения, чтобы скорость передачи R (6.37) достигла своего максимального значения, равного пропускной способности двоичного канала С=1/. Легко заметить, что это условие выполняется, если

(6.38)

что соответствует минимуму и максимуму R. Очевидно, выбор <J() не имеет смысла, так как в этом случае R>C, что противоречит выше доказанному утверждению теоремы Шеннона.

Одним из кодов, удовлетворяющих условию (6.38), является код Шеннона-Фано. Для ознакомления с принципами его построения рассмотрим в качестве примера источник сообщений, вырабатывающий четыре сообщения и с вероятностями: ; ;

Все сообщения выписываются в кодовую таблицу (табл. 6.1) в порядке убывания их вероятностей. Затем они разделяются на две группы так, чтобы суммы их вероятностей то возможности были одинаковыми. В данном примере в первую группу входит сообщение с вероятностью и во вторую — сообщения и с суммарной вероятностью, также равной 0,5.

Комбинациям, которые соответствуют сообщениям первой группы, притаивается в качестве первого символа кода 0, а комбинациям второй группы -1. Каждая из двух групп опять делится на две группы с применением того же правила присвоения символов 0 и 1.

Таблица 6.1

В идеальном случае после первого деления вероятности каждой группы должны быть равны 0,5, после второго деления— 0,25 и т. д. Процесс деления продолжается до тех пор, пока в группах не останется по одному сообщению.

При заданном распределении вероятностей сообщений код получается неравномерным, его комбинации имеют различное число элементов пi, причем, как нетрудно заметить, такой способ кодирования обеспечивает выполнение условия (6.38) полностью для всех сообщений.

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

Важным свойством кода Шеннона—Фано является то, что, несмотря на его неравномерность, здесь не требуются разделительные знаки. Это обусловлено тем, что короткие комбинации не являются началом более длинных комбинаций. Указанное свойство легко проверить на примере любой последовательности:

Таким образом, все элементы закодированного сообщения несут полезную информацию, что при выполнении условия (6.38) позволяет получить максимальную скорость передачи. Она может быть найдена также путем непосредственного вычисления по ф-ле (6.37)'

(6.39)

Для сравнения рассмотрим кодирование тех же четырех сообщений ,, , с применением обычного равномерного двоичного кода. Количество комианаций при этом определяется выражением где n — число элементов в комбинации. Так как m=4, то , а длительность каждой комбинации 2. Производя вычисления по аналогии с (6.39), получим

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

Возможность оптимального кодирования по методу Шеннона—Фано доказывает, что сформулированная выше теорема справедлива, по крайней мере, для источников независимых сообщений. Теорема Шеннона может быть доказана и для общего случая зависимых сообщений.

Одним из способов оптимального кодирования зависимых сообщений является применение так называемых «скользящих» кодов, основная идея которых состоит в том, что присвоение кодовых комбинаций по правилу Шеннона—Фано производится с учетом условных, а не априорных вероятностей сообщений. Число элементов в кодовой комбинации выбирается как , т. е. текущему сообщению присваивается та или иная комбинация в зависимости от того, какие сообщения ему предшествовали.

Необходимо подчеркнуть, что при оптимальном способе кодирования в сигналах, передающих сообщения источника, совершенно отсутствует какая-либо избыточность. Устранение избыточности приводит к тому, что процесс декодирования становится весьма чувствительным к воздействию помех. Это особенно сильно проявляется при оптимальном кодировании зависимых сообщений. Например, в «скользящих» кодах одна единственная ошибка может вызвать неправильное декодирование всех последующих сигналов. Поэтому оптимальные коды применимы только для каналов, в которых влияние помех незначительно.