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

71
Окончание табл. 4.2
Таким образом, передаваемому сообщению соответствует последователь- ность ссылок (слов):
{(0, 0, Д) (0, 0, Е) (0, 0, К) (0, 0, О) (4, 1, И) (0, 0, Р) (4, 1, В) (0, 0, А)
(0, 0, Н) (6, 1, Е) (0, 0, _) (12, 3, А)}.
Метод кодирования LZ77 приводит к сжатию тогда, когда затраты на ко- дирование оказываются в среднем меньше по сравнению с кодированием кодом
ASCII.
Сравним затраты на кодирование слова «КОДА». Фраза, состоящая из че- тырех букв, кодированная ASCII-кодом записывается ???? = 32 битами. Кодовое слово (12, 3, А) → «КОДА» требует только ???? = 24 бит. Эффективность сжатия равна
???? =
32 − 24 32
= 0,25, что соответствует 25%. Для длинных текстов кодирование методом LZ77 позво- ляет получить эффективность сжатия в пределах ???? = 50– 60%.
Для длинных текстов LZ77кодирование практически полностью устраняет избыточность. В этом случае средняя длина кодового слова на один символ ис- точника (текста) стремится к энтропии текста.
4.5.2. Декодирование LZ77-кода
LZ77-декодер осуществляет декодирование каждого кодового слова по идентичному словарю буфера поиска, который создается на приемной стороне.
При поступлении на вход декодера первых пяти кодовых слов (см. пример 4.8) получаем символы передаваемого сообщения (табл. 4.3).
Таблица 4.3
Декодирование LZ77-кода
№ п/п
Кодовое слово
(
????, ????, ????)
Буфер поиска
Сообщение
1
(0, 0, Д)
–
Д
2
(0, 0, Е)
Д
Е
3
(0, 0, К)
ДЕ
К
4
(0, 0, О)
ДЕК
О
5
(4, 1, И)
ДЕКО
ДИ
13
ДЕКОДИРОВА-
НИЕ_КОДА
Нет собщения
Слово не переда- ется

72
В слове (4, 1, И) число 4 – это указатель ???? позиции в обратном направле- нии от текущего принимаемого символа до записанного уже ранее в буфер по- иска образца. Символ И (указатель ???? в слове (4, 1, И)) – это следующая буква декодируемого сообщения. Последующий процесс декодирования показан в продолжении таблицы.
Окончание табл. 4.3
Декодирование LZ77-кода
Недостатком алгоритма LZ77 является конечный размер буферов памяти.
Типовой размер памяти буфера поиска фраз составляет величину ????
????
= 2 12
=
= 4096. Размер памяти буфера для записи кодируемой информации ????
????
= 2 4
Если образец повторяется, но предыдущий пример его является более удален- ным в прошлом, чем длина буфера поиска, сделать ссылку становится невозмож- ным. Кроме того, большие размеры адреса ???? и длины ???? образца могут потребо- вать относительно большого числа бит для их записи при формировании кодового слова (ссылки).
4.5.3. Алгоритм кодирования Лемпеля – Зива – Уэлча
Модификацией алгоритма эффективного кодирования LZ77 является алго- ритм LZ78, также разработанный Зивом и Лемпелем в 1978 г. В алгоритме LZ78 фактически буферы памяти не имеют конечный размер и изменена структура ко- дового слова. Модификацией алгоритма LZ78 является метод LZW предложен- ный Т. Уэлчем (Terry Welsh) в 1984 г.Метод LZW используется в следующих растровых файловых форматах сжатия изображений:
– GIF (Graphic Interchange Format) – формат обмена графическими дан- ными, находит применение в сети Интернет;
– TIFF (Tagged Image File Format) – формат представления графической информации, находит применение при подготовке печатных документов.
Кодирование по алгоритму LZW применяется в методах сжатия JPEG-LS,
PNG, в векторном файловом формате PDF (Portable Document Format).
Алгоритм кодирования LZW, как и LZ77, основывается на свойстве меж- символьной зависимости символов данных, повторяемости образцов. В процессе кодирования – декодирования создается словарь образцов. Как и в LZ77, образцы
6
(0, 0, Р)
ДЕКОДИ
Р
7
(4, 1, В)
ДЕКОДИР
OВ
8
(0, 0, А)
ДЕКОДИРОВ
А
9
(0, 0, Н)
ДЕКОДИРОВА
Н
10
(6, 1, Е)
ДЕКОДИРОВАН
ИЕ
11
(0, 0, _)
ДЕКОДИРОВАНИЕ
_
12
(12, 3, А)
ДЕКОДИРОВАНИЕ_
КОДА
13
Слово не принято
ДЕКОДИРОВАНИЕ_КОДА
Нет собще- ния

