Ещё пример задания. Ещё пример задания

Ещё пример задания

Р-11.По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:

А — 0, И — 00, К — 10, О — 110, Т — 111.

Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) КАА 2) ИКОТА 3) КОТ 4) ни одно из сообщений не подходит

Решение:

1) прежде всего заметим, что для заданного кода не выполняется ни прямое, ни обратное условие Фано; «виновата» в этом пара А – И: код буквы А совпадает как с началом, так и с окончанием кода буквы И; больше ни для одной пары кодовых слов прямое условие Фано не нарушено

2) это означает, что не все сообщения могут быть декодированы однозначно

3) теперь нужно понять, какие последовательности могут быть декодированы неоднозначно; в данном случае очевидно, что сообщения АА и И кодируются одинаково: 00, поэтому все слова, где есть АА или И, не могут быть декодированы однозначно

4) поэтому варианты 1 (КАА) и 2 (ИКОТА) отпадают

5) на всякий случай проверим вариант 3: КОТ = 10110111; первой буквой может быть только К (по-другому сочетание 10 получить нельзя), аналогично вторая буква – только О, а третья – только Т

6) Ответ: 3.

Ещё пример задания

Р-10.По каналу связи передаются сообщения, содержащие только 4 буквы П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.

Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение (способ 1, исключение вариантов):

1) код однозначно декодируется, если выполняется условие Фано или обратное условие Фано; в данном случае «прямое» условие Фано выполняется: с кода буквы О (0) не начинается ни один из двух других кодов;

2) новый код не может начинаться с нуля (иначе нарушится условие Фано)

3) начнём проверку с кодов длиной 1; единственный код, не начинающийся с нуля – 1 – не подходит, потому что с 1 начинаются два других кода: Т (111) и П (100

4) кодов длиной 2, начинающихся с 1, всего 2: 10 и 11, но их использовать нельзя, потому что с 10 начинается код буквы П, а с 11 – код буквы Т

5) рассматриваем коды длиной 3, начинающиеся с 1; коды 100 и 111 уже заняты, а ещё два – 101 и 110 – свободны и их можно использовать, причём условие Фано выполняется в обоих случаях;

6) поскольку нужно выбрать код с минимальным значением, выбираем 101

7) Ответ: 101.

Решение (способ 2, построение дерева):

1) условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков;

2) построим дерево для заданных кодовых слов О – 0, Т – 111 и П – 100:

3) штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» лист для кодового слова буквы С: 101 или 110; из них минимальное значение имеет код 101

4) таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов

5) Ответ: 101.

⇐ Предыдущая 1 2 345 6 Следующая ⇒