Основные алгебраические системы, используемые в теории кодирования.
ТЕМА 6. ДВОИЧНЫЕ ЦИКЛИЧЕСКИЕ (n,k) - КОДЫ
Задачи
1. Показать, что корректирующие свойства (6, 5) – кода, в котором избыточный элемент вводится как проверка на нечетность, в точности совпадают с корректирующими свойствами (6, 5) – кода с проверкой на четность.
2. Показать, что коды Хэмминга с dmin=3 соответствуют границе Хэмминга.
3. Показать, что (7, 3) – код, являющийся нулевым пространством кода Хэмминга (7, 4), является эквидистантным, т.е. все кодовые расстояния в этом коде равны.
4. Построить порождающую матрицу для итеративного кода, в котором по строкам и столбцам используется (8, 7) – код с проверкой на четность.
(Продолжение)
Выше, в разделе 5.2.1 были введены понятия группы и векторного пространства, которые лежат в основе определения и описания групповых кодов. Для изучения важного подкласса групповых кодов – циклических кодов – необходимо знакомство и с другими алгебраическими системами, такими как кольцо и поле.
в) Кольцо
Кольцом R называют множество элементов, на котором определены две операции – сложение a + b и умножение ab. Для того, чтобы R было кольцом оно должно удовлетворять следующим требованиям:
R.1 Множество R является абелевой группой по операции сложения (аддитивная абелева группа).
R.2 (замкнутость). Для любых двух элементов a и b из множества R определено произведение ab, которое является элементом R.
R.3 (ассоциативный закон). Для любых трех элементов a, b, и c из R a(bc)=(ab)c.
R.4 (дистрибутивный закон). Для любых трех элементов a, b, и c из множества R справедливы равенства a(b+c)=ab+ac и (b+c)a=ba+ca.
Кольцо называют коммутативным, если операция умножения коммутативна, т.е. для любых двух элементов R выполняется равенство ab=ba.
В теории групп очень важную роль играет понятие подгруппы. В теории колец соответствующую роль играет понятие идеала. Идеалом I называют подмножество элементов кольца R, обладающее следующими двумя свойствами:
1). I является подгруппой аддитивной группы кольца R;
2). Для любого элемента a из I и любого элемента r из R произведения ar и ra принадлежат I.
Поскольку идеал является подгруппой, могут быть образованы смежные классы (см. основные свойства группы). В этом случае смежные классы называют классами вычетов. Идеал образует первую строку разложения с нулевым элементом (единичным элементом по операции сложения) слева. Далее любой элемент кольца, не принадлежащий идеалу, может быть выбран в качестве образующего первого класса вычетов, а остальные элементы класса получают прибавлением образующего к каждому элементу идеала:
| 0=a1, | a2, | a3, | a4, | a5,… |
| r1=r1+a1, | r1+a2, | r1+a3, | r1+a4, | r1+a5,… |
| r2=r2+a1, | r2+a2 | r2+a3, | r2+a4, | r2+a5,… |
| ……. | ……. | ……. | ……. | ……. |
| ……. | ……. | ……. | …….. | ……. |
| ……. | ……. | ……. | ……. | ……. |
Первыми элементами в каждой строке являются, как и при построении смежных классов, элементы, не использованные в предыдущих строках.
Все свойства смежных классов верны также для классов вычетов:{r}+{s}={r+s} и умножение классов вычетов {r}{s}={rs}
В высшей алгебре доказывается, что классы вычетов по идеалу в некотором кольце образуют кольцо. Это кольцо называют кольцом классов вычетов.
В теории кодирования важную роль играют кольца целых чисел и кольца многочленов.
Основные свойства кольца:
1. Совокупность целых чисел образует идеал тогда и только тогда, когда она состоит из всех чисел, кратных некоторому целому числу.
Пусть m – наименьшее целое положительное число в идеале и s – любое другое кольцо в идеале. На основе алгоритма деления Евклида запишем выражение для наибольшего общего делителя чисел m и s:
d=am+bs,
где a и b - целые числа.
Из приведенного равенства вытекает, что d также принадлежит идеалу. Действительно, так как m – наименьшее число в идеале, то m≤d, а так как d делит m, то d≤m. Значит m=d и s кратно m.
Идеал, который состоит из всех чисел, кратных m и самого m, обозначают (m).
2. Каждый класс вычетов по модулю m содержит либо 0, либо целое положительное число, не превосходящее m. Нуль является элементом идеала, а все целые положительные числа, не превосходящие m, принадлежат различным классам вычетов.
Доказательство этого свойства основывается на рассуждениях, приведенных в примере 5.2.2.
Построенные в этом примере смежные классы являются также и классами вычетов по идеалу (2) и образуют кольцо целых чисел по модулю 2.
Сформулированные выше свойства колец целых чисел полностью справедливы и для многочленов. Сходство в строении и свойствах кольца целых чисел и кольца многочленов обусловлены тем, что оба они являются частными случаями алгебраического образования, известного как евклидово кольцо. Рассмотрим основные свойства колец многочленов, необходимые для понимания структуры циклических кодов.
3. Совокупность многочленов образует идеал тогда и только тогда, когда она содержит все многочлены кратные некоторому многочлену.
Идеал, образованный всеми многочленами, кратными f(x) обозначают (f(x)). Кольцо классов вычетов, образованных по этому идеалу, называют кольцом многочленов по модулю f(x).
4. Каждый класс вычетов по модулю многочлена f(x) степени n содержит либо 0, либо многочлен степени меньшей, чем n. Нуль является элементом идеала, а все многочлены степеней, меньших, чем n, принадлежат различным классам вычетов.
Пример 6.1. Особую роль в теории циклических кодов играет кольцо многочленов по модулю двучлена xn+1
Рассмотрим классы вычетов многочленов по модулю двучлена третьей степени – x3+1. В соответствии со свойством 4 каждый класс вычетов содержит либо 0, либо многочлен степени меньшей, чем 3. Как и ранее рассматриваем многочлены с коэффициентами в виде двоичных элементов. Приведенная ниже таблица отражает содержание классов вычетов многочленов по модулю многочлена x3+1
| {0}=000 | 1+x3 | x(1+x3) | . . . |
| {1}=100 | X3 | 1+x+x4 | . . . |
| {x}=010 | 1+x+x3 | x4 | . . . |
| {1+x}=110 | X+x3 | 1+x4 | . . . |
| {x2}=001 | 1+x2+x3 | x+x2+x4 | . . . |
| {1+x2}=101 | X2+x3 | 1+x+x2+x4 | . . . |
| {x+x2}=011 | 1+x+x2+x3 | x2+x4 | . . . |
| {1+x+x2}=111 | X+x2+x3 | 1+x2+x4 | . . . |
В левой колонке этой таблице приведены многочлены минимальной степени в своем классе вычетов. Именно они обозначают класс вычетов и поэтому взяты в фигурные скобки. Рядом с ними показано двоичном представление многочленов данного класса вычетов.
Двоичное представление класса вычетов показывает, что классы вычетов представляют собою векторное пространство размерности 3, состоящее из 8 двоичных последовательностей длины 3.
Из приведенного примера можно сделать следующий очень важный вывод: кольцо многочленов по модулю двучлена xn+1 отображает бесконечное множество многочленов на конечное n – мерное векторное пространство. При этом векторы этого пространства можно складывать и умножать по правилам сложения и умножения классов вычетов многочленов по модулю xn+1.
Кольцо многочленов по модулю двучлена xn+1, как и любое кольцо, имеет свой идеал. Как и в случае целых чисел, идеал I кольца многочленов по модулю xn+1 содержит классы вычетов, кратные некоторому классу вычетов {g(x)}, т.е. некоторый класс вычетов {s(x)}, принадлежит идеалу I тогда и только тогда, когда s(x) делится на g(x). Покажем, что g(x) при этом должен быть делителем xn+1.
Представим процесс деления xn+1 на g(x) в следующем виде:
xn+1=g(x)q(x)+r(x),
где q(x)- частное от деления, а r(x)-остаток от деления. При этом, очевидно, что степень r(x)- меньше степени g(x).Поэтому должно быть справедливо равенство:
{0}={xn+1}={g(x)}{q(x)}+{r(x)},
из которого вытекает, что класс вычетов {r(x)} также принадлежащий идеалу I. Поскольку степень r(x) меньше степени g(x), то r(x) должно быть нулевым и, следовательно, xn+1 кратен g(x).
Пример 6.2. Определим, какие идеалы существуют в кольце многочленов Примера 6.1. Рассматриваемое кольцо образуют классы вычетов многочленов по модулю x3+1. X3+1 имеет в качестве сомножителей два многочлена с двоичными коэффициентами:
x3+1=(x+1)(x2+x+1).
Следовательно, имеется два подмножества последовательностей длины 3, образующие идеалы рассматриваемого кольца. Один идеал включает все классы вычетов кратные {1+x}: {0}, {1+x}, {1+x2}, {x+x2}, отображаемые двоичными последовательностями (000), (110), (101) и (011) соответственно. Второй идеал состоит из классов вычетов {0} и {1+x+x2}, отображаемых двоичными последовательностями (000) и (111).
Представляет интерес сравнить полученные идеалы с результатами решения задач 2 и 5 из раздела 5.2.5.
5. Пусть xn+1=g(x)·h(x), где h(x)-многочлен степени k. Тогда идеал, порожденный классом вычетов {g(x)} в кольце многочленов по модулю xn+1, имеет размерность k.
Действительно, многочлен g(x),порождающий идеал, имеет степень n-k, а значит среди классов вычетов кольца многочленов по модулю xn+1 существуют классы вычетов {g(x)}, {xg(x)},…{xk-1g(x)},отображаемые k линейно независимыми векторами. При этом любой класс вычетов может быть представлен вектором, полученным линейной комбинацией. Например, S(x) - многочлен минимальной степени в своей классе вычетов и S(x)=g(x)·q(x)=g(x)(q0+q1x+…+qk-1xk-1) и {S(x)}=q0{g(x)}+q1{xg(x)}+…+qk-1{xk-1g(x)}, т.е k векторов {g(x)}, {xg(x)},…, {xk-1g(x)} порождают идеал. Значит размерность идеала, равна k.
В примере 6.2. один из идеалов порождается векторами {g(x)}={1+x} и {xg(x)}={x+x2}, а другой – {1+x+x2}.
Многочлен g(x) минимальной степени, такой, что его класс вычетов {g(x)} принадлежит идеалу, называет порождающим многочленом идеала.
г) Понятие о конечных полях
Полем называют множество элементов, на котором определены две операции. Одна из них называется сложением и обозначается a+b, а другая – умножением и обозначается a×b, даже если эти операции не являются обычными операциями сложения и умножения чисел. Для того чтобы множество элементов, на котором заданы операции сложения и умножения, было полем, необходимо, чтобы по каждой из этих операций выполнялись все групповые аксиомы, а также выполнялся дистрибутивный закон, т.е. для трех любых элементов поля а, b, с были справедливы равенства а×(b+с)=аb+ас и (b+с)а=bа+са.
Кроме того, по каждой операции группа должна быть коммутативной, т.е. должно выполняться, а+b=b+a и аb=bа. Следует заметить, что групповые свойства по операции умножения справедливы для всех ненулевых элементов поля.
Поля с конечным числом элементов q называют полями Галуа по имени их первого исследователя Эвариста Галуа и обозначают GF(q).
Число элементов поля q называют порядком поля. Конечные поля используются для построения большинства известных кодов и их декодирования.
В зависимости от значения q различают простые или расширенные поля. Поле называют простым, если q – простое число. Для обозначения простых чисел будем использовать символ p.
Простое поле образуют числа по модулю p: 0, 1, 2,…, p–1, а операции сложения и умножения выполняются по модулю p.
Наименьшее число элементов, образующих поле, равно 2. Такое поле должно содержать 2 единичных элемента: 0 относительно операции сложения и 1 относительно операции умножения. Это поле GF(2), или двоичное.
Правила сложения и умножений для элементов GF(2) задаются таблицами:
таблица сложения : таблица умножения:
| + | ∙ | ||||||
GF(3) – троичное поле с элементами 0, 1, 2. Для него таблица сложения и умножения имеют вид.
| + | ∙ | |||||||
Формирование таблиц производится приведением результата сложения или умножения чисел, записанных во главе строк или столбцов, по модулю p, т.е. в качестве результата операции принимается остаток от деления полученного числа на p.
Анализируя состав таблиц, легко убедиться, что 0 и 1 как единичные элементы по операции сложения и умножения не изменяют значения других элементов поля по соответствующей операции. Кроме того, видно, что для каждого элемента по операции сложения и для ненулевых элементов по операции умножения имеются обратные.
Ниже приведены правила сложения и умножения для элементов GF(4) при попытке построить это поле из чисел 0, 1, 2, 3 по предыдущей конструкции.
таблица сложения: таблица умножения:
| + | ∙ | ||||||||||
Из анализа таблиц видно, что для элемента 2 по операции умножения отсутствует обратный, т.е. набор чисел 0, 1, 2, 3 не является полем при введении операции по модулю 4. Такой результат объясним тем, что 4 не является простым числом. Для поля GF(5) с элементами 0, 1, 2, З, 4 правила сложения и умножения имеют вид.
таблица сложения: таблица умножения:
| + | ∙ | ||||||||||||
Изучим возможность построения полей с элементами в виде последовательностей чисел.
Определим условия, при которых последовательности длины m с элементами из поля GF(p) образуют поле.
Рассмотрим последовательности длины 4 с элементами из GF(2). Такие последовательности можно складывать как векторы, и нулевым элементом по операции сложения является 0000. Для задания операции умножения сопоставим каждой последовательности многочлен от α:
| Последовательность | Многочлен |
| 0 0 0 0 | 0 |
| 1 0 0 0 | 1 |
| 0 1 0 0 | Α |
| 1 1 0 0 | 1+α |
| 0 0 1 0 | α2 |
| 1 0 1 0 | 1+α2 |
| 0 0 0 1 | α3 |
| … | … |
| 1 1 1 1 | 1+α+α2+α3 |
Умножение таких многочленов может дать степень, большую, чем 3, т.е. последовательность, не принадлежащую рассматриваемому множеству.
Например, (1101)∙(1001)«(1+α+α3)∙(1+α3)=1+α+α4+α6. Для того чтобы свести ответ к многочлену степени не более 3, положим, что α удовлетворяет уравнению степени 4, например:
Π(α)=1+α+α4=0,
или
α4=1+α.
Тогда
α5=α+α2,α 6=α2+ α3;
1+α+α 4+α6=1+α+1+α+α2+α3=α2+α3.
Это эквивалентно делению на многочлен 1+α+α4 и нахождению остатка от деления:
| Щ+ | α6+α4+α+1 | α4+α+1 | ||
| α6+α3+α2 | α2+1 | |||
| =+ | α4+α3+α2+α+1 | |||
| α4+α+1 | ||||
| α3+α2–остаток | ||||
Таким образом, имеет место аналогия при формировании поля из чисел и последовательностей чисел (многочленов). Эта аналогия распространяется и на то, что для обратимости введенной операции умножения (чтобы система элементов в виде последовательностей длины m или многочленов степени меньшей m, образовывала поле) многочлен Π(a) должен быть неприводим над полем своих коэффициентов.
Поле, образованное многочленами над полем GF(р) по модулю неприводимого многочлена степени m, называется расширением поля степени m над GF(p) или расширенным полем. Оно содержит pm элементов и обозначается GF(pm).
Поле, образованное шестнадцатью двоичными последовательностями длины 4, или многочленами степени 3 и менее с коэффициентами из GF(2) по модулю многочлена α4+α+1 , неприводимого над GF(2), является примером расширенного поля GF(24), которое может быть обозначено также GF(16)
Важнейшим свойством конечных полей является следующее.
Множество всех ненулевых элементов конечного поля образует группу по операции умножения, т.е. мультипликативную группу порядка q–1.
Рассмотрим совокупность элементов мультипликативной группы, образованную некоторым элементом α и всеми его степенями α2, α3 и т.д. Так как группа конечна, должно появиться повторение, т.е. αi=αj. Умножая это равенство на (αi)–1 = (α–1)i, получим 1=αj-i. Следовательно, некоторая степень α равна 1.
Наименьшее положительное число e, такое, что αe=1, называется порядком элемента α. Совокупность элементов 1, α, α2,…, αe–1 образует подгруппу, поскольку произведение любых двух элементов принадлежит этой совокупности, а элемент, обратный αj, равен αe–j и тоже входит в эту совокупность.
Группа, которая состоит из всех степеней одного из ее элементов, называется циклической группой.
Из рассмотренного свойства конечных полей вытекают два важных следствия.
Первое из них утверждает, что многочлен xq–1–1 имеет своими корнями все q–1 ненулевых элементов поля GF(q), т.е.
В поле GF(q) элемент α, имеющий порядок e=q–1, называется примитивным. Отсюда следует, что любой ненулевой элемент GF(q) является степенью примитивного элемента. Второе следствие из рассмотренного свойства утверждает, что любое конечное поле GF(q) содержит примитивный элемент, т.е. мультипликативная группа GF(q) является циклической.
В табл..6.1 представлены различными способами элементы GF(24).
Таблица 6.1
| Последовательность длины 4 | Многочлен | Степень | Логарифм |
| 1 | 2 | 3 | 4 |
| 0000 | 0 | 0 | –∞ |
| 1000 | 1 | 1 | 0 |
| 0100 | Α | α | 1 |
| 0010 | α2 | α2 | 2 |
| 0001 | Α3 | α3 | 3 |
| 1100 | 1+α | α4 | 4 |
| 0110 | α+α2 | α5 | 5 |
| 0011 | Α2+α3 | α6 | 6 |
| 1101 | 1+α+α3 | α7 | 7 |
| 1010 | 1+α2 | α8 | 8 |
| 0101 | α+α3 | α9 | 9 |
| 1110 | 1+α+α2 | α10 | 10 |
| 0111 | a +a 2+a 3 | a11 | 11 |
| 1111 | 1+a+a2+a3 | a12 | 12 |
| 1011 | 1+a2+a3 | a13 | 13 |
| 1001 | 1+a3 | a14 | 14 |
Поле GF(24), представленное в табл. 6.1, построено по модулю α4+α+1. Примитивный элемент поля a является корнем этого многочлена.
Многочлен, корнем которого является примитивный элемент поля, называется примитивным многочленом. Если в качестве Π(α) выбрать примитивный неприводимый многочлен степени m над полем GF(2), то получим поле GF(2m) из всех 2m двоичных последовательностей длины m.
Выше было показано, что GF(4) нельзя представить в виде совокупности чисел 0, 1, 2, 3. Построим его как расширенное поле по модулю многочлена Π(α) =α2+α+1 .
В табл. 6.2 элементы этого поля представлены различными способами. Здесь принято, что примитивный элемент a является корнем Π(a), т.е. a2+a+1=0.
Таблица 6.2
| Последовательность длины 2 | Многочлен | Степень | Логарифм |
| –∞ | |||
| a | a | ||
| 1+a | a2 |
Правила сложения и умножения в этом поле приведены ниже.
таблица умножения таблица умножения
| 1+ | 1a | 1a2 | 1∙ | 1a | a2 | ||||||
| 1a | 1a2 | ||||||||||
| aa2 | 1a | 1a | a2 | ||||||||
| 1a | 1a | 1a2 | 1a | 1a | a2 | ||||||
| 1a2 | 1a2 | 1a | 1a2 | 1a2 | 1a |
Формирование первой строки, первого столбца и диагональных элементов таблицы сложения, а также двух первых строк и двух первых столбцов таблицы умножения не вызывает затруднения.
Поясним формирование других элементов:
1+a=a2, 1+a2=a, a+a2=1;
a∙a2=a3= a(1+a)=a+a2=1
на основе соотношения для примитивного элемента a2+a+1=0.