При котором код будет допускать однозначное декодирование

2

ЕГЭ по информатике 2021 — Задание 4 (Условие Фано)

Привет! Сегодня узнаем, как решать 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 в данной задаче не принципиально.

Ответ: 1000.

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

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

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

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

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

У нас осталось 4 (четыре) буквы, а свободных веток 3(три), поэтому мы должны продолжить дерево. но какую ветку продолжить ?

Если продолжить линию 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. Через канал связи передаётся сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в восьмеричный вид.

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

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

Ответ: 151646.

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

Однозначное декодирование

Понятие однозначного декодирования

Вы любите шпионов? А готовы почувствовать себя в их шкуре?

Нам нужно передать секретное сообщение на базу, а раз оно секретное, никто не должен понять, что мы передаем. Для этого надо представить наше сообщение в каком-то новом виде, который на первый взгляд будет бессмысленным, но мы будем знать, как его расшифровать.

Главное — чтобы расшифровать было возможно.

Мы уже знаем, что для компьютера информацию надо представить в двоичномкоде — подробнее об этом рассказано в статье «Основные понятия об информации». Но сам процесс кодирования информации — не такая простая вещь. Есть несколько факторов, которые нужно соблюсти, чтобы кодирование прошло хорошо.

Но чтобы научиться делать что-то правильно, сначала надо разобраться, как сделать неправильно. Давайте попробуем произвольным образом закодировать буквы К, У, Р, Л, Ы, чтобы составлять из них сообщения.

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

С помощью кодовых слов каждой отдельной буквы закодируем сообщение КУРЛЫК, для этого на место каждой буквы будем подставлять соответствующее ей кодовое слово:

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

Равномерное кодирование

Но как можно соблюдать это условие? Или еще круче — как строить кодовые слова, которые заранее будут этому условию удовлетворять?

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

Кодируем сообщение КУРЛЫК:

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

Такой метод действительно прост и в освоении, и при составлении кодовых слов, и при расшифровке. Но есть один минус — он не всегда эффективен.

Выбирая длину одного кодового слова, мы можем заранее определить количество возможных кодов: так как на каждой позиции может быть либо 0, либо 1, количество возможных кодов N длины i будет равно

\(N = 2^i\).

Выбрав длину 3 для наших кодовых слов, мы имеем 8 различных кодов, хотя кодируем всего 5 букв.

В других ситуациях потери могут быть плачевнее: для кодирования, например, 33 букв русского алфавита длина кодового слова должна быть не меньше 6 (если выберем 5, получим максимум 2 5 = 32 кодового слова, но тогда 1 буква останется незакодированной).

Но имея 2 6 = 64 кодовых слова для 33-х букв алфавита, мы явно взяли кодов больше, чем нужно.

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

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

Условие Фано и дерево вариантов

Условие Фано гласит: «ни одно кодовое слово не должно быть началом другого кодового слова».

В составленных нами в самом начале статьи кодовых словах это условие нарушалось — код буквы К (010) начинался с кода буквы У (01), а код Ы (001) — с кода Р (00). Из-за этого мы не могли быть точно уверены, где закончилось кодовое слово, а где оно продолжается.

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

Давайте попробуем таким образом получить ровно 5 кодовых слов, чтобы закодировать наши буквы К, У, Р, Л, Ы.

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

1. Допустим, мы добавим 0 и 1 к кодовому слову 1, и вместо него теперь получим два новых — 10 и 11. Теперь кодовых слов у нас уже три — 0, 10 и 11.
   Все еще мало, продолжаем построение дерева.

1. Мы проделали ту же операцию с кодовым словом 0, заменив его на 2 новых — 00 и 01.
   Кодовых слов стало 4, этого все еще мало, нужно продолжить построение дерева.

1. Из конечных узлов можно выбрать любой для продолжения построения, например — 01, продолжив это кодовое слово, получаем два новых — 010 и 011.

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

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

Так, код 010110010011010 мы можем однозначно декодировать, читая его слева направо:

