По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г –... | Яндекс.Репетитор

Задание#T4843

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г –

, И – , Т – .

Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАРАБАН?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать разбор и ответ

Указание:

Постройте дерево кодирования.

Решение:

Построим дерево кодирования.

Нужно закодировать ещё четыре буквы (А, Б, Н, Р), а в дереве есть два свободных узла. Каждое продолжение дерева из свободного узла создаёт два узла вместо одного, то есть количество узлов увеличивается на . Значит, нужно продолжить дерево в двух местах. С точки зрения длины кодов это можно сделать двумя способами:

из узла (длина кода ) получить два узла с длиной кода , затем продолжить дерево из любого из трёх свободных узлов длины ;
из узла (длина кода ) получить два узла с длиной кода , а затем из одного из них - два узла с длиной кода .

В первом случае мы получим новые коды длиной , , , , во втором – , , , .

Подсчитаем количество знаков для кодирования слова БАРАБАН в каждом из этих случаев. Очевидно, что для получения наименьшей длины самым коротким должен быть код буквы А (она встречается чаще всех), следующим – код буквы Б.

В первом случае длина кода букв А и Б – бит, букв Н и Р – бит, для кодирования слова БАРАБАН потребуется