Таблица 12.2. Местоположение ошибки и вид синдрома

Таким образом, зная вид синдрома, можно определить место, где произошла ошибка, и исправить принятый элемент на противоположный.

Пример 12.4. Передавалась кодовая комбинация 1000111. Принята кодовая комбинация 0000111. Синдром имеет вид 111. В соответствии с табл. 12.2 исказился первый элемент (ai). Изменим первый элемент на противоположный:

0000111 1000000. 1000111

Полученная в результате исправления ошибки кодовая комбинация совпадает с переданной.

Рассмотренный код (7,4) гарантированно обнаруживает двухкратные ошибки, а исправляет только однократные ошибки.

Циклические коды. В теории циклических кодов кодовые комбинации обычно представляются в виде полинома. Так, л-элементная кодовая комбинация записывается в виде

+... + а,х+ао,

где а, = {0,1}, причем а, = О соответствуют нулевым элементам комбинации, а а, = 1 - ненулевым. Например, комбинациям 1101 и 1010 соответствуют многочлены Д (х) = + +1 и 2 (х) = х + х.

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

Д (x)-(-/\2(x) = (x-(-x+l) + (x-(-x)= x + x+l,

поскольку X® + X® = х (1 ©1) = О.

Рассмотрим операцию деления на следуюидем примере:

x + x + xx + l х + х+1

х + х + х х + х+1

х + х + х

х + х + х

х + х+1

х + х+1

Деление выполняется, как обычно, только вычитание заменяется суммированием по модулю два.

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

Найдем алгоритмы построения циклического кода, удовлетворяющего перечисленным выше условиям. Задан полином Р(х) - ar-ix + + а-гх* + ... + 1, определяющий корректирующую способность кода, и задан исходный простой код, который требуется преобразовать в корректирующий циклический.

Обозначим многочлен, соответствующий комбинации простого кода, Q(x). Возьмем произведение Q(x)/ и разделим его на Р(х). В результате получим многочлен G(x) и остаток R(;/P(x):

= G(x)-b. (12.10)

Р(х) Р(х)

Умножим левую и правую части на Р(х), тогда (12.10) перепишется в виде

Q(x)x = G(x)P(x)+R(x). (12.11)

Перепишем равенство (12.11) в виде

G(x)P(x) = Q(x)x + R(x). (12.12)

Левая часть (12.12) делится без остатка на Р(х), значит, без остатка делится и правая часть. Из (12.12) вытекают два способа формирования комбинаций циклического кода: путем умножения многочлена G(x) на Р(х) и путем деления Q(x)/ на Р(х) и приписывания к Q(x)/ остатка от деления Р(х).

Пример 12.5. Задан полином G(x) = x-(-x, соответствующий комбинации простого кода. Сформировать комбинацию циклического кода (7,4) с производящим полиномом Р(х) = х+х+1. Можно получить комбинацию циклического кода в виде G(x)P(x) = = (х + х)( х + х +1) = х + х + х * + X. Однако в полученной комбинации нельзя отделить информационные элементы от проверочных, и код получается неразделимым.

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

R(x)=1

3) (X® + х +1) - комбинация циклического кода, полученная методом деления на производяидий полином. Она может быть переписана в виде 1010001. Первые четыре элемента - информационные, последние три - проверочные, т.е. полученный код - разделимый.

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

Циклические коды достаточно просты в реализации, обладают высокой корректируюидей способностью (способностью исправлять и обнаруживать ошибки) и поэтому рекомендованы МСЭ-Т для применения в аппаратуре ПД. Согласно рекомендации V.41 в системах ПД с ОС рекомендуется применять код с производящим полиномом Р(х) = х+х2х+1.

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

Po:=i-(i-Poj.

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

Ро:= t Oo.(i-Poj .

1) G(x)x=(x + x)x = x + x*; 2)