Контроль логических операций
К логическим операциям относятся операции сдвига, логического сложения и умножения. Несмотря на кажущуюся простоту этих операций, осуществление контроля сталкивается с рядом трудностей, объясняемых тем, что логические операции являются поразрядными операциями.
Операции сдвига. Пусть задано число А = а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-разрядного числа старшая единица выйдет за пределы разрядной сетки, то это эквивалентно вычитанию ann+1единиц из контрольного кода сдвинутого числа [n+1 – вес (n + 1)-го разряда].
Если при сдвиге контрольного кода выходит за пределы разрядной сетки разряд аks= 1, то это эквивалентно уменьшению контрольного кода на 2s. Такую потерю надо восстановить прибавлением к контрольному коду единицы. В общем случае выражение (4.6) принимает вид
rАл (rлА+ ann+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 .