каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для…
Каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Буква A Б Γ E Кодовое слово 11 Буква И M P T Кодовое слово 01 0010 100 000 0011 Укажите кратчайшее кодовое слово для буквы И. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Для восстановления кратчайшего кодового слова для буквы И, удовлетворяющего условию Фано, сначала рассмотрим уже известные кодовые слова:
- A: 11
- Б: 01
- Γ: 0010
- E: 100
- M: 000
- P: 0011
- T: (неизвестно)
Работаем с известными кодами и создадим кодовые слова для буквы И. Условие Фано требует, чтобы ни одно кодовое слово не было префиксом другого. Мы будем использовать доступные битовые комбинации, избегая уже используемых кодовых слов.
Посмотрим на доступные комбинации не более чем 4 бита:
- 0000 (используется кодом M)
- 0001 (свободно)
- 0010 (используется кодом Γ)
- 0011 (используется кодом P)
- 0100 (свободно)
- 0101 (свободно)
- 0110 (свободно)
- 0111 (свободно)
- 1000 (свободно)
- 1001 (свободно)
- 1010 (свободно)
- 1011 (свободно)
- 1100 (свободно)
- 1101 (свободно)
- 1110 (свободно)
- 1111 (свободно)
Среди свободных кодов, наиболее короткие — это 0001, 0100, 0101, 0110 и т.д.
Сравнивая числовые значения:
- 0001 (1)
- 0100 (4)
- 0101 (5)
- 0110 (6)
- 0111 (7)
- ...
Самый короткий код с наименьшим числовым значением для буквы И — это 0001.
