Помогите решить задачу. Для кодирования некоторой последовательности используется...

Question

Помогите решить задачу.
Для кодирования некоторой последовательности используется следующий неравномерный двоичный код: А-000 Б-01 В-001 Г-110 Д-111
Можно ли сократить длину кодового символа Г(110), чтобы код остался однозначно декодируемым? В ответе укажите возможный код для слова Г, если его можно сократить или 110, если такого сокращения нет.

Answer 1

Для того, чтобы код оставался однозначно декодируемым должно соблюдаться условие Фано - "никакое слово не может быть началом другого кодового слова". Значит код буквы Г не должен совпадать с кодом других букв.
00 совпадает с началом А
01 совпадает с Б
10 не совпадает и подходит
11 совпадает с началом буквы Д.
Ответ: 10

Comments

Спасибо, теперь все понятно