Проверочная таблица принятой кодовой комбинации примера 4.2
Результат суммирования по модулю 2 строк этой таблицы приведен в правом столбце: первая строка даёт нулевой результат, вторая и третья строки дают единичный результат. Такой результат свидетельствует о наличии искажения.
Для исправления ошибки результат суммирования читается по вертикали снизу вверх. Это даёт двоичное число 110, ему соответствует десятичное число 6. Полученный результат означает, что искажён шестой разряд принятой кодовой комбинации, считая слева направо. Искажён разряд k2. Поэтому принятый символ этого разряда, равный 1, заменяется на символ 0, получена исправленная (неискажённая) кодовая комбинация 1010101. Отбрасываются контрольные символы первой, второй и четвёртой позиций полной кодовой комбинации, неискажённая информационная комбинация имеет вид 1101 (см. пример 4.1).
21. Коды с обнаружением и исправлением ошибок. Циклический код: математические основы. Циклические коды
Эти коды широко применяются в аппаратуре передачи данных и системах телемеханики благодаря высокой эффективности [9]. Простота аппаратной реализации на регистрах сдвига и ячейках сумматора по модулю два в своё время обеспечила им широкое применение, а сравнительно небольшая избыточность делает их эффективными в настоящее время.
Кодовая комбинация имеет информационные и контрольные разряды, последние помещаются в конце комбинации, т.е. коды являются систематическими, равномерными, обозначаются (n, k), где n – полное число разрядов, k – число информационных разрядов. Информационной частью служит натуральный двоичный код.
Математические основы циклических кодов.
Кодовая комбинация представляется в виде многочлена (полинома) с фиктивной переменной x.
G(x) = an-1xn-1 + an-2xn-2 + ... + a1x + a0x0,
где коэффициенты аi, i=0, 1, 2, … n-1 принимает значения 0 или 1.
Если аi = 0, то этот член опускается.
Многочлен G(x) легко переводится в двоичный код. Например,
G(x) = x7 + x5 + x3 + x2 + 1→10101101.
Если многочлен G(x) имеет старшую степень 7, то он называется многочленом 7-й степени.
Над многочленами можно выполнять математические действия по определенным правилам.
Сложение и вычитание равносильны и выполняются по mod 2.
Умножение многочлена на x повышает степень каждого слагаемого многочлена на 1, умножение на хn повышает степень каждого слагаемого на n. Это соответствует передвижению кодовых комбинаций на одну или «n» позиций в сторону старшего разряда.
Например, (х3+х+1)х3=х6+х4+х3 → 1011000.
В двоичном коде произведение получается из умножаемого двоичного числа приписыванием к нему справа количества нулей, равного величине степени «n».
Умножение многочлена на многочлен выполняется по правилам алгебры, при этом операция сложения выполняется по mod 2.
Деление многочлена на многочлен выполняется по правилам алгебры, при этом операция вычитания равносильна сложению по mod 2. Деление производится до тех пор, пока степень остатка не станет меньше степени делителя (число разрядов остатка меньше числа разрядов делителя).
Среди множества многочленов существуют неприводимые, которые не могут быть представлены в виде произведения многочленов низших степеней. Они аналогичны простым числам, которые делятся без остатка лишь сами на себя и на 1.
Для построения многочлена F(x) циклического кода производят следующие преобразования и операции:
1. Многочлен G(x) информационной части умножают на xn-k; при этом степень многочлена G(x) повышается на величину «n-k».
2. К произведению (xn-k)*(G(x)) добавляют остаток R(x) от деления xn-k * G(x) на образующий многочлен P(x).
Это вытекает из следующих преобразований:
,
(4.7)
где Q(x) – частное от деления без учета остатка, R(x) – остаток от деления, степень которого меньше степени P(x).
Умножая равенство (4.7) на P(x) получим:
xn-K * G(x)=Q(x) * P(x)+R(x). (4.8)
Здесь Q(x)*P(x)=F(x) – искомый многочлен циклического кода, поэтому
F(x) = xn-K * G(x) + R(x), (4.9)
знак (-) заменен на (+), так как сложение выполняется по mod 2.
Пример 4.3
Найти кодовую комбинацию циклического (7, 4) кода для информационной комбинации 1011 и образующего многочлена P(x)=х3+x2+1.
Циклический (7,4) код имеет полное число разрядов n =7, число информационных разрядов k =4, число контрольных разрядов m =3.
Алгебраический многочлен информационной комбинации имеет следующий вид:
G(x)= х3+x+1 → 1011.
Умножение на xn-k даёт:
G(x) = (х3+x+1)х3 = х6+х4+х3.
Выполняем деление полученного произведения на образующий многочлен:
Таким образом, деление произведения xn-k * G(x) на образующий полином P(x) даёт остаток R(x)= х2, что соответствует двоичному числу 100.
Наконец, многочлен комбинации циклического кода.
F(x)=(х6+х4+х3)+х2.