Контроль логических операций

 

К логическим операциям относятся операции сдвига, логического сложения и умножения. Несмотря на кажущуюся простоту этих операций, осуществление контроля сталкивается с рядом трудностей, объясняемых тем, что логические операции являются поразрядными операциями.

Операции сдвига. Пусть задано число А = аnan -1… a 1 a 0, имеющее контрольный код rA = аk s... аk 1.

Обозначим код числа А, сдвинутый влево, через А л(без циклического переноса) и А л.ц(с циклическим переносом), а код числа, сдвинутый вправо, через А при А пр.ц соответственно. Обозначим контрольный код: А  rА (mod p), А л rА л(mod p); А пр rА пр(mod p); А л.ц r Ал.ц(mod p).

Сдвиг влево двоичного числа эквивалентен умножению на два. Так как при сдвиге числа происходит потеря некоторых его разрядов, можно предполагать, что контрольный код сдвинутого числа изменится на величину :

rА л  r л А +  (mod p), (4.6)

 

где r л А = 2 rА – сдвинутый влево контрольный код.

Величина  зависит от значений аn и аk s, которые при сдвиге выходят за пределы разрядной сетки.

Если при сдвиге n -разрядного числа старшая единица выйдет за пределы разрядной сетки, то это эквивалентно вычитанию an  n +1единиц из контрольного кода сдвинутого числа [ n +1 – вес (n + 1)-го разряда].

Если при сдвиге контрольного кода выходит за пределы разрядной сетки разряд аk s= 1, то это эквивалентно уменьшению контрольного кода на 2s. Такую потерю надо восстановить прибавлением к контрольному коду единицы. В общем случае выражение (4.6) принимает вид

rА л (r л А + an  n +1+ ak s) mod (2s–1), (4.7)

 

Веса разрядов кодовой комбинации, представленной в системе с основанием 2s, назначаются следующим образом:

s =3 аnаn -1 аn -2 аn -3… a 3 a 2 a 1

 

Вес  2221 20 22 … 222120

 

В результате значения поправок  для контроля выполнения левого сдвига по модулю будут:

Значение аn.......... 0 1 0 1

Значение аk s........ 0 0 1 1

Поправка ......... 0 -1 +1 0

 

Значение поправки  можно заменить ее дополнением до модуля. Для выполнения сдвига влево с циклическим переносом из старшего разряда в младший разряд необходимо уменьшить контрольный код на величину an ( n +1-1); так как  n +1=1, этот член равен 0. Следовательно, формула (4.7) примет вид

rА л.ц  r л А + ak s mod (2s-1), (4.8)

 

Пример. Найти контрольные коды для числа А = 1,01011010, сдвигаемого влево, при p =7 (s =3).

Решение. Сначала определяем контрольный код исходного числа путем сложения триад по модулю 7: rА = 101  011  010 = 011(mod7)

Затем сдвигаем влево число А л= 0,10110100 и его контрольный код r л А =110.

На основании выражения (4.7) при an = 1, ak s= 0 определяем контрольный код сдвинутого числа:

rА л=110–1+000= 101(mod 7).

 

Проводится сдвиг с циклическим переносом: A л.ц=0,10110101, для которого контрольный код rА л.ц= 110 + 000 = 110(mod 7).

Ответ: rА л=101, rА л.ц=110.

 

При сдвиге вправо происходит потеря младших разрядов числа и контрольного кода этого числа. Так как сдвиг вправо эквивалентен делению на 2, то

А пр=(А – q 1)/2; r пр A =(rA – ak s)/2.

 

Эти потери надо компенсировать. Значит, контрольный код сдвинутого вправо числа можно найти по формуле

rA пр= r пр A +(mod 2s-1). (4.9)

 

В зависимости от модуля поправка к контрольному коду в случае простого сдвига принимает следующие значения:

 

Значение а 1.……… 0 0 1 1

Значение аk 1........0 1 0 1

Поправка  для:

р =3............ 00 10 01 00

р =7............ 000 100 011 000

 

При модифицированном сдвиге вправо, который выполняется по правилу

А = 1, аn -1 an -2… a 2 a 1; А пр.м= 1,1 аn -1… a 3 a 2,

 

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

Значение а 1.……… 0 0 1 1

Значение аk 1..... …0 1 0 1

Поправка мдля:

р =3............ 10 01 00 10

р =7............ 100 001 000 100

 

Пример. Найти контрольные коды для числа А = 1,01110111101, сдвигаемого вправо, при p =7.

Решение. Сначала определяем контрольный код для исходного числа путем сложения триад по модулю 7: r A= 101  110  111  101  (mod 7). Затем сдвигаем вправо число

А пр=0,10111011110 и его контрольный код r пр А =001.

На основании формулы (4.9) при а 1= 1, аk 1= 0, поправки  = 011 определяем контрольный код:

rA пр  001+011  l00(mod 7).

 

Проводим модифицированный сдвиг числа А пр.м=1,10111011110, для которого контрольный код при  = 000:

rA пр.м 001 + 000  001(mod 7).

Ответ: rA = 010, rA пр= 100, rA пр.м=001.

 

Операция сложения по модулю 2. Операцию сложения по модулю 2 можно выразить через другие арифметические операции, например: А  В = А + В – 2(А  В).

Если применить к этому выражению уже известные приемы, то получим

А  В = А + В +.

 

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

(4.10)

 

где rА + В – контрольный код суммы двух чисел; – инверсия контрольного кода логического произведения двух чисел со сдвигом влево на один разряд.

 

Пример. Найти контрольный код логической суммы чисел А =010000111 и В =101110011 по модулю 7.

Решение. Прежде всего по изложенным выше правилам определим контрольные коды для исходных чисел: rA =010, rВ = 000, rA + В =010.

Затем вычислим следующие величины:

А  В = 000000011,; А  В сдв=000000110, r л1=110.

После этого определим инверсное значение = 001.

По формуле (4.10) находим контрольный код:

r = 010+001  011(mod 7).

Ответ: r =011.

 

Операция логического умножения. Операцию логического умножения двух чисел можно выразить через другие арифметические и логические операции:

А  В = 2-1(А + В)–2-1(А  Д).

Умножение на 2-1означает сдвиг кода числа, стоящего в скобках, вправо на один разряд. После перехода к сравнениям контрольный код для логического умножения получается по формуле

 

 

где – контрольный код суммы, сдвинутый вправо на один разряд; – инверсия контрольного кода логической суммы чисел, сдвинутой на разряд вправо.

При выполнении сдвигов необходима коррекция контрольных кодов в соответствии с изложенными выше правилами.

 

Пример. Найти контрольный код логического произведения чисел по модулю 3:

А = 10011001, rA = 00, В = 0,001111, rB = 01.

Решение. Прежде всего найдем сумму чисел и контрольный код:

А + В = 11101000, rA + B =01.

Затем по формуле (4.9) вычислим +Д= 10. Определим

A  B =11010110, r =01, =10, =01.

 

Следовательно, контрольный код логического произведения =10+10=00(mod 3).

Ответ: = 00.