Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:
А – 00; Б – 101; В – 011; Г – 111; Д – 110.
Как можно сократить длину кодового слова для буквы Б так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Если есть несколько вариантов, выберите кодовое слово с минимальным значением.
Ответ: 01. Почему? Б ведь не может быть 01, потому что В начинается на 01!

Здесь важно не только то, что код В начинается с 01. Для однозначного декодирования в таком задании обычно проверяют условие Фано: ни одно кодовое слово не должно быть началом другого кодового слова.

Даны коды:

А — 00, В — 011, Г — 111, Д — 110.

Если для Б взять 01, то код Б станет началом кода В:

Б — 01, В — 011.

Значит, по условию Фано такой код брать нельзя: при чтении последовательности, начинающейся с 011, можно спутать начало с буквой Б.

Минимальный подходящий вариант длины 2 — 10, потому что он не совпадает с началом ни одного другого кода и сам не имеет среди данных кодов своего начала.

Поэтому если требуется именно префиксный код, ответ должен быть 10, а не 01. Ответ 01 возможен только при более широкой проверке однозначной декодируемости, но для школьных задач такого типа обычно используют именно условие Фано.

0 0 Пожаловаться