двоичный код допускающий однозначное декодирование что это

В этом уроке мы поговорим о задании 4 из ЕГЭ по информатике 2022.

Задание 4 включает в себя понятие кодирование и декодирование информации.

Приступим к тренировочным заданиям из ЕГЭ по информатике 2022.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 00, 01, 100, 110. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Используем приём Дерево Фано. Расставим на этом дереве те буквы, для которых уже известны кодовые слова.

Дерево рисуется обычно сверху вниз. В начале от дерева рисуются две ветки: ветка 0 и ветка 1. От каждой ветки можно нарисовать ещё две ветки, так же 0 и 1, и т. д.

Для удобства ветки с 1 будем направлять вправо, а ветки с 0 будем направлять влево.

В конце каждой ветки можно размещать буквы, но если мы разместили букву, то эта ветка блокируется, и от этой ветки больше нельзя делать новые ответвления.

Нам осталось закодировать (расположить на дереве) две буквы: Д и Е.

Мы можем нарастить ещё две ветки от точки 1-1. Тогда получится код 111. И от точки 1-0. Тогда получится код 101.

Для буквы Д нужно выбрать код с наименьшим числовым значением. Значит, для буквы Д выбираем код 101, а для буквы Е выбираем код 111.

Закрепим приём дерево Фано на ещё одной примерной задаче из ЕГЭ по информатике 2022.

Для кодирования некоторой последовательности, состоящей из букв Н, О, П, Р, С, Т, У, Ф решили использовать неравномерный двоичный код, удовлетворяющий условию, что ни одно кодовое слово не является началом другого кодового слова. Для букв Н, О, П, Р, С, Т использовали соответственно кодовые слова 10, 110, 010, 0110, 111, 0111. Укажите кратчайшее возможное кодовое слово для буквы У, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Нам нужно закодировать ещё две буквы: У, Ф. У нас единственная возможность осталась прорастить ветку от точки 0. От этой точки проращиваем ветку 0 и от этой ветки проращиваем ещё две ветки 0 и 1.

Букву У размещаем на позиции 000, потому что для этой буквы нужно выбрать код с наименьшим числовым значением.

Ещё одна примерная задача из ЕГЭ по информатике 2022 является частым гостем в различных тренировочных вариантах.

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Д, Л, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 110, Б – 01, И – 000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ДЕЛЕНИЕ?

Расставим на дереве Фано буквы, для которых известны коды.

Нам осталось расположить 4 буквы: Д, Л, E, Н.

Буква Е встречается три раза в слове ДЕЛЕНИЕ, значит, ей нужно постараться присвоить самый короткий код. По дереву видно, что можно букве Е присвоить код 10.

Буквы Д, Л, Н встречаются в слове ДЕЛЕНИЕ 1 раз. Одну букву можно разместить на позицию 111. Так же можно продлить ветку из точки 00, а затем от позиции 001 сделать два отростка. У нас получатся ещё два свободных места: 0011 и 0010.

Можно оставшиеся буквы разместить следующим образом:

Подсчитаем какое количество двоичных знаков потребуется для кодирования слова ДЕЛЕНИЕ.

3+2+4+2+4+3+2=20
Ответ: 20

Далее решим непростую задачу из тренировочных вариантов ЕГЭ по информатике 2022. Похожая задача была в сборнике С. С. Крылова в 2021 году.

По каналу связи передаются сообщения, содержащие только четыре буквы: М, Н, Р, Т; для передачи используется двоичный код, допускающий однозначное декодирование.

Для букв М, Н, Р используются такие кодовые слова: М: 00011, Н: 1001, Р: 01100.

Укажите кратчайшее кодовое слово для буквы Т, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Нужно, чтобы код декодировался однозначно. Чтобы код декодировался однозначно, можно использовать условие Фано. Мы видим, что в уже известных кода не нарушается условие Фано. Узнаем код для буквы Т по дереву Фано. Отметим известные буквы.

Куда разместить букву Т? Чтобы кодовое слово было кратчайшее, разместим букву Т на позицию 11.

Сложность этой задачи заключается в том, что явно не указано, что нужно использовать условие Фано. Так же однозначное декодирование будет, если используется обратное условие Фано.

Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова. Сообщения при использовании такого кода декодируются однозначно и только с конца.

Т. е. сообщения нужно такие раскодировать справа налево. Здесь про то, как будут раскодировать сообщения, ничего не сказано, поэтому мы должны проверить, какой код получится для буквы Т, если здесь используется обратное условие Фано.

