Вопрос 46.1. Классификация кодов. Линейные коды. Оптимальное кодирование

Основные определения

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

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

Правило кодирования может быть выражено кодовой таблицей, в которой приводятся алфавит кодируемых сообщений и соответствующие им кодовые комбинации.

Кодовый алфавит ‑ множество возможных кодовых символов.

Основание кода ‑ их количество (обозначим m).

В общем случае при основании кода m правила кодирования N элементов сообщения сводятся к правилам записи N различных чисел в m -ичной системе счисления.

Значность кода или длина кодовой комбинации ‑ число разрядов n, образующих кодовую комбинацию. В зависимости от системы счисления, используемой при кодировании, различают двоичные и m -ичные (недвоичные) коды.

Классификация кодов

По разрядности коды делят на:

Равномерные. Коды, у которых все комбинации имеют одинаковую длину, называют равномерными. Для равномерного кода число возможных комбинаций равно m ⁿ. Примером такого кода является пятизначный код Бодо, содержащий пять двоичных элементов (m = 2, n = 5). Число возможных кодовых комбинаций равно 2⁵ = 32, что достаточно для кодирования всех букв алфавита. Применение равномерных кодов не требует передачи разделительных символов между кодовыми комбинациями.

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

По помехоустойчивости коды делят на:

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

Корректирующие. Корректирующими называются коды позволяющие обнаруживать и исправлять ошибки.

Линейные коды

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

Если записать k линейно-независимых блоков длины n в виде k строк, то получится матрица размером n ´ k, которую называют порождающей или производящей матрицей кода G.

Множество линейных комбинаций образует линейное пространство, содержащее 2 ^k блоков, т.е. линейный код, содержащий 2 ^k блоков длиной n, обозначают (n, k). При заданных n и k существует много различных (n, k)-кодов с различными кодовыми расстояниями d, определяемых различными порождающими матрицами. Все они имеют избыточность e_k =1- k / n или относительную скорость R_k = k / n.

Чаще всего применяют систематические линейные коды, которые строят следующим образом. Сначала строится простой код длиной k, т.е. множество всех k -последовательностей двоичных символов, называемых информационными. Затем к каждой из этих последовательностей приписывается r = n - k проверочных символов, которые получаются в результате некоторых линейных операций над информационными символами.

Простейший систематический код (n, n - 1) строится добавлением к комбинации из n - 1 информационных символов одного проверочного, равного сумме всех информационных символов по модулю 2. Такой код (n, n - 1) имеет d=2 и позволяет обнаружить одиночные ошибки и называется кодом с одной проверкой на четность.

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