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

22 Сен 2019 в 08:42
452 +2
1
Ответы
1

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

Пусть длина кодового слова для буквы Б равна n, для буквы В - m, для буквы Г - p.

Так как для буквы А используется кодовое слово длины 2, то для всех остальных букв должны использоваться кодовые слова длины не меньше 3, чтобы исключить возможность префиксов.

Получаем систему уравнений:
n ≥ 3
m ≥ 3
p ≥ 3

По условию код должен быть допускать однозначное декодирование, значит не должно быть префиксов.
Учитывая это, можем записать:
10 не может быть префиксом ни для одной из букв
11 не может быть префиксом ни для одной из букв
Таким образом, получаем:
n ≥ 4
m ≥ 4
p ≥ 4

Сумма длин кратчайших кодовых слов для букв Б, В и Г:
4 + 4 + 4 = 12

Таким образом, сумма длин кратчайших кодовых слов для букв Б, В и Г при которой код будет допускать однозначное декодирование равна 12.

19 Апр 2024 в 20:21
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир