Методы построения циклических кодов

В качестве информационных символов k для построения циклических кодов берут комбинации двоичного кода на все сочетания. В общем случае, если заданную кодовую комбинацию Q(X) умножить на образующий многочлен Р(Х), получится циклический код, обладающий теми или иными корректирующими свойствами в зависимости от выбора Р(Х). Однако в этом коде контрольные символы m будут располагаться в самых разнообразных местах кодовой комбинации. Такой код не является систематическим, что затрудняет его схемную реализацию. Ситуацию можно значительно упростить, если контрольные символы приписать в конце кода, то есть после информационных символов. Для этой цели целесообразно воспользоваться следующим методом.

1. Умножаем кодовую комбинацию G(X), которую мы хотим закодировать, на одночлен , имеющий ту же степень, что и образующий многочлен Р(Х).

2. Делим произведение  на образующий многочлен Р( ):

 

(1.1)

 

где Q(X) — частное от деления; R(X) — остаток.

Умножая выражение (1.1) на Р(Х) и перенося R(X) в другую часть равенства, согласно правилам алгебры двоичного поля, т. е. без перемены знака на обратный, получаем

 

 (1.2)

 

Таким образом, согласно равенству (1.2), циклический код, т. е. закодированное сообщение F(X), можно образовать двумя способами:

1 ) умножением одной из комбинаций двоичного кода на все сочетания [комбинация Q(X) принадлежит к той же группе того же кода, что и заданная комбинация G(X)] на образующий многочлен Р(Х);

2) умножением заданной кодовой комбинации G(X) на одночлен , имеющий ту же степень, что и образующий многочлен Р(Х), с добавлением к этому произведению остатка R(X), полученного после деления произведения  на образующий многочлен Р(Х).

Пример 1.1. Требуется закодировать одну из комбинаций двоичного кода 1101, что соответствует .

Не останавливаясь на выборе образующего многочлена Р(Х), о чем будет сказано далее, возьмем из табл. 1.1 многочлен Р(Х³)=Х³+Х+1→11→1011.

Умножая G(X) на , который имеет третью степень, получим

 

.

 

От умножения степень каждого многочлена повысилась, что эквивалентно приписыванию трех нулей к многочлену, выраженному в двоичной форме.

Разделив произведение  на образующий многочлен , согласно (1.1) получим

 

 

или в двоичном эквиваленте

Таким образом, в результате деления получаем частное Q(X) той же степени, что и G(X):

 

 

и остаток:

 

.

 

В итоге комбинация двоичного кода, закодированная циклическим кодом, согласно (1.2) примет вид

F(X)= 1111•1011 = 1101000 + 001 = 1101001.

Действительно, умножение 1111•1011 (первый способ) дает тот же результат, что и сложение 1101000 + 001 (второй способ).

Циклические коды, обнаруживающие одиночную ошибку (d=2). Код, образованный многочленом Р(Х)=Х+1, обнаруживает не только одиночную ошибку, но и любое нечетное число ошибок.

Предположим, что необходимо закодировать сообщение G(Х)=Х³+ +Х²+X+1→1101 с помощью образующего многочлена P(Х)=Х+1→11.

Умножим G(X) на Х^m, что эквивалентно добавлению нуля справа, так как m=1, поскольку Р(Х) имеет первую степень: (Х³+Х²+1)X= Х⁴+Х³+X→11010.

Разделив полученное выражение на Р(Х), найдем, что остаток R(X)=1. Следовательно, кодовый многочлен циклического кода в соответствии с уравнением (1.2) будет иметь вид

 

F(X)= G(X)Х^m + R(X)= Х⁴ + Х³ +X + 1→ 11010 + 1 = 11011.

 

Таким образом, в этом закодированном сообщении 11011 n = 5, k=4 и m=1, то есть информационным символом является комбинация 1101, а контрольным — единица в младшем разряде.

Сообщение, которое было закодировано (1101), является одной из 16 комбинаций четырехразрядного кода. Если требуется передать все эти сообщения в закодированном виде, то каждое из них следует кодировать так же, как и комбинацию 1101. Однако проделывать дополнительные 15 расчетов (в общем случае 2^k расчетов) нет необходимости. Это можно сделать проще, путем составления образующей (порождающей) матрицы.

Образующая матрица составляется из единичной транспонированной матрицы и матрицы дополнений.

Число столбцов транспонированной единичной матрицы равно числу информационных символов k. Матрица дополнений получается из остатков от деления единицы с нулями на образующий многочлен Р(Х), выраженный в двоичном эквиваленте. Число остатков равно числу информационных символов.

