Часть 1. Вопрос А9
Далее
Кодирование
информации
Верхняя Синячиха. Музей деревянного зодчества. Крестьянская усадьба
19 века.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д , решили использовать неравномерный двоичный код , позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код: А – 00, Б – 011, В – 101, Г – 100. Укажите, каким кодовым словом должна быть закодирована буква Д.
Длина этого слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования .
1) 001 2) 10 3) 11 4) 110
А9
Решение
Порядок построе-ния графа
Коммента-рий
Ответ
Метод решения - построение графа
1 00
0 11
1 0 1
Г
Б
В
0
1
1
0
А
00
Д
11
1
0
0
1
1
Длина кода должна быть наименьшей
0
К условию задачи
Неравномерный двоичный код
- Код является неравномерным, если количество знаков в коде символов различно.
А – 00, Б – 011, В – 1, Г – 100.
3
1
3
2
цифра
цифры
цифры
цифры
К условию задачи
Свойство однозначного декодирования
- Заключается в том, что код любой буквы не может являться частью кода другой буквы. Код каждой буквы в общей цепочке последовательности можно декодировать только однозначно.
А – 00, Б – 011, В – 101, Г – 100.
1 0 1 0 0 0 1 1 1 0 0
К условию задачи
Построение графа
2. На конце ветви строится следующая вершина графа, с двумя ветвями 0 и 1
1 00
0 11
1 0 1
Г
Б
В
0
1
0
1
А
00
0
1
0
1
3. Код буквы складывается из названий ветвей 0 и 1
0
1
1. Строится вершина графа, с двумя ветвями 0 и 1
К условию задачи
Комментарий
Длина кода должна быть наименьшей. 010 не удовлетворяет этому условию
1 00
0 11
Б
1 0 1
Г
В
1
0
1
0
Д
А
0
1
0
1
1
0
Код должен отвечать принципу однозначного декодировани. 01 часть кода 011.
К условию задачи