По каналу связи передаются сообщения, содержащие только буквы из набора: Н, П, Т, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Р — 1, Н — 01, О — 000. Для остальных букв кодовые слова неизвестны. Какое наименьшее количество двоичных знаков требуется для кодирования слова ПРОТОН?
Ответ: 17 двоичных знаков.
Кратко по шагам:
Условие Фано означает, что ни одно кодовое слово не является началом другого.
Уже заняты:
- \(Р=1\), значит все слова, начинающиеся с \(1\), использовать нельзя;
- \(Н=01\), значит все слова, начинающиеся с \(01\), нельзя;
- \(О=000\), значит все слова, начинающиеся с \(000\), нельзя.
Остаётся единственная свободная «ветка» — \(001\).
На два ещё не закодированных символа \(П\) и \(Т\) нужны два разных кодовых слова. Взять одно слово \(001\), а второе длиннее нельзя: тогда одно будет началом другого.
Поэтому делим \(001\) на два слова: \[ П=0010,\qquad Т=0011. \] Оба имеют длину \(4\), и меньшей суммарной длины не получить.Считаем длину слова ПРОТОН: \[ \begin{array}{c|c|c} \text{буква} & \text{код} & \text{длина}\\ П & 0010 & 4\\ Р & 1 & 1\\ О & 000 & 3\\ Т & 0011 & 4\\ О & 000 & 3\\ Н & 01 & 2 \end{array} \] Итого: \[ 4+1+3+4+3+2=17. \]
Проверка: код \(0010,\ 1,\ 000,\ 0011,\ 000,\ 01\) не нарушает условие Фано, а два неизвестных символа короче чем по \(4\) бита закодировать нельзя.
Ответ: 17.
Обсуждение
1 сообщениеКомпания-перевозчик доставляет срочные грузы между серверными узлами IT-хаба. Сеть соединений между узлами и время доставки (в условных единицах) заданы весовой матрицей смежности. Отсутствие прямого соединения обозначено как ∞. Задание: найди кратчайший путь от узла A до узла E.
