Выбор модуля для контроля

 

Достоинства числового метода контроля — в справедливости свойств сравнений для контрольных кодов, что облегчает контроль арифметических операций; достоинства цифрового метода в возможности достаточно просто получать контрольные коды без значительных затрат времени. Чтобы сохранить эти достоинства, необходимо выполнение условия r_A = r’_A.

Так как r_а ≡ А(mod р); r'_А ≡ ∑аi(mod p), имеем аiqi ≡ ∑аi(mod p),

Это равенство возможно тогда, когда почленно обе части выражения равны: аiqi ≡ аi(mod p), или qi ≡ l(mod p),

Последнее выражение можно получить, если в сравнении q ≡ 1(mod p) возводить обе части в одну и ту же степень. Следовательно, p = 1(mod р), или

q = mp+1,

где т — целое число.

Из предыдущего следует, что

p = (q-1)/т.

В результате получено, что для сохранения условия r_A = r'_А необходимо наложить ограничения на модуль р.

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

К модулю р предъявляют следующие общие требования:

1)величина модуля р должна быть такой, чтобы возникновение любой арифметической или логической ошибки нарушало сравнимость контроль­ных кодов;

2)образование контрольного кода должно осуществляться по возможности простыми средствами;

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

Ввиду того, что цифровая информацияв ЭВМ должна представляться символами двоичного алфавита, для контроля целесообразно перейти к системам счисления с основанием q=2^S, где s — некоторое целое положительное число (s ≥ 2). Переход от двоичного представления исходной информации к новому представлению с основанием q=2^S осуществляется разбиением информации на группы по S разрядов с последующим суммированием этих групп по модулю р = (2S-1)/т или при т = 1, р = 2S - 1.

В самом деле, если s = 2 , то исходная информацияразбивается на диады, при s = 3 — на триады, при s = 4 — на тетрады и т. д.

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

р = (2^S±1)/т.

Рассмотрим частные случаи образования сверток при наиболее распространенных значениях модуля р.

1. Контроль по модулю 3 (m = 1,s = 2, p = 3). Здесь контролируемая информацияпредставляется символами четверичной системы, и свертки образуются суммированием диад по модулю 3. Так как 22 = 1(mod 3), потребуется двухразрядный двоичный сумматор с цепью циклического переноса из старшего разряда в младший.

2. Контроль по модулю 7 (т = 1, s = 3, р = 7) . Здесь контролируемая информацияразбивается на триады и представляется символами восьмеричной системы. Так как 23 = 1(mod 7), для получения свертки нужно иметь трехразрядный двоичный сумматор с цепью циклического переноса.

3. Контроль по модулю 5 (т = 1, s = 2, р = 5). Из теории чисел известно, что для того, чтобы число, выраженное в системе с основанием q, делилось на число q + 1, необходимо и достаточно, чтобы разность между суммой цифр, стоящих на четных и нечетных местах, или наоборот, делилась на величину q+1 без остатка.

Из этого правила можно сделать следующий вывод: контрольный код по mod(q + 1) определяется по формуле

где b_i, — двоичное изображение цифр в системе с основанием 2S.

Так как, по условию, r_а ≤ р-1, то для получения свертки потребуется трехразрядный двоичный сумматор, работающий по модулю 5.