Файл: Теория информации.pdf

45 ных букв и двухбуквенных сочетаний. Сравнить коды по их эффективности и из- быточности.
Задача 6. Закодировать сообщение методом Шеннона-Фано «Теория ин- формацииКодированияМодуляции».
Задача 7. Построить код Шеннона-Фано для системы из семи букв: A, B, C,
D, E, F, G, вероятности появления которых соответственно 0,1; 0,2; 0,05; 0,3;
0,05; 0,15; 0,15. Определить среднее количество разрядов на одну букву. Декоди- ровать этим кодом последовательность:
10011101001000111101110101111000.
6.4 Контрольные вопросы
1 Что понимают под кодированием сообщения? Приведите примеры про- стейших кодовых сообщений.
2 Дать определение равномерных кодов. Привести пример.
3 Поясните принцип кодирования методом Шеннона-Фано. Привести пример.
4 В чем заключается процесс декодирования сообщения? Привести при- мер.
5 Пояснить сущность понятия «избыточность кода». Дать характеристику видов избыточности.
6 Привести и пояснить формулу для вычисления длины кодовой комби- нации. Привести пример.
7 Поясните за счет чего, обеспечивается сжатие информации при приме- нении эффективного кодирования.
8 Чем определяется минимальная длина кодовой комбинации при приме- нении эффективного кодирования?
9 Что такое оптимальный код? Какой параметр определяет оптимальность кода? Привести пример.
10 В каких случаях избыточность кода является полезным явлением? При- вести примеры.

46
7 Лабораторная работа № 7. Эффективное кодирование.
Метод Хаффмана
7.1 Цель работы
Освоение кодирования сообщений методом Хаффмана.
7.2 Теоретические сведения
Эффективное кодирование – это такой способ кодирования, при котором получается наименьший объем передаваемой информации и избыточность мини- мальна.
Для кодирования символов исходного алфавита используются двоичные ко- ды переменной длины: чем больше частота символа, тем короче его код.
Эффективность кода определяется средним числом двоичных разрядов для кодирования одного символа. При эффективном кодировании существует предел сжатия, ниже которого не «спускается» ни один метод эффективного кодирования
– иначе будет потеряна информация. Этот параметр определяется предельным значением двоичных разрядов возможного эффективного кода (7.1) где n – мощность кодируемого алфавита, fi- частота i-го символа кодируемого ал- фавита.
Метод Хаффмана относитсяк методу эффективного кодирования. Если имеются сообщения входного алфавита А {x1, x2,…, xn} c заданными вероятно- стями p1, p2, …, pn. Рассмотрим метод кодирования Хаффмана.
1. Необходимо расположить все сообщения в столбик в порядке убывания вероятностей их появления.
2. Затем два самых маловероятных сообщения объединить в одно y, которое имеет вероятность равную сумме вероятностей события x
n-1
, x n
т.е., p
n-1
+ p n
. В

47 результате получаются сообщения x1, x2, x
n-2
, y вероятности которых p1, p2, p
n-2
, p n-1
+p n
3. Необходимо повторять шаги 1 и 2 до тех пор, пока не получится единст- венное сообщение, вероятность которого равна 1.
4. Построить дерево, проводя линии, объединяющие сообщения и образую- щие последовательности подмножества. В этом дереве отдельные сообщения яв- ляются концевыми узлами. Соответствующие им кодовые слова можно опреде- лить, приписывая правым ветвям объединения символ 1, а левым – 0 (или наобо- рот).
Пример. Построить код Хаффмана для следующих данных:
Решение. Расположим сообщения в столбец в порядке убывания их вероят- ности

48
На основании полученной таблицы можно построить кодовое дерево
(риcунок 7.1).
Рисунок 7.1 – Кодовое дерево
7.3 Задание
Задача 1. 1.Построить код Хаффмана для ансамбля сообщений
Определить характеристики кода.
Задача 2. Построить код Хаффмана для ансамбля сообщений
Определить характеристики эффективного кода.
Задача 3. Построить код Хаффмана для ансамбля сообщений
Определить характеристики кода и скорость передачи сообщений по каналу при условии, что длительность двоичного символа
Сравнить с обычным двоичным кодированием.
Задача 4. Закодировать методом Хаффмана блоки «мы все учились понем- ногу чему-нибудь и как-нибудь».

49
Каково среднее число символов на знак? Сравнить с ответом задачи № 4, выпол- ненной по методу Шеннона-Фано.
Задача 5. Задан алфавит из трех символов с вероятностями 0,75; 0,1; 0,15.
Произвести кодирование отдельных букв и двухбуквенных сочетаний по методу
Хаффмана. Для полученных кодов найти средние длины и коэффициенты опти- мальности.
7.4 Контрольные вопросы
1 Поясните назначение и цели эффективного кодирования.
2 Что такое средняя длина кодовой комбинации? Как ее определить?
3 За счет чего при эффективном кодировании уменьшается средняя длина кодовой комбинации?
4 До какого предела может уменьшиться длина кодовой комбинации при эффективном кодировании?
5 При каком распределении букв первичного алфавита оптимальный не- равномерный код оказывается самым эффективным?
6 К какому типу алгоритмов кодирования относится метод Хаффмана, дать пояснение.
7 Приведите пояснение метода Хаффмана на примере.
8 Какая информация необходима для восстановления сообщения, закоди- рованного по методу Хаффмана?
9 Какой код наиболее эффективный: по методу Хаффмана или Шеннона-
Фано? Привести пример.
10 Привести случаи, когда метод Хаффмана не способен уменьшить размер данных.

50
Список использованных источников
1
Балюкевич, Э.Л. Основы теории информации: учебно-практическое пособие / Э.Л. Балюкевич. – М.: Евразийский открытый институт, 2008. – 216 с.
2
Задачи кодирования сообщений. Код Шеннона-Фэно. Алгоритм
Шеннона – Фано. [Электронный ресурс].
– Режим доступа: https://intellect.ml/18-
8-zadachi-kodirovaniya-soobshhenij-kod-shennona-feno-algoritm-shennona-fano-7001 3 Зверева, Е.Н. Сборник примеров и задач по основам теории информации и кодирования сообщений / Е.Н. Зверева, Е.Г. Лебедько. – СПб:
НИУ ИТМО, 2014. – 76 с.
4 Метод сжатия Хаффмана. Кодирование методом Хаффмана.
[Электронный ресурс].
–
Режим доступа:
http://life- prog.ru/view_programmer.php?id=2 5
Кудряшов, Б.Д. Теория информации / Б.Д. Кудряшов - Санкт-
Петербург: СПбГУ ИТМО, 2010. - 188 с.
6
Куприянов, А. И. Основы защиты информации: учеб. пособие для вузов / А. И. Куприянов, А. В. Сахаров, В. А. Шевцов.- 3-е изд., стер. - М. :
Академия, 2008. - 254 с.
7
Осокин, А.Н. Теория информации: учебное пособие / А.Н. Осокин,
А.Н. Мальчуков. Томск: Изд-во Томского политехнического университета, 2014.
– 208 с.
8
Фурсов, В.А. Теория информации: учебник / В.А. Фурсов. - Самара:
Изд-во Самар.,гос. аэрокосм, ун-та, 2011. - 128 с.
9
Хохлов, Г. И. Основы теории информации: учеб. пособие / Г.И.
Хохлов. - М. : Академия, 2008. - 172 с.