Кодирование сообщений источника и текстов. Равномерное кодирование. Дерево кода

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

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

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

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

Кодом называется отображение

( 6.2)

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

Кодируемая буква алфавита А	Кодовое слово

Такая таблица называется кодовой таблицей. В качестве примера можно привести таблицу кодирования алфавита из цифрвосьмеричной системы счисления словами из упоминавшегося ранее бинарного алфавита . В данном случае отображение (6.2) имеет вид.

Кодируемый знак	Кодовое слово
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

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

Знак	Кодовое слово (в десятичной системе счисления)	Кодовое слово (в шестнадцатеричной системе счисления)
…	…
a	97	61
b	98	62
c	99	63
d	100	64
e	101	65
f	102	66
g	103	67
h	104	68
i	105	69
j	106	6A
…	…

Кодирование слов. Отображение (6.2) позволяет перейти от кодирования отдельных знаков (букв конечного алфавита) к кодированию слов. Если - слово, состоящее из знаков (полученное конкатенацией знаков), то кодомслова(по определению) является конкатенация кодовзнаков, образующих слово, т. е.. Например, с применением таблицы ASCII кода (см. последнюю таблицу) словоhead будет закодировано последовательностью 10410197100 при использовании десятичной системы счисления или последовательностью 68656164 - в шестнадцатеричной.

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

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

Недостаточность количества знаков в алфавите является препятствием применения простой замены для кодирования (не обеспечивается инъективность и, следовательно, однозначность декодируемости при). Для устранения этой проблемы используются множества новых, "составных" объектов из степенейалфавита. Множествосостоит из упорядоченных последовательностей элементов из(векторов) длины. Число элементовмножестваравно. Например, для двоичного алфавитаимеем. Таким образом, взяв достаточно большую степень, можно получить нужное количество элементов вторичного алфавита.

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

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

Рис. 6.4. Процедура кодировании слов с использованием кодовой таблицы

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