Его формулировка немного отличается: «ни одно кодовое слово не должно быть окончанием другого». Такая формулировка уже допустит сосуществование кодовых слов 011 и 01, но не допустит 110 и 10, так как второе совпадает с окончанием первого.

И код 010110001110010 будет читаться уже в другую сторону – из конца в начало:

Практика

В жизни чаще всего используются равномерные кодировки в силу многих причин, таких как:

1. Большая устойчивость.

Представим, что мы передаем слово КУРЛЫК разными вариантами, но при передаче допускаем ошибку в четвертом бите (в четвертом символе нашего кода). Посмотрим, что получится в итоге.

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

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

2. Простота расширения.

Мы обсуждали, что проблема равномерного кодирования — в большом количестве «пустых мест». Но эти пустые места могут быть полезны. Например, захочет разработчик добавить в код несколько новых эмодзи. У него как раз есть незанятые коды для этих символов. Согласитесь, это удобнее, чем переписывать всю кодировку целиком.

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

Также применение неравномерной кодировки есть в 4 задаче ЕГЭ и во 2 задаче ОГЭ.

Разберем задачу №4 ЕГЭ:

По каналу связи передаются закодированные сообщения о состоянии системы, состоящие из пяти символов: A, B, C, D, E. При передаче сообщений используется двоичный код, при этом он допускает однозначное декодирование. Для символов A, B, C используются эти кодовые слова: 1, 010 и 001 (соответственно).

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

Решение.

Шаг 1. Построим дерево вариантов кодовых слов и отметим на нем уже известные коды букв:

Шаг 2. Заметим, что раз для символа A кодовое слово 1, то в дальнейшем нам не подойдут любые коды, начинающиеся с 1, так как для них и символа A не будет выполняться условие однозначного декодирования.

Шаг 3. Начнем разбирать по возрастанию кодовые слова, начинающиеся с 0:

• 0 — не подойдет, будет началом для кодовых слов 001 и 010.
• 00 — не подойдет, будет началом слова 001.
• 01 — не подойдет, будет началом слова 010.
• 000 — подойдет.
• 001 — не подойдет, буква C.
• 010 — не подойдет, буква B.
• 011 — подойдет.

Шаг 4. Получаем два недостающих кодовых слова равной длины: 000 и 011. Значит, можем использовать их для букв Е и D, при этом сохранив однозначное декодирование. Для D нужно слово, меньшее по значению, тогда верным ответом будет 000.

Ответ: 000
В этой статье мы познакомились с условием Фано и научились правильно кодировать и декодировать сообщения. Но различные виды информации требуют собственных уникальных подходов. Приглашаем вас продолжить изучение темы в статьях «Кодирование изображения» и «Кодирование звука».

Фактчек

• Условие однозначного декодирования необходимо для того, чтобы у закодированного сообщения был ровно один вариант расшифровки — исходный.
• Однозначное декодирование может давать равномерное кодирование, при котором все кодовые слова имеют одинаковую длину, или кодовые слова, составленные по условию Фано, которое гласит: «ни одно кодовое слово не должно совпадать с началом другого кодового слова».
• Существует другая вариация этого условия — обратное условие Фано, оно гласит: «ни одно кодовое слово не должно совпадать с окончанием другого кодового слова».
• Для составления кодовых слов, удовлетворяющих условию Фано, используется дерево вариантов.

Проверь себя

Задание 1.
Для чего необходимо условие однозначного декодирования?

1. Для более удобной шифровки сообщений.
2. Для построения минимально возможных кодовых слов.
3. Для сохранения возможности абсолютно точно получить исходное сообщение из закодированного.
4. Для красоты.

Задание 2.
Выберите верные утверждения:

1. При равномерном кодировании все кодовые слова имеют одну длину.
2. При равномерном кодировании кодовые слова не могут начинаться на один и тот же символ.
3. Для соблюдения условия Фано необходимо, чтобы ни одно кодовое слово не совпадало с окончанием другого кодового слова.
4. Обратное условие Фано не гарантирует однозначное декодирование.
5. Для составления кодовых слов, удовлетворяющих обратному условию Фано, используется дерево вариантов.

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

