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

Question

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

Каким из перечисленных ниже кодом может быть закодирова буква Д

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

1)000

2)10

3)11

4)1111

Пожалуйста с подробным объяснением. Заранее спасибо

Answer 1

При однозначном декодировании в коде одного символа не должно быть дублирования(повторения) части кода другого символа.

 

Т.к. длина кода должна быть наименьшей, то начнем с длины кода =1.

Все возможные варианты: 0, 1.

Вариант 0 возможен.

Вариант 1 не возможен, т.к. он является частью кода А Б В Г

 

Возьмём длину кода =2.

Все возможные варианты: 00, 01, 10, 11.

Вариант 00 возможен.

Вариант 01 возможен.

Вариант 10 не возможен, т.к. он является частью кода А Б

Вариант 11 не возможен, т.к. он является частью кода В Г

 

Возьмём длину кода =3.

Все возможные варианты: 000, 001, 010, 011, 100, 101, 110, 111.

Варианты 000, 001, 010, 011 возможны.

Варианты 100, 101, 110, 111 не возможны, т.к. уже заняты другими буквами.

 

Из предложенных ответов есть 000.

 

Вариант 1111 можно не брать, т.к. получается, что В (111) это часть кода 1111, то есть код 1111 состоит из символа, закодированного единицей + В