Решение:
Для выполнения прямого условия Фано букву Г мы можем поставить на свободную ветку дерева, то Г=11 (кратчайший путь), т.к. этот путь не будет являться ничьим началом кодового слова. При обратном условии Фано букву Г=10 можем поставить (кратчайший путь), т.к. 10 не является окончанием ни одного из приведенных кодовых слов в условии. Г=00 взять не можем, т.к. 00 является окончанием В, и тогда не выполняется обратное условие Фано. Из двух чисел 11 и 10 наибольшее – 11.
Ответ: 11.
Пример 4.3
Для передачи данных по каналу связи используется 5битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами: А – 11010, Б – 10111, В – 01101. При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку». ) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается «х»). Получено сообщение 11000 11101 10001 11111. Декодируйте это сообщение – выберите правильный вариант.
1) АххБ 3) хххх
2) АВхБ 4) АВББ
Решение:
Декодируем каждое слово сообщения. Первое слово: 11000 отличается от буквы А только одной позицией, поэтому на первом месте будет А. Второе слово: 11101 отличается от буквы В только одной позицией, поэтому на второй позиции будет В. Третье слово: 10001 отличается от любой буквы более чем одной позицией, поэтому третья позиция – x. Четвёртое слово: 11111 отличается от буквы Б только одной позицией, поэтому четвертая позиция – Б. Таким образом, ответ: АВхБ.
Ответ: 2.
Задачи для самостоятельного решения
Задача 4.4
По каналу связи передаются сообщения, содержащие только четыре буквы: М, А, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: М – 101, Р – 100, Т – 01. Укажите кодовое слово минимальной длины, которое можно использовать для буквы А. Если таких кодовых слов несколько, приведите кодовое слово с минимальным числовым значением.
Примечание. Условие Фано означает, что соблюдается одно из двух условий: либо никакое кодовое слово не является началом другого кодового слова, либо никакое кодовое слово не является окончанием другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Задача 4.5
По каналу связи передаются сообщения,