Карточки
Тесты
Главная
Курсы
Подписка
4. Кодирование и декодирование информации: #291240
По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код. Для букв А, Б и В используются кодовые слова $001$, $010$, $0111$ соответственно.
Укажите минимальную сумму длин кодовых слов для букв Г и Д, при которых код будет удовлетворять условию Фано.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Код длины $1$ можно выбрать только один — $1$, так как код $0$ является началом всех известных кодовых слов.
Для второй буквы код длины $2$ выбрать нельзя:
- $00$ является началом кода $001$;
- $01$ является началом кодов $010$ и $0111$;
- коды $10$ и $11$ начинаются с выбранного кода $1$.
Кратчайший подходящий код для второй буквы имеет длину $3$, например $000$.
Таким образом, можно использовать:
- Г — $1$;
- Д — $000$.
Сумма длин кодовых слов: $1+3=4$. Меньшая сумма невозможна.
20