73 соответствуют символам, словам, фразам, предложениям и пр. Процесс сжатия осуществляется посредством использования ссылок, представляемых в виде ин- дексов. На приемной стороне также создается словарь, который используется для декодирования кодированной информации синхронно с кодером.
Отличие метода кодирования LZW от LZ77 состоит в следующем:
1. Процесс кодирования начинается с загрузки в словарь (буфер поиска) образцов некоторого множества базовых символов алфавита, слов, фраз.
2. Образцы индексируются, например, десятичным номером.
3. При передаче символов сообщения, если в словаре находится нужный образец, отправляется только его индекс.
4. Процесс формирования образцов носит динамический характер.
Пример 4.9 . Необходимо передать сообщение ДЕКОДЕР_ КОДА с по- мощью алгоритма кодирования LZW.
Решение
1. Множество базовых символов алфавита передаваемого сообщения, со- стоящее из семи символов
{Д, Е, К, О, Р, _, А}, формирует начальный словарь.
2. Символам начального словаря соответствуют десятичные индексы:
Д → 1, Е → 2, К → 3, О → 4, Р → 5, _ → 6, А → 7.
3. Первая буква сообщения передается в виде ссылки (кодового слова)
(1).
4. Так как последовательности символов ДЕ в базовом словаре нет, в сло- варь записывается новый образец в виде числа (8), т. е. ДЕ → (8).
5. Далее передается символ Е в виде кодового слова
(2), и последовательность символов ЕК записывается в словарь под очередным ин- дексом (9).
6. Далее продолжаются однобуквенные передачи символов К, О и запись в словарь последовательностей КО, ОД.
7. Затем передается индексом (8) сразу два символа ДЕ, т. к. в словаре уже имеется этот образец.
По мере расширения словаря передаются все более длительные последова- тельности символов сообщения. Длина кодового слова также увеличивается.
Процесс кодирования представлен данными табл. 4.4 и 4.5.
Таблица 4.4

74
Словарь
Индекс
Словарь образцов
1
Д
2
Е
3
К
4
О
5
P
6
_
7
A
8
ДЕ
9
ЕК
10
KO
11
OД
12
ДЕР
13
Р_
14
_К
15
КОД
16
ДА
17
А...
Таблица 4.5
Кодирование методом LZW
Сообще- ние
Д
Е
К
О
ДЕ
Р
_
КО
Д
А
Кодовые слова
1 2
3 4
8 5
6 10 1
7
Метод кодирования LZW приводит к сжатию тогда, когда затраты на ко- дирование оказываются в среднем меньше по сравнению с кодированием кодом
ASCII. Затраты на кодирование сообщения ДЕКОДЕР_ КОДА ASCII-кодом со- ставляют
???? = 12 × 8 = 96 бит.
Кодирование LZW-кодом требует использования
???? = 10 × 8 = 80 бит.
Эффективность сжатия
???? =
96−80 96
≅ 0,16, что соответствует 16 %.
Как видно, даже на малой длине сообщения достигается сжатие. В типовом случае LZW-кодирование обеспечивает сжатие текстового файла исполняемого кода примерно наполовину исходного размера.

