36.Методы построения циклического кода.

6.4.1. Методом умножения

Информационный многочлен a_i(x) умножается на образующий многочлен g(x), то есть .

Достоинство метода – простота реализации при кодировании.

Недостаток – получаемый код – неразделимый, то есть заранее нельзя указать, где расположены информационные и проверочные символы. Поэтому при декодировании после исправления ошибок приходится делить на g(x) дважды, чтобы получить информационный многочлен.

Пусть имеем код (7; 4), то есть код исправляющий одиночные ошибки. Пусть g(x) = x³ Е x Е 1. Необходимо передать a_i(x) = 1011.

Для получения Р.К.К. – ƒ_i(x) умножим и получим:

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

На приемной стороне, чтобы судить есть ошибка или нет, необходимо принятую кодовую комбинацию (К.К.) поделить на g(x). Если ошибок нет, то остаток от деления r(x) должен быть равен нулю. Делим:

Получили остаток, отличный от нуля. По нему мы должны определить, в каком разряде имеет место ошибка. Для этого необходимо определить, какой остаток r_i(x) даст единичная ошибка в i-том разряде.

До ошибки в четвертом разряде остаток соответствует самой ошибке, а начиная с ошибки в 4-ом разряде происходит деление. В примере остаток , то есть ошибка в пятом разряде. Исправим ошибку:

Но, получив ƒ_i(x), мы не получили a_i(x), то есть снова приходится делить ƒ_i(x) на g(x), то есть

6.4.2. Методом деления

Чтобы получить разделимый код поступают следующим образом: a_i(x) умножают на x^m, что эквивалентно дописыванию к a_i(x) справа m нулей. Полученный многочлен делится на g(x). В результате получается частное от деления g(x) и остаток r(x).

Разрешенная кодовая комбинация ƒ_i(x) получается путем сложения и r(x), то есть

.

Степень многочлена g(x) – m, а степень остатка – (m – 1). Поэтому сложение эквивалентно приписыванию остатка r(x) к a_i(x), так как m разрядов в – нулевые. В то же время ƒ_i(x) делится на g(x) без остатка, так как

Данная методика используется при k > m.

Рассмотрим тот же пример:

a_i(x) = 1011; g(x) = 1011.

.

Так получилось потому, что a_i(x) совпало с g(x).

Если в линии связи произошла ошибка в пятом разряде , то будем иметь

.

Поделим на g(x) и получим остаток r(x):

Исправим принятую К.К.:

И сразу получаем a_i(x) как первые k символов, то есть 1011.

6.4.3. По методу группового кода

Ц.К. является разновидностью группового кода (Г.К.), а в Г.К. проверочные символы определяются как комбинация информационных. Для их определения можно воспользоваться следующим рекуррентным соотношением:

,

где

,

а n = 2^m – 1.

Зная значения информационных разрядов a₀ (старший разряд); a₁; a₂;... a_k–1 можно получить значения проверочных разрядов a_k; a_k+1;... a_n–1. Получается код, полностью совпадающий с кодом, полученным делением.

Метод применяется при m > k и k = n – m, если n = 2^m – 1.

Рассмотрим пример.

Циклический код, исправляющий одиночные ошибки (7; 4); g(x) = 1101.

Найдем Р.К.К. для a_i(x) = 0110.

1. Найдем функцию h(x).

Для этого поделим (xⁿ Е 1) на g(x), то есть (x⁷ Е 1) / g(x):

2. Определим проверочные символы Р.К.К., то есть a₄; a₅; a₆.

Используя формулу

,

найдем:

,

где (i = 0);

,

где (i = 1);

,

где (i = 2).

В итоге имеем Р.К.К.: 0110100.

По методу деления мы имеем ту же кодовую комбинацию: делим на g(x) и получаем r(x) = 100.

тогда Р.К.К. равна 0110100.