Question

По каналу связи передаются сообщения, содержащие только заглавные русские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б -10. Г-1110, Д-0111. Е - 010. Известно, что для кодирования слова АНАНАС потребовалось 16 двоичных знаков. Какое кодовое слово соответствует букве Н? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Ответ:.

Answer 1

Відповідь:

Нужно закодировать ещё четыре буквы (В, Д, Е, Н), а в дереве есть три свободных узла. Каждое продолжение дерева из свободного узла создаёт два узла вместо одного, то есть количество узлов увеличивается на 1 . Значит, нужно продолжить дерево в одном месте. С точки зрения длины кодов это можно сделать двумя способами:

из узла 10 (длина кода 2 ) получить два узла с длиной кода 3 ;

из узла 001 или 111  (длина кода 3 ) получить два узла с длиной кода 4 .

В первом случае мы получим новые коды длиной 3,3,3,3,  во втором – 2,3,4,4.

Подсчитаем количество знаков для кодирования слова ВВЕДЕНИЕ в каждом их этих случаев. В первом случае длина всех добавленных кодов (буквы В, Д, Е, Н) одинакова –3  бита. Длина кода буквы И задана – тоже 3  бита. Всего получается 8х3=24 бита.

Во втором случае длина добавленных кодов разная. Очевидно, что для получения наименьшей длины самым коротким должен быть код буквы Е (она встречается чаще всех), следующим – код буквы В. Тогда длина кода для Е – 2 бита, для В –3 , для Д и Н – по4 . Всего потребуется  бита. 3х2+2х3+4+4+3=23 бита

Пояснення:

Answer 2

Условие Фано гарантирует отсутствие префиксов в кодовых словах. Давайте начнем с известных нам кодовых слов и построим дерево кодирования:

yamlCopy code
Б - 10
Г - 1110
Д - 0111
Е - 010

Для кодирования слова "АНАНАС" использовано 16 двоичных знаков. По условию, кодовые слова не имеют общих префиксов, поэтому можно представить их в виде дерева:

markdownCopy code
      root
     / |  | \
   Б  Г  Д  Е
             |
             А
            / \
           Н   Н
          /     \
         А       А
        / \     / \
       Н   Н   Н   Н

Как видно из дерева, кодовое слово для буквы "Н" - это 111.