Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Ризаев Уч. пособие по ТИ.doc
Скачиваний:
3
Добавлен:
01.07.2025
Размер:
1 Мб
Скачать
☆

Глава4. Кодирование информации

  • Префиксные коды

  • Основные теоремы кодирования

  • Оптимальное кодирование

  • Код Шеннона-Фано

  • Блочное кодирование

  • Код Хаффмана

  • Совмещенный способ построения кода Хаффмана

  • Сжатие информации

Вопросы и упражнения

Лабораторная работа. Кодирование информации

Префиксные коды

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

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

Символ

Код1

Код2

Код3

Код4

x1

0

0

0

0

x2

0

00

01

10

x3

1

1

011

110

x4

11

11

0111

111

Видно, что код 1 не дает однозначного декодирования. Код 2, хотя и выражен более тонким образом, обладает тем же недостатком, так как при передаче последовательности x1x1, она будет закодирована в 00, что совпадает с кодовым словом для x3. Коды 1 и 2 не являются, таким образом, различимыми. Код 3 также не позволяет производить однозначное декодирование. Однозначно декодируемыми являются только коды обладающие свойством префикса.

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

Коды 1,2,3 не обладают свойством префикса, а код 4 обладает.

Например, код 0111100 декодируется в последовательность символов x1x4x2x1.

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

Разобьем дерево на уровни и тогда каждому коду можно присвоить определённый вес.

- вес j-кода j=1,М, где М- число допустимых кодов, k - уровень дерева. Дерево может иметь и более двух ветвей D>2.

Тогда вес j - кода будет равен , где D - основание системы счисления.

Основные теоремы кодирования

Теорема 1. Неравенство Крафта.

Неравенство является необходимым и достаточным условием существования кодовых слов, соответствующих концевым узлам дерева с длинами, равными kj.

Теорема 2. Средняя длина кода меньшая, чем является недостижимой ни при каком кодировании.

Доказательство:

Покажем, что

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

Доказательство.

Пусть D=2, M=20. В этом диапазоне заведомо имеется одно целое число

Теорема 4. Существуют такие способы кодирования для достаточно длинного сообщения x1, x2, … , что средняя длина кодового слова может быть сделана сколь угодно близкой к .

Доказательство. Возьмем произвольное целое N>1 и разобьем последовательность x1, x2, … , на группы N случайных величин. Каждую такую группу будем рассматривать как одну случайную величину Y=( x1, x2, … ,xN) и применим к ней теорему (3).

,

где HY=NHX , средняя длина слова, передающего сообщение Y=( x1, x2, … ,xN). Очевидно, что , тогда получим

Увеличивая N, Величину 1/N можно сделать сколь угодно малой, что доказывает теорему.