§ 1.6. Постановка задачи кодирования дискретных источников равномерными кодами

Обозначим через А некоторое множество, состоящее из элементов: Назовем его алфавитом кода источника. Элементы множества А будем называть кодовыми символами.

Последовательность кодовых символов называется кодовым словом, а любое семейство кодовых слов — кодом над алфавитом А.

Пример 1.6.1. Пусть А—множество букв русского алфавита (включая пробел). Любая последовательность букв заданной длины является кодовым словом длины над алфавитом А. Так, есть слово длины 8 -пробел). Другим примером кодового алфавита является множество десятичных цифр, включая пробел. Следующие последовательности являются примерами двух кодовых слов длины 5 и 4 соответственно.

Пример 1.6.2. Пусть двоичный алфавит. Множество последовательностей является кодом объема 4 над двоичным алфавитом. Это пример кода, слова которого имеют разную длину. Множество последовательностей также является двоичным кодом объема 4.

Определение 1.6.1. Код называется разномерным, если все его слова имеют одинаковую длину это число называется длиной кода. Если хотя бы два кодовых слова имеют различные длины, то код называют неравномерным.

Количество различных слов равномерного кода длины не превосходит числа различных D-ичных последовательностей длины Количество различных слов неравномерного кода с максимальной длиной кодовых слов не превышает (см. задачу 1.6.1).

Определение 1.6.2. Кодированием сообщений ансамбля X посредством кода называется отображение (необязательно взаимно однозначное) множества сообщений в множество кодовых слов.

Пример 1.6.3. Пусть Возможны следующие способы кодирования посредством двоичных кодов:

кодирований однозначно. В пп. б) и в) приведены два различных способа кодирования с одним и тем же множеством кодовых слов.

Рассмотрим теперь кодирование дискретного источника. Для того чтобы лучше понять основные проблемы, возникающие при кодировании, мы рассмотрим несколько подробных примеров.

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

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

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

При кодировании можно условиться о том, что всякое слово, не содержащееся в словаре, кодируется так же, как слово «ошибка». При декодировании вместо этих слов будет воспроизводиться слово «ошибка».

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

Заметим, что при побуквенном кодировании все слова телеграмм могут быть однозначно (безошибочно) закодированы.

Изложенная в примере 1.6.4 идея может быть применена для кодирования произвольных дискретных источников равномерными кодами.

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

Описанный метод кодирования дискретного источника мы будем называть равномерным кодированием. Ошибкой равномерного кодирования является событие, состоящее в появлении неоднозначного кодируемого блока.

При равномерном кодировании количество D-ичных кодовых символов, приходящихся на одно сообщение, равно

Определение 1.6.3. Число

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

Количество двоичных символов на сообщение естественно измерять числом а не Очевидно, что эти два числа совпадают, когда число кодовых слов равно В остальных случаях именно первое из этих чисел равно количеству двоичных символов на сообщение (см. задачу 1.6.2).

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

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

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

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

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

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

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

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

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

Оценим теперь скорость кодирования. Для этого необходимо оценить число

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

где При этом скорость кодирования

стремится к при больших

Возьмем, например, Если положить и найти из уравнения то получим Вероятность ошибки при кодировании последовательности сообщений длины т. е. вероятность появления такой последовательности, количество единиц в которой удовлетворяет неравенству можно оценить, правда весьма грубо, с помощью неравенства Чебышева (см. (1.2.14))

откуда получается Использование для оценки асимптотической формулы Муавра-Лапласа [6] дает при больших

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

Ниже мы покажем, что энтропия определяет наименьшее возможное значение скорости кодирования и согласно определению 1.6.4 дает величину скорости создания информации при равномерном кодировании.

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

1. Для любого и произвольного положительного найдутся и код со скоростью кодирующий отрезки сообщений длины для которого вероятность ошибйчне больше 6. Такое утверждение называется прямой теоремой кодирования.

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

Вначале, в §§ 1.7-1.9, мы будем рассматривать задачу равномерного кодирования дискретных источников. Затем, в мы рассмотрим задачу неравномерного кодирования. В заключение этой главы будут сопоставлены эти две задачи и соответствующие методы кодирования.