Корректирующие коды. Код Хэмминга

3. Циклические коды.  

Циклические коды основаны на представлении передаваемых данных в виде полинома и используются в основном при последовательной  передаче данных между ЭВМ и внешними запоминающими устройствами, а также при передаче данных по каналу связи. Контроль передачи данных с помощью циклических (полиномиальных) кодов основан на следующей закономерности: Если информационный полином умножить па некоторый так называемый порождающий полином, получившийся в результате этого кодовый полином передать приемнику информации и выполнить в нем обратное  действие, т.е.  деление полинома принятого сообщения на порождающий полином, то ненулевой остаток будет означать, что произошла ошибка. Нулевой остаток будет означать, что ошибки нет {или она не обнаружена). Для пояснения процедуры формирования циклического кода и его  декодирования выведем следующие обозначения G(x)—информационный полином, соответствующий передаваемой информации длиной т бит. Он имеет степень меньше т—1; Р(х)—порождающий полином степени k, определяющий число  контрольных бит, а также обнаруживающую корректирующую  способность циклического кода; F(x) —кодовый полином, соответствующий передаваемому циклическому коду. Это полином степени m+k, делящийся без  остатка на порождающий полином степени k Образование кодового полинома F(x) путем умножения информационного полинома G(x) на порождающий полином  Р(х) неудобно тем, что получающийся при этом код не будет  систематическим (контрольные биты не будут выделены). Вследствие этого применяется другой способ (формирования кодового полинома, при котором старшие коэффициенты образуют информационные  знаки, а младшие контрольные. Информационный полином G(х) степени т - 1, который необходимо закодировать, умножается на x^k, что соответствует сдвигу на k разрядов влево. Полученный таким образом полином х^k G(х) делится на Р(х) для определения остатка R(х): 

х^k G (х)/Р (х) = Q (х)   +   R (х)/Р (х).          (5)  

Из этого выражения следует

х^k G(x) = Q(x)P(x) +  R(x) F (х) = Q (х) Р(х)  = х^k G {х)   +   R (х)     (6) 

    Полином F(x) делится на Р(х) без остатка и поэтому является кодовым полиномом. 

Остаток r(x) имеет степень меньше k, и х^k G(х) имеет нулевые коэффициенты в k младших членах. Таким образом,  т старших коэффициентов кода F(x) равны коэффициентам информационного полинома G(x) и представляют собой кодируемое сообщение, а младшие k коэффициентов кодового полинома F(x) представляют собой коэффициенты остатка R(x), т.е. контрольные биты. Из вышеприведенного следует, что кодовый полином можно получить путем сдвига информационного полинома, на k бит, деления его на порождающий полином F (x) и записи остатка в младшие k бит кодового полинома. Процедура кодирования, соответствующего этому алгоритму реализуется с помощью сдвигового регистра с обратными связями, соответствующими виду порождающего полинома Р{х). Если полином, полученный при передаче сообщения, содержит ошибки, то он может быть представлен в виде  

H(x) = F(x)  +   E{x).                 (7)  

Это выражение означает, что если полином принятого сообщения H(x) не делится на Р (x), то при передаче информации  произошла ошибка E (х). Выбор порождающего полинома Р(x) зависит от характера ошибок при передаче. Можно записать следующие правила выбора порождающего  полинома для разных ошибок. ошибки в одном бите обнаруживаются, если порождающий полином содержит более одного члена; ошибки в двух битах обнаруживаются, если порождающий полином содержит три члена; ошибки в нечетном числе бит обнаруживаются, если порождающий полином содержит  множитель (х + 1); пакеты ошибок длиной менее к+1 бита обнаруживаются если порождающий полином содержит множитель х+1 и один множитель с тремя членами и более (k+1 — число бит порождающего полинома). Этот же порождающий полином обнаруживает с вероятностью 1 - (1/2)^k-1  пакеты  ошибок  длиной  (k+1)   бит   и с    вероятностью

1 - (1/2)^k пакеты ошибок  длиной более k+1 бит .

Рис. 3. Схема формирования и декодирования циклического кода  

На рис. 3 показана схема сдвигового регистра с обратными связями и схемами сложения по модулю 2, реализующими схему деления на порождающий полином. Важным преимуществом таких схем является возможность их применения для контроля передаваемой информации как при приеме, так и при  генерации контрольных бит при передаче, что позволяет обойтись одной такой схемой в приемной и  передающей аппаратуре. Рассмотрим в качестве примера схему, реализующую деление на  порождающий полином Р(х) ==x⁴+x+1. Предположим, что передаются  данные вида 11010011, которые представляются в виде полинома Как было сказано, циклический код передаваемых данных образуется путем умножения информационного полинома

  G(x) на x⁴: x⁴G(x) = x⁴(x⁷+x⁶+x⁴+x+1),   что эквивалентно сдвигу данных, соответствующих информационному  полиному G (x), на 4 бита в сдвиговом регистре. Как только первая единица (коэффициент при старшем члене полинома) сдвинется до конца регистра, т.е. появится на выходе триггера T4  при очередном сдвиге, будет выполнено вычитание делителя. Проследим за процессом деления x⁴G(x) на Р(х) и образования  остатка:

   Ч⁴G (x) = 110100110000  

   P (x) = 10011 
 

   110100110000   110011

   10011                 11000111 — частное

   10010 

   10011

           11100

          10011

             11110           

             10011

               11010             

               10011

                 1001 — остаток, т. е. R(x). 
 

   В течение первых восьми тактов сдвига на входе а схемы  И₁ имеется разрешение. Данные, соответствующие  информационному полиному, одновременно с передачей  на выход схемы ИЛИ поступают также и в сдвиговый регистр. К началу девятого такта разрешение со входа а снимается, a на вход b схемы И₂ подастся разрешение, в результате чего на выход схемы поступает остаток R(x), накопившийся в сдвиговом регистре. Таким образом, на выходе схемы ИЛИ образуется последовательность бит, соответствующая кодовому полиному F(x) = 110100111001. В том случае, когда описанная схема используется для декодирования принятой информации (обнаружение ошибок),  на ее вход поступает последовательность полинома Н(х). Если после т + k сдвигов сдвиговый регистр находится  в нулевом состоянии, это означает, что передача выполнена без ошибок.

   Циклические (полиномиальные) коды получили широкое распространение благодаря высокой обнаруживающей способности и относительной простоте схем кодирования и декодирования.  

4. Контроль арифметических операций.  

Арифметические операции, как правило, можно представить  в виде последовательности следующих элементарных операций: передача слова и операции преобразования содержимого триггерных регистров - сдвиг, взятие обратного кода и сложение. Операция сдвига информации в регистре представляем собой по существу передачу информации из 1-х разрядом регистра в (i + m)-е или (i—m)-е разряды в зависимости от направления сдвига (т —число разрядов, на которое, про изводится сдвиг). Поэтому для контроля операции сдвига можно использовать те же методы, что и для контроля передачи информации, например контроль четности суммы единиц. Регистр, в котором производится сдвиг, должен иметь дополнительный контрольный разряд, устанавливаемый перед  сдвигом в такое состояние, чтобы сумма единиц регистра  вместе с контрольным разрядом была, например, четной.  Кроме схемы определения общей четности содержимого  регистра необходимы схемы, устанавливающие четность разности между числом единиц, выдвигаемых из регистра, и числом единиц, вдвигаем ых в регистр. Если в освобождающиеся  при сдвиге разряды вдвигается 0, то достаточно иметь схему  определении четности суммы единиц выдвигаемых разрядов.  Одновременно со сдвигом выполняется контрольная операция,  заключающаяся в том, что состояние контрольного разряда меняется  на противоположное при нечётности суммы единиц выдвигаемых  разрядов. Тогда при правильном выполнении сдвига общая четность  суммы единиц в регистре после сдвига не меняется. Операция взятия обратного кода может быть также проконтролирована  путем использования кодов с проверкой четности. Если число  информационных разрядов в слове четно, то число единиц  в слове четно при четном числе нулей и нечетно при нечетном  числе нулей. В этом случае после образования обратного кода  четность числа единиц в слове сохраняется и правильность  выполнения операции можно определить, проверив сохранение  четности или нечетности суммы единиц в слове, включая  контрольный разряд. Если число информационных разрядов в слове нечетно то четному числу единиц в слове соответствует нечетное число нулей, а нечетному числу единиц—четное число нулей.  В этом случае после образования обратного кода четность числа  единиц изменится на обратную и для проверки правильности  выполнения операции необходимо взять обратный код от  содержимого контрольного разряда и проверить сохранение  четности или нечетности суммы единиц в слове с учетом  инвертированного контрольного разряда. Из множества разработанных способов контроля операции сложения  рассмотрим способ, использующий проверку четности. При сложении чисел а и b разряды суммы 5 образуются в соответствии с выражениями  
 

S₁=a₁  +   b₁   +    P₁;

S₂=a₂   +   b₂   +   P₂;                                       (8 )

......................................

  S_n = a_n +  b _n  +   P _n

где S_i, a_i b_i, P_i (i=1, 2, ... n) —соответственно значения разрядов суммы, слагаемых и переноса, поступающего в i-й разряд. Знак   +  означает сложение по модулю 2; n — число разрядов слагаемых и суммы. Сложив все n приведенных выше равенств по модулю 2. Получим 
 

S₁   +    S₂ + ... + S_n = (a₁  +   a₂   +  ...  + a_n)   +   (b₁  +  b₂  +  ...  +  b_n)  + (P₁   +   P₂ + ...  +  Pn).                                                   (9) 
 

четность суммы единиц слова, последнее уравнение можно  переписать в виде четность S = четность а ~ четность  b  +  четность Р.  (10) Таким образом, при правильном образовании суммы четность суммы ее единиц должна совпасть с четностью, определяемой выражением (10).  Однако, как указывалось ранее, контроль по четности не  обнаруживает четного числа ошибок. Сбой в схеме  образования цифры разряда суммы дает одиночную  ошибку, и она будет обнаружена. Если сбой произойдет в  схеме формирования переноса, то он может привести к  распространению ошибки по многим разрядам суммы.  В связи с этим для полноты контроля необходимо проверять  правильность образования переносов Pi. Такой контроль может быть организован с помощью схемы, которая проверяет, что в каждом разряде существует либо перенос в прямом коде, либо инверсия переноса и не  существует одновременно и то, и другое. Другой способ контроля заключается в дублировании схем формирования переносов и сравнении переносов основной  и дублирующей схем. Упрощенная схема контроля сумматора приведена на рис, 4. Оба слагаемых поступают на схемы формирования переносов. Сформированные переносы проверяются на совпадение  с помощью схемы, подобной изображенной на рис. 2. Для переносов и отдельно для суммы формируются контрольные  разряды четности. Затем схема проверки четности проверяет выполнение условия (10). Контроль выполнения арифметических операций (сложения,  вычитания, умножения) можно осуществлять с помощью  контрольных кодов, представляющих собой остатки от деления чисел на некоторый модуль R (контроль по  модулю R). 

Если в качестве контролируемого кода используется остаток  по модулю R, то в качестве, контрольной операции над остатками может быть выбрана та же арифметическая операция, которая производится над числами. Это следует из того, что для сложения, вычитания и умножения действительно  соотношение R(A*B) = R (R(A) * R(B))             (11)  где R(Х) —остаток числа  X по  модулю R; *—знак арифметических  операций сложения, вычитания или умножения.  

Рис. 4. Контроль сложения с использованием проверок по четности  

Контроль арифметических операций по модулю организуется следующим  образом. Каждому числу, участвующему в арифметической операции,  ставится в соответствие контрольный код — остаток по модулю R.  Одновременно с выполнением остаток операции над числами та же  операция производится над их  контрольными кодами, и контрольный код результата основной операции сравнивается с результатом операции над контрольными кодами исходных чисел. При несовпадении фиксируется ошибка. Чем меньше R, тем  меньше разрядность  контрольного кода и проще дополнительная аппаратура. Для двоичных чисел контроль по модулю возможен при R=3, поэтому в ЭВМ часто используют контроль по модулю 3. Покажем, что при контроле по модулю 3 обнаруживаются любые одиночные ошибки. Одиночная ошибка в каком-либо разряде двоичного числа соответствует нзменению  числа на ±2^i. Для обнаружения ошибки необходимо, чтобы контрольные коды чисел а и а ± 2ⁱ не совпадали, т.е.

R(a)<>R(а: ±:2ⁱ) = R(a) ± R(2ⁱ) или R(2^i)<>0. Но 2ⁱ не делится на 3 без остатка, следовательно, требуемое условие выполняется. Кроме одиночных ошибок при контроле по модулю 3 обнаруживается часть двойных ошибок,  а именно те, при которых правильный и ошибочный результаты имеют несовпадающие остатки от деления на 3.  
 
 
 
 

Рис. 5. Структурная схема сумматора с контролем по модулю 3  

На рис. 5 изображена  структурная схема сумматора с контролем по модулю 3 Отметим, что контрольный сумматор значительно проще основного, т. к.  содержит только два двоичных разряда. При реализации контроля важное значение имеет построение схем формирования остатков при  минимальных затратах оборудования. Очевидно, что нахождение  остатка путем прямого деления двоичного числа на 3—путь  неприемлемый, однако кодирование по модулю 3 обладает свойствами,  позволяющими строить достаточно простые комбинационные схемы  формирования остатка по модулю 3. Может быть применен контроль по модулю с большим основанием, чем 3. При этом увеличивается число кратных ошибок, которые могут обнаруживаться системой контроля, однако возрастает сложность кодирующей и декодирующей аппаратуры.