Форум » Кодирование и декодирование информации » задание 4 » Ответить
задание 4
Oki Doki: задание: (№ 1666) (А. Куканова) Для кодирования некоторой последовательности, состоящей из букв Ф, А, К, Т, О, Р решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды для некоторых букв: А — 10, К — 11, Т — 0100, О — 01, Р — 0000. Укажите кратчайшее возможное кодовое слово для буквы Ф, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением. Написано, что используется двоичный код, удовлетворяющий условию Фано, но буква О является началом буквы Т. Или я чего-то не понимаю, или в формулировке задания ошибка...
Ответов - 5
Поляков: Спасибо, вы правы, тут неточность формулировки. Код удовлетворяет обратному условию Фано. Должно быть так "двоичный код, допускающий однозначное декодирование". Исправлено.
Olga17: (№ 3504) (Е. Джобс) По каналу связи передаются сообщения, содержащие только семь букв: О, К, Т, Я, Б, Р, Ь. Для передачи используется двоичный код, допускающий однозначное декодирование. Кодовые слова для некоторых букв известны: К – 1010, Т – 100, Б – 0101, Р – 110, Ь – 001. Укажите минимальную возможную сумму длин кодов всех букв. Добрый вечер! Для решения строю двоичное дерево, нахожу коды известных букв. Свободными остаются ветви 000, 011 и 111. То есть для искомых букв О и Я остаются коды длиной 3. Тогда минимальная сумма длин кодов всех букв равна 3+4+3+3+4+3+3=23. Но в ответе 22. Скажите, пожалуйста, в чем моя ошибка.
EugeneJobs: Обратное условие Фано проверяли?
Olga17: Нет. Не проверяла. Тогда получается, что код 11 тоже подходит? так как не является окончанием ни одного другого кода. Подскажите, пожалуйста, обратное условие всегда нужно проверять? или только при определенном условии задачи?
EugeneJobs: В задаче на экзамене вообще должно быть примечание про то, что считать условием однозначного кодирования. Если же говорить про задачи на условие Фано без уточнения, то правильнее проверять всегда.
полная версия страницы