Получилась следующая ситуация. Если кодовые слова будут удовлетворяют условию Фано, то для буквы Т можно написать кратчайшее кодовое слово 11 с минимальным числовым значением. Если кодовые слова будут удовлетворяют обратному условию Фано, то для буквы Т можно написать кратчайшее кодовое слово 10 с минимальным числовым значением.

И в том и в другом случае будет однозначное декодирование. Но мы выбираем тот случай, когда кодовое слово будет наименьшим числовым значением. Таким образом, в ответе напишем 10.

Разберём ещё один нюанс в подобных задах из ЕГЭ по информатике.

Задача (Ещё раз про однозначное декодирование)

По каналу связи передаются сообщения, содержащие только четыре буквы: М, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, М используются такие кодовые слова: Т: 111, О: 0, М: 100. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Здесь условие похоже на то, которое было в предыдущей задаче. Но обратное условие Фано здесь не применимо, т.к. код для буквы О является окончанием для кода буквы М.

Выбираем из двух вариантов: 110 и 101. Но останавливаемся на 101, т.к. это кодовое слово с наименьшим числовым значением.

Решим задачу, которая часто встречается в бумажных сборниках по подготовке к ЕГЭ по информатике.

Задача (код не удовлетворяет условию Фано)

По каналу связи передаются шифрованные сообщения, содержащие только пять латинских букв: A, B, С, D, E. Для передачи используется неравномерный двоичный код. Для некоторых букв известны кодовые слова: A: 01, B: 10, C: 11, D: 000.

Укажите самое короткое кодовое слово для буквы E, при котором код не будет удовлетворять условию Фано, при этом в записи самого этого слова должно использоваться более одного символа, а само слово не должно совпадать ни с одним из используемых слов для букв с известными кодами.

Если таких слов несколько, то укажите слово с наименьшим числовым значением.

Здесь код не должен однозначно декодироваться.

Подходит код 00, т.к. длина этого кодового слова больше чем 1 символ. Этот код не совпадает ни с одним кодом для известных букв. Этот код нарушает принцип условия Фано, видно, что он является началом кодового слова буквы D. И этот код имеет самое маленькое числовое значение.

В 4 задании из ЕГЭ по информатике 2022 не обязательно может попасться задача, связанная с условием Фано. Может просто быть задача на кодирование и декодирование информации.

Для кодирования букв X, К, Л, О, Д решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ХОЛОДОК таким способом и результат запишите шестнадцатеричным кодом.

Распишем, как кодируются все буквы в двоичной системе. Ноль и один кодируются одним разрядом, поэтому к ним слева приписывается ноль, как написано в условии.

Выписываем слово ХОЛОДОК и под ним кодовые слова букв.

Чтобы перевести из двоичной системы число в шестнадцатиричную систему, мы должны двоичные цифры разбить по четвёркам, начиная с правого края. Каждая четвёрка превращается в цифру в шестандцатиричной системе. Таблицу перевода четвёрок двоичных цифр в шестнадцатиричную систему можно посмотреть в этой статье.

Т.к. ЕГЭ по информатике сдаётся в компьютерной форме, то можно воспользоваться стандартным калькулятором в режиме программист.

На этом всё! Пусть Вам повезёт на ЕГЭ по информатике 2022.

Источник

Привет! Сегодня узнаем, как решать 4 задание из ЕГЭ по информатике нового формата 2021.

Четвёртое задание из ЕГЭ по информатике раскрывает тему кодирование информации. Одним из центральных приёмов при решении задач подобного типа является построение дерева Фано. Рассмотрим на примерах этот метод.

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование

Т.к. код букв должен удовлетворять условию Фано (т.е. однозначно декодироваться), то расположим буквы, которые уже имеют код (A, B, C), на Дереве Фано.

Дерево Фано для двоичного кодирования начинается с двух направлений, которые означают 0(ноль) и 1(единицу) (цифры двоичного кодирования).

От каждого направления можно также рисовать только два направления: 0(ноль) и 1(единицу) и т.д. Для удобства будем рисовать 1(единицу) только вправо, а 0(ноль) только влево.

Получается структура похожая на дерево!

В конце каждой ветки можно располагать букву, которую мы хотим закодировать, но если мы расположили букву, от этой ветки больше нельзя делать новых ответвлений.

