Условие
От разведчика было получено сообщение:
001101001011101100101
В этом сообщении зашифрован пароль – последовательность русских букв. В пароле использовались только буквы А, Б, К, Л, О, С; каждая буква кодировалась двоичным словом по таблице, показанной на рисунке. Расшифруйте сообщение. Запишите в ответе пароль.
А | Б | К | Л | О | С |
10 | 111 | 101 | 001 | 00 | 011 |
Решение
Посмотрим на полученное сообщение. Начать расшифровывать его можно как с начала так и с конца. Попробуем расшифровать с начала.
0
. В таблице нет буквы с таким кодом. 001101001011101100101
Рассмотрим комбинацию — 00
. В таблице это буква О. Предположим, что мы расшифровали правильно и продолжим дальше.
001101001011101100101
1
а также комбинации 11
и 110
в таблице отсутствуют. Кода из четырех символов нет. Следовательно на прошлом шаге было сделано неверное предположение. 001101001011101100101
001101001011101100101
001101001011101100101
001
и это буква Л. 001101001011101100101
10
, либо 101
. Поэтому можно изменить направление и рассмотреть код с конца. 001101001011101100101
001101001011101100101
Кодов 1
и 01
нет. Значит последний код в шифровке — 101
— буква К.
001101001011101100101
Кодов 0
и 100
нет. Значит подходит код в шифровке — 00
— буква О.
001101001011101100101
1
и 11
нет. Значит подходит код в шифровке — 011
— буква С. 001101001011101100101
1
и 11
нет. Значит подходит код в шифровке — 111
— буква Б. 001101001011101100101
0
и 010
нет. Значит подходит код в шифровке — 10
— буква А. 001101001011101100101
0
и 100
нет. Значит подходит код в шифровке — 00
— буква О. 001101001011101100101
101
— буква К. 001101001011101100101
Обратим внимание на то, что расшифровать однозначно получилось, когда мы начали с конца. Это произошло в следствии того, что буквы сообщения были закодированы неравномерным кодом, соответствующим обратному условию Фано. Это значит, что длина кода может быть различной, но однозначной к пониманию, то есть ни один код не является концом другого.