1. 1, 11, 111, 1111, 11111, 0.
2. 01, 001, 0001, 00001, 1
3. 000, 111, 100, 001
4. 10, 11, 00, 1001
5. 10, 100, 1000, 10000

Задание 4.
Для передачи сообщений используются буквы А, Б, В, Г, Д. Известны некоторые кодовые слова: А = 01, Б = 111, В = 00, Г = 110. Какое кодовое слово может соответствовать кодовому слову для буквы Д, чтобы весь код удовлетворял условию Фано?

1. 0
2. 11
3. 101
4. 1100

Ответы: 1. — 3; 2. — 1, 5; 3. — 2, 3, 4, 5; 4. — 3.

6. Задание 4. Кодирование и декодирование информации

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

Задача 1

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление
чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится
1) 22162
2) 1020342
3) 2131453
4) 34017

Решение:
Представим коды указанных букв в дво­ич­ном коде, добавив незначащий нуль для одноразрядных чисел:

Закодируем по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010.
Разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём каждую тройку в восьмеричное число.
010 010 001 110 010 — 22162.
Пра­виль­ный ответ ука­зан под но­ме­ром 1.
Ответ: 1

Задача 2

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние: А-10, Б-11, В-110, Г-0. Через канал связи пе­ре­даётся со­об­ще­ние: ВАГ­БА­А­ГВ. За­ко­ди­руй­те со­об­ще­ние дан­ным кодом. По­лу­чен­ное дво­ич­ное число пе­ре­ве­ди­те в шест­на­дца­те­рич­ный вид.
1) D3A6
2) 62032206
3) 6A3D
4) CADBAADC

Решение:
За­ко­ди­ру­ем по­сле­до­ва­тель­ность букв: ВАГ­БА­А­ГВ — 1101001110100110. Разобьем это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём каждую четверку в шестнадцатеричное число:
1101 0011 1010 01102 = D3A6₁₆
Пра­виль­ный ответ ука­зан под но­ме­ром 1.
Ответ: 1

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

Опре­де­ли­те, какой набор букв за­ко­ди­ро­ван дво­ич­ной стро­кой 1000110110110, если из­вест­но, что все буквы в по­сле­до­ва­тель­но­сти – раз­ные:
1) cbade
2) acdeb
3) acbed
4) bacde

Решение:
Мы видим, что усло­вия Фано и об­рат­ное усло­вие Фано не вы­пол­ня­ют­ся, зна­чит код можно рас­ко­ди­ро­вать не­од­но­знач­но.
Значит, будем перебирать варианты, пока не получим подходящее слово :
1) 100 011 01 10 110
Пер­вая буква опре­де­ля­ет­ся од­но­знач­но, её код 100: a.
Пусть вто­рая буква — с, тогда сле­ду­ю­щая буква — d, потом — e и b.
Такой ва­ри­ант удо­вле­тво­ряет усло­вию, зна­чит, окон­ча­тель­но по­лу­чи­ли ответ: acdeb.
Ответ: 2

Задача 4

Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01010100100111100011?
1) 59143 2) 5971 3) 102153 4) 10273

Решение:
При кодировании под саму цифру отводится 4 разряда, и еще один под код проверки четности (т.е. всего под цифру отводится 5 разрядов).
Разобьем заданную последовательность на группы по 5 бит в каждой:
01010, 10010, 01111, 00011.
отбросим пятый (последний) бит в каждой группе:
0101, 1001, 0111, 0001.
это и есть двоичные коды передаваемых чисел:
01012 = 5, 10012 = 9, 01112 = 7, 00012 = 1.
таким образом, были переданы числа 5, 9, 7, 1 или число 5971.
Ответ: 2

Задача 5

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы — П, О, Р, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ют­ся 5-би­то­вые ко­до­вые слова:
П — 11111, О — 11000, Р — 00100, Т — 00011.
Для этого на­бо­ра ко­до­вых слов вы­пол­не­но такое свой­ство: любые два слова из на­бо­ра от­ли­ча­ют­ся не менее чем в трёх по­зи­ци­ях.
Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех (в пред­по­ло­же­нии, что пе­ре­да­ва­е­мые биты могут ис­ка­жать­ся, но не про­па­да­ют). За­ко­ди­ро­ван­ное со­об­ще­ние счи­та­ет­ся при­ня­тым кор­рект­но, если его длина крат­на 5 и каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции; при этом счи­та­ет­ся, что пятёрка ко­ди­ру­ет со­от­вет­ству­ю­щую букву. На­при­мер, если при­ня­та пя­тер­ка 00000, то счи­та­ет­ся, что пе­ре­да­ва­лась буква Р.

Среди при­ведённых ниже со­об­ще­ний най­ди­те то, ко­то­рое при­ня­то кор­рект­но, и ука­жи­те его рас­шиф­ров­ку (про­бе­лы не­су­ще­ствен­ны).
11011 11100 00011 11000 01110
00111 11100 11110 11000 00000

1) ПОТОП
2) РОТОР
3) ТОПОР
4) ни одно из со­об­ще­ний не при­ня­то кор­рект­но

Решение:
Длина обоих со­об­ще­ний крат­на пяти.
Ана­ли­зи­руя пер­вое со­об­ще­ние «11011 11100 00011 11000 01110», при­хо­дим к вы­во­ду, что оно при­ня­то не­кор­рект­но, по­сколь­ку нет та­ко­го слова, ко­то­рое бы от­ли­ча­лось от слова «01110» толь­ко в одной по­зи­ции.
Рас­смот­рим вто­рое со­об­ще­ние. Учи­ты­вая, что каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции, его воз­мож­но рас­шиф­ро­вать толь­ко как «ТОПОР».
Ответ: 3

Задача 6

Для пе­ре­да­чи дан­ных по ка­на­лу связи ис­поль­зу­ет­ся 5-би­то­вый код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б и В, ко­то­рые ко­ди­ру­ют­ся сле­ду­ю­щи­ми ко­до­вы­ми сло­ва­ми: А — 11010, Б — 10111, В — 01101.
При пе­ре­да­че воз­мож­ны по­ме­хи. Од­на­ко не­ко­то­рые ошиб­ки можно по­пы­тать­ся ис­пра­вить. Любые два из этих трёх ко­до­вых слов от­ли­ча­ют­ся друг от друга не менее чем в трёх по­зи­ци­ях. По­это­му если при пе­ре­да­че слова про­изо­шла ошиб­ка не более чем в одной по­зи­ции, то можно сде­лать обос­но­ван­ное пред­по­ло­же­ние о том, какая буква пе­ре­да­ва­лась. (Го­во­рят, что «код ис­прав­ля­ет одну ошиб­ку».) На­при­мер, если по­лу­че­но ко­до­вое слово 10110, счи­та­ет­ся, что пе­ре­да­ва­лась буква Б. (От­ли­чие от ко­до­во­го слова для Б толь­ко в одной по­зи­ции, для осталь­ных ко­до­вых слов от­ли­чий боль­ше.) Если при­ня­тое ко­до­вое слово от­ли­ча­ет­ся от ко­до­вых слов для букв А, Б, В более чем в одной по­зи­ции, то счи­та­ет­ся, что про­изо­шла ошиб­ка (она обо­зна­ча­ет­ся ‘х’).

По­лу­че­но со­об­ще­ние 11000 11101 10001 11111. Де­ко­ди­руй­те это со­об­ще­ние — вы­бе­ри­те пра­виль­ный ва­ри­ант.

1) АххБ
2) АВхБ
3) хххх
4) АВББ

Решение:
Де­ко­ди­ру­ем каж­дое слово со­об­ще­ния. Пер­вое слово: 11000 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Вто­рое слово: 11101 от­ли­ча­ет­ся от буквы В толь­ко одной по­зи­ци­ей. Тре­тье слово: 10001 от­ли­ча­ет­ся от любой буквы более чем одной по­зи­ци­ей. Четвёртое слово: 11111 от­ли­ча­ет­ся от буквы Б толь­ко одной по­зи­ци­ей.
Таким об­ра­зом, ответ: АВхБ.
Ответ: 2

Однозначное декодирование. Условие Фано

Код называется однозначно декодируемым, если любое сообщение, составленное из кодовых слов, можно декодировать единственным способом.
Равномерное кодирование всегда однозначно декодируемо.
Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:
Сообщение однозначно декодируемо с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова.
Сообщение однозначно декодируемо с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.

Задача 7

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из букв А, Б, В, Г, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный по длине код: A=1, Б=01, В=001. Как нужно за­ко­ди­ро­вать букву Г, чтобы длина кода была ми­ни­маль­ной и до­пус­ка­лось од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на буквы?
1) 0001
2) 000
3) 11
4) 101

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

Видим, что ближайший от корня дерева свободный лист (т.е. код с минимальной длиной) имеет код 000.
Ответ: 2

Задача 8

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв У, Ч, Е, Н, И и К, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный пре­фикс­ный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му остал­ся пре­фикс­ным? Коды осталь­ных букв ме­нять­ся не долж­ны.
Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.
При­ме­ча­ние. Пре­фикс­ный код — это код, в ко­то­ром ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го; такие коды поз­во­ля­ют од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность.
1) ко­до­вое слово для буквы Е можно со­кра­тить до 01
2) ко­до­вое слово для буквы К можно со­кра­тить до 1
3) ко­до­вое слово для буквы Н можно со­кра­тить до 10
4) это не­воз­мож­но

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

Легко заметить, что если букву Н перенести в вершину 10, она останется листом. Т.е. ко­до­вое слово для буквы Н можно со­кра­тить до 10.
Пра­виль­ный ответ ука­зан под но­ме­ром 3.
Ответ: 3

Задача 9

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв К, Л, М, Н, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для буквы Н ис­поль­зо­ва­ли ко­до­вое слово 0, для буквы К — ко­до­вое слово 110. Ка­ко­ва наи­мень­шая воз­мож­ная сум­мар­ная длина всех четырёх ко­до­вых слов?
1) 7
2) 8
3) 9
4) 10
При­ме­ча­ние. Усло­вие Фано озна­ча­ет, что ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний.

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

Легко заметить, что ближайшие от корня свободные листы (т.е. свободные коды с наименьшей длиной) – это 10 и 111. Таким об­ра­зом, наи­мень­шая воз­мож­ная сум­мар­ная длина всех четырёх ко­до­вых слов будет 1 + 3 + 2 + 3 = 9.
Пра­виль­ный ответ ука­зан под но­ме­ром 3.
Ответ: 3

Задача 10

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

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

Легко заметить, что ближайшие от корня свободные листы (т.е. свободные коды с наименьшей длиной) – это 101 и 110. Наименьшее числовое значение имеет код 101.
Ответ: 101

Благодарим за то, что пользуйтесь нашими материалами. Информация на странице «6. Задание 4. Кодирование и декодирование информации» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам. Чтобы успешно сдать необходимые и поступить в высшее учебное заведение или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из данного раздела.

Мысли вслух

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А — 00, Б — 01, В — 100, Г — 101, Д — 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Д — 11; 2) это невозможно; 3) для буквы Г — 10; 4) для буквы Д — 10

Как показывает практика, эта задача вызывает серьезные трудности не только у многих учеников, но даже у учителей информатики.

Нужно сказать, что этот материал практически не рассматривается в существующих школьных учебниках информатики, поэтому все (как ученики, так и учителя) вынуждены разбираться самостоятельно. В то же время вузовские учебники [2-5], где соответствующая теория изложена строго и научно, достаточно сложны для понимания. Попробуем разобраться в сути кодирования и декодирования на школьном уровне, то есть так, как можно объяснить ученикам 8-11 классов.

