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

Что проверяется:
Умение кодировать и декодировать информацию.
1.1.2. Процесс передачи информации, источник и приёмник информации. Сигнал, кодирование и декодирование. Искажение информации.
1.2.2. Умение интерпретировать результаты, получаемые в ходе моделирования реальных процессов

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

кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование
закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;
закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;
условие Фано – это достаточное, но не необходимое условие однозначного декодирования.
Что нужно знать:

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

Построим дерево для заданного двоичного кода:
1. Пример задания

для того чтобы выполнить условие Фано (ни одно кодовое слово не совпадает с началом другого кодового слова), необходимо, чтобы все буквы размещались в листьях дерева
у нас осталась единственная свободная ветка 10, на которую нужно «навесить» две буквы; это можно сделать так:
1. Пример задания

1. Пример задания