Числовой контроль по модулю

Числовой контроль по модулю относится к аппаратурным методам контроля.

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

Любое целое число можно представить в виде

A = q×a + r_a ,

где А, q, a и r_a - целые числа; q - модуль; a = éА/qù - наибольшая целая часть частного; r_a - остаток (вычет) от деления числа А на модуль q.

Остаток r_a для различных чисел может принимать значения r_a = 0, 1, 2, 3, ... q-1. Таким образом, каждому целому числу А можно поставить в соответствие некоторый остаток r_a, полученный в результате деления этого числа на некоторый модуль q. Это соответствие записывается в виде

А º r_a mod q

и читается так: число А сравнимо с остатком r_a по модулю q.

С каждым остатком по модулю q сравнимо некоторое множество чисел. Все они называются сравнимыми между собой по модулю q и составляют остаточный класс чисел, сравнимых по модулю q. Очевидно, количество остаточных классов для каждого модуля равно q-1. Разбив все кодовые слова на классы, можно параллельно с основной операцией в контролируемом устройстве выполнять в контролирующем устройстве аналогичную операцию над их остатками. Результаты, полученные в этих устройствах, будут также принадлежать к одному классу.

Действительно, сумма чисел сравнима по модулю q с суммой остатков данных чисел по этому же модулю, т.е.

,

а произведение чисел сравнимо по модулю с произведением остатков этих чисел по этому же модулю, т.е.

.

Приведённые соотношения лежат в основе числового контроля по модулю.

Правильность выполнения сложения и вычитания (С = А ± В), контролируется соотношениями

r'_c º (r_a + r_b) mod q , r'_c º (r_a - r_b) mod q .

Контрольное соотношение для операции умножения (С = А×В), имеет вид

r'_c º (r_a×r_b) mod q .

Однако это соотношение справедливо, когда не происходит потери разрядов произведения при их выходе за пределы разрядной сетки. Если эту потерю учесть, то получим

r'_c º [(r_a + r_b) - r_E] mod q ,

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

На рис.16.6 приведена структурная схема контроля выполнения основной операции (сложения, вычитания, умножения).

Рис.16.6. Схема контроля операций сложения,

вычитания, умножения

Рассмотрим последовательность выполнения контрольных операций.

От кодовых слов, представляющих числа А и В, образуются остатки r_a и r_b по выбранному модулю контроля q. Процесс образования остатков носит название свёртки числа, а соответствующий узел называется узлом свёртки. Параллельно с основной операцией (она обозначена *) над словами А и В в контролирующем устройстве выполняется аналогичная операция над остатками r_a и r_b. Затем результат операции С сворачивается и величина r_c сравнивается с предполагаемым остатком r'_c, полученным в контрольном устройстве. Совпадение r_c и r'_c свидетельствует о правильности выполнения операции.

Числовой контроль по модулю обнаруживает не все возможные ошибки. Ошибка обнаружена не будет, если она такова, что правильный и ошибочный результаты будут принадлежать к одному и тому же остаточному классу чисел, сравнимых по модулю q.

Из самого принципа контроля следует, что его наиболее целесообразно применять в устройствах, перерабатывающих цифровую информацию. Числовой контроль по модулю хорошо приспособлен к проверке правильности выполнения арифметических операций (сложение, вычитание, умножение), а с использованием искусственных приёмов он может применяться для контроля и других операций. С его помощью можно также контролировать правильность хранения и пересылки информации [14].

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

Пример 16.1. Для заданных чисел А = 82 и В = 49 определить контрольные коды самих чисел, их суммы, разности и произведения, если модуль q = 5. Произвести контроль выполнения вышеназванных операций.

Решение. Контрольные коды чисел:

r_a = 82 - = 2 ; r_b = 49 - = 4 .

Аналогично находим контрольные коды для суммы, разности и произведения:

А + В = 131 , r_{a+ b} = 131 - × 5 = 1 .

А - В = 33 , r_{a - b} = 33 - × 5 = 3 .

А×В = 4018 , r_{a× b} = 4018 - × 5 = 3 .

Проведём аналогичные операции (сложение, вычитание, умножение) по модулю над остатками исходных чисел:

r'_{a+ b} = (r_a + r_b) mod q = (2 + 4) mod 5 = 1 .

r'_{a - b} = (r_a - r_b) mod q = (2 - 4) mod 5 = 3 .

r'_{a× b} = (r_a×r_b) mod q = (2×4) mod 5 = 3 .

Контрольные коды совпадают, что свидетельствует о правильности выполнения операций.

Ответ: r_a = 2, r_b = 4, r_{a+ b} = r'_{a + b} = 1, r_{a - b} = r'_{a - b} = 3, r_{a× b} = r'_{a× b} = 3.

Для контроля операции деления (Z = A/B) используются соотношения

Z = ; A = B×Z + W ,

где А - делимое; В - делитель; Z - частное; W - остаток от деления А на В, откуда следует контрольное соотношение

r'_a º [(r_b× r_Z) + r_W] mod q .

Следовательно, контроль операции деления состоит в следующем:

получить от частного Z и остатка W вычеты r_Z и r_W;

произвести умножение r_b и r_Z по модулю q;

сложить полученное произведение по модулю q с r_W;

сравнить полученную сумму r'_a с контрольной характеристикой делимого r_a.

Структурная схема контроля операции деления представлена на рис.16.7.

Рис.16.7. Структурная схема контроля операции деления

Пример 16.2. Для заданных чисел А = 188 и В = 11 определить контрольные коды самих чисел, их частного и остатка от деления, если модуль q = 3. Произвести контроль операции деления.

