Основы эффективного кодирования

Сформулируем задачу статистического кодирования, которую часто приходится решать в технике документальной электросвязи. Пусть имеется сообщение, записанное с помощью букв некоторого алфавита А={а₁, а₂,...,а_к}, содержащего К букв. Алфавит Аназовем входным. Требуется закодировать это сообщение, т. е. указать правило, которое сопоставляет каждой букве алфавита последовательность из символов «0» и «1». Выбранный код, во-первых, должен обеспечивать возможность однозначного декодирования, т. е. позволять по принятой последовательности символов «0» и «1» однозначно восстановить переданное сообщение (букву). Во-вторых, на передачу сообщения в среднем должно быть затрачено минимальное число нулей и единиц, что позволит передать за единицу времени максимальное число сообщений.

Пример 1. Пусть А= {а₁, а₂, а₃ }. Некоторые возможные коды для букв алфавита А представлены в таблице 3.

Таблица 3- Коды для букв алфавита А

Код 1 не является однозначно декодируемым кодом. Для доказательства этого рассмотрим, например, двоичную последовательность 0101. Она может быть декодирована одним из сообщений: а₂а₁а₂а₁; а₃а₃; а₂а₁а₃; а₃а₂а₁. Код 2 декодируется однозначно, поскольку все кодовые слова этого кода имеют равные длины и различны. Код 3 также однозначно декодируемый, поскольку никакое его кодовое слово не является началом (префиксом) другого кодового слова.

Код, обладающий тем свойством, что никакое более короткое слово не является началом другого более длинного слова кода, называют префиксным. Префиксные коды всегда однозначно декодируемы.

Кодовое дерево для множества кодовых слов. Наглядное графическое изображение множества кодовых слов можно получить, установив соответствие между сообщениями и концевыми узлами двоичного дерева. Пример двоичного дерева изображен на рисунке 1. Две ветви, идущие от корня дерева к узлам первого порядка, соответствуют выбору между «0» и «1» в качестве первого символа кодового слова: левая ветвь соответствует «0», а правая—«1». Две ветви, идущие из узлов первого порядка, соответствуют второму символу кодовых слов, левая означает «0», а правая—«1» и т. д. Ясно, что последовательность символов каждого кодового слова определяет необходимые правила продвижения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению.

	Рисунок 1 - Кодовое дерево для множества кодовых слов

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

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

Вернемся к рассмотренному ранее примеру 1. Пусть вероятность появления в сообщении буквы а₁ равна 0,2; буквы а₂ – 0,3; а₃ - 0,5. Тогда среднее число двоичных символов, приходящихся на одну букву для кода 3 составляет: 0,2*1+0,3*2+0,5*3=2,3, а для кода 2—0,2*2+0,3*2+0,5*2= 2,0, т.е. код 2 в среднем экономичнее кода 3.

Рассмотрим еще один код—код 4, который букве а1 ставит в соответствие 10; а2 - 11; а3 - 0. Среднее число двоичных символов, приходящихся на одну букву этого кода: 0,2*2+0,3*2+0,5*1=1,5, т.е. код 4 экономичнее и кода 3, и кода 2. Спрашивается, можно ли предложить код, который будет экономичнее кода 4? Как построить самый экономичный код для данного сообщения? Ответы на эти и многие другие вопросы дает основная теорема кодирования, сформулированная и доказанная впервые К. Шенноном.

Пусть буквы a_i, i=1, K, входного алфавита А порождаются независимо с вероятностью p_i, т. е. P(a_i)=p_i, некоторым источником сообщений. Количество информации, приходящееся на сообщение a_i, равно –log₂p_i. Среднее количество информации в битах на одно сообщение (букву) обозначается Н(А)и называется энтропией источника сообщений:

(1)

Энтропию Н(А) можно рассматривать как меру «неопределенности» сообщения до того, как оно было принято.

В приведенной ниже основной теореме кодирования устанавливается связь между Н(А) и средним числом l символов «0» и «1» в кодовом слове.

Справедлива теорема, что для любого однозначно декодируемого кода всегда выполняется неравенство l>=H(A) и существует однозначно декодируемый код, для которого выполняется неравенство l<H(A)+1.

Данная теорема имеет глубокий смысл. В частности, из нее следует, что нельзя закодировать сообщение таким образом, чтобы средняя длина кодовых слов была меньше, чем энтропия сообщений. Кроме того, теорема утверждает, что существует кодирование, при котором средняя длина кодового слова немногим отличается от энтропии сообщения. Покажем, что среднее число символов на сообщение можно уменьшить, если кодировать не каждую букву в отдельности, а блоки по п букв из алфавита А. Пусть буквы алфавита А появляются независимо с вероятностями p₁,…, р_к. Множество всех блоков длины п в алфавите А обозначим А^п, Как хорошо известно,

Н(А^п)=пН(А) (2)

Обозначим среднее число «0» и «1», приходящихся на один блок из п букв, взятых из алфавита А, через l_n. Тогда среднее число символов, приходящихся на одну букву алфавита, определяется формулой

l=l_n/n (3)

Также справедлива теорема 2, что при любом сколь угодно малом положительном n можно найти натуральное число N такое, что среднее число сим­волов на одно сообщение l при n>N удовлетворяет неравенству

l < H(A)+1 (4)

Наоборот невозможно найти натуральное число N и однозначно декодируемый код, такие, чтобы выполнялось неравенство

l < H(A) (5)

Доказательство. Эта теорема вытекает из предыдущей теоремы. Подставляя в нее l_n вместо l, получаем

l_n ≤ H(Aⁿ)+1 (6)

Разделив (6) на п и учитывая (2) и (3), получим

Н(А) ≤ l < Н(А)+1/n (7)

Из неравенства (7) следует неравенство (4), если положить n=1/ ε.

В то же время неравенство (5) несовместимо с неравенством (7). Теорема доказана.

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

Поиск по сайту: