Как пользоваться Поиском

поиск по сайту
логин

пароль

регистрация     
забыли пароль?

Помощь сайту

Вопросы » Информатика, Логика » Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.

создана: 11.10.2019 в 20:41
................................................

 ( +21 ) 

:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г,

решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.

Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110.

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

 ( +3192 ) 
11.10.2019 20:56
Комментировать Верное решение
(баллы:+2)

А - 0, Б - 110,   В -?     Г - ?

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

Обратное условие Фано:  никакой код не был окончанием другого (более длинного) кода.

Решение.

Г = 1 - не подходит, т.к.  код Б начинается с 1.

00, 01 - не подходят, т.к. тогда А является началом этих кодов.

11 - не подходит, т.к. является началом кода Б.

10 - подходит, но так надо закодировать 2 буквы, то следует взять еще 3-битовый код:

111.  Коды 100, 101, 110 не подходят.   В=10, Г=111.

Суммарная длина равна 1+3+2+3 = 9

Ответ: 9.

 ( +3192 ) 
12.03.2023 22:36
Комментировать

 Более простое решение получается при построении  двоичного  дерева.

                           0 это  буква "А"     

              1               
     10                  11       
 100   101    110      111 

 

Из "1" получили два 2-х битовых 10 и 11 

и четыре 3-х битовых кода : 100, 101, 110, 111.

110 это "Б", для "В" возьмем 10 для "Г" - 111.

Сумма = 1+3+2+3 = 9

Хочу написать ответ