Как следует из результатов деления единицы с нулями на Р(Х)=Х+1→11, все остатки оказываются равными единице. Поэтому образующая матрица имеет вид

 

 

Единичная Матрица

транспо    дополнений

нирован

ная матрица

Четыре кодовые комбинации, из которых состоит образующая матрица, являются первыми кодовыми комбинациями циклического кода. Пятая комбинация нулевая, а так как в четырехразрядном непомехозащищенном коде всего N=2⁴ =16 комбинаций, то остальные 11 ненулевых комбинаций находят суммированием по модулю 2 всевозможных комбинаций строк образующей матрицы:

 

5. 000009. 13.

6. 10. 14.

7. 11. 15.

8. 12. 16.

 

Сгруппируем полученные комбинации следующим образом:

1.	00011	2.	00101	12.	01111
6.	00110	7.	01010	16.	11110
9.	01100	10.	10100	13.	11101
11.	11000	3.	01001	14.	11011
4.	10001	8.	10010	15.	10111

 

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

Заметим, что циклический сдвиг является результатом умножения кодовой комбинации на X. Действительно, вторую комбинацию можно записать как 00101→ Х² + 1, седьмую — как (Х² + 1)Х = X³ + X→01010 и т. п. Если при умножении на X степень становится равной X^m+l, то полученный результат нужно разделить на Х+1. Например, если комбинацию 10101→ Х⁴+ +Х² + 1 умножить на X, то получим Х⁵ + Х³ + X. Деля полученное выражение на Х⁵ + 1, найдем остаток Х³ + Х + 1 → 01011. Многочлен 01011 и является результатом циклического сдвига на один разряд влево многочлена 10101.

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

Циклические коды с d = З. Эти коды могут обнаруживать одиночные и двойные ошибки или обнаруживать и исправлять одиночные ошибки.

1. Выбор числа контрольных символов. Есть два способа выбора числа m. При первом способе исходят из того, что число контрольных символов m= = n — k зависит от числа информационных символов, а значит, и от длины всей кодовой комбинации. Выбор m производится, как и для кода Хэмминга, с исправлением одиночной ошибки. Условие  может быть записано в виде

(1.3)

 

где Е" — знак округления в сторону большего значения.

При втором способе число контрольных символов определяется по эмпирической формуле

 

m=Е" Iog₂[(k +1) + E" Iog₂ (k + 1)]. (1.4)

 

В основу выбора m в последнем выражении положено значение числа информационных разрядов. Это удобно, так как первое, что известно в начале кодирования, — именно число разрядов информационных символов. Уравнение (1.4) дает тот же результат, что и (1.3).

Из (1.3) вытекает, что наиболее экономичными являются коды, для которых log₂(n +1) выражается целым числом, то есть когда длина кодовой комбинации

 

n = 2^m – 1,(1.5)

 

где m должно быть целым числом. Так, при k=11, n=15 и m=4 без всяких округлений. Но при k=12, n=17, так как m = 5 выбрано с округлением в сторону большего значения, что увеличивает избыточность кода: в первом случае И=4/15=0,266, во втором И=5/17=0,295.

2. Выбор образующего многочлена Р(Х). Степень образующего многочлена l не может быть меньше числа контрольных символов m. Это значит, что если m=3, то из табл. 1.1 можно выбрать любой образующий многочлен Р(Х) начиная с третьей степени и выше. Для упрощения технической реализации кодирования степень Р(Х) следует выбирать равной числу m, т. е. l=m. Если в таблице имеется ряд многочленов с данной степенью, то из них следует выбрать самый короткий. Однако число ненулевых членов многочлена Р(Х) не должно быть меньше кодового расстояния d.

3. Нахождение элементов дополнительной матрицы. Дополнительную матрицу находят путем деления единицы с нулями на выбранный многочлен R(X) и выписывания всех промежуточных остатков. При этом должны быть соблюдены следующие условия:

а) число остатков должно быть равно числу информационных символов k;

б) для дополнительной матрицы пригодны лишь остатки с весом W, не меньшим числа обнаруживаемых ошибок r, т. е. в данном случае не меньшим 2 (W≥2); так обнаруживается не менее двух ошибок.

Из условий а) и б) определяется количество нулей, приписываемых к единице при делении ее на многочлен Р(Х);

в) так как элементы дополнительной матрицы являются для данной комбинации контрольными символами, то число разрядов дополнительной матрицы равно числу контрольных символов m. Вследствие того, что степень образующего многочлена выбирают равной m, число разрядов дополнительной матрицы равно также степени образующего многочлена. Например, если m=3, а остаток равен 11, то он должен быть записан как 011. Из сказанного вытекает, что разрядность остатка равна степени образующего многочлена.

