Задание 4
Кодирование и декодирование
Смотрим разбор демоварианта ЕГЭ-2021
Задание 1. ЕГЭ - 2019. Досрочная волна. Вариант 1.
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 00, 01, 100, 110. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Решение.
Кодовое слово для буквы П не может начинаться с 0, поскольку кодовые слова начинающиеся с 0, будут либо являться подстрокой кодовых слов для букв К и Л, либо включать в себя кодовые слова для букв К и Л. Кодовые слова 1, 10 и 11 взять не можем, поэтому букву П можно закодировать кодовыми словами 101 или 111. Возьмём кодовое слово с наименьшим числовым значением. Следовательно, букву П можно закодировать кодовым словом 101.
Ответ: 101.
Задание 2.
Для кодирования букв А,Б,В,Г используют неравномерный код Фано. Пусть закодировали А-01, Б-10. Какова наименьшая суммарная длина всех пяти кодовых слов.
Задача 3.
Для кодирования букв А, Б, В, Г, Д, Е используют неравномерный код Фано. Пусть закодировали А-0, Б-10.
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 00, 01, 100, 110. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Решение.
Кодовое слово для буквы П не может начинаться с 0, поскольку кодовые слова начинающиеся с 0, будут либо являться подстрокой кодовых слов для букв К и Л, либо включать в себя кодовые слова для букв К и Л. Кодовые слова 1, 10 и 11 взять не можем, поэтому букву П можно закодировать кодовыми словами 101 или 111. Возьмём кодовое слово с наименьшим числовым значением. Следовательно, букву П можно закодировать кодовым словом 101.
Ответ: 101.
Задание 2.
Для кодирования букв А,Б,В,Г используют неравномерный код Фано. Пусть закодировали А-01, Б-10. Какова наименьшая суммарная длина всех пяти кодовых слов.
Для кодирования букв А, Б, В, Г, Д, Е используют неравномерный код Фано. Пусть закодировали А-0, Б-10.
Какова наименьшая суммарная длина кодовых слов В, Г, Д, Е.
Задача 4.
Решение.
Для кодирования
некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили
использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для
буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова
наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?
Примечание.
Условие Фано означает, что никакое кодовое слово не является началом другого
кодового слова. Это обеспечивает возможность однозначной расшифровки
закодированных сообщений..Решение.
Для решения поставленной задачи, построим граф:
И еще один пример
Еще один пример с решением из прошлых лет. Взят с РешуЕГЭ
Решение.
Ответ: 14.
Кодовое слово длины 2 –
11, или любое из кодовых слов длины 3, неизбежно станет началом одного из слов
длины 4. Выбор длины 4 связан с тем, что была потребность в кодировании четырех
букв. Полученные кодовые слова в совокупности дают длину 16.
Ответ: 16.
И еще один пример
Еще один пример с решением из прошлых лет. Взят с РешуЕГЭ
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, Г — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Следующая буква должна кодироваться как 11, поскольку 10 мы взять не можем. 100 взять не можем из-за Г, значит, следующая буква должна быть закодирована кодом 101. Следующая буква должна кодироваться как 000, поскольку 00 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 001. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно 2 + 3 + 3 + 3 + 3 = 14.
Ответ: 14.
