Что такое однозначное декодирование информатика

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

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

Источник

Кодирование и декодирование данных

Домашнюю работу (для тех, кто брал карточку на оценку) на проверку можно прислать на почту umc.lebedkova@mail.ru в виде фото карточки и решения.

КОНСПЕКТ

Кодирование информации — процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки.

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

Примерами кодов являются последовательность букв в тексте, цифр в числе, двоичный компьютерный код и др.

При кодировании один символ исходного сообщения может заменяться одним или несколькими символами нового кода, и наоборот — несколько символов исходного сообщения могут быть заменены одним символом в новом коде. Примером такой замены служат китайские иероглифы, которые обозначают целые слова и понятия.

Кодирование может быть равномерным и неравномерным. При равномерном кодировании все символы заменяются кодами равной длины; при неравномерном кодировании разные символы могут кодироваться кодами разной длины (это затрудняет декодирование). Неравномерный код называют еще кодом переменной длины.

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

Декодирование — обратный процесс восстановления информации из закодированного представления.

В зависимости от системы кодирования информационный код может или не может быть декодирован однозначно. Равномерные коды всегда могут быть декодированы однозначно.

Для однозначного декодирования неравномерного кода важно, имеются ли в нем кодовые слова, которые являются одновременно началом других, более длинных кодовых слов.

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

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

Неравномерные коды, для которых выполняется условие Фано, называются префиксными. Префиксный код — такой неравномерный код, в котором ни одно кодовое слово не является началом другого, более длинного слова. В таком случае кодовые слова можно записывать друг за другом без разделительного символа между ними.

Например, код Морзе не является префиксным — для него не выполняется условие Фано. Поэтому в кодовый алфавит Морзе, кроме точки и тире, входит также символ–разделитель — пауза длиной в тире. Без разделителя однозначно декодировать код Морзе в общем случае нельзя.

РЕШЕНИЕ ЗАДАЧ

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

Решение:

Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:

Теперь закодируем последовательность букв из слова ВОДОПАД :

Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:

010 010 001 110 010

Результат: 22162

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

Какой набор букв закодирован двоичной строкой 1100000100110 ?

Решение:

Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.

Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:

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

Сделаем дерево, согласно кодам в таблице:

Сопоставим закодированное сообщение с кодами в дереве:

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

Задача 3:

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

Решение:

Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:

Суммарная длина всех четырёх кодовых слов равна:

(Н)1 + (К)2 + (Л)3 + (М)3 = 9

Ответ: 9.

ДОМАШНЕЕ ЗАДАНИЕ:

ВАРИАНТ 1 (для ребят, у которых фамилия начинается на букву А. Г, Д, Ж )

1) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 1100, 0010, 1010, 0000, 0111, 1101, 0101, 100, 0001. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

2) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 1010, 1101, 010, 00, 1000, 1110, 1001, 0111, 1011. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

ВАРИАНТ 2 (для ребят, у которых фамилия начинается на букву К, М, П, С )

3) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж использовали соответственно кодовые слова 11, 0010, 1011, 01, 0011, 000, 1010. Укажите кратчайшее возможное кодовое слово для буквы З, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

4) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е использовали соответственно кодовые слова 10, 110, 010, 0110, 111, 0111. Укажите кратчайшее возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

ВАРИАНТ 3 (для ребят, у которых фамилия начинается на букву Т, У, Ч, Ш, Я)

5) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е использовали соответственно кодовые слова 0101, 101, 011, 00, 0100, 11. Укажите кратчайшее возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

6) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е использовали соответственно кодовые слова 11, 0010, 100, 0011, 01, 000. Укажите кратчайшее возможное кодовое слово для буквы Ж, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Источник

Что такое однозначное декодирование информатика

Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.

Белый — 0, Зелёный — 11111, Фиолетовый — 11110, Красный — 1110, Чёрный — 10. Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет допускать однозначное декодирование.

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

Заметим, что кодовые слова, начинающиеся с 0, мы взять не можем, поскольку Белый уже закодирован кодовым словом 0. Кодовое слово 10 занято Чёрным. Кодовые слова, состоящие только из единиц, составить нельзя, иначе однозначное декодирование будет негарантированно. Значит, можем взять кодовое слово 110.

По каналу связи передаются сообщения, содержащие только 4 буквы: С, Л, О, Н; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв С, О, Н используются такие кодовые слова: С: 011, О: 00, Н: 11. Укажите такое кодовое слово для буквы Л, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите тот, у которого меньшая длина.

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

Вариант «1» не удовлетворяет условию Фано. Вариант «10» — удовлетворяет. Вариант «010» удовлетворяет условию Фано. Вариант «0» не удовлетворяет условию Фано.

