КНИГА-ТРЕНАЖЕР: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс. Евгений Леонидович Сидоркин
Чтение книги онлайн.

Читать онлайн книгу КНИГА-ТРЕНАЖЕР: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс - Евгений Леонидович Сидоркин страница 6

СКАЧАТЬ передачи сообщений, содержащих только буквы К, Л, М, Н, О, П, Р, решили использовать неравномерный двоичный код, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова, использованные для некоторых букв: К – 11, Л – 000, П – 0010, Р – 1011. Какое кодовое слово надо назначить для буквы М, чтобы код удовлетворял указанному условию и при этом длина слова МОЛОКО после кодирования была наименьшей? Если таких кодов несколько, укажите код с наименьшим числовым значением.

      Решение:

      Изобразим буквы К, Л, П, Р на дереве (рекомендую на экзамене прямо так и рисовать мышкой, как у меня выше нарисовано). По условию задачи необходимо, чтобы слово не являлось началом другого кодового слово, т.к. необходимо, чтобы выполнялось прямое условие Фано. Необходимо поставить в дерево две буквы: О и М, чтобы условие Фано выполнялось. Как это сделать? Т.к. буква О в слове «молоко» встречается 3 раза, то мы поставим эту букву на меньшую глубину дерева (01), чтобы получить наименьший код. Букву М, которая встречается всего 1 раз, поставим на большую глубину дерева (100). Итого имеем следующие длины: М=100=3, О=01=2*3 (т.к. 3 раза встречается, поэтому умножаем на 3) =6, Л=000=3, К=11=2. Длина кода равна=3+6+3+2=14.

      Ответ: 14.

      Рассмотрим задачу на обратное условие Фано.

      Пример 4.2

      По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б используются такие кодовые слова: А: 00011, Б: 1001, В: 01100. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.

      Решение:

      Для выполнения прямого условия Фано букву Г мы можем поставить на свободную ветку дерева, то Г=11 (кратчайший путь), т.к. этот путь не будет являться ничьим началом кодового слова. При обратном условии Фано букву Г=10 можем поставить (кратчайший путь), т.к. 10 не является окончанием ни одного из приведенных кодовых слов в условии. Г=00 взять не можем, т.к. 00 является окончанием В, и тогда не выполняется обратное условие Фано. Из двух чисел 11 и 10 наибольшее – 11.

      Ответ: 11.

      Пример 4.3

      Для передачи данных по каналу связи используется 5битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами: А – 11010, Б – 10111, В – 01101. При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку». ) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б СКАЧАТЬ