Такой подход позволяет однозначно декодировать сообщение, состоящее из этих букв.

Буква C заблокировала левую ветку, поэтому будем работать с правой частью нашего дерева.

Если мы расположим какую-нибудь букву на оставшуюся ветку (100), то эта ветка заблокируется, и нам некуда будет писать остальные 2 буквы. Поэтому продолжаем ветку (100) дальше.

Теперь свободно уже две ветки, а нам нужно закодировать ещё три буквы. Поэтому должны ещё раз продолжить дерево от какой-нибудь ветки.

Но уже видно, что букве F будет правильно присвоить код 1000, т.к. нам в условии сказано, что код буквы F должен соответствовать наименьшему возможному двоичному числу. Как расположить буквы D и E в данной задаче не принципиально.

Ещё один важный тип задания 4 из ЕГЭ по информатике нового формата 2021.

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 00, К — 010, Л — 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСЦИССА?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Коды букв должны удовлетворять условию Фано. Некоторые буквы уже имеют заданные коды (Б, К, Л). Нам нужно, чтобы слово АБСЦИССА имело как можно меньше двоичных знаков. Заметим, что буква C встречается три раза, а буква A два раза, значит, этим буквам стараемся присвоить как можно меньшую длину!

Отметим на дереве Фано уже известные буквы (Б, К, Л).

Если продолжить линию 1-0, то получится такая картина :

Теперь получились 4(четыре) свободные ветки равной длины (3(трём) двоичным символам). Т.к. ветки равной длины, то не важно на какую ветку какую букву расположим.

Посчитаем общую длину слова АБСЦИССА.

3 + 2 + 3 + 3 + 3 + 3 + 3 + 3 = 23.

Продлим линию 1-1-0 (можно и 0-1-1, не принципиально, т.к. эти ветки имеют одинаковую длину.), то получится:

С мы присваиваем 1-0, т.к. это буква повторяется в сообщении самое большое количество раз, значит, ей присваиваем самый маленький код, чтобы всё сообщение имело наименьшую длину.

Из этих же соображений букве А присваиваем код из трёх двоичных символов 0-1-1.

Подсчитаем общее количество символов в сообщении.

3 + 2 + 2 + 4 + 4 + 2 + 2 + 3 = 22

Длина получилась меньше, чем в первом варианте. Других вариантов нет, поэтому ответ будет 22.

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-10, Б-11, В-110, Г-0. Через канал связи передаётся сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в восьмеричный вид.

В этой задаче ничего не сказано про условие Фано. Здесь уже все буквы закодированы, осталось написать сам код.

Задача сводится к переводу из двоичной системы в восьмеричную систему. На эту тему был урок на моём сайте.

На этом всё! Увидимся на следующих занятиях по подготовке к ЕГЭ по информатике.

Источник

4 задание егэ информатика про кодирование и расшифровку сообщений

Кодирование информации

4-е задание: «Кодирование и декодирование информации»
Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 2 минуты.

Проверяемые элементы содержания: Умение кодировать и декодировать информацию

«Из-за невнимательного чтения условия задания экзаменуемые иногда не замечают, что требуется найти кодовое слово минимальной длины с максимальным (минимальным) числовым значением.

Кроме того, если в задании указано, что несколько букв остались без кодовых слов (как, например, в задании демоварианта), то кодовое слово для указанной буквы должно быть подобрано таким образом, чтобы осталась возможность найти кодовые слова, удовлетворяющие условию Фано, и для других букв. Так, например, если мы букву А закодируем нулём, а букву Б единицей, то букву В мы уже никак не сможем закодировать с соблюдением условия Фано, поэтому длину кодового слова для А или Б следует увеличить»

Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).

Кодирование и расшифровка сообщений

Для решения задач с декодированием, необходимо знать условие Фано:

Однозначное декодирование обеспечивается:

Решение 4 заданий ЕГЭ

Задание демонстрационного варианта 2022 года ФИПИ
Плейлист видеоразборов задания на YouTube:

Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

✍ Решение:

Результат: 22162

Решение ЕГЭ данного задания по информатике, видео:

Рассмотрим еще разбор 4 задания ЕГЭ:

✍ Решение:

Результат: b a c d e.

Этот вариант решения 4 задания ЕГЭ более сложен, но тоже верен.

Результат: b a c d e.

Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Решим следующее 4 задание:

✍ Решение:

Ответ: 6 5 4 3

Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

✍ Решение:

