Для кодирования некоторой последовательности букв, решили использовать неравномерный двоичный код, который удовлетворяет прямому условию Фано. Получилось так: Буква Кодовое слово…
Для кодирования некоторой последовательности букв, решили использовать неравномерный двоичный код, который удовлетворяет прямому условию Фано. Получилось так: Буква Кодовое слово Буква Кодовое слово А 010 Д 111 Б 011 Е 100 В 1100 Ж 1101 Г 101 Определите, какие кодовые слова противоречат обратному обратному условию Фано. Если таких слов несколько, укажите кодовое слово с наименьшим числовым значением. Примечание: Прямое условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений. Обратное условие Фано означает, что никакое кодовое слово не является окончанием другого кодового слова.
Коротко: нарушают обратное условие Фано те кодовые слова, которые являются суффиксами других кодовых слов.
Данные кодовые слова: 010, 011, 1100, 101, 111, 100, 1101
Проверим пары на суффиксность:
- 010 - не является суффиксом ни одного другого слова.
- 011 - не является суффиксом ни одного другого слова.
- 1100 - ни одно другое слово не оканчивается на 1100.
- 101 - является суффиксом слова 1101 (1101 оканчивается на 101).
- 111 - ни одно другое слово не оканчивается на 111.
- 100 - является суффиксом слова 1100 (1100 оканчивается на 100).
- 1101 - ни одно другое слово не оканчивается на 1101.
Итак, кодовые слова, противоречащие обратному условию Фано (то есть являющиеся суффиксами другого слова):
- 101 (Г)
- 100 (Е)
Из них минимальное по числовому значению (если трактовать число как двоичное значение слова) — это 100, что соответствует букве Е.
Итого: нарушают 100 (Е) и 101 (Г). Минимальное слово — 100.
