Форум » Кодирование и декодирование информации » вариант 5 задание 4 » Ответить
вариант 5 задание 4
s11kai: Добрый день! (166 № 3504) (Е. Джобс) По каналу связи передаются сообщения, содержащие только семь букв: О, К, Т, Я, Б, Р, Ь. Для передачи используется двоичный код, допускающий однозначное декодирование. Кодовые слова для некоторых букв известны: К – 1010, Т – 100, Б – 0101, Р – 110, Ь – 001. Укажите минимальную возможную сумму длин кодов всех букв. Если строить дерево, то получается свободных три листочка: 000, 011 и 111, но в таком случае, ответом будет число 23. Правильно ли я понимаю, что при кодировании, в конкретном случае, "листочек можно и оборвать" т.е. букву Я, например, закодировать кодом 11, поскольку он (код) не является концом другого кода, если исключить код 111? Спасибо!
Ответов - 2
Поляков: Этот код удовлетворяет как прямому, так и обратному условию Фано, поэтому нужно проверить оба варианта. Простроив дерево для обратного условия Фано (по обратным кодам), можем выбрать открытые ветки 11 и 001. Сумма кодов 22.
s11kai: Спасибо, Константин Юрьевич!
полная версия страницы