Подходит ли код под условие фано. Готовимся к ЕГЭ по информатике. Условие Фано. Практическое применение условия Фано
Рассмотрим другую кодовую таблицу: А Б В Г Д 000 01 10 011 100 Здесь условие Фано не выполняется, поскольку код буквы Б (01) является началом кода буквы Г (011), а код буквы Д (100) начинается с кода буквы В (10). Тем не менее, можно заметить, что выполнено «обратное» условие Фано: ни один код не является окончанием другого кода (такой код называют постфиксным). Поэтому закодированное сообщение можно однозначно декодировать с конца. Например, рассмотрим цепочку 011000110110. Последней буквой в этом сообщении может быть только В (код 10): В 0110001101 10 Вторая буква с конца – Б (код 01): Б В 01100011 01 10 и так далее: Б Д Г Б В 01 100 011 01 10.
Слайд 26 из презентации «Методы кодирования информации» . Размер архива с презентацией 734 КБ.Методы кодирования
краткое содержание других презентаций«Двоичное кодирование» - Цифры. Двоичное кодирование текстовой информации. Таблица кодировки. Информационный объем текста. Двоичное кодирование в компьютере. Кодирование текстовой информации. Таблица расширенного кода. Символ. Уникальный двоичный код. Буква латинского алфавита. Использование двоичной системы. Компьютеры.
«Кодирование информации в двоичном коде» - Определение. Системы счисления. Двоичная система счисления. Кодирование. Кодирование информации. Приведите примеры кодирования. Десятичная система счисления. Значение цифры. Значение цифры зависит от ее положения. Алфавит. Языки. Римская непозиционная система. Двоичное кодирование. Что здесь зашифровано.
«Способы кодирования» - Номер столбца. Буква исходного текста. Кодирование информации. Способы кодирования информации. Декодируйте информацию. Передаваемая информация. В мире кодов. Автоматическое кодирование. Метод координат. Достоинства и недостатки. Разнообразие кодов. Мальчик. Как можно назвать записную книжку с точки зрения хранения информации. Закодированный текст. Носитель информации. Ключевые слова. Разгадайте ребус.
«Способы кодирования информации» - В памяти компьютера информация представлена в двоичном коде. Кодирование и декодирование. Можно закодировать информацию. Способы кодирования информации. Составим простейшую кодовую таблицу. Чтобы узнать зашифрованное слово, возьмите только первые слоги. Что прочитал Лом на флагах встречной шхуны. Придумайте собственный способ кодирования букв русского алфавита. Задания. Зашифрованная информация. Луи Брайль придумал специальный способ представления информации.
«Методы кодирования информации» - Двоичное кодирование в компьютере. Количество информации. Оптический телеграф Шаппа. Условие Фано. Какой код использовать. Получено сообщение. «Да» или «Нет». Первый телеграф. Способы кодирования информации. Запись информации. Почему двоичное кодирование. Сигнальные флаги. Кодирование. Кодирование и декодирование. Кодирование информации. Выбор способа кодирования. Виды информации. Сколько вариантов.
Урок посвящен тому, как решать 5 задание ЕГЭ по информатике
5-я тема характеризуется, как задания базового уровня сложности, время выполнения – примерно 2 минуты, максимальный балл — 1
- Кодирование - это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом .
- Кодирование бывает равномерным и неравномерным :
- при равномерном кодировании всем символам соответствуют коды одинаковой длины;
- при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.
Пример:
Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:
Таким образом, мы получили равномерный код
, т.к. длина каждого кодового слова одинакова для всех кодов
(2).
Кодирование и расшифровка сообщений
Декодирование (расшифровка) - это восстановление сообщения из последовательности кодов.
Для решения задач с декодированием, необходимо знать условие Фано:
Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)
Префиксный код - это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно.
Однозначное декодирование обеспечивается:
Решение 5 заданий ЕГЭ
ЕГЭ 5.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0 , 1 , 2 , 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.
✍ Решение:
- Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
Результат: 22162
Решение ЕГЭ данного задания по информатике, видео:
Рассмотрим еще разбор 5 задания ЕГЭ:
ЕГЭ 5.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице:
| a | b | c | d | e |
|---|---|---|---|---|
| 000 | 110 | 01 | 001 | 10 |
Какой набор букв закодирован двоичной строкой 1100000100110 ?
✍ Решение:
- Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.
- Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:
✎ 1 вариант решения:
Результат: b a c d e.
✎ 2 вариант решения:
110
000 01
001 10
Результат: b a c d e.
Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:
Решим следующее 5 задание:
ЕГЭ 5.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4 , и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23 , то получим последовательность 0010100110).
Определите, какое число передавалось по каналу в виде 01100010100100100110 .
✍ Решение:
- Рассмотрим пример из условия задачи:
Ответ: 6 5 4 3
Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:
ЕГЭ 5.4:
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0 , для буквы К - кодовое слово 10 .
Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
✍ Решение:
✎ 1 вариант решения основан на логических умозаключениях:
- Найдём самые короткие возможные кодовые слова для всех букв.
- Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н ).
- Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11 . Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
- Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111 . Условие Фано соблюдается.
✎ 2 вариант решения :
(Н) -> 0 -> 1 символ
(К) -> 10 -> 2 символа
(Л) -> 110 -> 3 символа
(М) -> 111 -> 3 символа
Ответ: 9
ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):
По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова: А: 101010 , Б: 011011 , В: 01000 .
Г, при котором код будет допускать однозначное декодирование. наименьшим числовым значением.
✍ Решение:
- Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010 , Б начинается с нуля — 011011 ).
- Следующим наименьшим кодом было бы двухбуквенное слово 00 . Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00 .
Результат: 00
ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 16 (под редакцией Крылова С.С., Чуркиной Т.Е.):
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код: А — 01 , Б — 00 , В — 11 , Г — 100 .
Укажите, каким кодовым словом должна быть закодирована буква Д.
Длина
этого кодового слова должна быть наименьшей
из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
✍ Решение:
Результат: 101
Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:
ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 17 (Крылов С.С., Чуркина Т.Е.):
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код: А — 0 , Б — 111 , В — 11001 , Г — 11000 , Д — 10 .
Укажите, каким кодовым словом должна быть закодирована буква Е. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
✍ Решение:
1 - не подходит (все буквы кроме А начинаются с 1)
10 - не подходит (соответствует коду Д)
11 - не подходит (начало кодов Б, В и Г)
100 - не подходит (код Д - 10 - является началом данного кода)
101 - не подходит (код Д - 10 - является началом данного кода)
110 - не подходит (начало кода В и Г)
111 - не подходит (соответствует коду Б)
1000 - не подходит (код Д - 10 - является началом данного кода)
1001 - не подходит (код Д - 10 - является началом данного кода)
1010 - не подходит (код Д - 10 - является началом данного кода)
1011 - не подходит (код Д - 10 - является началом данного кода)
1100 - не подходит (начало кода В и Г)
1101 - подходит
Результат: 1101
Более подробное решение данного задания представлено в видеоуроке:
5 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Укажите кратчайшее кодовое слово для буквы Б
, при котором код будет удовлетворять условию Фано.
Если таких кодов несколько, укажите код с наименьшим
числовым значением.
✍ Решение:
Результат: 1100
Подробное решение данного 5 задания из демоверсии ЕГЭ 2018 года смотрите на видео:
Задание 5_9. Типовые экзаменационные варианты 2017. Вариант 4 (Крылов С.С., Чуркина Т.Е.):
По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А , Б , В используются кодовые слова:
А: 00011 Б: 111 В: 1010
Укажите кратчайшее кодовое слово для буквы Г
, при котором код будет допускать однозначное декодирование.
Если таких кодов несколько, укажите код с наименьшим
числовым значением.
✍ Решение:
Результат: 00
Задание 5_10. Тренировочный вариант №3 от 01.10.2018 (ФИПИ):
По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р ; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:
Е – 000 Д – 10 К – 111
Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР
.
В ответе напишите число – количество бит.
✍ Решение:
Д Е Д М А К А Р
10 000 10 001 01 111 01 110
Результат: 20
Смотрите виде решения задания:
Задание 31. Неравномерные коды. Условие Фано
5-54.Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А - 001, Б - 010, В - 000, Г - 011.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
1) 00 2) 01 3) 0000 4) 101
5-85. Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У – 000, Ч – 001, Е – 010, Н – 100, И – 011, К – 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
Примечание. Префиксный код – это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
1) кодовое слово для буквы Е можно сократить до 01
2) кодовое слово для буквы К можно сократить до 1
3) кодовое слово для буквы Н можно сократить до 10
4) это невозможно
5-94. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б – кодовое слово 011. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
5-74. По каналу связи передаются сообщения, содержащие только 4 буквы: E, Н, О, Т. В любом сообщении больше всего букв О, следующая по частоте буква – Е, затем – Н. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?
1) Е – 0, Н – 1, О – 00, Т – 11 2) О – 1, Н – 0, Е – 01, Т – 10
3) Е – 1, Н – 01, О – 001, Т – 000 4) О – 0, Н – 10, Е – 111, Т – 110
5-105. По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?
1) А:1, Б:01, В:001, Г:111
2) А:1, Б:01, В:10, Г:111
3) А:00, Б:01, В:10, Г:11
4) А:100, Б:101, В:11, Г:0
5-102. В сообщении встречается 10 разных букв. При его передаче использован неравномерный двоичный префиксный код. Известны коды трех букв: 11, 100, 101. Коды остальных семи букв имеют одинаковую длину. Какова минимальная суммарная длина всех 10-ти кодовых слов?
5-104. В сообщении встречается 50 букв А, 30 букв Б, 20 букв В и 5 букв Г. При его передаче использован неравномерный двоичный префиксный код, который позволил получить минимальную длину закодированного сообщения. Какова она в битах?
По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для буквA, B, C используются такие кодовые слова: A – 111, B – 0, C – 100.
Укажите кратчайшее кодовое слово для буквыD, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
9-1-23. После преобразования растрового 256-цветного графического файла в 16-цветный формат его размер уменьшился на 15 Кбайт. Каков был размер исходного файла в Кбайтах?
9-1-25. После преобразования растрового графического файла его объем уменьшился в 1,5 раза. Сколько цветов было в палитре первоначально, если после преобразования было получено растровое изображение того же разрешения в 16-цветной палитре?
13-37. При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 8 символов, первый и последний из которых – одна из 18 букв, а остальные – цифры (допускается использование 10 десятичных цифр). Каждый такой идентификатор в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование; все цифры кодируются одинаковым и минимально возможным количеством бит, все буквы также кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти в байтах, отводимый этой программой для записи 500 паролей.
13-38. При регистрации в компьютерной системе, используемой при проведении командной олимпиады, каждому ученику выдается уникальный идентификатор – целое число от 1 до 1000. Для хранения каждого идентификатора используется одинаковое и минимально возможное количество бит. Идентификатор команды состоит из последовательно записанных идентификаторов учеников и 8 дополнительных бит. Для записи каждого идентификатора команды система использует одинаковое и минимально возможное количество байт. Во всех командах равное количество участников. Сколько участников в каждой команде, если для хранения идентификаторов 20 команд-участниц потребовалось 180 байт?
13-50. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 300 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.
16-165. Значение арифметического выражения: 9 22 + 3 66 – 18 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?
Естественно возникает вопрос: существуют ли неравномерные коды, для которых декодирование всегда однозначно? Да, существуют.
Роберт Фано сформулировал следующее достаточное условие того, что код имеет однозначное декодирование: никакое кодовое слово не является началом другого кодового слова. Если это условие выполнено, то никаких проблем с декодированием не будет.
Пусть A 1 , A 2 и A 3 - слова над некоторым алфавитом такие, что A 1 =A 2 A 3 , то есть A 1 получается из A 2 простым приписыванием к нему слова A 3 (слова A 2 или A 3 могут быть односимвольными). Назовем слово A 2 , которое является начальной частью слова A 1 , префиксом слова A 1 . Например, для слова 11101101 префиксами будут слова 1110110 , 111011 , 11101 , 1110 , 111 , 11 , 1 .
Тогда условие Фано для кодов, можно сформулировать так:
Никакое кодовое слово не является префиксом другого кодового слова .
Коды, удовлетворяющие условию Фано, называются префиксными . Итак, если код префиксный, он допускает однозначное декодирование.
Например, код, состоящий из кодовых слов {0, 10, 11} , является префиксным, и следующую кодовую последовательность 01001101110 можно разбить на кодовые слова единственным образом: 0 10 0 11 0 11 10 .
А код, состоящий из кодовых слов {0, 10, 11, 100} , префиксным не является и он не допускает однозначного декодирования. Действительно, ту же самую последовательность можно разбить на кодовые слова разными способами: 0 10 0 11 0 11 10 или 0 100 11 0 11 10 .
Важно отметить, что условие Фано является только достаточным условием однозначного декодирования для кодов, но не является необходимым условием.
Например, простой код, состоящий всего из двух кодовых слов {1, 10} , очевидно не является префиксным, но он дает однозначное декодирование любой кодовой последовательности, полученной при кодировании этим кодом. Действительно, в такой последовательности не может стоять рядом два нуля. А тогда каждый ноль со стоящей перед ней единицей заменяем на прообраз второго кодового слова, а все оставшиеся единицы - на прообраз первого слова, это и будет однозначным декодированием.
Существуют и другие, менее простые коды, обладающие тем же свойством. Например, код {01,10,011} также не является префиксным, но обладает однозначным декодированием (попробуйте доказать это самостоятельно).
Как же все-таки определить является ли код однозначно декодируемым, если для него не выполняется условие Фано? Можно использовать следующий метод.
Пусть слово A 2 является префиксом слова A 1 . Тогда A 1 =A 2 A 3 , где A 3 некоторое слово, конечная часть слова A 1 . Назовем A 3 суффиксом пары слов A 1 и A 2 , одно из которых является префиксом другого, а саму пару A 1 и A 2 назовем префиксной .
Рассмотрим в заданном коде все префиксные пары кодовых слов и построим по ним множество всех суффиксов. Далее рассмотрим все пары префиксных слов, из которых одно является кодовым, а другое – суффиксом, и для них построим суффиксы, расширяя множество суффиксов. Продолжим этот процесс до тех пор пока не перестанут появляться новые суффиксы. Код является однозначно декодируемым тогда и только тогда, когда никакой суффикс не совпадает ни с каким кодовым словом.
Например, для кода {01,10,011} множеством суффиксов будет {1,0,11} . Ни один суффикс здесь не совпадает ни с одним кодовым словом, поэтому, можно утверждать, что этот код является однозначно декодируемым.
Задача 1. Определить обладают ли свойством однозначной декодируемости следующие коды: а) {110, 11, 100, 00, 10} б) {100, 001, 101, 1101, 11011} .
Декодирование последовательностей, полученных кодами, не являющимися префиксными, требует более сложного анализа, чем для префиксных кодов. Префиксные коды иногда называют мгновенными (мгновенно декодируемыми), так как для них при чтении кодовой последовательности конец кодового слова распознается сразу по достижении конечного символа слова. В этом состоит преимущество префиксных кодов.
Демонстрационный вариант ЕГЭ 2019 г. – задание №5
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение:
Ответ:
Демонстрационный вариант ЕГЭ 2018 г. – задание №5
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение:
Ответ: 1100
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Демонстрационный вариант ЕГЭ 2017 г. – задание №5
Решение:
Для нахождения кодовых слов будем использовать данную таблицу.
Если коды остальных букв будет начинаться на 0, код буквы А=0 будет являться началом их кодов, поэтому этот вариант не подходит. Если код Б=10, коды букв В, Г, Д, Е начинаются на11. Чтобы получить 4 разных кода, нужно использовать коды, состоящие из 4-х символов (1111, 1110, 1101, 1100) .
| 0 | 1 | ||||
| 1 | |||||
| 1 | 0 | ||||
| 1 | 0 | 1 | 0 | ||
А - 0 (1 символ)
Б - 10 (2 символа)
В - 1100 (4 символа)
Г - 1101 (4 символа)
Д - 1110 (4 символа)
Е - 1111 (4 символа)
1+2+4+4+4+4 = 19
Ответ: 19
Демонстрационный вариант ЕГЭ 2016 г. – задание №5
По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение:
Для нахождения кодовых слов будем использовать данную схему.
Если коды остальных букв будет начинаться на 0 , код буквы О =0 будет являться началом их кодов, поэтому этот вариант не подходит. Так как код буквы П =100 , а код буквы Т =111 , то буква С не может начинаться и заканчиваться этими цифрами.
Ответ: 101
Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
Если таким способом закодировать последовательность символов ГАВБГВ и записать результат в шестнадцатеричном коде, то получится:
1) DACBDC 1 6 2) AD26 16 3) 621310 16 4) 62DA 16
Решение:
ГАВБГВ = 0110001011011010
| 0110 | 0010 | 1101 | 1010 |
| 6 | 2 | D | A |
Ответ: 4
Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.
Для компактности результат записали в восьмеричной системе счисления. Выберите правильную запись кода.
1) 57414 2) 53414 3) 53412 4) 53012
Решение:
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 101 | 011 | 100 | 001 | 010 |
| 5 | 3 | 4 | 1 | 2 |
Ответ: 3
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01100010100100100110?
1) 6543 2) 62926 3) 62612 4) 3456
Решение:
01100010100100100110
| 01100 | 01010 | 01001 | 00110 |
| 6 | 5 | 4 | 3 |
Ответ: 1
Для кодирования букв О, Л, А, З, К используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ЗАКОЛКА и записать результат в шестнадцатеричном коде, то получится:
1) 4531253 2) 9876 3) E832 4) 238E
Решение:
| О | Л | А | З | К |
| 0=00 | 1=01 | 2=10 | 3=11 | 4=100 |
ЗАКОЛКА = 1110100000110010
| 1110 | 1000 | 0011 | 0010 |
| E | 8 | 3 | 2 |
Ответ: 3
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=00, Б=11, В=100. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
1) 010 2) 0 3) 01 4) 011
Решение:
A=00, Б=11, В=100, Г=?
Ответ: 3
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 111, Б — 110, В — 101, Г — 100.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
1) 1 2) 0 3) 01 4) 10
Решение:
А — 111, Б — 110, В — 101, Г — 100, Д — ?
Ответ: 2
По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А — 10110, Б — 11000, В — 00101. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?
1) 01110 2) 01011 3) 10001 4) не подходит ни одно из указанных выше слов
Решение:
1) 01 110: А — 10 110 — не отличаются не менее чем в трёх позициях
2) 01011: А — 101 10 , Б — 1 1000 , В — 0010 1 — отличаются не менее чем в трёх позициях
Ответ: 2
Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:
А — 10001, Б — 01101, В — 10110.
При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 01111, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘х’).
Получено сообщение 00110 11101 11000 11001. Декодируйте это сообщение – выберите правильный вариант.
1) ВБхх 2) ВБВА 3) хххх 4) ВБхА
Решение:
| 00110 | 11101 | 11000 | 11001 |
| В=1 0110 | Б=0 1101 | x | А=10 001 |
Ответ: 4
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 1; Б – 0100; В – 000; Г – 011; Д – 0101. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
1) для буквы Г – 11 2) для буквы В – 00 3) для буквы Г – 01 4) это невозможно
Решение:
Ответ: 2
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б – кодовое слово 011. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
1) 7 2) 8 3) 9 4) 10
Решение:
А-1, Б-011, В-00, Г-010
Ответ: 9
По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?
1) А:1, Б:01, В:001, Г:111
2) А:1, Б:01, В:10, Г:111
3) А:00, Б:01, В:10, Г:11
4) А:100, Б:101, В:11, Г:0
Решение:
Ни одно кодовое слово не является началом другого: А является началом Г в 1-й и 2-й вариантах.
Общая длина закодированного сообщения должна быть как можно меньше.
3) А:00 (15), Б:01 (10), В:10 (6), Г:11 (4)
2.15+2.10+2.6+2.4 = 70
4) А:100 (15), Б:101 (10), В:11 (6), Г:0 (4)
3.15+3.10+2.6_1.4 = 61
Ответ: 3
По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы П, Р, С, Т. Каждой букве соответствует своё кодовое слово, при этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв П, Р, С используются 5-битовые кодовые слова: П: 01111, Р: 00001, С: 11000. 5-битовый код для буквы Т начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы Т.
Решение:
С: 1 1000
Т: 1 0110 (Т начинается с 1 и заканчивается на 0)
С и Т: 2 буквы одинаковы, то это означает, что остальные 3 буквы должны быть разными.
Ответ: 1 0110