Вступление
Что такое кодирование, декодирование, условие Фано – всё, что встречается в задании № 4 ЕГЭ по информатике, разбираем в этой статье.
Термины, которые будем использовать:
Кодирование, декодирование, код, двоичный код, равномерный код, неравномерный код, условие Фано, обратное условие Фано, однозначное декодирование, бит.
Для передачи, обработки и хранения информации необходимо её зафиксировать с помощью определённой знаковой системы (алфавита), т. е. закодировать.
Что такое кодирование и какой код использовать при кодировании
Кодирование – это перевод информации с помощью некоторого кода в удобную форму, которая используется для её передачи, обработки или хранения.
Кодирование информации всегда происходит по определённым правилам.
Код – это правило кодирования или набор условных сигналов (символов) для записи информации.
Как правило, в задании № 4 используется двоичное кодирование информации.
Двоичный код – это код, в котором каждый разряд принимает одно из двух значений: 0 или 1.
Количество информации в битах (1 бит информации – это символ или сигнал, который также может принимать значение 0 или 1) определяется длиной сообщения в двоичном коде. Например, 01101 – пять битов, 01 – два бита.
Что такое равномерное и неравномерное кодирование
Давай разберёмся в этих двух определениях на примерах.
| Равномерный код – это код, в котором все кодовые слова имеют одинаковую длину. | Неравномерный код – это код, в котором кодовые слова имеют различную длину. | ||||||
|---|---|---|---|---|---|---|---|
| И | Н | Ф | А | И | Н | Ф | А |
| 00 | 01 | 10 | 11 | 0 | 10 | 110 | 1110 |
| Все символы имеют одинаковую длину — по два бита. Длина сообщения = 8 бит. | Все символы имеют различную длину — от одного до четырёх бит. Длина сообщения = 10 бит. | ||||||
Что такое декодирование и однозначно декодируемый код?
Декодирование – это процесс восстановления содержания закодированной информации.
Однозначно декодируемый код – код, в котором любое слово, составленное из кодовых слов, можно декодировать только единственным способом. Код декодируется однозначно, если выполняется условие Фано: никакое кодовое слово не может быть началом другого кодового слова.
Условие Фано – это достаточное, но необходимое условие однозначного декодирования.
Если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.
| Однозначное декодирование | Неоднозначное декодирование | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Код сообщения: 000010100010 Кодовые слова: К – 000, А – 010, Ш – 100 | Код сообщения: 01101 Кодовые слова: К – 0, А – 1, Ш – 10 | ||||||||||
| 000 | 010 | 100 | 010 | 0 | 1 | 10 | 1 | ||||
| К | А | Ш | А | К | А | Ш | А | ||||
| Чтобы расшифровать кодовые слова в данном сообщении, необходимо разбить его на группы по три символа (т. к. длина кодовых слов =3). | и другой вариант | ||||||||||
| 0 | 1 | 1 | 0 | 1 | |||||||
| К | А | А | К | А | |||||||
| Несколько вариантов расшифровки, значит декодирование не однозначно! | |||||||||||
Задания на кодирование, декодирование и условие Фано в ЕГЭ по информатике
Разберём несколько типовых заданий на нахождение кратчайшего кодового слова с наименьшим или наибольшим числовым значением; на нахождение минимальной длины сообщения или суммы длин кратчайших слов.
Задание 1
По каналу связи передаются секретные сообщения, содержащие только четыре буквы: Ф, Л, Э, Ш. Для передачи Артём использует двоичный код, удовлетворяющий условию Фано. Для буквы Ф используется кодовое слово 1. Укажите сумму длин кратчайших кодовых слов для букв Л, Э и Ш, при котором код будет допускать однозначное декодирование.
Ответ: 8.
Построим «дерево» по условию задачи. Так как Ф мы уже разместили, у нас ещё остаётся 3 буквы. Мы можем разветвить ветку 0 на 00 и 01. В этом случае мы можем поместить только 2 буквы, а нам надо 3. Поэтому одну из веток (01 или 00) разветвим ещё на 2. Давай разветвим ветку 00. Тогда мы разместим все 4 буквы. Общая сумма длин (кроме длины буквы Ф) составит 2 + 3 + 3 = 8.
Задание 2
По каналу связи передаются секретные сообщения, содержащие только четыре буквы: Ф, Л, Э, Ш. Для передачи Артём использует двоичный код, удовлетворяющий условию Фано. Для букв Ф, Л, Ш используются кодовые слова: Ф – 0; Л – 110; Ш – 101. Укажите кратчайшее кодовое слово для буквы Э, которое использовал Артём, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Ответ: 100.
Построим «дерево» по условию задачи. Как мы видим, букву Э можем поместить на место 100 или 111. У них одинаковая длина, значит, из этих двух вариантов необходимо определить код с наименьшим числовым значением.
Задание 3
По каналу связи передаются секретные сообщения, содержащие только четыре буквы: Ф, Л, Э, Ш. Для передачи Артём использует двоичный код, удовлетворяющий условию Фано. Для букв Ф, Л, Ш используются кодовые слова: Ф – 0; Л – 110; Ш – 101. Укажите кратчайшее кодовое слово для буквы Э, которое использовал Артём, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Ответ: 111.
Построим «дерево» по условию задачи. Как мы видим, букву Э можем поместить на место 100 или 111. У них одинаковая длина, значит, из этих двух вариантов необходимо определить код с наименьшим числовым значением.
Задание 4
В небольшой IT-компании для маркировки продукции используют символьные последовательности, содержащие только семь букв: А, В, Е, И, Н, С, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: В – 00, А – 010, Е – 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ИНТЕНСИВ?
Ответ: 23.
Построим «дерево» по условию задачи. Распишем по сколько раз в слове «ИНТЕНСИВ» встречаются буквы: А – 0, В – 1, Е – 1, И – 2, Н – 2, С – 1, Т – 1. Так как нам даны кодировки А, В и Е, нам необходимо закодировать оставшиеся 4 буквы: И, Н, Т, С. Нам необходимо найти наименьшее количество двоичных знаков, поэтому присвоим букве И код 10 и Н – 011 (так как они встречаются чаще всего, стараемся их сделать короче). Оставшуюся ветку разветвляем и присваиваем: Т – 1100, С – 1101. Общая сумма длин знаков слова «ИНТЕНСИВ» составит И = 2 x 2 + Н = 2 x 3 + Т = 1 x 4 + Е = 1 x 3 + С = 1 x 4 + В = 1 x 2 = 23.
Задание 5
В небольшой IT-компании для маркировки продукции используют символьные последовательности, содержащие только шесть букв: А, В, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Т – 11, А – 000, Н – 001. Какое наименьшее количество двоичных знаков потребуется для кодирования слова «ТРИНИТИ»?
Ответ: 16.
Построим «дерево» по условию задачи. Распишем по сколько раз в слове «ТРИНИТИ» встречаются буквы: И – 3, Т – 2, Р – 1, Н – 1, А – 0, В – 0. Так как нам даны кодировки А, Т и Н, нам необходимо закодировать оставшиеся 3 буквы: И, В, Р. Нам необходимо найти наименьшее количество двоичных знаков, поэтому можем букве И присвоить 01 или 10. Присвоим букве И 01 (так как она встречается чаще всего, стараемся её сделать короче). Оставшуюся ветку разветвляем и присваиваем: Р – 100, В – 101.
Общая сумма длин знаков слова «ТРИНИТИ» составит И = 3 x 2 + Т = 2 x 2 + Р = 1 x 3 + Н = 1 x 3 = 16.
Задание 6
Артём и Саня придумывают новые слова, используя только пять букв: Н, А, С, Т, О. Чтобы передать эти слова друг другу по каналу связи, они используют неравномерный двоичный код. Для букв Н, А, С, Т использовали кодовые слова 00, 01, 100 и 110 соответственно. Укажите самое короткое кодовое слово для буквы О, которое использовали ребята, при котором код не будет удовлетворять условию Фано, при этом в записи самого слова должно использоваться более одного символа, а само слово не должно совпадать ни с одним из используемых слов для кодирования букв Н, А, С, Т. Если таких слов несколько, то укажите слово с минимальным числовым значением.
Ответ: 10.
Построим «дерево» по условию задачи. Внимательно читаем условие. Кодовое слово для буквы О не должно удовлетворять условию Фано. Значит буква О должна быть частью кодового слова (именно частью, повторять полностью кодовое слово оно не может). Так как нам нужно, чтобы оно имело минимальное числовое значение, и длина составляла более 1, то у нас есть следующие варианты: 00, 01, 10, 11. 00 и 01 нам не подходят, так как уже являются кодовыми словами. Выбираем между 10 и 11. Минимальное из них 10.
(10 – более одного символа и самое короткое)
ВАЖНО!!! В следующих заданиях!
НЕОБХОДИМО ОБЯЗАТЕЛЬНО ОСТАВИТЬ ОДНУ ВЕТВЬ, ЧТОБЫ НА НЕЙ МЫ МОГЛИ РАЗМЕСТИТЬ ВЕСЬ АЛФАВИТ.
Задание 7
Артём придумал новый способ кодирования сообщений, состоящих из заглавных букв русского алфавита. Для кодирования каждой буквы Артём решил использовать неравномерный двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что все кодовые слова содержат не меньше двух и не больше трёх двоичных знаков, а слову ФЛЭШ соответствует код 000001110111. Какое наименьшее количество двоичных знаков может содержать сообщение, кодирующее слово ФЛЭШКА?
Ответ: 17.
Мы имеем код 000001110111, соответствующий слову «ФЛЭШ». Попробуем разбить код на буквы так, чтобы выполнялось условие Фано. 000001110111. Предположим 000 – это Ф, 001 – Л, 110 – Э, 111 — Ш. Построим «дерево» и проверим, все ли условия выполняются.
Условие Фано выполняется. Нам нужно наименьшее количество двоичных знаков слова «ФЛЭШКА». Оставшиеся 2 буквы мы могли бы разместить на оставшиеся 2 места, но необходимо оставить одну ветвь для кодирования остальных букв алфавита. Размести К на 01, а на 100 разместим А (101 оставляем пустым для остальных букв алфавита). Находим количество знаков: 3 + 3 + 3 + 2 + 3 + 3 = 17.
Задание 8
Флэш закодировал все заглавные буквы русского алфавита неравномерным двоичным кодом, при этом никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для некоторых букв Флэш использовал кодовые слова: Б – 00, Г – 010, Д – 1011, О – 11. Известно также, что код слова КАЗАК содержит 17 двоичных знаков. Сколько двоичных знаков содержит код слова «КОЗА»?
Ответ: 13.
Запишем, сколько каких букв в слове «КАЗАК»: К – 2, А – 2, З – 1. Так как А и К по 2, скорее в дереве они закодированы коротко: 011 – К и 100 – А. Проверим, какой длины будет буква З, если всего 17 двоичных знаков: 17 – 3 x 2 – 3 x 2 = 5. Оставшуюся ветвь раздваиваем и в 10100 записываем З, а 10101 оставляем для остальных букв. Теперь считаем количество двоичных знаков для «КОЗА»: 3 + 2 + 5 + 3 = 13.
Задание 9
Флэш передает своему другу сообщения, содержащие только заглавные русские буквы. Для передачи он использует двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: В – 1110, Г – 110, Д – 0000, Е – 01. Известно, что для кодирования слова «БАОБАБ» потребовалось 16 двоичных знаков. Какое кодовое слово соответствует букве А? Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Ответ: 001.
Запишем, сколько каких букв в слове «БАОБАБ»: Б – 3, А – 2, О – 1. Так как Б встречается больше всех, скорее в дереве она закодирована коротко. Самый короткий код — 10, в него закодируем Б. Из оставшихся самые короткие коды на дереве – 001 и 110. В 001 закодируем А. Теперь считаем количество двоичных знаков для оставшейся буквы О: 16 – 2 x 3 – 3 x 2 = 4. Для О подойдёт 0001 или 1111 (без разницы). В ответ запишем кодовое слово А.
Автор:
Быкова Оксана, методист «100балльного репетитора» по информатике ЕГЭ
