Передача информации по каналу с решающей обратной связью (стр. 4 из 11)
Многочлен в поле двоичных чисел называется неприводимым, если он делится без остатка только на себя или на единицу; что касается многочленов, приведенных в табл. 1.1, то это определение справедливо только для конечного поля двоичных чисел.
В основу циклического кодирования положено использование неприводимого многочлена Р(Х), который применительно к циклическим кодам называется образующим, генераторным или производящим многочленом (полиномом).
1.2.4 Методы построения циклических кодов
В качестве информационных символов 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 многочлен Р(Х3)=Х3+Х+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(Х)=Х3+ +Х2+X+1→1101 с помощью образующего многочлена P(Х)=Х+1→11.
Умножим G(X) на Хm, что эквивалентно добавлению нуля справа, так как m=1, поскольку Р(Х) имеет первую степень: (Х3+Х2+1)X= Х4+Х3+X→11010.
Разделив полученное выражение на Р(Х), найдем, что остаток R(X)=1. Следовательно, кодовый многочлен циклического кода в соответствии с уравнением (1.2) будет иметь вид
F(X)= G(X)Хm+ R(X)= Х4 + Х3 +X + 1→ 11010 + 1 = 11011.
Таким образом, в этом закодированном сообщении 11011 n = 5, k=4 и m=1, то есть информационным символом является комбинация 1101, а контрольным — единица в младшем разряде.
Сообщение, которое было закодировано (1101), является одной из 16 комбинаций четырехразрядного кода. Если требуется передать все эти сообщения в закодированном виде, то каждое из них следует кодировать так же, как и комбинацию 1101. Однако проделывать дополнительные 15 расчетов (в общем случае 2k расчетов) нет необходимости. Это можно сделать проще, путем составления образующей (порождающей) матрицы.
Образующая матрица составляется из единичной транспонированной матрицы и матрицы дополнений.
Число столбцов транспонированной единичной матрицы равно числу информационных символов k. Матрица дополнений получается из остатков от деления единицы с нулями на образующий многочлен Р(Х), выраженный в двоичном эквиваленте. Число остатков равно числу информационных символов.
Как следует из результатов деления единицы с нулями на Р(Х)=Х+1→11, все остатки оказываются равными единице. Поэтому образующая матрица имеет вид
Единичная Матрица
транспо дополнений
нирован
ная матрица
Четыре кодовые комбинации, из которых состоит образующая матрица, являются первыми кодовыми комбинациями циклического кода. Пятая комбинация нулевая, а так как в четырехразрядном непомехозащищенном коде всего N=24 =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→ Х2 + 1, седьмую — как (Х2 + 1)Х = X3 + X→01010 и т. п. Если при умножении на X степень становится равной Xm+l, то полученный результат нужно разделить на Х+1. Например, если комбинацию 10101→ Х4+ +Х2 + 1 умножить на X, то получим Х5 + Х3 + X. Деля полученное выражение на Х5 + 1, найдем остаток Х3 + Х + 1 → 01011. Многочлен 01011 и является результатом циклического сдвига на один разряд влево многочлена 10101.
Рассмотрение полученных комбинаций показывает, что все они имеют четное число единиц. Действительно, контрольные символы оказываются равными единице при нечетном числе единиц в исходной комбинации и нулю при четном числе единиц. Таким образом, циклический код с обнаружением одиночной ошибки является обычным кодом с четным числом единиц.
Циклические коды с d = З. Эти коды могут обнаруживать одиночные и двойные ошибки или обнаруживать и исправлять одиночные ошибки.
1. Выбор числа контрольных символов. Есть два способа выбора числа m. При первом способе исходят из того, что число контрольных символов m= = n — k зависит от числа информационных символов, а значит, и от длины всей кодовой комбинации. Выбор m производится, как и для кода Хэмминга, с исправлением одиночной ошибки. Условие
может быть записано в виде