Форум » Кодирование и декодирование информации » Задание 4 № 158 » Ответить
Задание 4 № 158
Гевлич: ДЗ КЕГЭ_4 № 158 (А. Куканова) Для кодирования некоторой последовательности, состоящей из букв Ф, А, К, Т, О, Р решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды для некоторых букв: А — 10, К — 11, Т — 0100, О — 01, Р — 0000. Укажите кратчайшее возможное кодовое слово для буквы Ф, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением. Примечание. Прямое условие Фано означает, что никакое кодовое слово не является началом другого кодового слова; обратное — что никакое кодовое слово не является концом другого кодового слова. Выполнения любого из них достаточно для однозначной расшифровки закодированных сообщений. Ответ: 0011 Решение Вариант решения 1 Строим дерево кодов Визуально по дереву графа видно, что кратчайшее возможное кодовое слово для буквы Ф – 001, такой код единственный Вариант решения 2 Метод перебора: Построим возможные коды, отметим использованные и проанализируем для остальных кодов, выполняется ли прямое или обратное условие Фано: 0 не выполняется прямое и обратное условие Фано: 01 и 10 1 не выполняется прямое и обратное условие Фано: 10 и 01 00 не выполняется прямое и обратное условие Фано: 0000 и 0000 01 код буквы О 10 код буквы А 11 код буквы К 000 не выполняется прямое и обратное условие Фано: 0000 и 0000 001 выполняется прямое условие Фано, обратное условие Фано можно не проверять! 010 011 … 0000 код буквы Р … 0100 код буквы Т Следовательно, кратчайшее возможное кодовое слово для буквы Ф – 001. Ответ: 001 Ответ приведенный на сайте Полякова К.Ю. для задания 4 № 158: 0011 Такой ответ может получиться, только, если в условии задачи исправить код для буквы Т - 0010!
Ответов - 7
Поляков: Обратите внимание, что для исходного набора кодовых слов прямое условие Фано не выполняется. Поэтому нужно играть на обратном. Ответ верный.
Inna: Обратное условие Фано при ответе 001 тоже выполняется. Какой ответе верен: 0011 и 001? Если правильный ответ 0011, то не понятно, как его получить?
Поляков: Там ответ 1100. Для 001 обратное условие Фано не выполнится в паре О-Ф.
Inna: Спасибо большое! Теперь все понятно.
Inna: И еще вопрос, если можно.Как построив дерево кодов, можно наглядно понять, какой код подходит для выполнения обратного условия Фано? Если да, то что об этом однозначно свидетельствует? При выполнении прямого условия Фано все коды символов должны размещаться на листках дерева? А как будет при выполнении обратного условия Фано?
Поляков: Inna пишет: Как построив дерево кодов, можно наглядно понять, какой код подходит для выполнения обратного условия Фано? Постройте дерево для обратных кодов.
Inna: Спасибо, теперь все получилось:-)))
полная версия страницы