Задание 5. По каналу связи передаются сообщения, содержащие только
четыре буквы: А, Б, В, Г; для передачи используется двоичный код,
удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые
слова: А – 0; Б – 110; В – 100.
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет
допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано
означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение:
1. Построение дерева: условие Фано означает, что ни одно кодовое слово не совпадает
с началом другого кодового слова; при этом в дереве кода все кодовые слова
должны располагаться в листьях дерева, то есть в узлах, которые не имеют
потомков.
2. Построим
дерево для заданных кодовых слов А – 0, Б – 110 и В – 100:
3. Штриховыми
линиями отмечены две «пустые» ветви, на которые можно «прикрепить» листья для
кодовых слов буквы Г: 101 и 111.
4. Поскольку
нужно выбрать код с минимальным значением, выбираем 101
Ответ: 101
Комментариев нет:
Отправить комментарий