![]()
|
|||||||
Кодирование информацииКодирование информации Кодирование информации— это обработка информации, заключающаяся в ее преобразовании в некоторую форму, удобную для хранения, передачи, обработки информации в дальнейшем. Код — это система условных обозначений (кодовых слов), используемых для представления информации. Кодовая таблица — это совокупность используемых кодовых слов и их значений. Нам уже знакомы примеры равномерных двоичных кодов — пятиразрядный код Бодо и восьмиразрядный код ASCII. Самый известный пример неравномерного кода — код Морзе. В этом коде все буквы и цифры кодируются в виде различных последовательностей точек и тире. Чтобы отделить коды букв друг от друга, вводят еще один символ — пробел (пауза). Например, слово «byte», закодированное с помощью кода Морзе, выглядит следующим образом: – · · · – · – – – · При использовании неравномерных кодов важно понимать, сколько различных кодовых слов они позволяют построить. Пример 1. Имеющаяся информация должна быть закодирована в четырехбуквенном алфавите {A, B, C, D}. Выясним, сколько существует различных последовательностей из 7 символов этого алфавита, которые содержат ровно пять букв А. Нас интересует семибуквенная последовательность, т. е. Если бы у нас не было условия, что в ней должны содержаться ровно пять букв А, то для первого символа было бы 4 варианта, для второго — тоже 4, и т. д. Тогда мы получили бы: 4 · 4 · 4 · 4 · 4 · 4 · 4 = 16384 варианта. Теперь вернемся к имеющемуся условию и заполним пять первых мест буквой А. Получим: Так как на 6-м и 7-м местах могут стоять любые из трех оставшихся букв B, C, D, то всего существует 9 (3 · 3) вариантов последовательностей. Но ведь буквы А могут находиться на любых пяти из семи имеющихся позиций. А сколько таких вариантов всего? Вспоминая комбинаторику, найдем число сочетаний Главное условие использование неравномерных кодов — возможность однозначного декодирования записанного с их помощью сообщения. Именно поэтому в технических системах широкое распространение получили особые неравномерные коды — префиксные коды. Префиксный код — код со словом переменной длины, обладающий тем свойством, что никакое его кодовое слово не может быть началом другого (более длинного) кодового слова. Например: 1. Код, состоящий из слов 0, 10 и 11, является префиксным. 2. Код, состоящий из слов 0, 10, 11 и 100, не является префиксным. Условие, определяющее префиксный код, называется прямым условием Фано (в честь Роберта Марио Фано), и позволяет однозначно декодировать сообщения, записанные с помощью неравномерных кодов. Также достаточным условием однозначного декодирования неравномерного код является обратное условие Фано. В нем требуется, чтобы никакой код не был окончанием другого (более длинного) кода. Пример 2. Двоичные коды для 5 букв латинского алфавита представлены в таблице: Выясним, какое сообщение закодировано с помощью этих кодов двоичной строкой: 0110100011000. Можно заметить, что для заданных кодов не выполняется прямое условие Фано: B=01, E=011, и D=10, C=100. А вот обратное условие Фано выполняется: никакое кодовое слово не является окончанием другого. Следовательно, имеющуюся строку нужно декодировать справа налево (с конца). Получим 01 10 100 011 000 = BDCEA Для построения префиксных кодов удобно использовать бинарные деревья, в которых от каждого узла отходят только два ребра, помеченные цифрами 0 и 1. Пример 3. Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются такие кодовые слова: А — 0, Б — 10, В — 110. Каким кодовым словом может быть закодирована буква Г? Если таких слов несколько, укажите кратчайшее из них. Построим бинарное дерево: Чтобы найти код символа, нужно пройти по стрелкам от корня дерева к нужному листу, выписывая метки стрелок, по которым мы переходим. Определим положение букв А, Б и В на этом дереве, зная их коды. Получим: Чтобы код был префиксным, ни один символ не должен лежать на пути от корня к другому символу. Уберем лишние стрелки: На получившемся дереве можно определить подходящее расположение буквы Г и его код. Г — 111.
|
|||||||
|