ЕГЭ – 2021, задание 4. Кодирование и декодирование информации

ЕГЭ – 2021, задание 4. Кодирование и декодирование информации

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

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

Кодирование информации всегда происходит по определенным правилам. Правило кодирования называется кодом.

Последовательность символов известной длины из конечного набора знаков (алфавита) используемых для кодирования, называется кодовым словом (например, кодовое слово для буквы «O» в азбуке Морзе имеет длину равную трем и представляет последовательность из трех символов тире «— — —»).

Способы кодирования информации зависят от конкретной задачи.

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

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

Обратное условие Фано гласит, что ни одно кодовое слово не может служить концом другого кодового слова.

Например, в кодовых словах 01, 011, 010, 110, 100 нарушено прямое условие Фано, так как кодовое слово 01 является началом кодового слова 011. Обратное условие не нарушено, поэтому задачу по раскодированию с такими кодовыми словами рекомендуется решать с конца сообщения, что обеспечит его однозначное декодирование.

В кодовых словах 01, 001, 100, 101, 110 нарушено обратное условие Фано, так как кодовое слово 01 является концом кодовых слов 001 и 101. Прямое условие не нарушено, поэтому задачу с такими заданными кодовыми словами для однозначного декодирования рекомендуется решать с начала сообщения.

В кодовых словах 01, 001, 010, 100, 110 нарушены оба условия Фано, так как кодовое слово 01 служит началом кодового слова 010 и концом кодового слова 001. Тогда при решении такой задачи однозначное декодирование невозможно, решать можно с любой стороны – все равно придется перебирать варианты.

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

Кодирование может быть равномерное и неравномерное;

• при равномерном кодировании все символы кодируются кодами равной длины;

• при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование

При решении задач по декодированию достаточно умения логически мыслить и строить кодовые деревья, быть внимательным и аккуратным – и все получится!

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1 (демо-2021)

Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв – П и Р – кодовые слова неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение.

При решении задачи нужно учесть, что хотя в ответе нужно привести код одной буквы П, но неизвестными по условию остаются два кодовых слова - для букв П и Р, поэтому в данной задаче ищем два доступных кодовых слова, а в ответе выбираем из них код с меньшим числовым значением. При этом из двух бит можно построить всего 4 кода, а нам задано пять букв, то есть искомый код должен быть трехзначным. Из двузначных кодов не занят код 10, тогда из него можно построить два трехзначных кода, не нарушающих условие Фано – 100 и 101. Тогда ответом будет меньшее число – 100.

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

Ответ: 100

Задача 2.

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

Решение.

При решении задачи нужно учесть, что хотя в ответе нужно привести код одной буквы Д, но неизвестными по условию остаются два кодовых слова - для букв Д и Е, поэтому в данной задаче ищем два доступных кодовых слова, а в ответе выбираем из них код с меньшим числовым значением. При этом здесь используется неравномерное кодирование, причем условия Фано не нарушены. Из двузначных кодов свободны 00 и 01, при этом 00 нарушает и начало, и конец, поэтому использоваться не может. Тогда остается только один двузначный код – 10 и возможность использовать трехзначные коды: 010, 011, 100, 101, 110. Выбираем из них наименьшее число – 010.

Ответ: 010

Задача 3.

По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы: X, Y, Z, W; для кодировки букв используются кодовые слова длины 5. При этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв X, Y, Z используются 5-битовые кодовые слова: X: 01111, Y: 00001, Z: 11000. Определите 5-битовое кодовое слово для буквы W, если известно, что оно начинается с 1 и заканчивается 0.

Решение.

Из заданного условия имеем один код буквы Z в требуемом диапазоне – 11000. Тогда для получения кода, который отличается тремя позициями (две остаются на месте, и больше трех их отличий быть не может) достаточно поменять оставшиеся три бита на противоположные, получим код 10110. При этом отличия с заданными буквами: Х – 3, Y – 4.

Ответ: 10110

Задача 4.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?

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

Решение.

В двух заданных кодах нарушено обратное условие Фано, поэтому будем составлять коды, не нарушая начала. Запишем подряд все возможные коды и вычеркнем из них не подходящие нам, получим: 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111. Тогда здесь подходят только четыре последних кода, и сумма длин всех шести кодов будет равна 1 + 2 + 4 *4 = 19.

Ответ: 19

Задача 5.

По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);

б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

1) А:0, Б:10, В:110, Г:111

2) А:0, Б:10, В:01, Г:11

3) А:1, Б:01, В:011, Г:001

4) А:00, Б:01, В:10, Г:11

Решение.

Варианты ответов 2 и 3 отпадают, так как в них нарушено заданное условие Фано (буквы А:0, В:01 и Б:01, В:011 соответственно).

В варианте 1 получаем последовательность длиной 16*1 + 8*2 + 4*3 + 4*3 = 56 бит,

в варианте 4 – (16 + 8 + 4*2) * 2 = 64 бита, тогда верный ответ – 1.

Ответ: 1

Задача 6.

В любом сообщении больше всего букв А, следующая по частоте буква – С, затем – И. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?

1) А – 0, И – 1, С – 00, Т – 11                      2) С – 1, И – 0, А – 01, Т – 10

3) А – 1, И – 01, С – 001, Т – 000                4) С – 0, И – 11, А – 101, Т – 100

Решение.

Варианты ответов 1 и 2 отпадают, так как в них нарушены оба условия Фано.

Из первого условия задачи о частоте встречающихся букв подходит вариант 3.

Ответ: 3

Задача 7.

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

Определить, какой набор букв закодирован двоичной строкой 0110100011000.

Решение.

Из таблицы видим, что нарушено начало кодов (буквы В и Е, с и D), тогда декодирование строки следует начинать с конца. Однозначно получаем:

01 10 100 011 000 - ВDСЕА

Ответ: ВDСЕА

Задача 7.

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

Определите, какое число передавалось по каналу в виде 01010100100111100011.

Решение.

Разобьем заданную последовательность по 5 бит, удалим каждый пятый бит и получим последовательность

01010100100111100011 = 01010 10010 01111 00011
что соответствует цифрам 5, 9, 7 и 1.

Ответ: 5971