Ответ:
1. Проверка условия Фано
Таблица 1: коды 0, 10, 110, 111. Ни один код не является началом другого: код 0 не является началом остальных кодов, начинающихся с 1; коды 10, 110 и 111 также не являются префиксами друг друга. Условие Фано выполняется.
Таблица 2: код 0? Среди заданных кодов кода 0 нет, однако код 00 является началом кода 001. Следовательно, условие Фано нарушается. Декодирование действительно может быть неоднозначным: сообщение 00 можно разбить как код Г (00) или как два кода А (0|0).
Однозначное декодирование без разделителей гарантирует таблица 1, поскольку её коды удовлетворяют префиксному условию.
2. Декодирование
Разбиваем сообщение на коды таблицы 1 слева направо: 100111100 = 10 | 0 | 111 | 10 | 0.
Это соответствует буквам: 10 — Б, 0 — А, 111 — Г, 10 — Б, 0 — А.
Ответ: БАГБА.
3. Пример собственной таблицы кодирования
Частоты букв не заданы, поэтому достаточно, чтобы А имела код длины 1 бит, а остальные буквы — более длинные коды. Выберем код, в котором ни одно кодовое слово не является началом другого:
А — 0; Б — 100; В — 101; Г — 110; Д — 111.
Код А короче остальных. Ни один из кодов 100, 101, 110, 111 не является началом другого, и код 0 не является началом ни одного из них. Значит, код удовлетворяет условию Фано.
1. Проверка условия Фано
Таблица 1: коды 0, 10, 110, 111. Ни один код не является началом другого: код 0 не является началом остальных кодов, начинающихся с 1; коды 10, 110 и 111 также не являются префиксами друг друга. Условие Фано выполняется.
Таблица 2: код 0? Среди заданных кодов кода 0 нет, однако код 00 является началом кода 001. Следовательно, условие Фано нарушается. Декодирование действительно может быть неоднозначным: сообщение 00 можно разбить как код Г (00) или как два кода А (0|0).
Однозначное декодирование без разделителей гарантирует таблица 1, поскольку её коды удовлетворяют префиксному условию.
2. Декодирование
Разбиваем сообщение на коды таблицы 1 слева направо: 100111100 = 10 | 0 | 111 | 10 | 0.
Это соответствует буквам: 10 — Б, 0 — А, 111 — Г, 10 — Б, 0 — А.
Ответ: БАГБА.
3. Пример собственной таблицы кодирования
Частоты букв не заданы, поэтому достаточно, чтобы А имела код длины 1 бит, а остальные буквы — более длинные коды. Выберем код, в котором ни одно кодовое слово не является началом другого:
А — 0; Б — 100; В — 101; Г — 110; Д — 111.
Код А короче остальных. Ни один из кодов 100, 101, 110, 111 не является началом другого, и код 0 не является началом ни одного из них. Значит, код удовлетворяет условию Фано.