75
4.5.4. Декодирование LZW-кода
LZW-декодер осуществляет декодирование каждого кодового слова по идентичному словарю, который создается на приемной стороне. При поступле- нии на вход декодера последовательности значений индексов (см. пример 4.9)
1, 2, 3, 4, 8, 5, 6, 10, 1, 7, для каждого индекса выбираются соответствующие последовательности симво- лов из словаря образцов (табл. 4.6). В результате получаем принятое сообщение.
Таблица 4.6
Декодирование LZW-кода
Кодовые слова
1 2
3 4
8 5
6 10 1
7
Сообще- ние
Д
E
K
O
ДE
Р
_
КО
Д
А
4.6. Задания для самостоятельного выполнения
1. Источник формирует символы
???? = {????
1
, ????
2
} = {????, ????} c вероятностями
{????
1
=
9 10
, ????
2
=
1 10
}. Имеется блоковый источник с двукратным расширением
????
2
= {(????????), (????????), (????????), (????????)} = {????
1
, ????
2
, ????
3
, ????
4
, }. Для кодирования блокового ис- точника применяется следующий префиксный код:
????
1
→ (0),
????
2
→ (10),
????
3
→ (110),
????
4
→ (111).
Вычислить:
1.1. Энтропию источника.
1.2.Энтропию блокового источника.
1.3.Среднюю длину слова декодируемого кода.
1.4 Среднюю длину слова на один символ источника ????.
2. Источник формирует символы
???? = {????
1
, ????
2
} c вероятностями {????
1
=
=
9 10
, ????
2
=
1 10
}. Имеется блоковый источник с трехкратным расширением ????
3
=
{????
1
, ????
2
, ????
3
, ????
4
, ????
5
, ????
6
, ????
7
, ????
8
}. Для кодирования блокового источника применяется следующий префиксный код:
????
1
→ (1),
????
2
→ (011),
????
3
→ (010),

76
????
4
→ (001),
????
5
→ (00011),
????
6
→ (00010),
????
7
→ (00001),
????
8
→ (00000).
Вычислить:
2.1. Энтропию источника.
2.2. Энтропию блокового источника.
2.3.Среднюю длину слова декодируемого кода.
2.4. Среднюю длину слова на один символ источника
????.
3. Размерность алфавита источника
???? = {????
1
, ????
2
, … , ????
6
} равна ???? = 6. По- строить дерево Хаффмена для следующих значений вероятностей появления символов источника:
????
1
= 0,05, ????
2
= 0,15, ????
3
= 0,05, ????
4
= 0,4, ????
5
= 0,2, ????
6
= 0,15.
4. Записать слова кода Хаффмена для задания 3.
5. Декодировать последовательность
???? = 1110111011110101101, ис- пользуя полученный код Хаффмена.
6. Источник символов
{????, ????, ????, ????, ????} характеризуется следующими вероят- ностями:
????
????
=
1 5
, ????
????
=
1 5
, ????
????
=
1 5
, ????
????
=
1 5
, ????
????
=
1 5
Построить дерево Хаффмена.
7. Записать слова кода Хаффмена для задания 6.
8. Источник формирует символы
???? = {????
1
, ????
2
} c вероятностями {????
1
=
9 10
, ????
2
=
1 10
}. Имеется блоковый источник с трехкратным расширением ????
3
=
= {????
1
, ????
2
, ????
3
, ????
4
, ????
5
, ????
6
, ????
7
, ????
8
}. Построить дерево Хаффмена блокового источника.
9. Записать слова кода Хаффмена для задания 8.
10. Источник формирует символы алфавита
???? = {????
1
, ????
2
, … , ????
8
} =
=
{
????, ????, ????, ????, ????, !,∗, ????} c вероятностями их появления
{????
1
= 0,5, ????
2
= 0,1, ????
3
= 0,1, ????
4
= 0,1, ????
5
= 0,06, ????
6
= 0,04,
????
7
= 0,05, ????
8
= 0,05}.
Построить кодовое дерево Хаффмена.
11. Записать код Хаффмена для задания 10.
12. Для передачи звука используется 8 уровней квантования. Распределе- нию уровней отвечает гистограмма со следующими значениями:
{????
1
= 0,3, ????
2
= 0,23, ????
3
= 0,15, ????
4
= 0,08, ????
5
= ????
6
= ????
7
= ????
8
= 0,06}.
Построить кодовое дерево Хаффмена.

