2020-07-12
158Задание 5 № 10281
По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы П, Р, С, Т. Каждой букве соответствует своё кодовое слово, при этом для набора кодовых слов выполнено такое свойство:
любые два слова из набора отличаются не менее чем в трёх позициях.
Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв П, Р, С используются 5-битовые кодовые слова: П: 01111, Р: 00001, С: 11000. 5-битовый код для буквы Т начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы Т.
Решение
С начинается с 1 и заканчивается 0, значит в первую очередь сравниваем с С
С 1 1 0 0 0
Отличается
в трех цифрах
Т 1 - - - 0
Т.е надо инвертировать 100 ---- > 011
Таким образом, для Т получаем 1 011 0
Ответ 10110
Внимание, если в тексте задачи-«кратчайшее, наименьшее»-рисуем графы!!!
Задание 5 № 13351
Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.
|
|
|
|
|
Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Нарисуем граф по нашим данным, отсюда видим, что наименьшее незанятое значение это 110.
Ответ 110
Задание 5 № 7658
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
Примечание.
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Задание 5 № 9356
По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Заметим, что С не должно начинаться на 0(О=0),не дБ равно 11(входит в Т) и 10(входит в П),а также не равно 111(Т), 100(П)-тк дБ однозначное кодирование
Задание 5 № 15790
|
|
|
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, Г — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Решение.
А-010
Б-011
Г-100
И-
М-
Р-
Я- Нас интересуют И и Я
Строим граф , сначала строим до наших известных букв, а потом смотрим незадействованные ветви и листья
начало
 |
1 
0
1(11) 0(10) 1 (01) 0(00)
1(111) 0(110) 1(101) 0(100)= Г 1(011) =Б0 (010) =А 1 0
У нас осталось 4 буквы –ИМРЯ, причем т.к слово МАГИЯ д.б наименьшее, значит ИЯ должны быть наименьшие из ИМРЯ. Строим граф дальше для ИМРЯ –т.е еще должно быть 4 ветви свободных из них потом выберем с наименьшим значением
У нас уже есть одна буква это 101 (рядом с Г), значит осталось 3 буквы, здесь есть два варианта, продолжить 1(11) или 0(00) дальше, т.е одно из них разветвляется на 2 буквы, а второе остается полноценной буквой. Пусть 11-это будет буква и мы не будем ее разветвлять, а оставшийся 0(00) разветвим для букв до 001 и 000
начало
|
1 0
1(11) 0(10) 1 (01) 0(00)
1(111) 0(110) 1(101) 0(100)= Г 1(011) =Б0 (010) =А 1(001) 0(000)
Итак для оставшихся ИМРЯ у нас есть коды 11, 101, 001, 000, нам надо выбрать из них два наименьших, это 11 и любой из 101,001,000, значит для И берем наименьший 11, остальные на др. буквы
А-010 -3
Б-011
Г-100 3
И-11 2
М-101 3
Р-001
Я-000 3
----------
3+3+3+3+2=14
Ответ 14