Решение. Контрольные коды заданных чисел:

r_a = 188 - = 2 ; r_b = 11 - = 2 .

Аналогично находим контрольные коды их частного и остатка от деления:

Z = = 17 , r_Z = 17 - = 2 ;

W = 188 - ×11 = 1 , r_W = 1 - = 1 ;

Произведём проверку правильности выполнения операции деления:

r'_a = [(r_b× r_Z) + r_W] mod q = [(2×2) + 1] mod 3 = 2 .

Контрольные коды r_a и r'_a совпадают, что свидетельствует о правильности выполнения операции.

Ответ: r_a = r'_a = 2, r_b = 2, r_Z = 2, r_W = 1.

Из рис. 16.6 и 16.7 видно, что в состав контролирующего устройства должны входить специфические узлы, предназначенные для получения вычетов и выполнения операций над ними.

Узлы свёртки, сумматоры и умножители по модулю. Узлы свёpтки предназначены для получения остатка от деления числа на модуль контроля q. Эта операция выполняется суммированием цифр разрядов числа по модулю q.

Представим двоичное число А=a_n a_n-1 ... a₁ a₀ в виде

А=a_n×2ⁿ a_n-1×2^n-1 ... a₁×2¹ a₀×2⁰ .

Разделив А на q, получим

.

Так как для получения остатка все операции в этом выражении выполняются по модулю q, то сомножители 2ⁱ/q можно заменить соответствующими остатками r_i, которые называются весовыми коэффициентами. Тогда остаток r_а можно вычислить по формуле

r_а = (a_n r_n + a_n-1 r_n-1 + ... + a₁ r₁ + a₀ r₀) mod q .

Следовательно, процесс получения остатка числа по модулю q сводится к суммированию по модулю q содержимого всех разрядов числа с учётом их весовых коэффициентов.

Значения весовых коэффициентов r_i легко определяются делением 2ⁱ/q и представлены в табл.16.4.

Анализируя табл.16.4 заметим, что модули q = 2ⁱ (i=1, 2, 3, ...) неприменимы для контроля, поскольку позволяют проконтролировать всего i младших разрядов числа. Кроме того, из табл.16.4 видно, что весовые коэффициенты являются периодической функцией номера разряда. Это позволяет упростить операцию свёртки, так как она разбивается на ряд однотипных действий. Особенно просто свёртка осуществляется при модулях q = 2ⁱ-1 (модули 3, 7, 15, ...), так как значения весовых коэффициентов внутри периода (по группам) совпадают с весами разрядов числа, записанного в двоичной системе счисления. Именно эти модулю и будут рассматриваться в дальнейшем.

Существует много разновидностей узлов свёртки. Рассмотрим наиболее характерные из них.

Последовательная схема свёртки, представленная на рис.16.8, содержит один одноразрядный сумматор, два сдвигающих регистра: RgA - для хранения свёртываемого числа А, Rgr_a – для хранения промежуточных и окончательного результатов и элемент задержки (триггер).

Рис.16.8. Последовательная схема свёртки

Операция свёртки здесь производится путём последовательного суммирования разрядов числа А с содержимым Rgr_a. Перенос, возникающий при суммировании старшего разряда Rgr_a, через элемент задержки поступает в младший разряд.

Схема проста и требует малого количества оборудования, которое практически не зависит от величины модуля. Недостаток - большое время сворачивания.

Параллельная (пирамидальная) схема свёртки, построенная на полных одноразрядных сумматорах, имеет многоярусную структуру. В каждом ярусе отдельные сумматоры суммируют цифры сворачиваемого числа с одинаковым весом. На рис.16.9 представлена параллельная схема свёртки 12-разрядного числа по модулю 7. Веса соответствующих разрядов обозначены на рисунке цифрами. Перенос, получаемый при суммировании цифр с весом 4, поступает на вход сумматора следующего яруса, суммирующего цифры с весом 1. Верхний ярус сумматора заканчивается трёхразрядным сумматором с цепью циклического переноса. Здесь формируется окончательное значение остатка.

Преимуществом схемы является однотипность её элементов и малое время выполнения операции сворачивания. Недостаток - большое количество оборудования.

Сумматор по модулю q = 2^m-1 строится на одноразрядных сумматорах как обычный m-разрядный сумматор, содержащий цепь циклического переноса из старшего разряда в младший. На рис.16.10 показана схема сумматора по модулю 3. Здесь же обозначены веса цифр слагаемых и суммы. Особенностью таких сумматоров является двузначность нулевого остатка. Нулевой остаток выражается как 00...0 и как 11...1. Действительно, нулевой остаток всегда сравним с самим модулем, т.е.

0 º q mod q .

Этот факт можно использовать для повышения эффективности контроля. Если в качестве нулевого остатка всегда выбирать q, то наличие нуля в контрольных разрядах будет свидетельствовать о возникновении ошибки.

Рис.16.9. Пирамидальная схема свёртки по модулю 7

Умножители по модулю служат для получения произведения остатков по модулю. Умножение вычетов можно выполнить с помощью сумматора путём многократного сложения сдвинутых сомножителей. Однако в этом случае умножение займёт много времени. Поскольку количество разрядов в перемножаемых вычетах невелико (2, 3, 4), то целесообразно использовать матричные или табличные умножители, обеспечивающие при малом количестве оборудования малое время выполнения операции.

Рис.16.10. Схема сумматора по модулю 3

Числовой контроль по модулю позволяет контролировать не только выполнение арифметических, но и логических операций, таких, как поразрядное логическое сложение, поразрядное логическое умножение, поразрядное сложение по модулю 2, операции сдвига и инвертирования [14, 22].

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

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