77 13. Записать слова кода Хаффмена для задания 12.
14. Вычислить среднюю длину кода, кодирующего звук для задания 12.
15. Вычислить энтропию источника звука для задания 12.
16. Для передачи изображения используется 6 уровней квантования. Рас- пределению уровней отвечает гистограмма со следующими значениями:
{????
1
= 0,27; ????
2
= 0,21; ????
3
= 0,23; ????
4
= 0,15; ????
5
= ????
6
= 0,07}.
Построить кодовое дерево Хаффмена.
17. Записать слова кода Хаффмена для задания 16.
18. Вычислить среднюю длину кода, кодирующего изображение для зада- ния 16.
19. Вычислить энтропию источника изображения для задания 16.
20. Используйте алгоритм кодирования LZ77 для сжатия сообщения ТЕО-
РИЯ ИНФОРМАЦИИ – ТЕОРИЯ КОДИРОВАНИЯ.
21. Оцените эффективность сжатия для задания 20.
22. Используйте алгоритм кодирования LZW для сжатия сообщения
ТЕОРИЯ ИНФОРМАЦИИ – ТЕОРИЯ КОДИРОВАНИЯ.
23. Оцените эффективность сжатия для задания 22.
5. КАНАЛЫ БЕЗ ПАМЯТИ И ПЕРЕДАЧА ИНФОРМАЦИИ
5.1. Комбинирование источников

78
(связанные источники)
До текущего изучения информационных понятий рассматривались дис- кретные источники, формирующие сообщения отвечающие свойству независи- мости. Однако, реальные информационные объекты не описываются независи- мыми процессами. Читая текст на любом языке, можно увидеть зависимость между рядом стоящими буквами, словами. Например, выраз на роднай мове
«Статут Вялікага княства Літоўскага» подтверждает зависимость не только между буквами, но и словами. Текущие вероятности символов, букв, слов зависят от предыдущих. Количественная оценка источников, с учетом взаимной связи информационных составляющих, будет отличаться от оценки, основанной на независимости последовательных событий. При теоретическомописании по- добных связанных информационных процессов используют модель передачи ин- формации в виде комбинированных источников.
Не теряя общего представления о комбинировании ???? источников, ограни- чимся рассмотрением двух источников, ???? = 2.
Определение 5.1. Под комбинированием источников ???? = {????
1
, ????
2
, … , ????
????
} и
???? = {????, ????
2
, … , ????
????
} понимают источник (????, ????), который характеризуется множе- ством {????, ????}.
Источник (????, ????) включает в себя пары совместных событий (????, ????) из ???? и ????, т. е. в пару (????, ????) включается один символ из источника ???? и один символ из источника ????.
Замечание. Источник с обозначением (????, ????) называется источником произ- ведения двух источников.
Вероятности ????(????, ????) пар совместных событий удовлетворяют выражению нормировки
∑ ∑ ????(????
????
, ????
????
) = 1.
????
????=1
????
????=1
Если ???? = {????
1
, ????
2
}, ???? = {????
1
, ????
2
}, то комбинированный источник – произве- дение четырех пар совместных событий
(
????, ????) = {(????
1
, ????
1
), (????
1
, ????
2
), (????
2
, ????
1
), (????
2
, ????
2
)}.
Условие нормировки вероятностей ????(????
????
, ????
????
) совместных событий этих ис- точников записывается как
∑ ∑ ????(????
????
, ????
????
) = ∑[????(????
????
, ????
1
) + ????(????
????
, ????
2
)]
2
????=1
=
2
????=1 2
????=1
= ????(????
1
, ????
1
) + ????(????
1
, ????
2
) + ????(????
2
, ????
1
) + ????(????
2
, ????
2
) = 1.