В чём проблема?

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

Пример 1. Пусть для кодирования фразы «МАМА МЫЛА ЛАМУ» выбран такой код:

Коды букв «сцепляются» в одну битовую строку и передаются, например, по сети:
Эта цепочка битов приходит в пункт назначения, и тут возникает проблема — как восстановить исходное сообщение (конечно, при условии, что мы знаем код, то есть знаем все пары «символ–кодовое слово», которые использовались при кодировании).

Итак, мы получили 0010011100010111010010. Легко понять, что при использовании кода (1) раскодировать такое сообщение можно самыми разными способами. Например, можно предположить, что оно составлено только из букв А (код 1) и Л (код 0). Тогда получаем
В общем, ни мамы, ни ламы.

Определение. Код называется однозначно декодируемым, если любое кодовое сообщение можно расшифровать единственным способом (однозначно).

Сказанное выше означает, что код (1) НЕ является однозначно декодируемым. Как же определить, является ли заданный код однозначно декодируемым? Этим вопросом мы и займемся.

Равномерные коды

Проблема состоит в том, чтобы правильно разбить полученную битовую цепочку на отдельные кодовые слова. Для того, чтобы её решить, можно, например, использовать равномерный код, то есть код, в котором все кодовые слова имеют одинаковую длину. Например, в нашей фразе 6 символов, поэтому можно использовать 3-битный код (который позволяет закодировать 8 = 2 3 различных символов).

Пример 2. Закодируем фразу из примера 1, используя код:

Получаем закодированное сообщение
Длина этого сообщения — 42 бита вместо 22 в предыдущем варианте, зато его легко разбить на отдельные кодовые слова и раскодировать («_» обозначает пробел):
Видим, что равномерные коды неэкономичны (закодированное сообщение в примере 2 почти в два раза длиннее, чем в примере 1), но зато декодируются однозначно.

Неравномерные коды

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

Пример 3. Используем для кодирования фразы из примера 1 следующий код:

Получаем
Здесь 34 бита. Это, конечно, не 22, но и не 42.

Несложно показать, что эта битовая цепочка декодируется однозначно. Действительно, первая буква — М (код 01), потому что ни одно другое кодовое слово не начинается с 01. Аналогично определяем, что вторая буква — А. Действительно, за 01 следует 00 (код буквы А) и никакое другое кодовое слово не начинается с 00. Это же свойство, которое называется условием Фано, выполняется не только для кодовых слов 01 и 00, но и кодовых слов всех других букв (проверьте это самостоятельно).

Условие Фано. Никакое кодовое слово не совпадает с началом другого кодового слова.

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

Упражнение. Расшифруйте сообщение, закодированное кодом (3). При расшифровке кода очередной буквы не заглядывайте вперёд!
Термины «условие Фано» и «префиксный код» не используются в заданиях ЕГЭ и ГИА, однако для решения этих задача важно, чтобы ученики понимали содержание условия Фано.

Пример 4. Рассмотрим ещё один код

Ясно, что он не является префиксным: код буквы А (00) совпадает с началом кода буквы Л (001) и код пробела (11) совпадает с началом кода буквы Ы (11). Закодированное сообщение
также имеет длину 34 бита, как и при использовании кода (3). Начнем раскодировать с начала. Ясно, что первой стоит буква М, потому что ни один другой код не начинается с 10. Затем — комбинация 001, которая может быть кодом буквы Л или кодом буквы А (00), за которым следует код буквы Ы или пробела. Получается, что для декодирования сообщения нам нужно «заглядывать вперёд», что очень неудобно.

Попробуем декодировать с конца битовой строки. Последние биты 0101 могут представлять только букву У, следующие 10 — только букву М и т.д. Можно проверить, что теперь сообщение однозначно декодируется с конца! Это происходит потому, что выполняется условие, которое можно назвать «обратным» условием Фано: никакое кодовое слово не совпадает с окончанием другого кодового слова. Коды, для которых выполняется обратное условие Фано, называют постфиксными (постфикс или суффикс слова — это его конечный фрагмент). В этом случае тоже обеспечивается однозначное декодирование. Таким образом,

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

