Содержание
- 2. Задача 1 Пусть для кодирования фразы «Доброе утро» выбран такой код:
- 3. Коды букв «сцепляются» в единую битовую строку и передаются, например, по сети: Доброе утро→ 11100000100001110101000 В
- 4. 11100000100001110101000 Раскодировать данное сообщение можно разными способами. В том числе предположим, что оно состоит только из
- 5. Код называется однозначно декодируемым, если любое кодовое сообщение можно расшифровать единственным способом (однозначно).
- 6. Значит, код не является однозначно декодируемым.
- 7. Задача 2 Равномерные коды. Для той же фразы используем равномерный код:
- 8. Равномерные коды неэкономичны – гораздо длиннее неравномерных. Это приводит к усложнению кодирования, но при этом они
- 9. Задача 3 Чтобы сократить длину сообщения, можно попробовать применить неравномерный код, т.е. код, в котором кодовые
- 10. Используем следующий код: 0100101110000101011111101111010000 Эта битовая цепочка декодируется однозначно.
- 11. Первая буква - Д (код 01), т.к. ни одно другое кодовое слово не начинается с 01.
- 12. УСЛОВИЕ ФАНО Никакое кодовое слово не совпадает с началом другого кодового слова. Такие коды называются префиксными
- 13. Задача 4 Рассмотрим ещё один код: Он не является префиксным, т.к. код буквы Д (10) совпадает
- 14. Закодируем наше сообщение: ДОБРОЕ УТРО→ 10 00 1011 001 00 0101 1111 1000 0111 001 00
- 15. Попробуем раскодировать сообщение с конца – оно однозначно декодируется! Выполняется обратное условие Фано: никакое кодовое слово
- 16. Коды, для которых выполняется обратное условие Фано, называются постфиксными.
- 17. Сделаем вывод: Сообщение декодируется однозначно, если для используемого кода выполняется прямое или обратное условие Фано.
- 18. Условие Фано - это достаточное, но не необходимое условие однозначной декодируемости Это значит, что: - для
- 19. Задача 5 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д используется
- 20. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было
- 21. РЕШЕНИЕ: Исходный код – префиксный. Для него выполняется условие Фано – ни один из трёхбитных кодов
- 22. Теперь проверим ответы. Сократим Д до 11. Если полученный код нарушит прямое условие Фано, то свойство
- 23. Вариант 2 сразу не рассматриваем – ответ у нас найден. Вариант 3 нарушает прямое условие Фано
- 25. Скачать презентацию