Теория информации (стр. 19 из 29)
Пусть в абелевой группе Gn задана определенная подгруппа А. Если В – любой, не входящий в А элемент из Gn, то суммы (по модулю 2) элементов В с каждым из элементов подгруппы А образуют определенный класс группы Gn по подгруппе А, порождаемый элементом В.
Элемент В, естественно, содержится в этом смежном классе, так как любая подгруппа содержит нулевой элемент. Взяв последовательно некоторые элементы Bj группы, не вошедшие в уже образованные смежные классы, можно разложить всю группу на смежные классы по подгруппе А.
Элементы Bj называют образующими элементами смежных классов по подгруппам.
В таблице разложения, иногда называемой групповой таблицей, образующие элементы обычно располагают в крайнем левом столбце, причем крайним левым элементом подгруппы является нулевой элемент.
Пример25: Разложить группу трехразрядных двоичных кодовых комбинаций по подгруппе двухразрядных кодовых комбинаций.
Решение: Разложение выполняют в соответствии с таблицей:
Таблица 4.4.
| A1=0 | A2 | A3 | A4 |
| 000 | 001 | 010 | 011 |
| B1 | A2ÅB1 | A3ÅB1 | A4ÅB1 |
| 100 | 101 | 110 | 111 |
Пример26: Разложить группу четырехразрядных двоичных кодовых комбинаций по подгруппе двухразрядных кодовых комбинаций.
Решение: Существует много вариантов разложения в зависимости от того, какие элементы выбраны в качестве образующих смежных классов.
Один из вариантов:
Таблица 4.5.
| A1=0 | A2 | A3 | A4 |
| 0000 | 0001 | 0110 | 0111 |
| B10100 | A2ÅB10101 | A3ÅB10110 | A4ÅB10111 |
| B21010 | A2ÅB21011 | A3ÅB21000 | A4ÅB21001 |
| B31100 | A2ÅB31101 | A3ÅB31110 | A4ÅB31111 |
Кольцом называют множество элементов R, на котором определены две операции (сложение и умножение), такие, что
1) множество R является коммутативной группой по отношению;
2) произведение элементов аÎR и bÎR есть элемент R (замкнутость по отношению и умножению);
3) для любых трех элементов a,b,c из R справедливо равенство a(bc)=(ab)c (ассоциативный закон для умножения);
4) для любых трех элементов a,b,c из R выполняются соотношения a(b+c)=ab+ac и (b+c)a=ba+ca (дистрибутивные законы);
Если для любых двух элементов кольца справедливо соотношение ab=ba, то кольцо называют коммутативным.
Кольцо может не иметь единичного элемента по умножению и обратных элементов.
Примером кольца может служить множество действительных четных целых чисел относительно обычных операций сложения и умножения.
Полем F называют множество, по крайней мере, двух элементов, в котором определены две операции – сложение и умножение, и выполняются следующие аксиомы:
1) множество элементов образуют коммутативную группу по сложению;
2) множество ненулевых элементов образуют коммутативную группу по умножению;
3) для любых трех элементов множества a,b,c выполняется соотношение (дистрибутивный закон) a(b+c)=ab+ac.
Поле F является, следовательно, коммутативным кольцом с единичным элементом по умножению, в котором каждый ненулевой элемент обладает обратным элементом. Примером поля может служить множество всех действительных чисел.
Поле GF(P), состоящее из конечного числа элементов Р, называют конечным полем или полем Галуа. Для любого числа Р, являющегося степенью простого числа q, существует поле, насчитывающее р элементов. Например, совокупность чисел по модулю q, если q - простое число, является полем.
Поле не может содержать менее двух элементов, поскольку в нем должны быть по крайней мере единичный элемент относительно операции сложения (0) и единичный элемент относительно операции умножения (1). Поле, включающее только 0 и 1, обозначим GF(2). Правила сложения и умножения в поле с двумя элементами следующие:
| + | 0 | 1 | × | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 |
Рис. 4.5 Правила сложения и умножения в поле с двумя элементами
Двоичные кодовые комбинации, являющиеся упорядоченными последовательностями из n Элементов поля GF(2), рассматриваются в теории кодирования как частный случай последовательностей из n элементов поля GF(P). Такой подход позволяет строить и анализировать коды с основанием, равным степени простого числа. В общем случае суммой кодовых комбинаций Aj и Ai называют комбинацию Af = Ai + Aj, в которой любой символ Ak (k=1,2,…,n) представляет собой сумму k-х символов комбинаций, причем суммирование производится по правилам поля GF(P). При этом вся совокупность n-разрядных кодовых комбинаций оказывается абелевой группой.
В частном случае, когда основанием кода является простое число q, правило сложения в поле GF(q) совпадает с правилом сложения по заданному модулю q.
4.7 Линейный код как пространство линейного векторного пространства
В рассмотренных алгебраических системах (группа, кольцо, поле) операции относились к единому классу математических объектов (элементов). Такие операции называют внутренними законами композиции элементов.
В теории кодирования широко используются модели, охватывающие два класса математических объектов (например, L и W). Помимо внутренних законов композиции в них задаются внешние законы композиции элементов, по которым любым двум элементам wÎW и аÎL ставится в соответствие элемент сÎL.
Линейным векторным пространством над полем элементов F (скаляров) называют множество элементов V (векторов), если для него выполняются следующие аксиомы:
1) множество V является коммутативной группой относительно операции сложения;
2) для любого вектора v изV и любого скаляра с из F определено произведение cv, которое содержится в V (замкнутость по отношению умножения на скаляр);
3) если u и v из V векторы, а с и d из F скаляры, то справедливо с(с+v)=cu+cv; (c+d)v=cv+dv (дистрибутивные законы);
4) если v-вектор, а с и d-скаляры, то (cd)v=c(dv) и 1*v=v
(ассоциативный закон для умножения на скаляр).
Выше было определено правило поразрядного сложения кодовых комбинаций, при котором вся их совокупность образует абелеву группу. Определим теперь операцию умножения последовательности из n элементов поля GF(P) (кодовой комбинации) на элемент поля ai GF(P)аналогично правилу умножения вектора на скаляр: ai(a1, a2, … , an)= (aia1, aia2, … , aian)
(умножение элементов производится по правилам поля GF(P)).
Поскольку при выбранных операциях дистрибутивные законы и ассоциативный закон (п.п.3.4) выполняются, все множество n-разрядных кодовых комбинаций можно рассматривать как векторное линейное пространство над полем GF(2) (т.е. 0 и 1). Сложение производят поразрядно по модулю 2. При умножении вектора на один элемент поля (1) он не изменяется, а умножение на другой (0) превращает его в единичный элемент векторного пространства, обозначаемый символом 0=(0 0…0).
Если в линейном пространстве последовательностей из n элементов поля GF(P) дополнительно задать операцию умножения векторов, удовлетворяющую определенным условиям (ассоциативности, замкнутости, билинейности по отношению к умножению на скаляр), то вся совокупность n-разрядных кодовых комбинаций превращается в линейную коммутативную алгебру над полем коэффициентов GF(P).
Подмножество элементов векторного пространства, которое удовлетворяет аксиомам векторного пространства, называют подпространством.
Линейным кодом называют множество векторов, образующих подпространства векторного пространства всех n-разрядных кодовых комбинаций над полем GF(P).
В случае двоичного кодирования такого подпространства комбинаций над полем GF(2) образует любая совокупность двоичных кодовых комбинаций, являющаяся подгруппой группы всех n-разрядных двоичных кодовых комбинаций. Поэтому любой двоичный линейный код является групповым.
4.8 Построение двоичного группового кода
Построение конкретного корректирующего кода производят, исходя из требуемого объема кода Q, т. е. необходимого числа передаваемых команд или дискретных значений измеряемой величины и статистических данных о наиболее вероятных векторах ошибок в используемом канале связи.
Вектором ошибки называют n-разрядную двоичную последовательность, имеющую единицы в разрядах, подвергшихся искажению, и нули во всех остальных разрядах. Любую искаженную кодовую комбинацию можно рассматривать теперь как сумму (или разность) но модулю 2 исходной разрешенной кодовой комбинации и вектора ошибки.
Исходя из неравенства 2k– l
Q (нулевая комбинация часто не используется, так как не меняет состояния канала связи), определяем число информационных разрядов k, необходимое для передачи заданного числа команд обычным двоичным кодом.Каждой из 2k - 1 ненулевых комбинаций k -разрядного безызбыточного кода нам необходимо поставить в соответствие комбинацию из п символов. Значения символов в п – kпроверочных разрядах такой комбинации устанавливаются в результате суммирования по модулю 2 значений символов в определенных информационных разрядах.
Поскольку множество 2k комбинаций информационных символов (включая нулевую) образует подгруппу группы всех n-разрядных комбинаций, то и множество 2kn-разрядных комбинаций, полученных по указанному правилу, тоже является подгруппой группы n-разрядных кодовых комбинаций. Это множество разрешенных кодовых комбинаций и будет групповым кодом.