По каналу связи передаются сообщения, содержащие только 4 буквы А, Б, В, Г;
для передачи используется двоичный код, допускающий однозначное декодирование.
Для букв А, Б, В используются такие кодовые слова: А: 000111, Б: 111, В: 1010. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование.
Если таких кодов несколько, укажите код с наименьшим числовым значением.
По условию Фано решением является 01, но в ответах прописано 00 (но код буквы А начинается с 00!), и подобрать последовательность, которая неоднозначно декодировалась бы, при таком шифре не удалось...
Помогите, пожалуйста, разобраться: мы чего-то не догоняем или всё-таки опечатка?
Вы правы, с вики "Коды Шеннона — Фано префиксные, то есть никакое кодовое слово не является префиксом любого другого". 00 - префикс для буквы с кодом 000111.
Да, действительно решение по условию Фано здесь не всегда даёт нужный ответ. Получается, что нужно прежде всего анализировать возможность слияния кодов.
Г : 0 -> ГГГБ неотличимо от А
Г : 1 -> ГГГ неотличимо от Б
Г :00 -> ни Г, ни ГГ не дают такого префикса, чтобы он, слившись с любой/любыми
последующими буквами, выглядел как код/набор кодов других букв.
Код Фано предназначен для передачи сообщений. То есть мы можем получать закодированное сообщение и в процессе раскодировать. В Вашем случае, мы вначале должны принять сообщение, проанализировать, не сливаются ли коды и только потом раскодировать. То есть мы получаем часть сообщения 00 - видим что оно отвечает коду в нашей таблице и сразу переводим. Не дожидаясь, вдруг дальше получиться 001 и оно тоже есть в таблице (тогда вы просто некорректно ее составили).
Возможно, ответ не очень вовремя, но на будущее.
В данном случае не указано, какое именно условие Фано (прямое или обратное) должно работать, значит, проверяем оба.
По прямому лучший ответ, действительно, 01 (не является началом других кодовых слов), а по обратному - 00 (не является концом других кодовых слов).
