- •Предисловие
- •Лекция 1. Информация. Начальные понятия и определения
- •1. Информация и данные
- •2. Адекватность и формы адекватности информации
- •3. Качество информации
- •4. Понятие об информационном процессе
- •5. Формы представления информации
- •6. Преобразование сообщений
- •Лекция 2. Необходимые сведения из теории вероятностей
- •1. Понятие вероятности
- •2. Сложение вероятностей независимых несовместных событий
- •3. Умножение вероятностей независимых совместных событий
- •4. Нахождение среднего для значений случайных независимых величин
- •5. Понятие условной вероятности
- •6. Общая формула для вероятности произведения событий
- •7. Общая формула для вероятности суммы событий
- •Лекция 3. Понятие энтропии
- •1. Энтропия как мера неопределенности
- •2. Свойства энтропии
- •3. Условная энтропия
- •Лекция 4. Энтропия и информация
- •1. Объемный подход к измерению количества информации
- •2. Энтропийный подход к измерению количества информации
- •Лекция 5. Информация и алфавит
- •Лекция 6. Постановка задачи кодирования. Первая теорема Шеннона.
- •Лекция 7. Способы построения двоичных кодов. Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды.
- •1. Постановка задачи оптимизации неравномерного кодирования
- •00100010000111010101110000110
- •2. Неравномерный код с разделителем
- •3. Коды без разделителя. Условие Фано
- •00100010000111010101110000110
- •00100010000111010101110000110
- •4. Префиксный код Шеннона–Фано
- •5. Префиксный код Хаффмана
- •Лекция 8. Способы построения двоичных кодов. Другие варианты
- •1. Равномерное алфавитное двоичное кодирование. Байтовый код
- •2. Международные системы байтового кодирования текстовых данных. Универсальная система кодирования текстовых данных
- •3. Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе
- •4. Блочное двоичное кодирование
- •101010111001100010000000001000000000000001
- •5. Кодирование графических данных
- •6. Кодирование звуковой информации
- •Лекция 9. Системы счисления. Представление чисел в различных системах счисления. Часть 1
- •1. Системы счисления
- •2. Десятичная система счисления
- •3. Двоичная система счисления
- •4. 8- И 16-ричная системы счисления
- •5. Смешанные системы счисления
- •6. Понятие экономичности системы счисления
- •Лекция 10. Системы счисления. Представление чисел в различных системах счисления. Часть 2.
- •1. Задача перевода числа из одной системы счисления в другую
- •2. Перевод q p целых чисел
- •3. Перевод p q целых чисел
- •4. Перевод p q дробных чисел
- •6. Перевод чисел между 2-ичной, 8-ричной и 16-ричной системами счисления
- •Лекция 11. Кодирование чисел в компьютере и действия над ними
- •1. Нормализованные числа
- •2. Преобразование числа из естественной формы в нормализованную
- •3. Преобразование нормализованных чисел
- •4. Кодирование и обработка целых чисел без знака
- •5. Кодирование и обработка целых чисел со знаком
- •6. Кодирование и обработка вещественных чисел
- •Лекция 12. Передача информации в линии связи
- •1. Общая схема передачи информации в линии связи
- •2. Характеристики канала связи
- •3. Влияние шумов на пропускную способность канала
- •Лекция 13. Обеспечение надежности передачи информации.
- •1. Постановка задачи обеспечения надежности передачи
- •2. Коды, обнаруживающие одиночную ошибку
- •3. Коды, исправляющие одиночную ошибку
- •Лекция 14. Способы передачи информации в компьютерных линиях связи
- •1. Параллельная передача данных
- •2. Последовательная передача данных
- •3. Связь компьютеров по телефонным линиям
- •Лекция 15. Классификация данных. Представление данных в памяти компьютера
- •1. Классификация данных
- •2. Представление элементарных данных в озу
- •Лекция 16. Классификация структур данных
- •1. Классификация и примеры структур данных
- •2. Понятие логической записи
- •Лекция 17. Организация структур данных в оперативной памяти и на внешних носителях
- •1. Организация структур данных в озу
- •2. Иерархия структур данных на внешних носителях
- •3. Особенности устройств хранения информации
- •Контрольные вопросы
- •Список литературы
5. Префиксный код Хаффмана
Способ оптимального префиксного двоичного кодирования был предложен Д. Хаффманом. Схему построения кодов Хаффмана мы рассмотрим на том же примере, на котором рассматривали построение кодов Шеннона–Фано.
Пусть имеется первичный алфавит , состоящий из шести знаков:, где. Пусть вероятности появления этих знаков в сообщениях таковы:,,,,и. Расположим эти знаки в таблице в порядке убывания вероятностей.
Создадим новый вспомогательный алфавит , объединив два знака с наименьшими вероятностями и заменив их одним (новым) знаком. Вероятность этого нового знака будет равна сумме вероятностей тех исходных знаков, которые в него вошли. Остальные знаки исходного алфавита включим в новый вспомогательный алфавитбез изменений. Расположим знаки полученного алфавитадля удобства в порядке убывания. В алфавитена 1 знак меньше, чем в исходном алфавите.
Продолжим таким же образом создавать новые алфавиты до тех пор, пока в последнем полученном вспомогательном алфавите не останется два знака. В нашем случае получается 4 (четыре) вспомогательных алфавита: ,,и. Результат действий по созданию вспомогательных алфавитов можно представить в видетабл. 8:
Табл. 8. Вспомогательные алфавиты
|
, |
, |
, , |
, ,, |
|
, |
, , |
, |
, , |
|
, |
, |
, , |
|
|
, |
, |
|
|
|
, |
|
|
|
|
|
|
|
|
Для удобства можно было работать только с таблицей вероятностей, не обращая внимание на содержание алфавитов (табл. 9):
Табл. 9. Таблица вероятностей
| ||||
| ||||
|
| |||
|
|
| ||
|
|
|
| |
|
|
|
|
|
Последовательность предпринятых действий по объединению и упорядочиванию знаков для формирования вспомогательных алфавитов можно показать стрелками (табл. 10).
Табл. 10. Последовательность действий при формировании вспомогательных алфавитов
| ||||
| ||||
|
| |||
|
|
| ||
|
|
|
| |
|
|
|
|
|
Теперь эту таблицу продублируем, однако, для простоты (чтобы освободить место для письма) не будем переписывать вероятности, подразумевая, что они остаются на своих местах – в своих клетках. Вместо вероятностей будем писать коды. Приписывать очередной разряд будем справа, как и в случае кодов Шеннона–Фано.
Последовательность действий (в направлении, обратном направлению стрелок) выглядит следующим образом.
Символам алфавита присвоим сверху вниз 0 и 1, то есть символы ииз алфавитаполучат коды «0» и «1» соответственно (табл. 11):
Табл 11. Построение кода Хаффмана
|
|
|
|
0 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Символ (то есть символиз алфавита) наследует по стрелке код «1». Коды дляистроим следующим образом. Первый слева разряд их кода наследуется по стрелке от– то есть «0». Вторые слева их разряды будут «0» и «1» сверху вниз дляисоответственно (табл. 12):
Табл 12. Построение кода Хаффмана (продолжение)
|
|
|
1 |
0 |
|
|
|
00 |
1 |
|
|
|
01 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Аналогично строятся коды и далее (табл. 13).
Табл 13. Построение кода Хаффмана (продолжение)
00 |
00 |
00 |
1 |
0 |
10 |
10 |
01 |
00 |
1 |
11 |
11 |
10 |
01 |
|
010 |
010 |
11 |
|
|
0110 |
011 |
|
|
|
0111 |
|
|
|
|
Последовательность действий
Итак, полученные коды выглядят так (табл. 14):
Табл 14. Код Хаффмана
-
Знак
Код
0.30
00
0.20
10
0.20
11
0.15
010
0.10
0110
0.05
0111
Полученные коды удовлетворяют условию Фано, то есть являются префиксными и, следовательно, не требуют разделителя.
Найдем среднюю длину полученного кода:
.
Таким образом, для кодирования одного символа первичного алфавитапотребовалось в среднем 2.45 символов вторичного (двоичного) алфавита, как и в случае кода Шеннона–Фано.
Избыточность полученного двоичного кода равна:
,
то есть избыточность также около 2.5.
Посмотрим, является ли этот код оптимальным. Нулей в полученных кодах – 8 штук, а единиц – 9 штук. Таким образом, вероятности появления 0 и 1 существенно сблизились (0.47 и 0.53 соответственно). Следовательно, полученный код оптимален.
Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона–Фано становится очевидной, если сравнить избыточности этих кодов для какого-либо естественного языка. При кодировании русского алфавита кодами Хаффмана средняя длина кода оказывается равной , при этом избыточность кода равна, то есть не превышает 1, что заметно меньше избыточности кода Шеннона–Фано.
Код Хаффмана важен в теоретическом отношении, поскольку в теории информации доказано, что он является самым экономичным из всех возможных, то есть ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана.
Таким образом, можно заключить, что существует способ построения оптимального неравномерного алфавитного кода.
Код Хаффмана, кроме теоретического, имеет и практическое значение. Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) – широко применяются в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.