• для однозначной декодируемости достаточно выполнение хотя бы одного из двух условий, или прямого, или обратного;
• могут существовать коды, для которых не выполняется ни прямое, ни обратное условие Фано, но они, тем не менее, обеспечивают однозначное декодирование.

Однозначно декодируемые коды

Пример 5. Рассмотрим код, предназначенный для кодирования сообщений, состоящих только из букв А, Б и В:

Так как код буквы А (0) совпадает как с началом, так и с концом кода буквы В (010), для этого кода не выполняются ни прямое, ни обратное условие Фано. Поэтому пока мы не можем с уверенностью сказать, декодируется ли он однозначно.

Закодируем сообщение
и попытаемся раскодировать эту строку, используя код (5). В первую очередь, замечаем, что две соседние единицы могут появиться только при использовании буквы Б (код 11), поэтому сразу выделяем две таких группы:
Здесь жёлтым фоном выделена уже декодированная часть сообщения. В оставшейся части единица может появиться только в коде буквы В (010), в битовой строке находим две такие группы:
Оставшиеся нули — это коды букв А. Анализ алгоритма показывает, что такой код всегда однозначно декодируется.

Полный ответ на вопрос об однозначной декодируемости получил в начале 1960-х годов советский математик Ал.А. Марков, предложивший решение с помощью графов [2]. Продемонстрируем его метод на примере.

Пример 6. Рассмотрим код

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

1. Определяем все последовательности (строки), которые
   а) совпадают с началом какого-то кодового слова и одновременно с концом какого-то кодового слова и
   б) сами не являются кодовыми словами.
   В данном случае это две последовательности:
   0 (начало кода буквы А и конец кода буквы Б) и
   1 (начало кода буквы Г и конец кода буквы Д);
   10 (начало кода буквы Д и конец кода буквы Б);
   последовательности 01 и 11 не учитываем, потому что они совпадают с кодами букв А и Г;
2. Добавляем к этому множеству <0, 1, 10>пустую строку, которую обычно обозначают греческой буквой Λ; элементы полученного множества <Λ, 0, 1, 10>будут вершинами графа:

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

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

1. цикл «Λ0Λ», соответствующий сообщению ΛА0ГΛ = 01011; это сообщение может быть расшифровано как АВ и как БГ;
2. цикл «Λ1Λ», соответствующий сообщению ΛА1АΛ = 01101; это сообщение может быть расшифровано как АД и как ВА;
3. цикл «Λ01Λ», соответствующий сообщению ΛА01АΛ = 010101; это сообщение может быть расшифровано как ААА и как БД;
4. цикл «Λ0101Λ», соответствующий сообщению ΛА0101АΛ = 01010101; это сообщение может быть расшифровано как АБД и как БДА;

Таким образом, код (6) не обладает свойством однозначной декодируемости.

Проверим таким же способом код (5), который, как мы уже выяснили, не является ни префиксным, ни постфиксным. Множество последовательностей, которые совпадают с началом и концом кодовых слов, состоит из пустой строки и единицы: <Λ, 1>. Граф, построенный с помощью приведённого выше алгоритма, содержит два узла и одну петлю:

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

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

Ещё примеры

Пример 7. Рассмотрим задачу А9 из демо-варианта КИМ ЕГЭ-2013 [1], которая сформулирована в начале статьи. Нужно оптимизировать код
выбрав один из вариантов
Решение. Сначала давайте посмотрим на исходный код, приведённый в условии. Можно заметить, что он префиксный — для него выполняется условие Фано: ни один из трехбитных кодов не начинается ни с 00 (код А), ни с 01 (код Б). Поэтому сообщения, закодированные с помощью такого кода, декодируются однозначно.