79
5.2. Взаимная информация
Пусть источники ???? и ???? последовательно выдают символы ????
????
∈ ???? и ????
????
∈ ????.
Источники связаны между собой, например, каналом. Вход канала – это источ- ник ????, выход канала – это источник ????. Обозначим ????(????
????
, ????
????
) вероятность совмест- ного появления событий (????
????
, ????
????
) комбинированного источника (????, ????). Процесс взаимодействия этих источников в виде передачи-приема информации от ???? →
???? также можно характеризовать вероятностью ????(????
????
, ????
????
).
Определим количество информации ????
????
????
,????
????
об отдельном событии (
????
????
, ????
????
) ис- точника произвеления (????, ????). Cовместна вероятность (см. формулы (2.9, 2.10) появления двух событий ????
????
и ????
????
источника (
????, ????) равна
????(????
????
, ????
????
) = ????(????
????
|????
????
)????(????
????
) = ????(????
????
|????
????
)????(????
????
).
Количество передаваемой источником (????, ????) информации можно найти, используя количественную характеристику ????
????
????
,????
????
, выражаемую в виде логариф- мической функции (2.21)
????
????
????
,????
????
= log
2 1
????(????
????
,????
????
)
= − log
2
????(????
????
, ????
????
) =
=
− log
2
????(????
????
|????
????
)????(????
????
) = − log
2
????(????
????
|????
????
)????(????
????
).
????
????
????
,????
????
= − log
2
????(????
????
|????
????
) − log
2
????(????
????
) = ((− log
2
????(????
????
|????
????
) − log
2
????(????
????
)) бит, где ????(????
????
) и ????(????
????
) – значения априорных вероятностей, соответственно, источни- ков ???? и ????.
Введем обозначения ????(????
????
) = −log
2
????(????
????
) – количество информации о со- бытии ????
????
источника
???? и ????(????
????
) = −log
2
????(????
????
) – количество информации о событии
????
????
источника
????.
Тогда можно записать следующее выражение:
????
????
????
,????
????
= − log
2
????(????
????
|????
????
) + ????(????
????
) = (− log
2
????(????
????
|????
????
) + ????(????
????
)) бит.
Далее отдельно рассмотрим составляющие последнего выражения
????
????
????
,????
????
= − log
2
????(????
????
|????
????
) + ????(????
????
), (5.1)
????
????
????
,????
????
= − log
2
????(????
????
|????
????
) + ????(????
????
). (5.2)
Выражение (5.1) можно представить иначе, записав его в виде
????
????
????
,????
????
= − log
2
????(????
????
|????
????
) − ????(????
????
) + ????(????
????
) + ????(????
????
). (5.3)

80
Так как (−????(????
????
)) = log
2
????(????
????
), то (5.3) преобразуется в
????
????
????
,????
????
= − log
2
????(????
????
|????
????
) + log
2
????(????
????
) + ????(????
????
) + ????(????
????
),
Обозначим через −????
????
= −log
2
????(????
????
|????
????
) + log
2
????(????
????
) =
= log
2
????(????
????
)
????(
????
????|
????
????)
= −log
2
????(
????
???? |
????
????)
????(????
????
)
После этого, выражение (5.3) примет вид
????
????
????
,????
????
= −log
2
????(
????
???? |
????
????)
????(????
????
)
+ ????(????
????
) + ????(????
????
) = −????
????
+ ????(????
????
) + ????(????
????
). (5.4)
Определение.5.2. Информационная составляющая
????
????
= log
2
????(????
????
|????
????
)
????(????
????
)
= log
2
????(????
????
|????
????
)
????(????
????
)
количества информации о паре события (????
????
, ????
????
) источника произведения (????, ????) называется взаимной информацией.
Как видно, взаимная информация ????
????
определяется логарифмом от отноше- ния условной (апостериорной) и априорной вероятности.
Таким образом, количество информации комбинированного источника о совместном событии (????
????
, ????
????
) определяется суммой информаций исходных источ- ников с вычетом некоторой составляющей − взаимной информации. Степень не- определенности комбинированного источника уменьшается, что равносильно снижению количества информации, передаваемой таким источником.
Аналогичное рассмотрение составляющей (5.2) приводит к формуле
????
????
????
,????
????
= −log
2
????(
????
????|
????
???? )
????(????
????
)
+ ????(????
????
) + ????(????
????
) = −????
????
+ ????(????
????
) + ????(????
????
) (5.5)
Для пояснения информационного содержания понятия взаимная информа- ция ????
????
вновь рассмотрим взаимосвязь источников.
1. Пусть источники
???? = {????
1
, ????
2
, … , ????
????
} и ???? = {????
1
, ????
2
, … , ????
????
} являются неза- висимыми. Тогда ????(????
????
, ????
????
) = ????(????
????
)????(????
????
)
, а взаимная информация пары событий этих источников определяется выражением
????
????
= log
2
????(
????
????|
????
????)
????(????
????
)
= log
2
????(
????
????|
????
????)
????(????
????
)
.(5.6)
C учетом формулы совместной вероятности (2.9) (????(????
????
, ????
????
) =
????(????
????
|????
????
)????(????
????
)) и выражения ????(????
????
|????
????
) =
????(????
????
,????
????
)
????(????
????
)
, выражение (5.6) равно