Файл: прикладная теория информации.pdf

38
3. ЭФФЕКТИВНОЕ КОДИРОВАНИЕ ДЛЯ ДИСКРЕТНОГО
ИСТОЧНИКА БЕЗ ПАМЯТИ
3.1. Условия взаимной однозначности алфавитного кодирования
Кодирование связано с преобразованием выходных символов дискретного источника (событий источника) в последовательностьсимволов заданного кодо- вого алфавита. На рис. 3.1 изображена математическая модель системы передачи информации с кодированием.
Рис. 3.1. Система передачи информации с кодированием
Определение 3.1. Код источника – это множество дискретных последова- тельностей всех событий, представленных символами кодового алфавита.
В качестве кодового алфавита часто используются символы двоичного
{0,1} или бинарного алфавита {1, −1}. Например, слово ???? = (????
1
????
2
… ????
7
) =
= (−1 − 1 − 111 − 11) представлено символами бинарного алфавита источ- ника, ???? = 2. В этом случае размерность кодового алфавита равна двум. На прак- тике размерность (обозначается ????) кодового алфавита может быть большей.
Определение 3.2. Последовательности символов называются кодовыми словами или кодовыми векторами.
В результате кодирования осуществляется однозначное присвоение кодо- вых слов символам источника. Недопустимо присваивать разным символам ис- точника одинаковые кодовые слова. Код должен удовлетворять условию сингу- лярности (лат. Singularis – единственный), когда каждое кодовое слово соответ- ствует уникальному символу дискретного источника. Как правило, кодовые слова получаются n -кратным расширением источника одиночных символов.
Определение 3.3. Длина кода n (значность) – число символов кодового слова.
Говорят, что двоичное слово ???? = (????
1
????
2
… ????
????
) = (1110010) имеет длину
???? = 7, слово ???? = (????????????????????????) – длину ???? = 6. Параметр n определяет следующие виды кодов:
– равномерные (блоковые), n = const;
– неравномерные, n = var.
Код можно представить в виде списка, в котором каждому кодовому слову

39 однозначно соответствует символ источника.
Пример 3 .1 . Пусть для передачи сообщения «????????????????????» используется сле- дующие кодовые слова равномерного кода:
???? → (000),
???? → (010),
???? → (001),
???? → (111),
???? → (100).
Для построения этого кода использовались символы двоичного источника
???? = {0,1}. Кодированному сообщению «????????????????????» соответствует последователь- ность независимых символов ????
????
∈ {0,1}:
???????????????????? → (111000001010100).
Пусть символы источника ????
????
появляются с вероятностью
????
????
=
1 2
. Количе- ство информации в этом сообщении равно
???? = log
2 1
????(????
1
…????
15
)
= log
2 1
(
1 2
)
15
= − log
2 2
−15
= 15 бит.
Пример 3 .2. В случае неравномерного кодирования используем код со словами:
???? → (00),
???? → (10),
???? → (010),
???? → (110),
???? → (111).
Сообщению «????????????????????» соответствует последовательность двоичных сим- волов:
???????????????????? → (1100001010111).
Из примеров 3.1 и 3.2 следует очевидный вывод: неравномерный код бо- лее эффективный. Для передачи сообщения «????????????????????» с использованием не- равномерного кода потребовалось 13 двоичных символов (чипов). При равно- мерном кодировании того же сообщения затрачено 15 чипов.
Правила кодирования должны отвечать следующим требованиям:
1) Необходимо добиваться высокой вероятности однозначного (правиль- ного) декодирования исходной информации дискретного источника по

40 закодированной последовательности;
2) Число чипов, требуемых на один символ источника, должно быть мини- мальным.
3.2. Эффективное кодирование
Основная идея эффективного кодирования базируется на использовании коротких кодовых слов для событий, характеризующихся высокой вероятно- стью. В этом случае уменьшается средняя длина закодированных сообщений.
При этом должно обеспечиваться однозначное декодирование (желательно без введения дополнительных символов – меток синхронизации между кодовыми словами).
Определение 3.4. Код является эффективным, если он имеет наименьшую возможную среднюю длину кодового слова.
Многие алгоритмы эффективного кодирования в качестве однозначно де- кодируемого кода используют префиксные моментальные коды.
Определение 3.5. Префиксный код – это множество кодовых слов, в кото- ром каждое кодовое слово не совпадает с началом более длинного слова.
3.2.1. Моментальные коды
Определение 3.6. Если процесс однозначного декодирования каждого ко- дового слова осуществляется сразу же после приема всех символов кодового слова и принимается решение о соответствующем символе источника, то код с таким свойством называется моментальным.
Коды, рассмотренные в примерах 3.1 и 3.2, относятся к моментальным.
Критерием моментальности префисного кода является то, что ни одно слово не совпадает с началом более длинного кодового слова.
3.2.1.1. Код с запятой
Примером моментального кода служит код с запятой. Нуль в конце слова означает запятую, разделяющую кодовые слова. При получении нуля момен- тально принимается решение о декодировании соответствующего символа. На рис. 3.2 показан пример множества слов кода с запятой:
????
1
→ (0),
????
2
→ (10),
????
3
→ (110),
????
4
→ (1110),
????
5
→ (11110).
Рис. 3.2. Код с запятой

