Question

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е и Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово 1; для буквы Б используется кодовое слово 01. Какова минимальная общая длина кодовых слов для всех семи букв?

Answer 1

А-1
Б-01
В-0001
Г-0010
Д-0011
Е-00000
Ж-00001
1+2+4*3+5*2=25

Answer 2

Условие Фано означает, что никакое кодовое слово не является префиксом другого кодового слова. Это означает, что длины кодовых слов должны быть выбраны таким образом, чтобы ни одно кодовое слово не было префиксом другого.

Рассмотрим возможные варианты кодовых слов для оставшихся пяти букв: В, Г, Д, Е и Ж. Если кодовое слово для Б состоит из двух битов (01), то кодовое слово для любой другой буквы не может начинаться с 0, иначе оно будет префиксом кодового слова для Б. Таким образом, кодовые слова для оставшихся пяти букв должны начинаться с 1.

Рассмотрим возможные варианты кодовых слов для оставшихся пяти букв, начинающихся с 1:

• В: 10 или 11
• Г: 100 или 101
• Д: 1100, 1101 или 1110
• Е: 11110, 11111 или 11011
• Ж: 11010, 10010 или 10110

Минимальная общая длина кодовых слов равна сумме произведений частот каждой буквы на длину ее кодового слова. Предполагая, что все буквы имеют одинаковую частоту, мы можем вычислить минимальную общую длину, сложив длины всех кодовых слов и разделив их на количество букв:

1 (A) + 2 (Б) + 2 (В) + 3 (Г) + 4 (Д) + 5 (Е) + 5 (Ж) = 22

Общая длина кодовых слов для всех семи букв равна 22 битам.