Эффективное кодирование неравновероятных символов сообщений

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

Очевидно, что эффективное кодирование будет оптимальным, если неравномерное распределение вероятностей появления символов алфавита источника сообщений с помощью определенным образом выбранного кода переводят в равновероятное распределение вероятностей появления независимых элементов кодовых символов. В этом случае среднее количество инфор­мации, приходящееся на один элемент символа кода, будет максимальным. Для определения вида кода, удовлетворяющего этому требованию, можно рассмот­реть «функцию стоимости» (цены передачи символов сообщения) в виде:

, (2.5)

где P(x_i) — вероятность появления i -го символа алфавита исходного кодируемого сообщения;

m — объем алфавита;

W_i — стоимость передачи i -го символа алфавита, которая пропорциональна длине кодового слова.

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

1. Длина кодового символа (n_i)должна быть обратно пропорциональна вероятности появления соответствующего символа исходного кодируемого сообщения (x_i);

2. Начало более длинного кодового символа не должно совпадать с началом более короткого (для возможности разделения кодовых символов без применения разделительных знаков);

3. В длинной последовательности элементы символов кода должны быть независимы и равновероятны.

Теоретическое обоснование возможности эффективного кодирования передаваемых по каналу сообщений обеспечивает теорема, доказанная К. Шенноном и которая носит название первая теорема Шеннона или основная теорема Шеннона о кодировании для каналов без помех. Эта теорема гласит, что если источник сообщений имеет энтропию Н [бит/символ], а канал обладает пропускной способностью С [бит/сек] (пропускная способность характеризует максимально возможное значение скорости передачи информации), то всегда можно найти способ кодирования, который обеспечит передачу символов сообщения по каналу со средней скоростью

[символ/сек],

где ε — сколь угодно малая величина.

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

[символ/сек].

Эта теорема часто приводится в иной формулировке: сообщения источника сообщений с энтропией Н всегда можно закодировать последовательностями элементов кодовых символов с объемом алфавита k так, что среднее число элементов символов кода на один символ кодируемого сообщения (l _ср.) будет сколь угодно близко к величине H / log₂ k, но не менее ее.

Не вдаваясь в доказательство этой теоремы, отметим, что эта теорема показывает возможность наилучшего эффективного кодирования, при котором обеспечивается равновероятное и независимое поступление элементов символов кода, а следовательно, и максимальное количество переносимой каждым из них информации, равное log₂ k (бит/элемент). К сожалению, теорема не указывает конкретного способа эффективного кодирования, она лишь говорит о том, что при выборе каждого элемента кодового символа необходимо чтобы он нес максимальное количество информации, а, следовательно, все элементы символов кода должны появляться с равными вероятностями и взаимнонезависимо.

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