Кодирование дискретных источников

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

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

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

Далее сформулируем предельные возможности статистических ко­дов.

Рассмотрим вначале последовательность В_п = (b⁽¹⁾,...,b⁽ⁿ⁾) сле­дующих друг за другом п элементов дискретного источника {В,р(b)}. Каждый элемент выбирается из алфавита {bi,...,bк}, и, таким образом, имеются К^п последовательностей различной длины п, которые могут появляться на выходе источника. Поставим задачу кодирования этих последовательностей в слова кода с фиксированной длиной. Если ко­довый алфавит состоит из m символов и если длина каждого кодового слова равна l, то существуют m^l различных кодовых слов. Следова­тельно, если нужно сопоставить различные кодовые слова разным по­следовательностям источника (если необходимо взаимно однозначное отображение), то получаем . Таким образом, для кодов с фиксированной длиной при декодировании необходимо иметь по мень­шей мере log К/ log M кодовых символов на одну букву источника.

Если мы хотим в целях эффективного кодирования использовать меньше, чем log К/ log M символов на одну букву источника, то, оче­видно, нужно ослабить требование того, чтобы всегда была возмож­ность полного однозначного соответствия.

В подтверждение сказанному рассмотрим пример [1]. Предполо­жим, что на телеграфе введена автоматическая обработка телеграмм,

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

Рассмотрим вначале побуквенное кодирование. В этом случае ис­пользуется код, содержащий 2⁶ = 64 кодовых слова, и каждой букве телеграммы сопоставляется некоторое кодовое слово. Пусть использу­ется равномерный код со словами в 6 двоичных символов. При этом в ЗУ можно поместить N/6 букв. Если считать, что средняя длина те­леграммы — 20 слов, а средняя длина слова 8 букв, то в ЗУ можно поместить примерно N/960 телеграмм.

Второй способ кодирования состоит в том, что выделяется специ­альный словарь, например, из 2¹³ = 8192 слов (достаточно практически для любой телеграммы). Каждое слово может быть закодировано с помощью двоичной последовательности длиной 13 символов. В этом случае в ЗУ можно записать N /260 телеграмм, т.е. в 3-4 раза боль­ше, чем в первом случае. (При кодировании и декодировании можно считать слово, отсутствующее в словаре, «ошибкой».)

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

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

Постановка задачи равномерного кодирования источника. Пусть А = { а₁,..., а_т } — алфавит кода источника — некоторое мно­жество, состоящее из m элементов; а_i — кодовые символы. Последо­вательность кодовых символов задает кодовое слово, любое семейство кодовых слов — это код над алфавитом А. (Примеры: множество букв русского алфавита, множество цифр и т.д.) Код называется равномер­ным, если все его слова имеют одинаковую длину l, называемую длиной (значностью) кода. В противном случае код называется неравномер­ным. Количество различных слов равномерного кода длины l не пре­восходит т¹ —числа различных m -ичных последовательностей длины l.

Определение. Кодированием сообщений ансамбля В посредством кода А называется отображение множества сообщений В^п в множество кодовых слов.

Предлагается следующий способ равномерного кодирования [1]: множество всех последовательностей сообщений источника длиной п делится на два подмножества, одно из которых создается всеми по­следовательностями — блоками длины п, однозначно отображаемыми кодовыми словами. Это подмножество называется множеством одно­значно кодируемых и декодируемых блоков. Остальные блоки образуют второе подмножество, которому соответствует одно единственное ко­довое слово. Длина l всех кодовых слов одинакова; она определяет­ся числом М кодовых слов: l — наименьшее целое, удовлетворяющее неравенству m^l ≥ М. Процесс кодирования и декодирования заключа­ется в разбиении последовательности сообщений на выходе источника на блоки длиной п и сопоставлении каждому блоку соответствующего кодового слова длины l. Ошибкой процедуры декодирования при этом является событие, состоящее в появлении неоднозначно кодируемого блока. Количество m -ичных кодовых символов, приходящихся на од­но сообщение, определяется соотношением l/n ≥ log M/ log m. Число log M/n = R для заданных значений М и п называется скоростью рав­номерного кодирования источника. Скорость R измеряется в двоичных символах на сообщение. Таким образом, существо равномерного ко­дирования заключается в выборе множества однозначно кодируемых n -последовательностей сообщений.

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

Величина H может рассматриваться как скорость.создания инфор­мации, если может быть доказано следующее важное утверждение:

Для любого R > Н и произвольного положительного δ найдется значение п и код со скоростью R, для которого вероятность ошибки не превосходит δ. (Прямая теорема кодирования источника.)