- •Энтропия как мера неопределенности физической системы
- •Энтропия сложной системы
- •Условная энтропия
- •Основные свойства условной энтропии
- •Количественные аспекты информации
- •Количество информации, как мера снятой неопределенности
- •Объем информации
- •Взаимная информация
- •Взаимная информация
- •Вопросы
- •Упражнения
- •Лабораторная работа Свойства энтропии
- •Глава 2. Неопределенность непрерывных случайных величин Энтропия непрерывной случайной величины х
- •Количество информации для непрерывных систем
- •Принцип экстремума энтропии и экстремальные распределения
- •Сравнительная оценка сообщений, передаваемых по нормальному закону и равновероятному закону распределений
- •Епсилон -энтропия (ε-энтропия )
- •Вопросы
- •Упражнения
- •Глава3. Глава 3 Передача информации по каналам связи
- •Источники сообщений
- •Избыточность информации
- •Передача информации по каналу связи. Пропускная способность канала
- •Матрица для нахождения условной вероятности
- •Матрица условных вероятностей имеет вид
- •Согласование скорости выдачи информации, выдаваемой источником, с пропускной способностью канала связи
- •Согласование оконечных устройств с каналами связи
- •Вопросы
- •Упражнения
- •Лабораторная работа Скорость передачи информации и пропускная способность каналов связи
- •Глава4. Кодирование информации
- •Префиксные коды
- •Основные теоремы кодирования
- •Оптимальное кодирование
- •Код Шеннона-Фано
- •Блочное кодирование
- •Код Хаффмана
- •Совмещенный способ построения кода Хаффмана Совмещенный способ построения кода Хаффмана – объединение двух процессов: обычного алгоритма построения и метода дерева.
- •Сжатие информации
- •Классификация сжатия по виду информации
- •1) Побуквенное сжатие
- •2) Сжатие слов и словосочетаний
- •3) Сжатие и свертывание текста
- •4) Сжатие массивов чисел
- •5) Сжатие графической информации
- •Вопросы
- •Упражнения
- •Лабораторная работа Кодирование информации
- •Содержание отчета
- •Глава 5. Помехоустойчивое кодирование
- •Коды с обнаружением ошибок
- •1. Код с проверкой на четность.
- •2. Код с постоянным весом.
- •Корректирующие коды
- •Код Хэмминга
- •Проверяем ее
- •Техническая реализация кода Хэмминга
- •Декодирование циклических кодов
- •Вопросы
- •Упражнения
- •Приложение
Глава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 можно сделать сколь угодно малой, что доказывает теорему.
