10748

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

За правильное выполненное задание получишь 1 балл. На решение отводится примерно 2 минуты.

Для выполнения задания 4 по информатике необходимо знать:

Кодирование - это перевод информации из одной формы представления в другую.

Декодирование - это обратный процесс кодированию.

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

  • при равномерном кодировании все символы кодируются кодами равной длины; Например: ASCII или Unicode.
  • при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование, связанные с появлением неоднозначности кода. Например: Символ А кодируется цифрой 0, Б - последовательностью 01, а В - последовательностью 1. Итак, например, сообщение "011" может быть раскодировано, как AВВ или БВ. При неоднозначность кода информацию можно декодировать по разному.

Для однозначного декодирования код должен удовлетворять условию Фано: никакое кодовое слово не может быть началом другого кодового слова.

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

Задача №1

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 000, 001, 010, 11. Для двух оставшихся букв — П и Р — длины кодовых слов неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

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

Задача №2

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Буква Кодовое слово   Буква Кодовое слово
А 00   Л 1101
Б     Р 1010
Е 010   С 1110
И 011   Т 1011
К 1111   У 100

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

Задача №3

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, В, Г, Д, Ж, З, Е, И, Л. Для передачи используется неравномерный двоичный код. Для пяти букв используются кодовые слова.

Буква Кодовое слово Буква Кодовое слово
А 1001 В  
Б 101 Г  
Е 001 Д  
И 0100 Ж  
Л 1111 З  

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

Задача №4

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, В, Г, Д, Ж, З, Е, И, Л. Для передачи используется неравномерный двоичный код. Для четырех букв используются кодовые слова.

Буква Кодовое слово Буква Кодовое слово
А 00 В 11
Б   Г  
Е   Д 101
И   Ж 100
Л   З  

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

Задача №5

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

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

Пройти тест

Начать