Устройство для формирования остатка по модулю =2 +1

СОЮЗ СОВЕТСКИСОЦИАЛИСТИЧЕСНРЕСПУБЛИН гггг 4 С 06 Р 11/1 РЕТЕНИ 131БйвЛ 5л(21) 3961665/24-24 (22) 16.08.85 (46) 23.09,87. Бюл (7.1) Львовский пол 35хнический инстиомсомолаи В М Титк тут им. Ленин (72) Н.В.Черк (53) 681.3(08 (56) Авторско М 1084799, клАвторское У 1084798, кл СУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ К АВТОРСКОМУ СВИДЕТЕЛЬОТ кого ксский . . ов.8) свидетельство СССР С 06 Р 11/10, 1982видетельства СССР С 06 Р 11/08, 1982 54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСАТКА ПО МОДУЛЮ ш=2 +157) Изобретение относится к вычисли елькой технике; предназначено дляК ормирования остатка по модулю ш=2 + 1 и может быть использовано для кон роля вычислительных операций суммирования, вычитания, умножения и передачи данных, а также в модулярнойарифметике. Цель изобретения - упрощение устройства и повьппение быстродействия, Устройство содержит одноразрядные сумматоры 1, блоки одноразрядных сумматоров 2, входы 3 устройства, выходы 4 остатка устройства,причем количество блоков сумматоровравно (1+1), где 1=1 ое и, и - разрядность входного числа, количество сумматоров в -м блоке 2, где 1.=1(1-1), равно р Е/2, количество сумматоров в 1 - м блоке 2 - В+1), количество сумматоров в (1+1)-м блоке2 - 1 с. Положительный эффект достигается за счет новых взаимосвязей междублоками сумматоров и новой структуры1 133956Изобретение относится к вычислительной технике, предназначено дляформиррвауния остатка по модулю ш=с=:2 +1 и может быть использовано для:контроля вычислительных операций суммирования, вычитания, умножения ипередачи данных, а также в модулятор. ной арифметике.Цель изобретенйя - упрощение устройства и повышение быстродействия,На чертеже изображено предлагаемое устройство,Устройство содержит одноразрядныесумматоры 1, блоки 2 одноразрядных 15сумматоров, входы 3 устройства, выходы 4 остатка устройства, причем количество блоков сумматоров равно (1+1),где 1=1 ояпу и разрядность Входного числа, количество сумматоров в:.-м блоке 2, где х=1(1-1), равно р-к/2 количество сумматоров вТ-м блоке 2 - (к+1), количество сум -маторов в (1+1)-м блоке 2Устройство работает следующим образом.В основу принципа действия устройства заложен алгоритм вычисления ос(4) Отсюда(А) 2 +1=сА -А+А - +А 2 +1 (5)Так как для правой части (5) справедливо правило ассоциативности, тоК- (А+А + +А , ) 2 +1. (6)сумма 2 А)2 +1=А,+А А2 +1 сумма 1 2 +162татка по модулю 2"+1. Представимп-разрядное двоичное число А в видесуммы разрядов со своими весовымимножителямиА та,2 +а,2 а, 2(1)Найдем выражение для остатка помодулю ш=2 +1, Для этого разобъемчисло (1) на группы цифр так, чтобыА=А,2+А 2 +А 2 А 2 , (2)причемА=а 2 +а,2 а 2оА=а 2+а, 2 а 2 (3)л г,ОА=а2 +а2 а, 2ф " (у+11Здесь А , А, . А - 1 с-разрядныечисла.В этом случае остаток от делениячисла А по модулю 2 +1 равенеЗначащий разряд переполнения тразрядной сетки суммы 1 выражения (6) эквивалентен младшему разряду суммы и наоборот.Схема устройства реализует выражение (5). Б сумматорах первых (1-1) блоков начинают суммы 1 и 2, а в сумматорах Т-го блока складывают обе суммы, причем сечения 2 инвертируют. В 1-м блоке сумматоров имеется Ь+1)-й сумматор знаков, учитывающий знак суммы, получаемой в сумматорах этого блока. Если образуется отрицательное число, его надо превратить в положительное, для этого его надо вычесть из модуля числа. Но так как результат на 1-м блоке получается в обратном коде, его надо сложить с модулем числа, это действие эквивалентно суммированию к коду числа 10 . В соответствии с этим выбрана оптимальная структура (1+1)-го блока.Формула изобретения Устройство для формирования остатка по модулю ш=2 +1, где 1 с=1,21 содержащее блоки одноразрядных сумматоров, причем входы сумматоров первого блока являются входами устройства, выходы сумматоров последнегоблока являются выходами остатка, первые входысумматоров последнегоблока соединены с выходами 1 первыхсумматоров предпоследнего блока,о т л и ч а ю щ е е с я тем, что,с целью упрощения устройства, исходное п-разрядное число разделено на 45 р=п/ гРУпп (с добавлением нулевыхзначений разрядов до ближайшего большего целого числа кратного двум) поЕ разрядов, общее число блоков сумматоров равно 1+1, где 1=1 ое и, числосумматоров в 1.-м блоке сумматоров,где 1 1, ,1- 1, равно р 1,/2, числосумматоров в 1.-м и (1+1)-м блокахсумматоров равно соответственно 1+1и к, причем первые и вторые входы сум маторов-й нечетной группы первогоблока соединены соответственно с Я-йи (Я+1)-й нечетными группами из 1разрядов исходного числа, где 1 = 1,Составитель М.ИваныкинРедактор Е.Папп Техред М.Дидык Корректор М.Демчик Заказ 4223/39Тираж 672 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4 з 133 ды сумматоров-й четной группы первого блока соединены соответственно с 0-й и (Я+1)-й четными группами входов иэ Е разрядов исходного числа, выход переноса последнего сумматора 3-го блока сумматоров соединен с входом переноса первого сумматора (3+1) - го блока сумматоров Д=1, ,1), первые и вторые входы сумматоров м -й нечетной группы и-го блока сумматоров соединены соответственно с выходами -й и (+1)-й нечетными группами сумматоров (Я)-го блока сумматоров, . первые и вторые входы сумматоров М -й 9566четной группы р -го блока сумматоров соединены соответственно с выходами -й и (+1)-й четными группами сумматоров (и)-го блока сумматоров, где и=2 (1-1); Ы =1 р/2 , (3 =2-1; первые прямые и вторые инверсные входы сумматоров 1-го блока соединены соответственно с выходами сумматоров первой и второй групп (1-1)-го блока, первый вход (к+1)-го сумматора 1-го блока подключен к шине логической единицы, выход Ь+1)-го сумматора 1-го блока подключен к второму входу второго сумматора (1+1)-го блока.