![]()
|
|||||||
базовый уровень, время – 2 мин)Стр 1 из 6Следующая ⇒ 5 (базовый уровень, время – 2 мин) Тема: Кодирование и декодирование информации. Что нужно знать: · кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите) · обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход · один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия) · кодирование может быть равномерное и неравномерное; · закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова; · закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова; · условие Фано – это достаточное, но не необходимое условие однозначного декодирования. Пример задания Р-16.Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.. Решение: 1) Построим дерево для заданного двоичного кода: 2) согласно условию Фано, код декодируется однозначно, если все используемые кодовые слова соответствуют листьям такого дерева; видим, что для заданных кодовых слов это условие выполняется 3) может показаться, что ответ – 01, поскольку на эту ветвь можно «подвесить» букву Д, однако это не так – тогда будет некуда подвешивать оставшуюся букву – Е 4) поэтому для того, чтобы добавить в это дерево две буквы (Д и Е) и сохранить выполнение условия Фано, нужно в узле 01 сделать развилку, тогда получается два свободных кода, 010 и 011, из них меньший – 010 5) Ответ: 010.
|
|||||||
|