Передача информации по каналу с решающей обратной связью (стр. 5 из 11)
(1.3)где Е" — знак округления в сторону большего значения.
При втором способе число контрольных символов определяется по эмпирической формуле
m=Е" Iog2[(k +1) + E" Iog2 (k + 1)]. (1.4)
В основу выбора m в последнем выражении положено значение числа информационных разрядов. Это удобно, так как первое, что известно в начале кодирования, — именно число разрядов информационных символов. Уравнение (1.4) дает тот же результат, что и (1.3).
Из (1.3) вытекает, что наиболее экономичными являются коды, для которых log2(n +1) выражается целым числом, то есть когда длина кодовой комбинации
n = 2m– 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 = Е" Iog2 [(4 + 1 ) + E"log2 (4 + 1 )] = Е" Iog2 (5 + 3)= 3.
Из табл.1.1 выбираем один из образующих многочленов третьей степени. Пусть Р(Х)=Х3 + Х + 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, в качестве образующего можно было бы взять и многочлен Р(Х)=Х3 + Х2 + 1→ 1101. В этом случае образующая матрица приняла бы вид
a10001101
a20010111
a30100011
a41000110
Многочлен Р(Х)=Х3 + Х + 1→ 1011 называется обратным или двойственным многочленом многочлена Р(Х)=Х3 + Х2 + 1→ 1101. Действительно, сравнивая записанные в двоичной форме выражения обоих многочленов, видим, что нули и единицы в обратном многочлене расположены зеркально относительно основного многочлена, т. е. младший разряд становится старшим. Так, многочлен 1110101 является обратным многочлену 1010111. Двойственный многочлен можно записать в виде
Р*(Х)=Хn-1Р(Х-1). (1.6)
В нашем примере Р*(Х)= Х3(Х-3 + Х-2 + 1) = Х3 + Х + 1. Использование двойственных многочленов расширяет возможности построения циклических кодов, так как если Р(Х) — неприводимый многочлен, то и многочлен Р*(Х) также неприводим.
Циклическое кодирование можно осуществлять не только путем составления образующей матрицы из транспонированной матрицы и матрицы дополнения. Тот же результат достигается, если каждый из членов единичной транспонированной матрицы умножить на образующий многочлен. Так, если образующий многочлен Р(Х)=Х3 + Х + 1→ 1011, то умножение транспонированной единичной матрицы на этот многочлен даст
0001X1011=0001011
0010Х1011=0010110
0100X1011=0101100
1000X1011=1011000
Заметим, что, например, умножение 0100X1011 эквивалентно 1011X X100=101100. Нуль слева (0101100) приписывается для комплектности кода. Результатом умножения явился циклический сдвиг образующего многочлена. Сложением полученных комбинаций можно образовать те же комбинации, что и с помощью двух предыдущих образующих матриц.
Нами был выбран в качестве исходного четырехэлементный двоичный код на все сочетания (k = 4), что позволило образовать 24=16 комбинаций циклического кода. Эти комбинации являются разрешенными, так как после кодирования разрядность кода из-за наличия контрольных символов m = 3 увеличилась до n= 7. Из 128 комбинаций семиразрядного двоичного кода 112 будут неразрешенными. При этом сравнение комбинаций, полученных с помощью образующей матрицы обоими многочленами, показывает, что из 32 комбинаций совпадают только нулевые и составленные из одних единиц.
Таким образом, из двоичного кода на все сочетания (k=4) были образованы два циклических кода с помощью различных образующих многочленов: Р(X)=1011 и P(X)=1101. При этом, несмотря на то что в каждом коде комбинации различны, оба кода вполне правомочны, так как комбинации в каждом из них отличаются друг от друга на кодовое расстояние d=3. В то же время сравнение кодов, составленных образующей матрицей [многочлен Р(Х)=Х3 + Х + 1] и умножением транспонированной матрицы на тот же многочлен, показывает полную идентичность комбинации этих кодов.
Теперь, когда ясна роль образующего многочлена при составлении циклических кодов, вырисовываются также следующие его свойства, которые могут помочь при изучении более сложных циклических кодов.
Первое свойство образующего многочлена заключается в том, что все разрешенные комбинации делятся на него без остатка. Это свойство следует из (1.2), и его можно проверить, разделив любую комбинацию кода на образующий ее многочлен. Таким образом, многочлен Р(Х) как бы позволяет образовать или выбрать из большего числа комбинации, удовлетворяющие только заданному закону построения кода, т. е. разрешенные. Поэтому многочлен Р(Х) и называется образующим.
Второе свойство образующего многочлена таково, что на него делится без остатка не только разрешенная комбинация, имеющая степень n — 1, но и двучлен Хn + 1. В нашем примере n = 7. При делении числа 10000001 на 1011 получается частное 10111 без остатка. Это значит, что образующий многочлен входит в качестве сомножителя в разложение двучлена Хn + 1, который с учетом равенства (1.5) можно записать в виде
. Так для двучлена 
составляющие сомножители разложения должны быть неприводимыми многочленами, степени которых являются делителями числа m= 3. К числам, на которые m= 3 делится без остатка, относятся 1 и 3. Из табл. 1.1 выпишем все неприводимые многочлены первой и третьей степеней, которые и явятся сомножителями в разложении двучлена Х7+1: