13

КАДР

Глава 4. Алфавитное кодирование

Рассмотрим два алфавита А = { ,…, }, B = { ,…, }. Обозначим символом А = ,…, слово в алфавите А. Пусть ,…, – слова в алфавите B.

Определение. Соответствие вида

– ,

– ,

…

– .

называют схемой кодирования и обозначают символом Σ.

Каждому слову А = ,…, в алфавите А сопоставляется слово B = = ,…, в алфавите B в соответствии с заданной схемой кодирования Σ. Слово B является кодом слова A.

Слова ,…, называются элементарными кодами. Такое кодирование называют алфавитным.

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

Множество слов в алфавите A есть сообщение, а множество сопоставляемых им кодовых слов в алфавите В – код сообщения. При передаче кода сообщения по каналу связи и последующем приеме кода необходимо восстановить сообщение, то есть выполнить декодирование. При реализации алфавитного кодирования декодирование возможно не для всех кодов сообщений, то есть не для всех схем кодирования Σ.

КАДР

4.1. Критерий однозначности кодирования

Нас интересуют все слова в алфавите А (их бесконечное множество). При заданной схеме кодирования Σ слова в алфавите А порождают слова в алфавите В. Если между словами этих множеств имеет место взаимно-однозначное соответствие, то кодирование однозначно, то есть по коду В однозначно восстанавливается слово А.

Рассмотрим пример однозначного кодирования. А = { , }, B = { , }, Σ:

Пусть В = . Имея в виду заданную схему кодирования, заключаем, что перед обязательно стоит . Тогда получаем следующую расшифровку: ( )( ) ( ), то есть соответствующее слово в алфавите А представляется в виде

.

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

Определение. Представим слово В в виде В = , тогда слово называется началом или префиксом В, а слово – окончанием слова В.

Определение. Схема Σ обладает свойством префикса, если для любых i, j (1  i, j  r, i  j) слово не является префиксом слова .

Теорема 4.1. Если схема кодирования Σ обладает свойством префикса, то представляемое ей кодирование однозначно.

Доказательство. Допустим противное. Кодирование не однозначно , то есть существует слово В в алфавите В, допускающее две расшифровки. Это значит, что для слова В существуют два разбиения на элементарные коды:

B = ,…, ,

B = ,…, .

Пусть = ,…, = , а  . В силу равенства первых (n – 1) элементарных кодов равны и представляемые ими начальные отрезки расшифровок слова B. Значит, равны и оставшиеся отрезки расшифровок. В таком случае одно из слов , является префиксом другого, что противоречит условию теоремы. Ч.Т.Д.

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

Пусть В = ,…, – слово в алфавите В. Обозначим через – слово, получающееся из В путем перечисления его символов в обратном порядке (путем обращения слова В): = ,…, , :

,

…

.

Для рассматриваемого примера Σ:

и :

то есть обладает свойством префикса, следовательно, алфавитное кодирование, задаваемое схемой , однозначно.

КАДР

Теорема 4.2. Если схема кодирования Σ либо схема кодирования обладает свойством префикса, то кодирование, задаваемое схемой Σ( ), однозначно.

Доказательство. Пусть произвольное слово А в алфавите А закодировано словом В с использованием схемы Σ( ), для которой не выполняется свойство префикса, а для (Σ) это свойство выполняется. Выделим элементарные коды в соответствии со схемой Σ( ), заменим их кодами схемы (Σ). Согласно теореме 4.1 полученное слово имеет единственную расшифровку. Следовательно, единственную расшифровку имеет слово В. Ч.Т.Д.

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

А = { , , }, B = { , , }. Задана схема Σ:

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

Будем считать, что в рассматриваемой схеме кодирования Σ все элементарные кодовые слова (элементарные коды) попарно различны.

Пусть l(B) – длина слова В, а L( ) – длина элементарного кода, L есть длина схемы Σ, L = l( ,…, ).

Определение. Разложение элементарных кодов вида

= ,…, , p  0, будем называть нетривиальным разложением.

Тривиальное разложение: = , = = , где  – пустое слово.

В нетривиальном разложении не может заканчиваться элементарным кодом, а не может начинаться элементарным кодом.

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

A = { , , , , }, B = { , , }, Σ:

= ( )( )

= ( )( ) = ( )( )

= ( )( )

= ( )( ) = ( )( ) = ( )( )

= ( )( )( ) = ( )( ) = ( ) ( )

.

КАДР