Коды: общие сведения, основные свойства

Среди всех кодов наиболее полно к настоящему времени изучены линейные коды. Эти коды называются также систематическими или групповыми. Рассмотрим эти определения подробнее.

Группой называется множество элементов Г, для которых определена некоторая операция (сложения или умножения) и выполняются следующие аксиомы:

1. Если операция применена к двум элементам группы, то результат операции является также элементом группы, т.е. если а, b принадлежат Г то а+b также принадлежит Г для операции сложения и а*b принадлежит Г для операции умножения.

2. Для любых трех элементов группы a, b, c выполняется ассоциативный закон:

(a+b)+c=a+(b+c) – для операции сложения

a*(b*c)=(a*b)*c – для операции умножения

3. Существует нейтральный элемент. Если в качестве операции взято сложение, то нейтральный элемент называется нулем и удовлетворяет уравнению а+0=а. Если в качестве операции взято умножение, то нейтральный элемент называется единицей и удовлетворяет выражению а*1=а.

4. Каждый элемент группы обладает обратным элементом таким, что а+(-а)=0 для сложения, а*а^-1=1 для умножения.

Группа с операцией сложения называется аддитивной, а с операцией умножения – мультипликативной.

Некоторое подмножество элементов группы Г называется подгруппой Н, если оно удовлетворяет всем аксиомам группы.

Примеры группы:

· Совокупность всех действительных чисел без нуля образует группу, если в качестве операции взято умножение. Нейтральным элементом является 1, а обратным а^-1.

· Совокупность всех действительных чисел образует группу если в качестве операции взято обычное сложение. Нейтральным элементом является 0, а обратным элементом – этот же элемент с другим знаком.

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

k n-k k n-k k n-k

0001 011 0111 010 1101 001

0010 110 1000 101 1110 100

0011 101 1001 110 1111 111

0100 111 1010 011 0000 000

0101 100 1011 000

0110 001 1100 010

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

Если передаваемые сообщения представляют собой k-разрядные двоичные числа, то групповой код всегда может быть построен таким образом, что эти сообщения будут являться первыми k символами кода, как это сделано для рассмотренного выше примера. Код, построенный таким образом, называется систематическим кодом и обозначается (n;k)-код. Первое число в скобках показывает общее число символов в коде второе – число информационных символов. Для нашего примера обозначение кода будет таким: (7;4). Оставшиеся l=n-k символов называются проверочными. В групповых кодах проверочные символы образуются путем суммирования по модулю два символов, стоящих на определенных позициях кодового слова. Поскольку операция суммирования по модулю два является линейной, то коды, образованные таким образом, называются линейными.