К логическим операциям относятся операции сдвига, логического сложения и умножения. Несмотря на кажущуюся простоту этих операций, осуществление контроля сталкивается с рядом трудностей, объясняемых тем, что логические операции являются поразрядными операциями.
Операции сдвига. Пусть задано число А = а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.
