Question

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 1, 010, 011. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Answer 1

Можно построить граф, у нас будет так:

010, 011, 000, 1 - занято, останется 001, которое нам придётся разбить на 2 части, так как нам еще шифровать буквы Е и Ж, оставим минимальный код для Д, получится 0010.

Ответ: 0010

Answer 2

Для создания кода Фано, который обеспечивает однозначное декодирование, важно, чтобы ни одно кодовое слово не было префиксом другого кодового слова. Для букв А, Б, В, Г уже заданы кодовые слова:

• А: 000
• Б: 1
• В: 010
• Г: 011

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

Проверим доступные комбинации для Д:

• 00 (префикс для А и В)
• 1 (префикс для Б)
• 010 (префикс для В)
• 011 (префикс для Г)

Исключив префиксы для других букв, у нас остается только один вариант: кодовое слово для Д должно быть "100". Это кратчайшее возможное кодовое слово для буквы Д, при котором код Фано обеспечивает однозначное декодирование.