Question

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых из трех). Эти коды представлены в таблице.
A    B    C    D    E
000    01    100    10    011
Определить, какой набор букв закодирован двоичной строкой 0110100011000
1) EBCEA   2) BDDEA   3)BDCEA   4) EBAEA ?

Answer 1

Так как код записывается, начиная с младшего разряда, то рассмотрим двоичную строку справа налево: 0110 100 011 000. Легко увидеть, что последние три буквы будут С, Е, А. Кода 110 нет, значит рассмотрим код из двух бит. 10 – D, 01 – B. Значит, двоичной строкой закодирован набор букв 3) BDCEA. Других вариантов дешифровки заданной двоичной строки не существует.

Ответ: 3) BDCEA

Answer 2

1. здесь используется неравномерное кодирование, при котором декодирование может быть неоднозначным, то есть, заданному коду может соответствовать несколько разных исходных сообщений
2. попробуем декодировать с начала цепочки, первой буквой может быть B или E, эти случаи нужно рассматривать отдельно
3. пусть первая буква – E с кодом 011, тогда остается цепочка 0100011000

• для кода 0100011000 первой буквой может быть только B с кодом 01, тогда остается 00011000 ( начало исходной цепочки – EB?)
• для кода 00011000 первой буквой может быть только A с кодом 000, тогда остается 11000, а эта цепочка не может быть разложена на заданные коды букв
• поэтому наше предположение о том, что первая буква – E, неверно

1. пусть первая буква – B с кодом 01, тогда остается цепочка 10100011000

• для кода 10100011000 первой буквой может быть только D с кодом 10, тогда остается 100011000  (можно полагать, что начало исходной цепочки – BD?)
• для кода 100011000 первой буквой может быть только С с кодом 100, тогда остается 011000 (начало исходной цепочки – BDC?)

Несмотря на то, что среди ответов есть единственная цепочка, которая начинается с , здесь нельзя останавливаться, потому что «хвост» цепочки может «не сойтись»

• для кода 011000 на первом месте может быть B (код 01) или E (011); в первом случае «хвост» 1000 нельзя разбить на заданные коды букв, а во втором – остается код 000 (буква А), поэтому исходная цепочка может быть декодирована как BDCEA

правильный ответ – BDCEA