Кодирование информации

     где m - основание системы счисления; x₀ … x_n-1 - коэффициенты при степенях m; x Ì 0, m - 1.

     Пусть, к примеру, значение l_i = M = 59 , тогда его код по основанию m = 8, будет иметь вид

     M = 59 = 7·8¹ + 3·8⁰ =73₈ .

     Код того же числа, но по основанию m = 4 будет выглядеть следующим образом:

     M = 59 = 3×4² + 2×4¹+ 3×4⁰ = 323₄ .

     Наконец, если основание кода m = 2,  то

     M = 59 = 1×2⁵ + 1×2⁴ + 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 111011₂ .

     Таким образом, числа 73, 323 и 111011 можно считать, соответственно, восьмеричным, четверичным и двоичным кодами числа M = 59.

     В принципе основание кода может быть любым, однако наибольшее распространение  получили двоичные коды, или коды с основанием 2, для которых размер алфавита кодовых символов Â{ x_j } равен двум, x_j Ì 0,1. Двоичные коды, то есть коды, содержащие только нули и единицы, очень просто формируются и передаются по каналам связи и, главное, являются внутренним языком цифровых ЭВМ, то есть без всяких преобразований могут обрабатываться цифровыми средствами. Поэтому, когда речь идет о кодировании и кодах, чаще всего имеют в виду именно двоичные коды. В дальнейшем будем рассматривать в основном двоичное кодирование. [3, c. 51]

     Самым простым способом представления  или задания кодов являются кодовые  таблицы, ставящие в соответствие сообщениям l_i соответствующие им коды (табл. 1). 

     

     Таблица 1  

     Другим  наглядным и удобным  способом описания кодов  является их представление  в виде кодового дерева (рис..1).  

     

     Рис. 1 

     Для того, чтобы построить кодовое  дерево для данного кода, начиная  с некоторой точки - корня кодового дерева - проводятся ветви - 0 или 1. На вершинах кодового дерева находятся буквы алфавита источника, причем каждой букве соответствуют своя вершина и свой путь от корня к вершине. К примеру, букве А соответствует код 000, букве В – 010, букве Е – 101 и т.д.

     Код, полученный с использованием кодового дерева, изображенного на рис. 1, является равномерным трехразрядным кодом.

     Равномерные коды очень широко используются в  силу своей простоты и удобства процедур кодирования-декодирования: каждой букве  – одинаковое число бит; принял заданное число бит – ищи в кодовой таблице соответствующую букву.

     Наряду  с равномерными кодами могут применяться  и неравномерные коды, когда каждая буква из алфавита источника кодируется различным числом символов, к примеру, А - 10, Б – 110, В – 1110 и т.д.

     Кодовое дерево для неравномерного кодирования  может выглядеть, например, так, как  показано на рис. 2. 

       
 
 
 
 

     Рис. 2 

     При использовании этого кода буква  А будет кодироваться, как 1, Б - как 0, В – как 11 и т.д. Однако можно  заметить, что, закодировав, к примеру, текст АББА = 1001 , мы не сможем его однозначно декодировать, поскольку такой же код дают фразы: ЖА = 1001, АЕА = 1001 и ГД = 1001. Такие коды, не обеспечивающие однозначного декодирования, называются приводимыми, или непрефиксными, кодами и не могут на практике применяться без специальных разделяющих символов. Примером применения такого типа кодов может служить азбука Морзе, в которой кроме точек и тире есть специальные символы разделения букв и слов. Но это уже не двоичный код.

     Однако можно построить неравномерные неприводимые коды, допускающие однозначное декодирование. Для этого необходимо, чтобы всем буквам алфавита соответствовали лишь вершины кодового дерева, например, такого, как показано на рис. 3. Здесь ни одна кодовая комбинация не является началом другой, более длинной, поэтому неоднозначности декодирования не будет. Такие неравномерные коды называются префиксными. 
 
 
 
 
 

       
 
 
 
 
 
 

     Рис..3 

     Прием и декодирование неравномерных  кодов - процедура гораздо более  сложная, нежели для равномерных. При этом усложняется аппаратура декодирования и синхронизации, поскольку поступление элементов сообщения (букв) становится нерегулярным. Так, к примеру, приняв первый 0, декодер должен посмотреть в кодовую таблицу и выяснить, какой букве соответствует принятая последовательность. Поскольку такой буквы нет, он должен ждать прихода следующего символа. Если следующим символом будет 1, тогда декодирование первой буквы завершится – это будет Б, если же вторым принятым символом снова будет 0, придется ждать третьего символа и т.д.

     Зачем же используются неравномерные коды, если они столь неудобны?

     Рассмотрим  пример кодирования сообщений l_i из алфавита объемом K = 8 с помощью произвольного n-разрядного двоичного кода.

     Пусть источник сообщения  выдает некоторый текст с алфавитом от А до З и одинаковой вероятностью букв Р(l_i ) = 1/8.

     Кодирующее  устройство кодирует эти буквы  равномерным трехразрядным кодом (см. табл. 1).

     Определим основные информационные характеристики источника с таким алфавитом:

     - энтропия источника    , ;

     - избыточность источника    ;

     - среднее число символов в коде   ;

     - избыточность кода    .

     Таким образом, при кодировании  сообщений с равновероятными буквами избыточность выбранного (равномерного) кода оказалась равной нулю.

     Пусть теперь вероятности появления в  тексте различных букв будут разными (табл. 2). 

     Таблица 2

 

     Энтропия  источника  в этом случае, естественно, будет меньшей и составит _{= 1.781.}

     Среднее число символов на одно сообщение при  использовании того же равномерного трехразрядного кода

     

     Избыточность  кода в этом случае будет 

      ,

     или довольно значительной величиной (в  среднем 4 символа из 10 не несут никакой  информации).

     В связи с тем, что при кодировании неравновероятных сообщений равномерные коды обладают большой избыточностью, было предложено использовать неравномерные коды, длительность кодовых комбинаций которых была бы согласована с вероятностью выпадения различных букв.

     Такое кодирование называется статистическим.

     Неравномерный код при статистическом кодировании  выбирают так, чтобы более вероятные буквы передавались с помощью более коротких комбинаций кода, менее вероятные - с помощью более длинных. В результате уменьшается средняя длина кодовой группы в сравнении со случаем равномерного кодирования.

     Один  из способов такого кодирования предложен Хаффменом. Построение кодового дерева неравномерного кода Хаффмена для передачи одного из восьми сообщений l_i с различными вероятностями иллюстрируется табл. 3. 

     Таблица 3