Теоремы побуквенного неравномерного двоичного кодирования

1.Прямая теорема

Для алфавита X ={x, p(x)} с энтропией H существует побуквенный неравномерный префиксный двоичный код со средней длиной кодовых слов K ≤ H +1.

2.Обратная теорема

Для любого однозначно декодируемого двоичного кода алфавита X={x, p(x)} с энтропией H средняя длина кодовых слов K удовлетворяет неравенству K ≥ H.

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

H ≤ K ≤ H+1 (4.7)

Первая теорема гарантирует, что при любых самых неблагоприятных статистических характеристиках источника сообщений можно построить неравномерный код длины не больше чем H+1. Вторая теорема говорит о том, что даже при самых «удачных» вероятностях символов первичного алфавита нельзя построить код средней длиной меньше Н. Из этих же теорем вытекает оценка общей эффективности кода: К_ОЭ ≤ 1.

4.4. Передача информации по каналу с помехами

До сих пор мы предполагали, что информация, поступившая от кодера/передатчика в канал связи в точности соответствует информации, принятой приемником/декодером из канала. Наличие помех в канале связи приводит к тому, что часть информации при перемещении по каналу теряется, искажается, зашумляется. Информация, принятая приемником, не полностью снимает неопределенность относительно переданной источником, хотя и уменьшает ее. Если на вход канала связи поступил сигнал u, а с выхода канала принят сигнал v, то говорят о взаимной информации I(u,v).

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

Взаимной (полезной) информацией между сообщениями u и v называется величина I(u,v), определяемая соотношением:

I(u,v) = H(u) – H(u|v), в котором H(u) является энтропией источника информации, а H(u|v) представляет собой потерю информации, принимаемой от источника, обусловленную воздействием помех на передаваемое сообщение.

Используя зависимость (3.11), можно записать иначе:

I(u,v) = H(u) – H(u|v) = H(u) – (H(u,v) – H(v)) = H(u) + H(v) – H(u,v) =

= H(u) + H(v) – (H(u) + H(v|u)) = H(v) – H(v|u)

То есть взаимная информация симметрична:

I(u,v) = H(u) – H(u|v) = H(v) – H(v|u) (4.8)

В формуле (4.8):

H(u) – априорная энтропия источника сообщения;

H(u|v) – апостериорная энтропия, которая учитывает утечку информации при передаче из-за разрушения ее помехами. Иначе называется ненадежность канала;

H(v) – энтропия приемника (выхода) канала;

H(v|u) – характеризует постороннюю информацию, вносимую помехами. Называется энтропия шума.

Формулу (4.8) можно проиллюстрировать следующей схемой.

Пусть передатчик сигнала оперирует алфавитом Nu, порождая сигналы u_i, а приемник сигнала обладает алфавитом Nv и воспринимает сигналы v_i. Тогда по формуле (3.8):

, (4.9)

а по формуле (3.10):

(4.10)

А информация, перемещаемая по каналу связи, определяется в соответствии с формулой (4.8):

(4.11)

Рассмотрим два крайних случая. Первый случай – абсолютно зашумленный канал, то есть выходной сигнал абсолютно не зависит от входного (обрыв связи). При этом в силу независимости сигналов P(v_j|u_i)=P(v_j). Подставив это в формулу (4.11), поменяв порядок суммирования и учтя, что , получим:

То есть в случае обрыва связи полезная информация отсутствует.

Второй случай – отсутствие помех. При этом наблюдается жесткая статистическая связь между входом и выходом: P(v_j|u_i)={1, 0}. Если P(v_j|u_i)=1 то log P(v_j|u_i)=0. Если P(v_j|u_i)=0, то P(v_j|u_i)∙log P(v_j|u_i)=0 (см. доказательство первого свойства энтропии в разделе 3.3). В любом случае H(v|u)=0, а значит I(u,v) = H(v) = H(u). Как видим, в этом случае информация источника доходит до приемника без изменений.

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

, (4.12)

где τ – средняя длительность передачи одного символа первичного алфавита.

Пропускная способность также определяется по аналогии с каналом без помех, с учетом потерь информации.

(4.13)