ций кода;, в представленных примерах одна группа состоит из 6 комбинаций. Биты четности определяются не только для отдельных комбинаций в соответствующих строчках, но и для отдельных столбцов, в результате чего возникает дополнительная (в табл. 3.7 седьмая) комбинация, задающая четность столбца. Этя комбинация дополняется соответствующим битом четности.

При передаче всей группы комбинаций и их записи в памяти проверяется четность столбцов. Если она в порядке, то предполагается и правильная передача всей группы комбинаций. Если она неправильна, то определяется новая четность столбцов всех семи комбинаций. Каждая единица при этом означает ошибку в соответствующем столбце. Неправильная комбинация, обнаруженная проверкой четности соответствующей строки, исправля- -ется тем, что к ней прибавляется по модулю 2 новая четность столбцов. Преимуществом перекрестной четности является экономия времени, так как одновременно проверяется большое количество комбинаций. Программа исправления имеет 20-30 команд.

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

а) ДЛЯ данной комбинации, в которой п двоичных цифр, определяется число контрольных бит г из соотношения

2>п+1; (3.5)

б) отдельные позиции результирующей комбинации кода нумеруются слева направо так, что контрольным битам соответствуют позиции Pi(i=\, 2, 4, 8 ...), а остальные места занимает передаваемая информация Хг (/=3, 5, 6, 7, 10, И ...);

в) контрольные биты будут иметь значение 1 или О такое, чтобы в следующих уравнениях было выполнено требование четности, при которой сумма всех бит по модулю 2 каждого уравнения была равна 0:

Со = Pi©X3©X,+,©X8©Xu©Xi3©Xi,e . . .= 0

Q = P2©3©e©7®10®ll®"U®15© ... =0

С2 = Р4©адХв©х,©л:12©Х1з©Хи©Х15© . . . =о

C3=Pg©Xe©Xio©Xu©Xi2©Xi3eXi4©Xi5© . . .=0 (3.6) и т. д.

При передаче каждой комбинации кода проверяются ур-ния (3.6). Если сумма Ci = 0, то передача правильная, а если, {=1, то в переданной комбинации есть ошибка. Далее определяется двоичное число

N= Cr-i 2- + . . . + С,2 + Ci2i + Со2«. (3.7)

Если имеет место ошибка, то число определяет ее место в переданной информации.

Рассмотрим, например, десятичные цифры в коде 8421. Так как «=4, то число проверок четности должно быть согласно (3.5) /=3 и для каждого десятичного числа справедлива комбинация Р\Р2ХзРХьУъ1. Для каждой десятичной цифры определяются значения бит четности Р\, Р2, Ръ из урнния (3.6). Например, для (9) 1о=;(1001)2=-?Гз-?5б7 имеем:

1=адЗД7=1©0©1 =0,

Р2 = Хз©Хв©Х,= 1фО©1 =0,

Р4 = 6©вФ7 = 0©0©1 = 1.

Таким образом, в коде Хзмминга ,(9)зс=0011001. Точно так же определяются остальные комбинации. На рис. 3.2 имеется пример

определения места ошибки. Зная место ошибки, ее можно легко исправить.

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

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

110101 = \-Х+1.Х+0-Х+1-Х+0-Х+\=Х+Х+Х+\.

Циклический код определяется так называемым образующим многочленом G(X) порядка п-k и использует только такие многочлены, которые делятся на образующий многочлен. Для того чтобы закодировать данную информацию 1(Х) порядка k или меньшего, целесообразно поступать так, чтобы в результирующем многочлене кода коэффициенты высшего порядка представляли символы информации, а коэффициенты низшего порядка - контрольные символы. Последовательность действий такова: X-I(X) делим на многочлен G(X) так, что

X"-* / (X) = G (X) Q (X) + R (X), (3.8)

здесь Q(X) представляет частное от деления, а R(X) - остаток.

Рис. 3.2. Определение места ошибки (В коде Хэммияга: / - регистр синдрома; 2 - схемы проверки на четность; 3 - регистр кода

Так как сумма представлена в арифметике mod2 (в которой сумма тождественна разности), то закодированная информация имеет вид

F{X)X-I{X} + R{X) = Q{X)G{X) (3.9)

и кратна G(X), т. е. является многочленом кода. Так как R(X) имеет степень, меньшую n-k, а Х->1(Х) имеет нулевые коэффициенты при степенях X, меньших п-k, то коэффициенты k высших порядков в закодированной информации F(X) соответствуют коэффициентам передаваемой информации 1(Х). Закодированная информация после передачи делится на многочлен G(X). Если остаток R(X) равен О, то передача произведена правильно, а если не равен О, то при передаче возникла ошибка.

Циклические коды обеспечивают очень эффективное и сравнительно простое обнаружение ошибок:

а) циклический код с произвольным образующим многочленом G(X), имеющим больше одного члена, обнаруживает все одиночные ошибки. Самый простой образующий многочлен, который имеет больше одного члена, это Х+1;

б) циклический код с образующим многочленом G(X)=X+\ обнаруживает не только все одиночные ошибки, но и произвольное нечетное число ошибок;

в) любой циклический код с образующим многочленом порядка п-k обнаруживает любой пакет ошибок длиной sn-k. Причём под пакетом ошибок подразумевается произвольная комбинация ошибок, имеющая s разрядов, включая первую и последнюю ошибки. Ошибки, изображенные в виде многочлена Е(Х) = =Z7+X6-fX3=000000011001000, представляют пакет длиной s=5.

Если s = n-k+l, то код обнаруживает (1-2-<"--*)) 100% пакетов ошибок. Если s=n-k, то код обнаруживает (1-2-("~)) 100% пакетов ошибок.

Для того чтобы было возможно исправление ошибок, каждой обнаруживаемой комбинации ошибок должен соответствовать свой остаток R(X) после деления закодированной информации F(X) на многочлен G(X). В этом случае ошибки можно исправить, пользуясь таблицами остатков R(X) и соответствующих комбинаций ошибок. Переданную с ошибками закодированную информацию можно выразить соотношением H(X)=F(X)+E(X). После деления Н(Х) на многочлен G(X) появляется определенный остаток R(X), которому в таблице остатков соответствует Е(Х). Исправление производится сложением Н(Х) +Е(Х) в арифметике mod2.