Заметим, что «обратное» условие Фано не выполняется: код буквы А (00) совпадает с окончанием кода буквы В (100), а код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Теперь проверим, что получится, если сократить код буквы Д до 11 (вариант 1). Свойство однозначной декодируемости может быть потеряно только тогда, когда в результате такого сокращения нарушится условие Фано, то есть код буквы Д совпадёт с началом какого-то другого кодового слова. Видим, что этого не произошло — нет других кодовых слов, которые начинаются с 11, поэтому вариант 1 — это и есть верное решение.

Остается убедиться, что варианты 3 и 4 не подходят. Если мы сократим код буквы Г до 10 (вариант 3), условие Фано оказывается нарушенным, так как теперь код буквы Г (10) совпал с началом кода буквы В (100). Одновременно нарушено и «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100). Но, как мы знаем, при этом код может всё-таки быть однозначно декодируемым.

Конечно, можно построить граф, как было сделано выше, и проверить, есть ли в нём циклы, включающие вершину Λ. В данном случае граф выглядит так:

1. цикл, соответствующий сообщению ΛГ0Λ1АΛ = 100100; это сообщение может быть расшифровано как ГБА или как ВВ;
2. цикл, соответствующий сообщению ΛГ0Λ1ГΛ = 100110; это сообщение может быть расшифровано как ГБГ или как ВД.

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

Наконец, нужно убедиться, что вариант 4 не удовлетворяет условию. Если мы сократим код буквы Д до 10, условие Фано оказывается нарушенным, так как теперь код буквы Д (10) совпал с началом кода буквы В (100). Как и раньше, нарушено «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100) и код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Построим граф по методу Ал.А. Маркова:

1. цикл, соответствующий сообщению ΛД0Λ1АΛ = 100100; это сообщение может быть расшифровано как ДБА или как ВВ;
2. цикл, соответствующий сообщению ΛД0Λ1БΛ = 100101; это сообщение может быть расшифровано как ДББ или как ВГ.

Пример 8. Оптимизируйте код
сохранив свойство однозначной декодируемости сообщений. Выберите один из вариантов:
Решение. Определим, за счёт чего обеспечивается однозначная декодируемость исходного кода. Легко видеть, что код префиксный — для него выполняется условие Фано: ни одно из трёхбитовых кодовых слов не начинается ни с 11 (код А), ни с 10 (код Б). В то же время, обратное условие Фано не выполняется, потому что код буквы А (11) совпадает с окончанием кода буквы В (011).

Проверим вариант 1 — сократим код буквы Г до 00. При этом нарушилось условие Фано, которое обеспечивало однозначную декодируемость исходного варианта: теперь код буквы Г (00) совпадает с началом кода буквы Д (001). Но и обратное условие Фано тоже не выполняется для пары букв А-В. Поэтому можно предположить, что такой код не обладает свойством однозначной декодируемости. И действительно, легко находится цепочка 001011, которую можно раскодировать как ГБА (00 10 11) или ДВ (001 011).

Рассмотрим вариант 3 — сократим код буквы В до 01. При этом условие Фано выполняется, поскольку ни одно из кодовых слов не начинается с 01, то есть код является префиксным и однозначно раскодируется. Это и есть правильный ответ.

На всякий случай проверяем вариант 4 — сокращает код буквы Б до 1. При этом код перестает быть префиксным, и обратное условие Фано также не выполнено (код буквы Б совпадает с началом и концом кода буквы А). Сразу понятно, что последовательность 11 можно раскодировать как А или как ББ, поэтому этот вариант неверный.

Выводы

В заметке выполнен подробный анализ задачи на кодирование, которая предлагается на ЕГЭ в последние несколько лет. Нужно заметить, что в нём затрагивается вузовский курс дискретной математики. Понятно, что нельзя требовать от школьников знания теорем Ал.А. Маркова об однозначном декодировании, но учителю полезно более глубоко представлять себе эти вопросы, которые можно разбирать на факультативах. В качестве дополнительной литературы по этой теме можно рекомендовать [3-5].

С точки зрения практического подхода, для решения всех известных автору реальных задач подобного типа достаточно найти вариант, при котором выполняется условие Фано или обратное условие Фано (одно из двух!).