КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ ИНФОРМАЦИИ

ПОДГОТОВКА К ЕГЭ ПО ИНФОРМАТИКЕ (ЗАДАЧИ 4)

КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ ИНФОРМАЦИИ

1. По каналу связи передаются сообщения, содержащие только буквы A, B, С, D. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова: 

A – 1, B – 010, C – 000.

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

2. По каналу связи передаются сообщения, содержащие только буквы A, B, С, D. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова: 

A – 111, B – 0, C – 110.

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

3. По каналу связи передаются сообщения, содержащие только буквы из набора: В, Ф, К, А, Ю, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 0, К – 1001. Для четырёх оставшихся букв В, Ф, Ю и Р кодовые слова неизвестны. Определите минимальное количество двоичных знаков, необходимых для кодирования слова КЮАЮВЮФ.

4. По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 010, Б  – 011, Г  – 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

5. По каналу связи передаются сообщения, содержащие только семь букв: А, Г, Д, Е, П, Р, Ф. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г – 100, Д – 11, Е – 0. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ПАРАГРАФ?

6. Известно, что слово КАШКА закодировали с помощью последовательности 1110110011101. При этом код удовлетворяет условию Фано. Найдите минимальную длину кодовой последовательности для слова ПАМПУШКА? Известно, что другие буквы в кодируемой последовательности встретиться не могут.

7. Для кодирования сообщений, состоящих только из букв Д, Е, О, М использовали неравномерный двоичный код, удовлетворяющий условию Фано. Известно, что при этом слово ДЕД кодируется с помощью последовательности 1010101. Найдите минимальную длину кодовой последовательности для слова ДОМ

8. Для кодирования букв Л, О, В, У, Ш, К, А, использован неравномерный двоичный код, допускающий однозначное декодирование. Для кодирования букв У и В использовали кодовые слова 11 и 10 соответственно. Какова минимально возможная суммарная длина для букв Л, О, Ш, К, А, если известно, что кодовые слова для всех этих букв имеют одинаковую длину?

 

9. Для кодирования некоторой последовательности, состоящей из букв П, Р, О, Б, Н, И, К, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв П, Р, О, Б использовали соответственно кодовые слова 00, 1001, 0101, 111. Найдите наименьшую возможную длину кодовой последовательности для слова КОРОН.

10. По каналу связи передаются сообщения, содержащие буквы русского алфавита. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Р, А, З используются кодовые слова 01, 110, 111 соответственно. Укажите минимально возможную суммарную длину закодированной последовательности для слова КРАКЕН

11. По каналу связи передаются сообщения, содержащие только шесть букв: Я, Н, В, А, Р, Ь. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Н – 00, В – 01, Р – 10, Ь – 111. Укажите минимально возможную длину закодированной последовательности для слова ВАРВАР.

12. По каналу связи передаются сообщения, содержащие только буквы из набора: К, А, П, И, Б, Р, Д. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для некоторых букв кодовые слова известны: Б – 00, Р – 100, К – 111. Какое количество двоичных знаков потребуется для кодирования слова КАПИБАРА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

13. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: А – 11, Б – 000, В – 100, Г – 01, Д – 101. Укажите возможный код минимальной длины для буквы Я. Если таких кодов несколько, укажите тот из них, который имеет максимальное числовое значение.

14. Для передачи данных используется 5-битный код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами: 

A – 11111, Б – 00011, В – 00100

Любые два кодовых слова отличаются друг от друга не менее, чем в трёх позициях. Поэтому если при передаче кода буквы произошла одна ошибка, можно считать, что передавалась буква, код которой отличается от принятого в одной позиции. Если принятое кодовое слово отличается от кодовых слов букв А, Б и В более, чем в одной позиции, считается, что произошла ошибка, которую обозначают символом «*».
Декодируйте сообщение

00110 00000 11111 11010

15. Для передачи данных используется 5-битный код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами: 

A – 11011, Б – 10000, В – 00111

Любые два кодовых слова отличаются друг от друга не менее, чем в трёх позициях. Поэтому если при передаче кода буквы произошла одна ошибка, можно считать, что передавалась буква, код которой отличается от принятого в одной позиции. Если принятое кодовое слово отличается от кодовых слов букв А, Б и В более, чем в одной позиции, считается, что произошла ошибка, которую обозначают символом «*».
Декодируйте сообщение

01111 10001 11100 11011

16. По каналу связи передаются сообщения, содержащие только десять букв: А, Б, В, Г, Д, О, П, Р, С, Т. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для девяти букв кодовые слова известны:

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

17. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, для которого выполняется условие Фано: никакое кодовое слово не совпадает с началом другого кодового слова. Известно, что слову САККОС соответствует код 10000111101010. Какой код соответствует слову СОК?

18. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, для которого выполняется условие Фано: никакое кодовое слово не совпадает с началом другого кодового слова. Известно, что слову ПАПУАС соответствует код 11101100010010. Какой код соответствует слову СУП?

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

Белый – 0, Зелёный – 11111, Фиолетовый – 11110, Красный – 1110,

Чёрный – 10.

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