41
Например, последовательность ???? = (1111001101101011100) декодиру- ется как ????
5
????
1
????
3
????
3
????
2
????
4
????
1
. Очевидно, введение разделительного символа умень- шает эффективность кодирования. На практике желательно использовать коды без запятой, когда при установленной синхронизации возможна передача коди- рованной информации без специального разделения кодовых слов. Кодовую конструкцию моментального кода удобно иллюстрировать с помощью кодового дерева.
3.2.2. Кодовое дерево
Кодовое дерево имеет начальную точку отсчета (корень). Из этой точки изображаются одна или две ветви. Ветвям присваиваются значения символов 0 и 1. Слева располагаются ребра, соответствующие символу 0, справа – ребра, со- ответствующие символу 1. Ветви имееют промежуточные узлы. Затем из этих узлов строятся еще одна или две ветви и т. д. пока не будет изображен конечный узел, соответствующий каждому символу источника – кодовому слову. Кодовое слово получается в результате движения по ветвям от корня и записи символов
0 и 1 ветвей. Для однозначно декодируемого кода не должно быть конечных уз- лов на более длинном пути, заканчивающемся узлом, т. е. кодовым словом. Рас- смотрим пример изображения кодового дерева для кодового алфавита {0, 1}.
Пример 3 .3 . Пусть символы источника задаются множеством ???? =
= {????, ????, ????, ????, ????}. Для кодирования источника используем префиксный код со словами:
???? → (00),
???? → (10),
???? → (010),
???? → (110),
???? → (111).
На рис. 3.3 показано кодовое дерево неравномерного кода. Черные точки
(конечные узлы дерева) соответствуют словам кода.
Рис. 3.3. Кодовое дерево неравномерного префиксного кода

42
Изображение кодового дерева равномерного кода из примера 3.1 ???? →
→ (000), ???? → (010), ???? → (001), ???? → (111), ???? → (100) показано на рис. 3.4.
Рис. 3.4. Кодовое дерево равномерного кода
Изображение множества слов кода с запятой {????
1
→ (0), ????
2
→ (10), ????
3
→
→ (110), ????
4
→ (1110), ????
5
→ (11110)} показано на рис. 2.5.
Рис. 3.5. Кодовое дерево кода с запятой
3.3. Неравенство Крафта
Для ответа на вопрос, будет ли предлагаемое множество кодовых слов кода при декодировании точно соответствовать исходной информации источника, применяется неравенство Крафта и проверка свойства однозначного декодиро- вания с использованием кодового дерева. Все кодовые слова должны представ- ляться конечными узлами дерева.
Определение 3.7. Для построения однозначно декодируемого q-ичного кода, содержащего ???? кодовых слов с длинами ????
1
, ????
2
, … , ????
????
, необходимо и до- статочно, чтобы выполнялось неравенство Крафта:
∑
????
−????
????
≤ 1,
????
????=1
(3.1)

43 где ???? обозначает число разных символов (размерность) кодового алфавита, ???? – число символов источника.
Для двоичного алфавита (???? = 2) неравенство Крафта записывается как
∑
????
−????
????
= ∑
2
−????
????
= 2
−????
1
+ 2
−????
2
+ ⋯ + 2
−????
????
≤ 1.
????
????=1
????
????=1
(3.2)
Из (3.2) следует, что неравенство Крафта для двоичного равномерного кода, когда ???? = ????
1
= ⋯ = ????
????
, примет следующий вид:
∑
2
−????
????
≡ ????2
−????
≤ 1.
????
????=1
(3.3)
Например, для ???? = 3, ???? = 2 имеем:
∑
2
−????
????
= 2
−????
1
+ 2
−????
2
+ 2
−????
3
=
3
????=1 2
−2
+ 2
−2
+ 2
−2
= 3 ∙ 2
−2
=
3 4
< 1.
Рассмотрим примеры применения неравенства Крафта.
Пример 3.4. Используются следующие кодовые слова длиной ???? = 3 рав- номерного кода:
???? → (000),
???? → (010),
???? → (001),
???? → (111),
???? → (100).
Удовлетворяет ли код неравенству Крафта?
Решение. Так как ????
1
= ????
2
= ⋯ = ????
5
= ???? = 3, то
????2
−????
= 5 ∙ 2
−3
=
5 8
< 1.
Данный код однозначно декодируемый.
Замечание. Для двоичного равномерного кода максимальное число кодовых слов равно
???? = 2
????
Это значение позволяет закодировать 2
????
символов блокового источника.
Пример 3 .5 . Пусть для кодирования используется префиксный код со словами:
???? → (00),
???? → (10),
???? → (010),
???? → (110),
???? → (111).

