Question

В сообщении встречается 7 разных букв. При его передаче использован неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды трёх букв: 1, 01, 001. Коды остальных четырёх букв имеют одинаковую длину. Какова минимальная суммарная длина всех 7-ми кодовых слов?​

Answer 1

Ответ:A - 1

B - 01

C - 001

D - 00000

E - 00001

F - 00010

G - 00011

Answer 2

Ответ: 26.

Построим дерево Фано для известных нам кодов букв. По нему мы видим, что свободна только ветвь 000. Чтобы получить 4 различных кода требуется 2 разряда (логарифм 4 по основанию 2), поэтому для кодов оставшихся 4 букв необходимо 5 разрядов (к двум требуемым добавляются три лидирующие нуля). Общее количество бит кодов: 5 * 4 + 1 + 2 + 3 = 26.