Ответ: 9

✍ Решение:

Результат: 00

✍ Решение:

Результат: 101

Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:

Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

✍ Решение:

Результат: 1100

Подробное решение данного 4 (раньше №5) задания из демоверсии ЕГЭ 2018 года смотрите на видео:

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

✍ Решение:

Дерево по условию Фано (однозначно декодируется с начала):

Дерево по обратному условию Фано (однозначно декодируется с конца):

Результат: 00

По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.

✍ Решение:

Результат: 20

Смотрите виде решения задания:

Источник

Двоичный код допускающий однозначное декодирование что это

Тема: Кодирование и декодирование информации.

· кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)

· обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход

· один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)

· кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование

· закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;

· закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;

· условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Пример задания:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Б – 01 2) это невозможно

3) для буквы В – 01 4) для буквы Г – 01

Решение (1 способ, проверка условий Фано):

1) для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано;

2) проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»);

«прямое» условие Фано не выполняется (код буквы Б совпадает с началом кода буквы В);

«обратное» условие Фано не выполняется (код буквы Б совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит ;

«прямое» условие Фано не выполняется (код буквы В совпадает с началом кода буквы Б);

«обратное» условие Фано не выполняется (код буквы В совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит ;

«прямое» условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В); но «обратное» условие Фано выполняется (код буквы Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит ;

Решение (2 способ, дерево):

1) построим двоичное дерево, в котором от каждого узла отходит две ветки, соответствующие выбору следующей цифры кода – 0 или 1; разместим на этом дереве буквы А, Б, В, Г и Д так, чтобы их код получался как последовательность чисел на рёбрах, составляющих путь от корня до данной буквы (красным цветом выделен код буквы В – 011):

2) здесь однозначность декодирования получается за счёт того, что при движении от корня к любой букве в середине пути не встречается других букв (выполняется условие Фано);

3) теперь проверим варианты ответа: предлагается перенести одну из букв, Б, В или Г, в узел с кодом 01, выделенный синим цветом

4) видим, что при переносе любой из этих букв нарушится условие Фано; например, при переносе буквы Б в синий узел она оказывается на пути от корня до В, и т.д.; это значит, что предлагаемые варианты не позволяют выполнить прямое условие Фано

5) хочется уже выбрать вариант 2 («это невозможно»), но у нас есть еще обратное условие Фано, для которого тоже можно построить аналогичное дерево, в котором движение от корня к букве дает её код с конца (красным цветом выделен код буквы В – 011, записанный с конца):

видно, что обратное условие Фано также выполняется, потому что на пути от корня к любой букве нет других букв

6) в заданных вариантах ответа предлагается переместить букву Б, В или Г в синий узел; понятно, что Б или В туда перемещать нельзя – перемещённая буква отказывается на пути от корня к букве Г; а вот букву Г переместить можно, при этом обратное условие Фано сохранится

Ещё пример задания:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

1) 00 2) 01 3)11 4) 010

8) заметим, что для известной части кода выполняется условие Фано – никакое кодовое слово не является началом другого кодового слова

9) если Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ; поэтому первый вариант не подходит

10) если Д = 01, такая кодовая цепочка совпадает с началом Г = 011, невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г; поэтому второй вариант тоже не подходит

11) если Д = 11, условие Фано тоже нарушено: кодовое слово А = 1 совпадает с началом кода буквы Д, невозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит

12) для четвертого варианта, Д = 010, условие Фано не нарушено;

· условие Фано – это достаточное, но не необходимое условие однозначного декодирования, поэтому для уверенности полезно найти для всех «неправильных» вариантов контрпримеры: цепочки, для которых однозначное декодирование невозможно

Еще пример задания:

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится

14) из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный

15) последовательность БАВГ кодируется так: 01 00 10 11 = 1001011

16) разобьем такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем

1001011 = 0100 1011₂ = 4B ₁₆

17) правильный ответ – 1.

· расчет на то, что при переводе тетрад в шестнадцатеричную систему можно забыть заменить большие числа (10–15) на буквы (1011₂ = 11, получаем неверный ответ 411₁₆)

· может быть дан неверный ответ, в котором нужные цифры поменяли местами (расчет на невнимательность), например, B 4₁₆

· в ответах дана последовательность, напоминающая исходную (неверный ответ BACD ₁₆), чтобы сбить случайное угадывание

Еще пример задания:

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:

Источник