Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

5. Кодирование и декодирование

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Декодирование двоичных кодов в буквенные сообщения

Задание 1 #8322

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

\[\begin{array}{c|c|c|c|c} a&b&c&d&e\\ \hline 10&010&11&011&00\\ \end{array}\\\]

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

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

Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы и переписываем ее, заменяя кодовые слова на буквы: 011|00|010|10|11 = debac.

Ответ: debac

Задание 2 #8323

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

\[\begin{array}{c|c|c|c|c|c} a&b&c&d&e&f\\ \hline 101&01&000&00&11&100\\ \end{array}\\\]

Какой набор букв закодирован двоичной строкой 101000110100100? Буквы не могут повторяться.

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

Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы (получим 2 возможных случая):

(1) 101|000|11|01|00|100

(2) 101|00|01|101|00|100

Во (2) случае мы видим повторение кодовых слов 00 и 101. Значит, случай (2) не подходит (т.к. по условию буквы не могут повторяться).

Значит, наш ответ – (1) случай. Перепишем его, заменяя кодовые слова на буквы: 101|000|11|01|00|100 = acebdf.

Ответ: acebdf

Задание 3 #8324

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

\[\begin{array}{c|c|c|c|c|c} a&b&c&d&e&f\\ \hline 11&110&001&00&010&101\\ \end{array}\\\]

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

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

Разбиваем двоичную строку на части (справа налево) с помощью данной в условии таблицы и переписываем, заменяя кодовые слова на буквы: 001|00|010|110|11|101 = cdebaf.

Ответ: cdebaf

Задание 4 #8325

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

\[\begin{array}{c|c|c|c|c} X&Y&Z&W&I\\ \hline 10&011&00&01&110\\ \end{array}\\\]

Какой набор букв закодирован двоичной строкой 100111000011? Буквы не могут повторяться.

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

Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы (получим 2 возможных случая):

(1) 10|01|110|00|011

(2) 10|011|10|00|011

Во (2) случае мы видим повторение кодовых слов 011 и 10. Значит, случай (2) не подходит (т.к. по условию буквы должны быть различные).

Значит, наш ответ – (1) случай. Перепишем его, заменяя кодовые слова на буквы: 10|01|110|00|011 = XWIZY.

Ответ: XWIZY

Задание 5 #8326

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

\[\begin{array}{c|c|c|c|c} a&b&c&d&e\\ \hline 01&110&00&010&???\\ \end{array}\\\]

Кодовое слово буквы e такое, что оно должно быть минимально возможной длины и удовлетворять обратному условию Фано (кодовое слово любой буквы не является концом кодового слова другой).

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

Чтобы выяснить двоичный код буквы e, построим граф. Так как обратное условие Фано должно выполняться, кодовое слово любой буквы не должно являться концом кодового слова другой. Значит, строим граф ”с конца” кодового слова (то есть читаем значения задом наперед: a: 01 \(\rightarrow\) 10, b: 110 \(\rightarrow\) 011, c: 00 \(\rightarrow\) 00, d: 010 \(\rightarrow\) 010).

Из графа видно, что кодовое слово минимальной длины, удовлетворяющее обратному условию Фано, – 11. Значит, кодовое слово буквы e – 11.

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

Разбиваем двоичную строку на части (справа налево) с помощью данной в условии таблицы и переписываем, заменяя кодовые слова на буквы: 00|010|01|11|110 = cdaeb.

Ответ: cdaeb

Задание 6 #8327

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

\[\begin{array}{c|c|c|c|c|c} a&b&c&d&e&f\\ \hline 101&01&100&11&001&???\\ \end{array}\\\]

Кодовое слово буквы f такое, что оно должно быть минимально возможной длины и удовлетворять условию Фано (кодовое слово любой буквы не является началом кодового кода другой).

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

Чтобы выяснить двоичный код буквы f, построим граф. Так как условие Фано должно выполняться, кодовое слово любой буквы не должно являться началом кодового слова другой. Значит, строим граф ”с начала” кодового слова.

Из графа видно, что кодовое слово минимальной длины, удовлетворяющее условию Фано, – 000. Значит, кодовое слово буквы f – 000.

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

Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы и переписываем строку, заменяя кодовые слова на буквы: 100|000|001|01|101|11 = cfebad.

Ответ: cfebad

Задание 7 #8328

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

\[\begin{array}{c|c|c|c} a&b&c&d\\ \hline 11&0&00&???\\ \end{array}\\\]

Кодовое буквы d такое, что оно должно быть минимально возможной длины и кодовое слово буквы b должно являться началом этого кодового слова.

Какой набор букв закодирован двоичной строкой 0100110? Буквы не могут повторяться.

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

Из графа видно, что кодовое слово минимальной длины, началом которого является кодовое слово буквы b, – 01. Значит, кодовое слово буквы d – 01.

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

Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы (получим 2 возможных случая):

(1) 01|0|01|10

(2) 01|00|11|0

В (1) случае мы видим повторение кодового слова 01. Значит, случай (1) не подходит (по условию буквы не должны повторяться).

Значит, наш ответ – (2) случай. Перепишем его, заменяя кодовые слова на буквы: 01|00|11|0 = dcab.

Ответ: dcab