44
Удовлетворяет ли код неравенству Крафта?
Решение. Так как ????
1
= ????
2
= 2, ????
3
= ????
4
= ????
5
= 3, ???? = 5, то
∑ 2
−????
????
=
1 4
+
1 4
+
1 8
+
1 8
+
1 8
=
7 8
< 1.
5
????=1
Данный код также однозначно декодируемый.
3.4. Средняя длина кодового слова
Определение 3.8. Мерой эффективности кода является его средняя длина кодовых слов:
????
????
= ∑
????
????
????
????=1
????
????
, (3.4) где ???? – число символов источника с n-кратным расширением источника одиноч- ных символов;
????
1
, … , ????
????
– вероятности символов источника с n-кратным расширением;
????
1
, … , ????
????
– длина соответствующих кодовых слов.
Пример 3 .6 . Пусть для передачи сообщения «????????????????????» используются следующие кодовые слова равномерного кода:
???? → (000),
???? → (010),
???? → (001),
???? → (111),
???? → (100).
Для построения кода использовались символы двоичного источника ???? =
{0,1}. Пусть код характеризуется вероятностями ????
1
= ????
2
= ????
3
= ????
4
= ????
5
==
1 5
Код имеет среднюю длину
????
????
= ∑
1 5
5
????=1
????
????
=
1 5
3 + ⋯ +
1 5
3 =
15 5
= 3.
Пример 3 .7 . Пусть для передачи сообщения «????????????????????» используются следующие кодовые слова неравномерного кода:
???? → (00),
???? → (10),
???? → (010),
???? → (110),
???? → (111).

45
Для построения этого кода использовались символы двоичного источника
???? = {0,1}. Пусть код характеризуется вероятностями ????
1
= ????
2
= ????
3
= ????
4
= ????
5
=
=
1 5
. Код имеет среднюю длину
????
????
= ∑
1 5
5
????=1
????
????
=
1 5
2 +
1 5
2 +
1 5
3 +
1 5
3 +
1 5
3 = 2,6.
Очевидно, более эффективной является та информационная система, кото- рая использует коды с минимально возможными длинами кодовых слов.

46
???? = ∑ ????
????
????
????=1
????
????
=
1 2
∙ 2 +
1 4
∙ 2 +
1 8
∙ 3 +
1 16
∙ 3 +
1 16
∙ 3 =
9 4
= 2,25.
В рассмотренном примере для средней длины кодового слова выполняется соотношение 1:
???? = 2,25 > ???? = 1,875.
Соотношение 2. Пределы средней длины кодового слова.
Можно получить кодирование источника двоичным кодом, у которого средняя длина кодового слова удовлетворяет выражению
???? ≤ ???? ≤ ???? + 1. (3.6)
При этом выражение
???? ≤ ???? + 1 (3.7) определяет максимально возможное значение средней длины двоичного эффек- тивного кода. Если вернуться к примеру 3.8, для кода имеем
???? = 1,875 < ???? = 2,25 < ???? + 1 = 1,875 + 1.
3.5. Задания для самостоятельного выполнения
1. Построить кодовое дерево кода
???? = {????
1
, ????
2
, … , ????
8
}
, где ????
1
= (01), ????
2
=
= (00), ????
3
= (111), ????
4
= (110), ????
5
= (100), ????
6
= (1011), ????
7
= (10101), ????
8
=
= 10100.
2. Построить кодовое дерево кода
???? = {????
1
, ????
2
, … , ????
11
}, где ????
1
=
= (0001), ????
2
= (001), ????
3
= (01), ????
4
= (010), ????
5
= (0111), ????
6
= (0110), ????
7
=
= (1000), ????
8
= (1001), ????
9
= (101), ????
10
= (110), ????
11
= (111).
3. Является ли код
???? → (01),
???? → (10),
???? → (011),
???? → (101). однозначно декодируемым? Построить кодовое дерево этого кода.
4. Является ли код
???? = {????
1
, ????
2
, … , ????
8
} = {????
1
= (01), ????
2
= (00), ????
3
=
= (111), ????
4
= (110), ????
5
= (100), ????
6
= (1011), ????
7
= (10101), ????
8
= (10100)} однозначно декодируемым?
5. Является ли код
???? = {????
1
, ????
2
, … , ????
11
} = {????
1
= (0001), ????
2
= (001), ????
3
=
= (01), ????
4
= (010), ????
5
= (0111), ????
6
= (0110), ????
7
= (1000), ????
8
= (1001), ????
9
=
= (101), ????
10
= (110), ????
11
= (111)}. однозначно декодируемым?