Пристрій для формування залишків по модулю

СОЮЗ СОВЕТСНИХ СОЦИАЛИСТ РЕСПУБЛИК ,q,SU,n, 1401610 (51)4 А1 Н 03 М 7/18 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСНОМУ СВИДЕТЕЛЬСТВУ (21) 4122316/24-24 (22) 19.09.86 (46) 07.06.88. Бгол. № 21 (71) Львовский политехнический институт им. Ленинского комсомола (72) Н*В,Черкасский (53) 681.3 (088.8) (56) Авторское свидетельство СССР 8 1084798, кл. Н 03 М 7/18, 1982. > Авторское свидетельство СССР № 1305685, кл. Н 03 М 7/18, 21.10.85. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКОВ ПО МОДУЛЮ (57) Изобретение относится к вычислительной технике и предназначено для формирования остатков по модулю один надцать от многоразрядного числа без выполнения операции деления в модулярной арифметике, а также в системах аппаратного контроля. Целью изобретения является расширение области применения за счет формирования остатков по модулю одиннадцать. Поставленная цель достигается тем, что устройство для формирования остатков по модулю, содержащее одноразрядные сумматоры, объединенные в группы, блок элементов И, элемент запрета, корректирующие одноразрядные сумматоры, дополнительные одноразрядные сумматоры, содержит дополнительные одноразрядные сумматоры и мультиплексор с соответствующими связями. 1 ил. о СІЇ о 1401610 1 Изобретение относится к вычислительной технике и предназначено для формирования остатков по модулю одиннадцать от многоразрядного числа. 5 Цель изобретения - расширение области применения за счет формирования остатков по модулю одиннадцать. На чертеже представлена схема устройства для формирования, остатков по модулю (для тридцатидвухраэрядного числа по модулю одиннадцатьJ. Устройство содержит одноразрядные сумматоры l f -It, объединенные в группы 2,~2._, дополнительные одно- 15 разрядные сумматоры З т - 3 ( ^ , блок 4 элементов И, элемент 5 запрета, мультиплексор 6 и корректирующие одноразрядные сумматоры 7^~1^* , Устройство работает следующим об- 20 разом. . = • . 2° 2і 2 + 1 2 -10 24 2 5 10 4 9 2 7 3 6 1 9 2 7 2 8 2 э 7 3 8 5 Пусть А(п) - исходное число, заданное в следующей двоичной системе счисления: А = Ао А,2 •г + где Art, A А 2 - группы последовательных двоичных цифр с одинаковым количеством разрядов, Остаток от деления числа А(п) на модуль ш равен . ..:-.,*. .. г = где S: = С1 Sm, StA. S= *.. У т, (2) 2 Для отыскания минимальных значений S составляют таблицу положительных и отрицательных остатков от деления последовательного ряда степени двойки на модуль одиннадцать. f 0 2" 10 9 2 6 4 2 Как видно из таблицы, значения вычетов периодичны. Для Sj = і 1 этот период равен q = 5, Отсюда выражение для отыскания вычета г " можно записать как Таким образом, получение остатка связано с суммированием 1 частей Аразрядностью q = 5 числа А(п), причем все нечетные слагаемые А, отрицательные. При отработке суммы (3) единица переполнения q-разрядной сет-А -1 ~ А 3 ки слагаемых А, одинакового знака эк(3) 35 вивалентна единице младшего разряда = 5. тех же слагаемых, но с противоположВыражение (3) позволяет свернуть ным знаком. Это обстоятельство позвомногоразрядное число до 5-разрядного ляет синтезировать прямоугольную матвычета пс модулю одиннадцать. Для рицу без увеличения разрядной сетки отыскания остатка г (наименьшего высумматоров по мере накопления резульчета) необходима дополнительная тата с диагональной цепью распростсвертка. ранения сигнала переноса сумматоров. В целях исключения операции вычитания используется дополнение по модугде В ( и B t - четыре младших и один лю отрицательных слагаемых А; и всех старший разряды г" . • * результатов, получаемых на выходах При использовании выражения (4) возсумматоров каждой ступени. Компенсаможно получение отрицательного остатция 3 производится в сумматорах 3 пука, в связи с чем следует произвести тем добавления "10", в частности, в переход к положительному остатку.Присумматоры 3 э и 3(Р . чем 50 гА0 = г s + ^ (5) В сумматорах 3 производится переход от 5-разрядного вычета к 4-разгде г о 5 - обратный код значения осрядному.Для этого содержимое суммататка г; г доп ' дополнение г до модуля т; „ торов Ц-1+ последней группы 25 подается на входы дополнительных суммато