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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХ 9) (11) Н 1)4 С 06 Р 11/О ИСАНИЕ ИЗОБРЕТЕНИЯ ти ВАНИЯ (1-1) (1 = оса рвогоодноней ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ Н АВТОРСНОМУ СВИДЕТЕЛЬСТ(71) Львовский политехнический инстут им. Ленинского комсомола(54)(57) УСТРОЙСТВО ДЛЯ фОРМИРООСТАТКОВ ПО МОДУЛЮ, содержащеегруппу одноразрядных сумматоров- где р - разрядность числа р Э1 простое число), причем входы перо, второго слагаемого и переноса одноразрядных сумматоров первои группы соединены соответственно с первой, второй и третьей группы по р-разрядов информационного входа устройства,выходы суммы одноразрядных сумматоров 1-й группы соединены с входами первого слагаемого соответствующих одноразрядных сумматоров (д+1)-й группы д1-(1-3), входы второго слагаемого одноразрядных сумматоров (+1)-й группы соединены соответственно с разрядами .+3)-й группы информационного входа устройства, выход перен к-го %=1-и) одноразрядного сумматора -й группы соединен с входом переноса Ь+1)-го одноразрядного сумматора (1+1)-й группы, выходы суммы одноразрядных сумматоров предпоследней группы соединены с входами пе слагаемого соответствующихразрядных сумматоров послед группы, выход переноса 1-го одноразрядного сумматора предпоследней группы (1 = 1-з, з=п-р(1-2) соединен с входом второго слагаемого(3+1)-го одноразрядного сумматора последней группы, вход переноса 3-гоодноразрядного сумматора последнейгруппы соединен с выходом переноса-1) одноразрядного сумматора последней группы, выход переноса 1-го одноразрядного сумматора последней группы (1=э+1-р) соединен с входом переноса (Т+1)-го одноразрядного сумматора последней группы, о т л и ч аю щ е е с я тем, что, с целью расп 1 ирения области применения за счет формирования остатков по модулю чиселМерсенна, оно содержит блок свертки,содержащий группу одноразрядных сумматоров, группу элементов И, элементИСКЛЮЧАЮЩЕЕ ИЛИ и элемент И, причемвыход переноса р-го одноразрядногосумматора -й группы соединен с входом переноса первого одноразрядногосумматора (1+1)-й группы, выход переноса р-го одноразрядного сумматорапоследней группы соединен с входомпереноса первого одноразрядного сум-матора последней группы, выход переноса з-го одноразрядного сумматора(1-3)-ей группы соединен с входом переноса (з+1)-го одноразрядного сумматора последней группы, выходы суммыодноразрядных сумматоров с (э+1)-гопо р-й (1-.3)-й группы соединены с входами первого слагаемого соответствующих одноразрядных сумматоров последней группы, выход переноса С-го одноразрядного сумматора (1-3)-ей группысоединен с входом второго слагаемого1305685 следней группы, выходы одноразрядныхсумматоров группы блока свертки являются выходом устройства, выходы суммы одноразрядных сумматоров последнейгруппы и выход переноса з-го одноразрядного сумматора последней группысоединены соответственно с первымивходами элементов И группы блока свертки, причем в блоке свертки первыевходы (р+1)-го и (я+1)-го элементовИ группы соединены соответственно спервым и вторым входами элементаИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого ипервые входы элементов И, кроме(р+1)-го и (з+1)-го,группы соединенысоответственно с входами элемента И,1Изобретение относится к вычислительной технике и предназначено для формирования остатков по модулям чисел Мерсенна, которые имеют вид М2 -1, где р - простое число, и используются при цифровой обработке сигналов.Целью изобретения является расширение области применения за счет формирования остатков по модулю чисел10 Мерсенна.На фиг, 1 представлена схема устройства для формирования остатков по модулю; на фиг. 2 представлена схема блока свертки. 15Устройство для формирования остатков по модулю (фиг. 1) содержит одноразрядные сумматоры 1.1-1.р, объединенные в группы 2.1-2(1-1), блок 3 свертки, вход 4 блока 3 свертки,вы ход 5 устройства. Блок 3 свертки (фиг. 2) содержит группу элементов И 6.1-6.р, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 7, элемент И 8, группу одноразрядных сумматоров 9.1-9.р.25В основу принципа работы положены следующие соображения.Исходное число А может быть представлено в виде многочлена А = А +А 2 + А 2 +р 2 Ро Остаток от деления многоразрядногочисла А на модуль числа Мерсенна Мравен инверсный выход которого соединен свторыми входами элементов И группы,выходы которых, креме (р+1)-го, соединены с входами первого слагаемогосоответствующих одноразрядных сумматоров группы, выход (р+1)-го элементаИ группы соединены с входом второгослагаемого (я+1)-го одноразрядногосумматора группы, выход переноса р-гоодноразрядного сумматора группы соединен с входом переноса первого одноразрядного сумматора группы, выходпереноса 1-го одноразрядного сумматора группы соединен с входом переносаЬ+1)-го одноразрядного сумматорагруппы,2( АЪ МР = Ао +А +АгМР где А,АА - последовательные группы двоичных чисел по р-разрядов, начиная с младших.В соответствии с (1) и (2) вес р-ого разряда суммы (2) равен весу младшего разряда, в связи с чем выходы переносов старших р-разрядов сумматоров могут быть соединены с входами переносов младших разрядов, что позволяет синтезировать прямоугольную матрицу сумматоров с диагональной цепью распространения сигнала переноса, На выходе матрицы сумматоров должен быть блок свертки, назначение которого состоит в преобразовании входного (р+1)-разрядного кода в рразрядный остаток.Устройство для формирования остатков по модулю (фиг. 1 и 2) работает следующим образом:Рассмотрим работу устройства на примере формирования остатка от 32- разрядного числа по модулям числаИсходное 32-разрядное число (фиг.1) развито на трехразрядные числа АА, . В этом случае устройство содержит группы 2.1-2.16, в каждой из которых по три сумматора 11 - 1.3, а в группе 2.9 - два сумматора,так какчисло А - двухразрядное. В первой группе 2.1 наблюдается сумма чисел А + А+А, в коде с сохранением пере1305685 А 2 Аф 4 оар-з 0 а 2 Е " аР Ии-) " ЙР носов. В последующих группах складываются полученный результат со следующим числом Л также в коде с сохранением переносов, при этом единицу переноса из старшего сумматора сумми-руют с младшим разрядом следующей группы,В блоке 3 элемент И 8 не препятствует прохождению сигналов с входа через элементы И 6 на входы суммато ров 9, так как при наличии хотя быодного нулевого сигнала на входе элемента И 8, на входе его будет едцничный сигнал. Только код со всеми едцничными сцгналамц поступит на входы смматооов 9 в вцпе нулевых сигналов. Правомерность такого преобразования вытекает цз того, что остаток "111" по модулю М, = 7, =111, равен 1 ОС О 1305685 оставитель В. Клехред А.Кравчук орректор Л. Патай Редактор Г. Гербер аказ 1453/47 дписное роизводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная ВНИИПИ Госу по делам113035, Москв ираж 673рственного комитета СССобретений и открытийЖ, Раущская наб., д