Форум » Кодирование и декодирование информации » тренировочный КИМ №190121 задание 5 » Ответить
тренировочный КИМ №190121 задание 5
Бобровская: Дан ответ 01,для буквы Б. Но в этом случае не будет выполнено обратное цсловие Фано(как написано в ответах). И как можно сократить Б до 01, если его код дан 101. Что я не так делаю?
Ответов - 5
polyakovss: Здравствуйте! Задача Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00; Б – 101; В – 011; Г – 111; Д – 110. Как можно сократить длину кодового слова для буквы Б так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Если есть несколько вариантов, выберите кодовое слово с минимальным значением. Вы пишете: Дан ответ 01 для буквы Б. Но в этом случае не будет выполнено обратное условие Фано (как написано в ответах). Нет. Ни один из оставшихся кодов не заканчивается на 01. Поэтому обратное условие Фано выполнено. Как решить задачу? Означает ли фраза "код, удовлетворяющий условию Фано", что нужно рассматривать только прямое условие Фано? Да. Означает ли отсутствие фразы "код, удовлетворяющий условию Фано", что нужно рассматривать и обратное условие Фано? Да. В задаче отсутствует фраза "код, удовлетворяющий условию Фано". Поэтому нужно рассматривать и обратное условие Фано. Построим дерево для заданных кодовых слов, читая их слева направо (прямое условие Фано: А – 00; Б – 101; В – 011; Г – 111; Д – 110). Согласно условию Фано, код декодируется однозначно, если все используемые кодовые слова соответствуют листьям такого дерева. Видим, что для заданных кодовых слов это условие выполняется (выполняется прямое условие Фано). Код Б - 101 можно в этом случае сократить до Б - 10. Построим дерево для заданных кодовых слов, читая их справа налево (обратное условие Фано: А – 00; Б – 101; В – 110; Г – 111; Д – 011). Видим, что для заданных кодовых слов это условие выполняется (выполняется обратное условие Фано). Код Б - 101 можно в этом случае сократить до Б - 10. При обычном чтении слева направо код Б - 01. Таким образом, для Б - 10 выполняется прямое условие Фано, а для Б - 01 выполняется обратное условие Фано. Кодовое слово с минимальным значением: Б - 01. Ответ: Б - 01.
Бобровская: Спасибо за ответ. По первой части все понятно. У меня тоже получился ответ, что Код Б - 101 можно в этом случае сократить до Б - 10. А почему мы должны построить дерево в обратном порядке, по обратному условию Фано, и ответ принимается только 01? Ведь в условии это не сказано.
polyakovss: Здравствуйте! Вы пишете: А почему мы должны построить дерево в обратном порядке, по обратному условию Фано? Посмотрите пример задания Р-06 в ege5.doc Решение (2 способ, дерево) пункт 5 (страница 9): ... у нас есть еще обратное условие Фано, для которого тоже можно построить аналогичное дерево, в котором движение от корня к букве дает её код с конца (красным цветом выделен код буквы В – 011, записанный с конца): 110 (выделено красным)... Далее смотрите на код буквы Г (пункт 6). Код буквы Г сокращается так же, как код буквы Б в рассмотренной ранее задаче. Смотрите рисунок. Вы пишете: А почему ответ принимается только 01? Ведь в условии это не сказано. Нет, сказано. В задаче отсутствует фраза "код, удовлетворяющий условию Фано". Поэтому нужно рассматривать и прямое, и обратное условие Фано. В условии сказано, что если есть несколько вариантов, нужно выбрать кодовое слово с минимальным значением. Для Б - 10 выполняется прямое условие Фано, а для Б - 01 выполняется обратное условие Фано. Кодовое слово с минимальным значением: Б - 01. Поэтому именно его и выбираем.
Бобровская: Константин Юрьевич, спасибо. Все поняла. Очень хорошая задача. Учит вниманию.
polyakovss: Здравствуйте! Благодарю за отзыв. Но я не Константин Юрьевич, а Сергей Сергеевич Поляков.
полная версия страницы