Кодирование информации
- Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
- Кодирование бывает равномерным и неравномерным:
- при равномерном кодировании всем символам соответствуют коды одинаковой длины;
- при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.
Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).
Кодирование и расшифровка сообщений
Для решения задач с декодированием, необходимо знать условие Фано:
- если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано:
- условие Фано – это достаточное, но не необходимое условие однозначного декодирования.
Однозначное декодирование обеспечивается:
Однозначное декодирование
Декодирование
Решение 5 заданий ЕГЭ
О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.
✍ Решение:
- Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
О -> 0 -> 00 В -> 1 -> 01 Д -> 2 -> 10 П -> 3 -> 11 А -> 4 -> 100
ВОДОПАД:010010001110010
010 010 001 110 010 ↓ ↓ ↓ ↓ ↓ 2 2 1 6 2
Результат: 22162
Решение ЕГЭ данного задания по информатике, видео:
Рассмотрим еще разбор 5 задания ЕГЭ:
| a | b | c | d | e |
|---|---|---|---|---|
| 000 | 110 | 01 | 001 | 10 |
Какой набор букв закодирован двоичной строкой 1100000100110?
✍ Решение:
- Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.
- Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:
✎ 1 вариант решения:
110 000 01 001 10 ↓ ↓ ↓ ↓ ↓ b a c d e
Результат: b a c d e.
✎ 2 вариант решения:
-
Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.
- Сделаем дерево, согласно кодам в таблице:
- Сопоставим закодированное сообщение с кодами в дереве:
110 000 01 001 10
Результат: b a c d e.
Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины
4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110).
Определите, какое число передавалось по каналу в виде 01100010100100100110.
✍ Решение:
- Рассмотрим пример из условия задачи:
Было2310 Стало00101001102
0010100110 (0010 - 2, 0011 - 3)
01100 01010 01001 00110
0110 0101 0100 0011
0110 0101 0100 0011 ↓ ↓ ↓ ↓ 6 5 4 3
Ответ: 6 5 4 3
Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10.
Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
✍ Решение:
- Найдём самые короткие возможные кодовые слова для всех букв.
- Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
- Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
- Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
- Суммарная длина всех четырёх кодовых слов равна:
(Н)1 + (К)2 + (Л)3 + (М)3 = 9
✎ 2 вариант решения:
- Будем использовать дерево. Влево откладываем 0, вправо — 1:
- Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
(Н) -> 0 -> 1 символ (К) -> 10 -> 2 символа (Л) -> 110 -> 3 символа (М) -> 111 -> 3 символа
(Н)1 + (К)2 + (Л)3 + (М)3 = 9
Ответ: 9
По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова:
А: 101010, Б: 011011, В: 01000
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
✍ Решение:
- Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
- Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.
Результат: 00
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код:
А - 01 Б - 00 В - 11 Г - 100
Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
✍ Решение:
- Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:
- Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:
- Перепишем сверху вниз получившееся кодовое слово для Д: 101
Результат: 101
Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
✍ Решение:
- Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
- При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:
Результат: 1100
Подробное решение данного 5 задания из демоверсии ЕГЭ 2018 года смотрите на видео:
По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются кодовые слова:
А: 00011 Б: 111 В: 1010
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
✍ Решение:
- Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
- Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).
- Получившееся числовое значение кодового слова для буквы Г — 01.
- Получившееся числовое значение кодового слова для буквы Г — 00.
- После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00.
Дерево по условию Фано (однозначно декодируется с начала):
Дерево по обратному условию Фано (однозначно декодируется с конца):
Результат: 00
По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:
Е – 000 Д – 10 К – 111
Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.
✍ Решение:
- С помощью дерева отобразим известные коды для букв:
- В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:
- Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
Д Е Д М А К А Р 10 000 10 001 01 111 01 110
Результат: 20
Смотрите виде решения задания:
