Кодирование_декодирование

Что нужно знать:

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

• обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход

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

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

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

• закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;

• условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

1) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 1 2) 1110 3) 111 4) 11

2) 3). Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

1) 00 2) 01 3)11 4) 010

4). Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Б – 01 2) это невозможно

3) для буквы В – 01 4) для буквы Г – 10

5). По каналу связи передаются сообщения, содержащие только 4 буквы: Е, Н, О, Т. Для кодирования букв Е, Н, О используются 5-битовые кодовые слова: Е - 00000, Н - 00111, О - 11011. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Т, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 11111 2) 11100 3) 00011 4) не подходит ни одно из указанных выше слов

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

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

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

X: 01111, Y: 00001, Z: 11000. Определите 5-битовое кодовое слово для буквы W, если известно, что оно начинается с 1 и заканчивается 0.

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

Задачи для тренировки

1. По каналу связи передаются сообщения, содержащие только пять букв: Р, А, Н, Е, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово 0; для буквы Е используется кодовое слово 10. Какова минимальная общая длина кодовых слов для всех пяти букв?

2. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 00, 111, 1000, 1001, 1010, 1100, 1101, 010, 011. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

3. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 0011, 1011, 1111, 0110, 0001, 1100, 0010, 0111, 0000. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

4. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, З, И, Й. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г, Д, Е, Ж, З, И использовали соответственно кодовые слова 0100, 0101, 1000, 11, 000, 101, 0010, 0011, 1001. Укажите кратчайшее возможное кодовое слово для буквы Й, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

5. (Досрочный ЕГЭ-2018) По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А – 0; Б – 110; В – 101. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.

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

7. По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А и Б используются такие кодовые слова: А – 1; Б – 011. Укажите сумму длин кратчайших кодовых слов для букв В и Г, при котором код будет допускать однозначное декодирование.

8. По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово: А – 1. Укажите сумму длин кратчайших кодовых слов для букв Б, В и Г, при котором код будет допускать однозначное декодирование.

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

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

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

12. По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 110, Б – 01, И – 000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВВЕДЕНИЕ?

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

14. По каналу связи передаются сообщения, содержащие только семь букв: А, В, К, Л, О, Т, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: К – 00, Л – 01, О – 1000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АВТОЛАВКА?

15. По каналу связи передаются сообщения, содержащие только семь букв: А, И, К, Л, Р, Ц, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 01, Я – 11. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КИРИЛЛИЦА?

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

17. (А. Богданов) По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, Д, О, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б – 010, В – 011. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВОДООТВОД?

18. (А. Минак) По каналу связи передаются шифрованные сообщения, содержащие заглавные буквы кириллицы. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 101, 110, 100, 111 соответственно. Укажите минимальную сумму длин кодовых слов для букв Д и Е, при котором код будет удовлетворять условию Фано.

Ответы

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

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

1) EBCEA 2) BDDEA 3) BDCEA 4) EBAEA