4. Составление образующей матрицы. Берут транспонированную единичную матрицу и справа приписывают к ней элементы дополнительной матрицы. Пример составления образующей матрицы был дан при рассмотрении циклического кода с обнаружением одиночной ошибки.

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

Пример 1.2. Образовать циклический код, позволяющий обнаруживать двукратные ошибки или исправлять одиночную ошибку из всех комбинаций двоичного кода на все сочетания с числом информационных символов k = 4.

По уравнению (1.4) находим число контрольных символов:

m = Е" Iog₂ [(4 + 1 ) + E"log₂ (4 + 1 )] = Е" Iog₂ (5 + 3)= 3.

Из табл.1.1 выбираем один из образующих многочленов третьей степени. Пусть Р(Х)=Х³ + Х + 1→ 1011. Находим остатки от деления единицы с нулями на Р(Х), которые соответственно равны 011, 110, 111, 101. Остатков должно быть четыре согласно числу информационных символов. Выписывая транспонированную единичную матрицу и приписывая к ней справа матрицу дополнений в виде остатков, получаем образующую матрицу

 

k4		k3	k2	k1	m3	m2	m1
a1	0	0	0	1	0	1	1
a2	0	0	1	0	1	1	0
a3	0	1	0	0	1	1	1
a4	1	0	0	0	1	0	1

 

Так как все члены единичной матрицы являются комбинациями заданного четырехразрядного двоичного кода, то четыре комбинации образующей матрицы представляют собой четыре комбинации требуемого циклического кода. Остальные 11 комбинаций циклического кода (начиная с пятой) могут быть получены путем суммирования по модулю 2 этих четырех комбинаций образующей матрицы так, как было проделано для кода с d=2:

 

5.

6.

7.

8.

9.

10.

11.

12.

13.

14

15

 

Заметим, что комбинация 13 была получена при выводе уравнения (1.2). Если сложить комбинации , то получим циклический код 1011000, в котором контрольными символами являются одни нули. Нулевая комбинация может быть также использована: у нее все символы — нули.

Как следует из табл. 1.1, в качестве образующего можно было бы взять и многочлен Р(Х)=Х³ + Х² + 1→ 1101. В этом случае образующая матрица приняла бы вид

 

a₁0001101

a₂0010111

a₃0100011

a₄1000110

 

Многочлен Р(Х)=Х³ + Х + 1→ 1011 называется обратным или двойственным многочленом многочлена Р(Х)=Х³ + Х² + 1→ 1101. Действительно, сравнивая записанные в двоичной форме выражения обоих многочленов, видим, что нули и единицы в обратном многочлене расположены зеркально относительно основного многочлена, т. е. младший разряд становится старшим. Так, многочлен 1110101 является обратным многочлену 1010111. Двойственный многочлен можно записать в виде

 

Р*(Х)=Х^n-1Р(Х^-1). (1.6)

 

В нашем примере Р*(Х)= Х³(Х^-3 + Х^-2 + 1) = Х³ + Х + 1. Использование двойственных многочленов расширяет возможности построения циклических кодов, так как если Р(Х) — неприводимый многочлен, то и многочлен Р*(Х) также неприводим.

Циклическое кодирование можно осуществлять не только путем составления образующей матрицы из транспонированной матрицы и матрицы дополнения. Тот же результат достигается, если каждый из членов единичной транспонированной матрицы умножить на образующий многочлен. Так, если образующий многочлен Р(Х)=Х³ + Х + 1→ 1011, то умножение транспонированной единичной матрицы на этот многочлен даст

 

0001X1011=0001011

0010Х1011=0010110

0100X1011=0101100

1000X1011=1011000

 

Заметим, что, например, умножение 0100X1011 эквивалентно 1011X X100=101100. Нуль слева (0101100) приписывается для комплектности кода. Результатом умножения явился циклический сдвиг образующего многочлена. Сложением полученных комбинаций можно образовать те же комбинации, что и с помощью двух предыдущих образующих матриц.

Нами был выбран в качестве исходного четырехэлементный двоичный код на все сочетания (k = 4), что позволило образовать 2⁴=16 комбинаций циклического кода. Эти комбинации являются разрешенными, так как после кодирования разрядность кода из-за наличия контрольных символов m = 3 увеличилась до n = 7. Из 128 комбинаций семиразрядного двоичного кода 112 будут неразрешенными. При этом сравнение комбинаций, полученных с помощью образующей матрицы обоими многочленами, показывает, что из 32 комбинаций совпадают только нулевые и составленные из одних единиц.

