4.3. Эффективное кодирование дискретных сообщении

Применим полученные результаты к проблеме кодирования дискретных сообщений. Пусть А - источник последовательности элементарных сообщений (знаков) с объемом алфавита К и производительностью Н(А). Для передачи по дискретному каналу нужно преобразовать сообщения в последовательность кодовых символов В так, чтобы эту кодовую последовательность можно было затем однозначно декодировать^*. Для этого необходимо, что-бы скорость передачи информации от источника к коду I'(А, В) равнялась производительности источника Н(А). Но, с другой стороны, согласно (4.24) I(А, В)≤Н'(В). Следовательно, необходимым условием для кодирования является Н(В)^Н' (А) или, обозначая через Т_К длительность кодового символа, а через Т_С длительность элементарного сообщения, Н(В)≥H'(A), или

v_K H(B)≥v_CH(a)

где v_K = 1/Т_K - число кодовых символов, a v_C = 1/T_C - число сообщений, передаваемых в секунду. Будем рассматривать для простоты только двоичный код, при котором алфавит В состоит из символов 0 и 1. Тогда Н(В)≤log 2 = 1 бит. Поэтому необходимое условие (4.26) сводится к тому, что

^* (В этом параграфе предполагается, что последовательность кодовых символов принимается без ошибок. Поэтому рассматриваемую ниже теорему часто называют теоремой кодирования для канала без помех. )

Но отношение (4.27) представляет среднее число кодовых символов, приходящихся на одно элементарное сообщение. Таким образом, для возможности кодирования и однозначного декодирования сообщения необходимо, чтобы среднее число двоичных символов на сообщение было не меньше энтропии Н (А). Является ли это условие достаточным?

Одна из основных теорем теории информации утверждает, что юно "почти достаточно". Точнее, содержание теоремы кодирования для источника заключается в том, что, передавая двоичные символы со скоростью v_K, симв./с, можно закодировать сообщения так, чтобы передавать их со скоростью

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

Эта теорема почти тривиальна, если источник передает сообщения независимо и равновероятно. В этом случае Н(a) = log К и, если еще к тому же K - целая степень двух (K = 2ⁿ), то Н(А) = n. С другой стороны, используя для передачи каждого сигнала последовательность из n двоичных символов, получим 2ⁿ = K различных последовательностей и можем каждому сигналу сопоставить одну из кодовых последовательностей, так что (4.28) выполняется даже при ε = 0.

Таким же образом можно закодировать сообщения любого источника с объемом алфавита К, затрачивая υ₀ = log K двоичных символов на элементарное сообщение. Если, однако, сообщения передаются не равновероятно, и (или) не независимо, то H(A)<log K и сформулированная теорема утверждает, что возможно более экономное кодирование, с затратой υ≈H(A) символов на сообщение. Относительная экономия символов при этом окажется равной (υ₀-υ)/υ₀≈χ [см. (4.9)]. Таким образом, избыточность определяет достижимую степень "сжатия сообщения".

Доказательство этой теоремы можно найти в [9]. Здесь же ограничимся несколькими примерами.

Так, если элементарными сообщениями являются русские буквы (K = 32 = 2⁵) и они передаются равновероятно и независимо, то Н(А) = 5 бит. Каждую букву можно закодировать последовательностью из пяти двоичных символов, поскольку существует 32 такие последовательности. Разумеется, таким же равномерным кодом можно закодировать и буквы в связном русском тексте, и именно так часто поступают на практике. Но можно обойтись значительно меньшим числом символов на букву. Как указывалось выше, для русского литературного текста Н(A) m 1,5 бит и, следовательно, возможен способ эффективного кодирования (или кодирования со сжатием сообщения), при котором в среднем на букву русского текста будет затрачено немногим более 1,5 двоичных символа, т. е. на 70% меньше, чем при примитивном коде.

Существует довольно много способов сжатия сообщений или сокращения избыточности текста. Так, напр, эта фр. напис. сок-ращ. и тем не м. мож. надеят., что чит-ль пойм, ее прав. В предыдущей фразе удалось уменьшить число букв (а следовательно и символов, если ее кодировать равномерным кодом) почти на. 40%.

Другая возможность заключается в том, чтобы кодировать не- отдельные буквы, а целые слова. В достаточно большом словаре имеется около 10 000 слов, содержащих в среднем по 7 букв. Считая, что в среднем каждое слово может иметь 3 грамматические формы, нам придется закодировать около 30 000 типичных слов. Если применить равномерный код, то на каждое слово придется затратить 15 двоичных символов (2¹⁵ = 32 768). Таким образом, а среднем на букву придется немногим больше двух символов, т. е. сжатие достигнет почти 60% вместо теоретических 70%. Слова, не вошедшие в словарь, придется передавать обычным способом, затрачивая пять символов на букву. Но поскольку такие нетипичные слова будут встречаться крайне редко, это не внесет заметной поправки в общий баланс.

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

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

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

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

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