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

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

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

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

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

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

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

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

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

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

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

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

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

Вес  2221 20 22 … 222120

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

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

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

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

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

rАл.ц  rлА+ aks 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, aks= 0 определяем контрольный код сдвинутого числа:

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

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

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

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

Апр=(А–q1)/2; rпрA=(rA–aks)/2.

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

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

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

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

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

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

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

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

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

А = 1,аn-1an-2…a2a1; Апр.м= 1,1аn-1…a3a2,

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

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

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

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

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

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

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

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

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

На основании формулы (4.9) при а1= 1, аk1= 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 .

Наши рекомендации