Таким образом, из двоичного кода на все сочетания (k=4) были образованы два циклических кода с помощью различных образующих многочленов: Р(X)=1011 и P(X)=1101. При этом, несмотря на то что в каждом коде комбинации различны, оба кода вполне правомочны, так как комбинации в каждом из них отличаются друг от друга на кодовое расстояние d=3. В то же время сравнение кодов, составленных образующей матрицей [многочлен Р(Х)=Х³ + Х + 1] и умножением транспонированной матрицы на тот же многочлен, показывает полную идентичность комбинации этих кодов.

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

Первое свойство образующего многочлена заключается в том, что все разрешенные комбинации делятся на него без остатка. Это свойство следует из (1.2), и его можно проверить, разделив любую комбинацию кода на образующий ее многочлен. Таким образом, многочлен Р(Х) как бы позволяет образовать или выбрать из большего числа комбинации, удовлетворяющие только заданному закону построения кода, т. е. разрешенные. Поэтому многочлен Р(Х) и называется образующим.

Второе свойство образующего многочлена таково, что на него делится без остатка не только разрешенная комбинация, имеющая степень n — 1, но и двучлен Хⁿ + 1. В нашем примере n = 7. При делении числа 10000001 на 1011 получается частное 10111 без остатка. Это значит, что образующий многочлен входит в качестве сомножителя в разложение двучлена Хⁿ + 1, который с учетом равенства (1.5) можно записать в виде . Так для двучлена  составляющие сомножители разложения должны быть неприводимыми многочленами, степени которых являются делителями числа m = 3. К числам, на которые m = 3 делится без остатка, относятся 1 и 3. Из табл. 1.1 выпишем все неприводимые многочлены первой и третьей степеней, которые и явятся сомножителями в разложении двучлена Х⁷+1:

Х⁷+1= (Х+1)(Х³ + Х +1)(Х³ + Х² + 1)(1.7)

Один из неприводимых многочленов третьей степени и должен быть выбран для кодирования, если k=4. Заметим, что такое разложение двучлена Хⁿ+1 является одним из методов выбора образующего многочлена.

В рассмотренном примере при k=4 и m=3 n=k+m=7. В литературе циклические коды такого типа называются кодами (7,4). Из примера не следует, что для всех циклических кодов с обнаружением двойной ошибки образующий многочлен будет всегда иметь третью степень. Чем больше длина кода, тем выше степень образующего многочлена, что объясняется увеличением числа контрольных символов. Так, при k=26 согласно уравнению (1.4) m = 5. Это значит, что степень образующего многочлена должна быть не меньше пятой. Такой код обозначают как код (31,26).

Циклические коды с d=4. Эти коды могут обнаруживать одиночные, двойные и тройные ошибки или обнаруживать двойные и исправлять одиночные ошибки.

1. Выбор числа контрольных символов. Число контрольных символов в этом коде должно быть на единицу больше, чем для кода с d=3:

 

(1.8)

 

Для нахождения  можно воспользоваться уравнением (1.4). Если число контрольных символов определяется, как в коде Хэмминга, то уравнение (1.3) примет вид

 

 (1.9)

 

2. Выбор образующего многочлена. Образующий многочлен : равен произведению двучлена (Х+1) на многочлен

 

(1.10)

 

Это объясняется тем, что двучлен (Х+1) позволяет обнаружить все одиночные и тройные ошибки, а многочлен Р(Х) — двойные ошибки. Так, для кода (7,3), обнаруживающего все трехкратные ошибки, можно было бы выбрать .

В общем случае степень l многочлена  равна числу m. Дальнейшая процедура кодирования остается такой же, как и при образовании кода с обнаружением двойной ошибки.

Пример 1.3. Требуется закодировать сообщение 10101010101010 циклическим кодом с d = 4:

 

G(X)= Х¹³ + Х¹¹ + Х⁹ + Х⁷ + Х⁵ + Х³+ Х →10101010101010.

 

Определяем число контрольных символов по уравнению (1.4):

 

 

Из уравнения (1.8) следует, что . Выбираем из табл. 1.1 образующий многочлен для d=3. Пусть . Тогда

 

 

Так как необходимо закодировать только одно сообщение G(X), а не весь ансамбль двоичных кодов с k=14, то будем придерживаться процедуры кодирования, выполняемой по уравнению (1.2). Выбираем одночлен  . Тогда

 

 

Разделив полученное выражение на , находим остаток:

 

 

Следовательно, передаваемая закодированная комбинация будет иметь вид F(X) = (Х¹⁹ + Х¹⁷ + Х¹⁵ + Х¹³ + Х¹¹ + Х⁹ + Х⁷) + (Х⁴ + Х³ + Х² + X + 1) .

 

10101010101010       011111

 

Информационные    Контрольные

символы             символы