Математическое введение в групповой код

Основой математического описания систематических кодов является линейная алгебра (теория векторных пространств, матрицы, группы). К.К. рассматриваются как элементы множества. Множества, для которых определены некоторые алгебраические операции, называются алгебраическими системами. Обычно основную операцию называют сложением (а + b = c) или умножением (a · b = c), а обратную ей вычитанием или деление.

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

Группой называется множество элементов, среди которых определена хотя бы одна основная операция, причем она должна быть ассоциативной [(a + b) + c = a + (b + c), a · (b · c) = (a · b) · c], и должна обладать обратной операцией.

Из определения группы вытекают следующие следствия:

1. Любые три элемента группы должны удовлетворять равенству:

(a + b) + c = a + (b + c) – основная операция сложение (о.о.с.);
a · (b · c) = (a · b) · c – основная операция умножение (о.о.у).

2. В каждой группе G_n существует однозначно определенный элемент, удовлетворяющий для всех a из G_n условию:

а + 0 = 0 + а = а – о.о.с. (элемент 0 называется нулем);
а · 1 = 1 · а = а – о.о.у. (элемент 1 называется единицей).

Если операция, определенная в группе, коммутативна (a + b = b + а, а · b = b · a), то группа называется коммутативной или абелевой. Группа, состоящая из конечного числа элементов, называется конечной. В конечной группе должно выполняться требование замкнутости, т.е. в результате операции применяемой к любым элементам группы, должны снова образовываться элементы этой же группы. Чтобы множество n-разрядных К.К. было конечной группой, основная операция должна быть выбрана так, чтобы требование замкнутости выполнялось. Отсюда следует, что при выполнении операций число разрядов в результирующей К.К. не должно увеличиваться.

Например, сложение по модулю 2():

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

Примеры

1. Множество 0001, 0110, 0111, 0011 – не группа, т.к. нет нулевого элемента.

2. Множество 0000, 1101, 1110, 0111 – тоже не группа, т.к. не выполняется условие замкнутости К.К.; 0011 не принадлежит искомому множеству.

3. Множество 000, 001, 010, 011, 100, 101, 110, 111 – является группой.

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

Пример: 000, 001, 010, 011 подгруппа группы 000, 001, 010, 011, 101, 110, 111.

Пусть абелевой группе G_n задана определенная подгруппа А. Если В – любой, не входящий в А, элемент из G_n, то суммы элемента В с каждым из элементов А образуют смежный класс группы G_n по подгруппе А, порожденный элементом В. Элемент В соответственно содержится в этом смежном классе, т.к. любая подгруппа содержит нулевой элемент. http://peredacha-informacii.ru/ Последовательно некоторые элементы B_j группы, не вошедшие в уже образованные смежные классы, можно разложить всю группу на смежные классы по модулю А. Элементы B_j называются образующими (главными) элементами смежных классов подгруппы. В таблице разложения, иногда называемой групповой таблицей, образующие элементы обычно располагаются в крайнем левом столбце.