Выбирая из второго и третьего варианта, останавливаемся на втором, поскольку он короче.

Правильный ответ указан под номером 2.

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

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

Вариант «1» не удовлетворяет условию Фано. Вариант «0» — не удовлетворяет. Вариант «01» удовлетворяет условию Фано. Вариант «101» удовлетворяет условию Фано.

Выбирая из четвёртого и третьего варианта, останавливаемся на третьем, поскольку он короче.

Правильный ответ указан под номером 3.

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

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

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

Вариант «1» не удовлетворяет условию Фано. Вариант «0» — не удовлетворяет. Вариант «11» удовлетворяет условию Фано. Вариант «001» удовлетворяет условию Фано.

Выбирая из четвёртого и третьего варианта, останавливаемся на третьем, поскольку он короче.

Правильный ответ указан под номером 3.

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

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

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

Вариант «1» не удовлетворяет условию Фано. Вариант «0» — не удовлетворяет. Вариант «00» удовлетворяет условию Фано. Вариант «110» удовлетворяет условию Фано.

Выбирая из четвёртого и третьего варианта, останавливаемся на третьем, поскольку он короче.

Правильный ответ указан под номером 3.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А–111, Б–110, В–100, Г–101.

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

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

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

Каждый из этих вариантов может быть новым словом, т. к. не является началом ни одного из кодовых слов. Поэтому выбираем самое короткое — 0.

Правильный ответ указан под номером 1.

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

Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.

Рассмотрим варианты для буквы Д, начиная с самого короткого.

1) Д=10: код буквы Д является началом кода буквы Б=101, поэтому этот вариант не подходит.

2) Д=11: код буквы Д является началом кода буквы В=111, Д=110, поэтому этот вариант не подходит.

3) Д=000: код буквы Д не является началом другого кода, следовательно, это правильный ответ.

4) Д=1111: код буквы Д является началом кода буквы В=111, поэтому этот вариант не подходит.

Правильный ответ указан под номером 3.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 001, Б — 010, В— 000, Г — 011.

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

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

Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.

Рассмотрим варианты для буквы Д, начиная с самого короткого.

1) Д=00: код буквы Д является началом кода буквы В=000, поэтому этот вариант не подходит.

2) Д=01: код буквы Д является началом кода буквы Б=010, Г=011, поэтому этот вариант не подходит.

3) Д=101: код буквы Д не является началом другого кода, следовательно, это правильный ответ.

Правильный ответ указан под номером 3.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 111, Б — 110, В — 101, Г — 100.

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

Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода. Рассмотрим варианты для буквы Д, начиная с самого короткого.

1) Д=1: код буквы Д является началом всех представленных кодов букв, поэтому этот вариант не подходит.

2) Д=0: код буквы Д не является началом другого кода, поэтому этот вариант подходит.

3) Д=01: код буквы Д не является началом другого кода, поэтому этот вариант подходит.

4) Д=10: код буквы Д является началом кодов букв В и Г, следовательно, этот вариант не подходит.

Таким образом, подходят два варианта: 0 и 01. 0 короче, чем 01.

Правильный ответ указан под номером 2.

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А — 0;

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

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.

Рассмотрим варианты для буквы Г, начиная с самого короткого.

1) Г=1: код буквы Г является началом кода буквы Б — 110, поэтому этот вариант не подходит.

2) Если код Г=01, то условие Фано нарушается, поскольку тогда код буквы А является началом кода буквы Г.

3) Если код Г=101, то условие Фано не нарушается. Данное кодовое слово является кратчайшим для буквы Г.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Однозначные коды не подходят по условию Фано. Кратчайшее подходящее кодовое слово — 01. Но выбирая его, не останется вариантов закодировать букву E, значит, нужно взять минимум трехзначный код. Минимальный из них, подходящий по условию Фано — 010. Тогда букву Е можно закодировать как 011.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Поскольку все однозначные и двузначные слова не подходят по условию Фано, нужно найти трехзначное слово, которое было бы максимально и удовлетряло условию. Так как 111, 101 и 110 нарушают условие Фано, то искомое слово — 010.

Заметим, что двузначное кодовое слово 01 не подходит, поскольку при его использовании нельзя подобрать кодовое слово для буквы Е.

Дублирует задание 13481.

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

Поскольку все однозначные и двузначные слова не подходят по условию Фано, значит, нужно найти трехзначное слово, которое было бы минимально и удовлетворяло условию. Это слово — 100. Однако при выборе кода 100 мы закрываем возможные варианты для D И E. Значит, трехзначные слова нам тоже не подходят, если взять четырехзначные то там мы для кодирования можем взять слово 1000. Тогда для кодирования D и E можно использовать слова 10010 и 10011.

Источник