Кодирование. Общие понятия

Преобразование дискретного сообщения в сигнал обычно осуществляется в виде двух операций — кодирования и модуляции. Кодирование представляет со­бой преобразование сообщения в последовательность кодовых символов, а мо­дуляция — преобразование этих символов в сигналы, пригодные для передачи по каналу. С помощью кодирования и модуляции источник сообщений согла­суется с каналом.

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

Так, для передачи заглавных букв русского алфавита (их 32) необходимо передать числа от 0 до 31. Для передачи любого числа, записанного в десятичной форме, требуется передача десяти цифр — от 0 до 9. Практически для этого нужны десять сигналов, соответствующих различным цифрам. Систему передачи дискретных сообщений можно существенно упро­стить, если воспользоваться при кодировании двоичной системой счисления.

В десятичной системе основанием счисления является число 10. Поэтому любое целое число Кможно представить в виде

K=a_n10ⁿ+...+a₂10²+a₁10¹+a₀10⁰, (4.1)

где a₀, a₁, ...,a_n - коэффициенты, принимающие значение от 0 до 9. Так, число 265 можно записать как 2 10² + 6 10¹ + 5 10°. Очевидно, в качестве основания счисления можно принять любое целое число т и представить число N как

К=a_nmⁿ+...+a₂m²+a₁m¹+a₀m⁰,(4.2)

где a₀, a₁, ...,a_n - коэффициенты, принимающие значение от 0 до т - 1. Задаваясь величиной m, можно построить любую систему счисления.

При m=2 получим двоичную систему, в которой числа записываются с помощью двух цифр 0 и 1.

Например, число 13 в двоичной системе записывается 1101, что соответствует выражению 1 2³ +1 2² +0 2¹ + 1 2°.

Арифметические действия в двоичной системе весьма просты. Так, сложение осуществляется по следующим правилам:

0 + 0 = 0;

0+1 = 1;

1+0=1;

1 + 1 = 1.

Различают поразрядное сложение без переноса в старший разряд, так назы­ваемое "сложение по модулю два". Правила этого сложения следующие:

0 + 0 = 0;

0 + 1 = 1;

1 + 0 = 1,

1 + 1 = 0.

Если преобразовать последовательность элементов сообщения в последовательность двоичных чисел, то для передачи последних по каналу связи достаточно передавать всего лишь два различных сигнала. Например, символы 0 и 1 могут передаваться колебаниями с различными частотами или импульсами тока разной полярности. Благодаря своей простоте двоичная система счисления широко применяется при кодировании дискретных сообщений.

При кодировании происходит процесс преобразования элементов сообще­ния в соответствующие им числа (кодовые символы). Каждому элементу сооб­щения присваивается определённая совокупность кодовых символов, которая называется кодовой комбинацией. Совокупность кодовых комбинаций, отобра­жающих дискретные сообщения, образует код. Правило кодирования может быть выражено кодовой таблицей, в которой приводятся алфавит кодируемых сообщений и соответствующие им кодовые комбинации. Множество возможных кодовых символов называется кодовым алфавитом, а их количество m— основанием кода. В общем случае при основании кода т правила кодирования K элементов сообщения сводятся к правилам записи K различных чисел в m-ичной системе счисления. Число разрядов п, образующих кодовую комбинацию, называется разрядностью кода или длиной кодовой комбинации. В зависимости от системы счисления, используемой при кодировании, различают двоичные и т-ичные (недвоичные) коды.

Коды, у которых все комбинации имеют одинаковую длину, называют равномерными. Для равномерного кода число возможных комбинаций равно mⁿ.Примером такого кода является пятизначный код Бодо, содержащий пять двоичных элементов (m= 2, п = 5). Число возможных кодовых комбинаций равно 2⁵ = 32, что достаточно для кодирования всех букв русского алфавита. Однако этого недостаточно для передачи сообщения, содержащего буквы, цифры, различные условные знаки (точка, запятая, сложение, умножение и т.п.). Поэтому в настоящее время используется "Международный код №2" (МТК-2). В коде МТК-2 используется регистровый принцип, согласно которому одна и та же пятиэлементная кодовая комбинация может использоваться до трёх раз в зависимости от положения регистра: русский, латинский, цифровой. Общее число различных знаков при этом равно 84, что достаточно для кодирования телеграммы.

Для передачи данных рекомендован семиэлементный код МТК-5. Коды МТК-2 и МТК-5 являются первичными (простыми). Основными параметрами кодов являются: основание кода т, длина кодовой комбинации n, расстояние между кодовыми комбинациями d_ij и вес кодовой комбинации w. Расстояние d_ij характеризует различие между двумя кодовыми комбинациями и определяется по Хеммингу числом несовпадающих в них разрядов, т.е. числом единиц в сумме двух комбинаций по модулю 2. Число ненулевых элементов в кодовой комбинации определяет её вес w. Применение равномерных кодов упрощает построение автоматических буквопечатающих устройств и не требует передачи разделительных символов между кодовыми комбинациями.

Неравномерные коды характерны тем, что у них кодовые комбинации отличаются друг от друга не только взаимным расположением символов, но и их количеством. Это приводит к тому, что различные комбинации имеют различную длительность. Такие коды требуют либо специальных разделительных знаков, указывающих конец одной и начало другой кодовой комбинации, либо же должны строиться так, чтобы никакая кодовая комбинация не являлась началом другой. Коды, удовлетворяющие этому условию, называются неприводимыми или префиксными. Заметим, что равномерный код также является неприводимым. Строение кода удобно представлять в виде графа (кодового дерева), в котором из каждого узла исходит число ветвей, равное основанию кода (для двоичного кода, например, шаг вверх означает 0, шаг вниз — 1).

Типичным примером неравномерных кодов является код Морзе, в котором символы 0 и 1 используются только в двух сочетаниях - как одиночные (1 и 0) или как тройные (111 и 000). Сигнал, соответствующий одной единице, называется точкой, трём единицам - тире. Символ 0 используется как знак, отделяющий точку от тире, точку от точки и тире от тире. Совокупность 000 используется как разделительный знак между кодовыми комбинациями.

По признаку помехозащищённости коды делят на примитивные (первичные) и корректирующие. Коды, у которых все возможные кодовые комбинации ис­пользуются для передачи информации, называются простыми или кодами без избыточности (примитивными). В простых равномерных кодах превращение одного символа комбинации в другой, например 1 в 0 или 0 в 1, приводит к появлению новой разрешённой комбинации, т.е. к ошибке. Корректирующие коды строятся так, что для передачи сообщения используются не все кодовые ком­бинации, а лишь некоторая их часть (разрешённые кодовые комбинации). Тем самым создаётся возможность обнаружения и исправления ошибки при непра­вильном воспроизведении некоторого числа символов. Корректирующие свойства кодов достигаются введением в кодовые комбинации дополнительных (избыточных) символов.