Пример 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 |
| Золотой колокол зазвонил | |
| Тоненький голосок пищал | |
| Подарили дорогой подарок | |
| Довольный домовой удалился | |
| Громко зазвонил домофон | |
| Большое медвежье логово | |
| Красивый речевой оборот | |
| Хороший получился холодец | |
| Мы увидели великое болото | |
| Я увидел высокий потолок |
|
|