10 класс Информатика ГДЗ учебник Поляков 1 часть Параграф 6. Декодирование
Стр.67.
1. Чтобы сообщение, закодированное с помощью неравномерного кода, можно было однозначно декодировать, необходимо выполнение условия Фано. Это означает, что ни одно кодовое слово не должно совпадать с началом другого кодового слова. Такой код называют префиксным. Если условие Фано выполнено, то каждое кодовое слово уникально и не может быть перепутано с другим при декодировании.
2. Для проверки выполнения обратного условия Фано строят дерево, где каждый узел представляет собой кодовый символ. Начинают с корня, от которого отходят два ребра (помеченные 0 и 1). Если все листья дерева соответствуют конечным кодовым словам и ни одно кодовое слово не является окончанием другого, то условие Фано выполняется. В таком случае дерево называется постфиксным.
3. Перебор вариантов приходится использовать, когда кодовая таблица не удовлетворяет ни прямому, ни обратному условию Фано. В таких случаях каждое сообщение может иметь несколько интерпретаций, и единственный способ точно декодировать сообщение — это перебрать все возможные варианты и проверить их на соответствие кодовой таблице.
4. Пример:
- Слово: «КОДЕР»
- Кодовая таблица:
- К: 0
- О: 10
- Д: 110
- Е: 1110
- Р: 1111
Закодированное сообщение: «01011011101111»
Теперь ваш напарник должен декодировать это сообщение, используя предоставленную кодовую таблицу. Процесс декодирования будет таким:
- 0 -> К
- 10 -> О
- 110 -> Д
- 1110 -> Е
- 1111 -> Р
Таким образом, декодированное сообщение: «КОДЕР».
| § 4 | § 5 | § 6 | § 7 | § 8 |