Пример 1. Построить ОНК для передачи сообщений, в которых вероятности появления букв первичного алфавита равны:
Вероятности появления символов на выходе источника сообщения следующие:
Расставим символы в порядке возрастания вероятностей:
0,05 | 0,05 | 0,1 | 0,25 | 0,25 | 0,3 |
P1 | P5 | P6 | P2 | P4 | P3 |
Связываем две первые пары символов в узел
Вставляем этот узел обратно в последовательность. Вероятность его появления равна сумме вероятности появления букв в нём.
0,1 | 0,1 | 0,25 | 0,25 | 0,3 |
P6 | P2 | P4 | P3 |
Далее вновь связываем первые две последовательности в узел и возвращаем его туда.
0,2 | 0,25 | 0,25 | 0,3 |
P2 | P4 | P3 |
Далее
0,25 | 0,3 | 0,45 |
P4 | P3 |
Далее вновь складываем первые две буквы в узел
0,45 | 0,55 |
В итоге общее дерево будет иметь вид
Для определения ОНК надо проставить переходам между символами, если переход влево – 0, вправо – 1.
Таким образом, дерево будет иметь вид:
Код каждого символа – это последовательность переходов к нему.
Р1 | |
Р2 | |
Р3 | |
Р4 | |
Р5 | |
Р6 |
Таким образом ОНК будет иметь вид: 00000111100001001
Пример 2. Построить ОНК для фразы «МАМА МЫЛА ПОЛ».
Для начала посчитаем частоты всех символов
М | |
А | |
‘ ’ | |
Ы | |
Л | |
П | |
О |
Расположим символы по возрастанию частоты.
Ы | П | О | ‘ ’ | Л | М | А |
Теперь мы достаём два первых элемента из очереди и связываем их, создавая новый узел дерева, в котором они оба будут потомками, а приоритет нового узла будет равен сумме их приоритетов. После этого мы добавим получившийся новый узел обратно в очередь
О | ‘ ’ | Л | М | А |
Теперь повторяем те же шаги для получения следующих узлов:
‘ ’ | Л | М | А |
М | А |
А |
Теперь, чтобы получить код для каждого символа, надо просто пройтись по дереву, и для каждого перехода добавлять 0, если мы идём влево, и 1- если идём вправо.
Таким образом коды символов будут выглядеть следующим образом:
М | |
А | |
‘ ‘ | |
Ы | |
Л | |
П | |
О |
Таким образом ОНК фразы будет выглядеть так:
ВОПРОСЫДЛЯ САМОПРОВЕРКИ И ВОПРОСЫДЛЯ ЗАЩИТЫПЗ
1). Что такое информационная избыточность?
2). Что такое оптимальные коды?
3). Сформулировать методику Шеннона-Фано
ПРИЛОЖЕНИЕ
Самостоятельная работа по практическому занятию №9
«Решение задач с использованием оптимального кодирования информации»
Самостоятельная работа по теме занятия включает в себя:
- изучение теоретического материала лекционных занятий, учебной литературы, Интернет-ресурсов, раздела «Краткие сведения из теории» настоящего описания ПЗ;
- выполнение практических заданий и решение задач
Задачи и практические задания
1. Составьте ОНК для фразы
2. Постройте оптимальный код сообщения, состоящего из 16 равновероятностных букв. Чему равна средняя длина кодового слова в полученных кодах?
Вариант | Задача 1 |
Золотой колокол зазвонил | |
Тоненький голосок пищал | |
Подарили дорогой подарок | |
Довольный домовой удалился | |
Громко зазвонил домофон | |
Большое медвежье логово | |
Красивый речевой оборот | |
Хороший получился холодец | |
Мы увидели великое болото | |
Я увидел высокий потолок |