Задание 4

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

Теория

Кодирование информации – представление информации в такой форме, в которой её было бы удобно хранить, обрабатывать и передавать. Правило преобразования информации к такому представлению называется кодом.

Кодирование бывает равномерным (коды одинаковой длины для всех символов) и неравномерным (коды разной длины).

Пример равномерного кодирования: А — 00, Б — 01, В — 11

Пример неравномерного кодирования: А — 00, Б — 110, В — 111

Декодирование — восстановление сообщения из последовательности кодов (расшифровка).

Мы разобрались с основными понятиями и теперь можем переходить к практике. Например, тебе нужно декодировать сообщение 00001. Ты знаешь, что для К, Т, О использовали коды 0, 1, 00 соответственно. Исходя из условия, которое у нас есть, мы можем получить несколько вариантов ответа. 

Как же декодировать это сообщение однозначно? Для этого тебе нужно знать Условия Фано.

Условия Фано

Прямое условие Фано: 

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

К — 0, Т — 1, О — 00: прямое условие не выполнено.

Код называется префиксным, если соблюдено прямое условие.

Пример: 

Для К, Т, О используются коды 1, 010, 000 соответственно. Каким наименьшим кодовым словом может быть закодирована С, при котором будет допускаться однозначное декодирование, удовлетворяющее прямому условию Фано?

С не может кодироваться как 

• 0, так как кодирование буквы О начинается с 0.
• 1, потому что это соответствует К.
• 10 и 11, потому что код К соотносится с 1.

С не может кодироваться с 01 и 00, т.к. букве Т соответствует 010, а О — 000.

Значит, С может кодироваться как 001 (наименьшее возможное значение).

Обратное условие Фано: 

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

К — 0, Т — 1, О — 00: обратное условие не выполнено.

Код называется постфиксным, если соблюдено обратное условие.

Пример: 

Для К, Т, О используются коды 100, 110, 010 соответственно. Каким наименьшим кодовым словом может быть закодирована С, при котором будет допускаться однозначное декодирование, удовлетворяющее обратному условию Фано?

С не может кодироваться как 

• 0, потому что К соответствует 100, Т — 110, О — 010.
• 10, так как Т — 110, О — 010.

Значит, С может кодироваться как 01 (наименьшее возможное значение). 

Для возможности однозначного декодирования достаточно выполнения одного из условий (или прямого, или обратного).