Контрольні питання. Способи побудови двійкових кодів

Висновки

M = 59 = 3×42 + 2×41+ 3×40 = 3234.

M = 59 = 7·81 + 3·80 =738.

Способи побудови двійкових кодів

Любое дискретное сообщение из алфавита источника можно закодировать последовательностью соответствующим образом выбранных кодовых символов из алфавита.

Например, любое число (а можно считать числом) можно записать в заданной позиционной системе счисления.

Позиционная система счисления определяется целым числом, называемым основанием системы счисления. Система счисления с основанием также называется b -ричной (в частности, двоичной, троичной, десятичной и т. п.).

Целое число в -ричной системе счисления представляется в виде конечной линейной комбинации степеней числа:

где — это целые числа, называемые цифрами, удовлетворяющие неравенству.

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

Построение такой записи числа называют позиционным кодированием числа, а саму запись — позиционным кодом числа.

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

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

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

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

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

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

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

Буква x i	Число xi	Код с основанием 10	Код с основанием 4	Код с основанием 2
А
Б
В
Г
Д
Е
Ж
З

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

Рис. 1

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

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

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

· каждой букве – одинаковое число бит;

· при получении заданного числа бит – в кодовой таблице ищется соответствующая буква.

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

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

А

З

Б

В

Г

Д

Е

Ж

Рис. 2

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

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

А

Б

В

Г

Д

Рис. 3

Дата добавления: 2013-12-12