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

СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИ 130 СПУБЛ(51) 4 0 ЕТЕН элемен причемного с ыход перенос еский инстиола(56) Авт 9 108479Гаврил тические щих ЭЦВМ с. 150, р тво СССР 08, 1982 .М. Ариф одейству рское свидетель кл. С 06 Р 11 ов Ю.В., Пучко устройства бысто,элемента ИСКЛЮЧАЮи втоЩЕЕ ИЖ вх ыход ов И оторого и первые вхокроме (р+1)-го исоединены соответсты элеме я+1)-го енно с одами емента инв выход квходами орого лемен которых, кромевходами первыхющих одноразрядвыход (р+1)-годинен с входом(я+1)-го однора ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ИСАНИЕ ИЗОБ Н АВТОРСКОМУ СВИДЕТЕЛЬСТВ(54)(57) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКОВ ПО МОДУЛЮ, содержащее (1-1) группу одноразрядных сумматоров (1 = Гп 1- где и - разрядность числа р -Упростое число), причем входы первого и второго слагаемых одноразрядных сумматоров первой группы соединены соответственно с первой и второй группами из р разрядов информационного входа устройства, выходы суммы одноразрядных сумматоров 1-й группы соединены с входами первого слагаемого соответствующих одноразрядных сумматоров (д+1)-й группы д = 1-(1-2), входы второго слагаемого одноразрядных сумматоров (1+1)-й группы соединены со-, ответственно с разрядами (д+2)-й группы информационного входа устройства, о т л и ч а ю щ е е с.я тем, что, с целью расширения области применения за счет формирования остатков по модулю чисел Мерсенна, оно содержит блок свертки, содержащий группу одноразряднвх сумматоров, группу элементов И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и одноразряд умматора -й группы соединен с входом переноса Ь+1)-го одноразрядного сумматора -й группы, выход переноса р-го одноразрядного сумматора 1-й группы соединен с входом переноса первого одноразрядного сумматора (+1)-й группы, выход переноса ш-го одноразрядного сумматора последней группы (ш=1-я; я=п-р(1-2) соединен с входом переноса (ш+1)-го одноразрядного сумматора последней группы, выходы суммы одноразрядных сумматоров последней группы, выходы одноразрядных сумматоров с (я+1)-го по (р-и)-й предпоследней группы и вы- аФ ход переноса я-го одноразрядного сумматора последней группы соединено соответственно с первыми входами элементов И группы блока свертки, выходы Се суммы одноразрядных сумматоров блока свертки являются выходом устройства, причем в блоке свертки выход переноса Ффффф к-го одноразрядного сумматора соеди нен с входом переноса %+1)-го одно- (,) разрядного сумматора %=1-р),входы (р+1)-го и (я+1)-го элементов И груп- р пы соединены соответственно с первым соединен с вторыми ов И группы, выходы (р+1)-го, соединены с слагаемых соответствуных сумматоров группы, элемента И группы соевторого слагаемого зрядного сумматора1305684 группы, выход переноса р-го одноразрядного сумматора группы соединен с Изобретение относится к вычислительной технике и предназначено дляформирования остатков по модулям чисел Мерсенна, которые имеют вид МРР2 -1, где р - простое число и используются при цифровой обработкесигналов.Целью изобретения является расширение области применения за счет формирования остатков по модулю чиселМерсенна,На фиг, 1 представлена схема устройства для формирования остатков помодулю; на фиг. 2 представлена схемаблока свертки.Устройство для формирования остатков по модулю (фиг. 1) содержит одноразрядные сумматоры 1.1-1,р, объединенные в группы 2,1-2(2-1), блок 3свертки, вход 4 блока 3 свертки и выход 5 устройства. Блок 3 свертки(фиг, 2) содерЖит группу элементов И6.1-6.р, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 7,элемент И 8, группу одноразрядныхсумматоров 9.1-9.р.В основу принципа работы положеныследующие соображения.Исходное число А может быть представлено в виде многочлена А = А + А,2 + А .2 +. (1) Остаток от деления многоразрядного числа А на модуль числа Мерсенна М равен остатку от деления много- Рчлена (1) на этот модуль(А МР = (Ао + А+ А 2 ) МР, (2) где Ао:А,А - последовательные группы двоичных чисел по р разрядов двоичных цифр, начиная с младших разрядов.В соответствии с (1) и (2) вес р-го разряда суммы (2) равен несу мпадшего разряда, в связи с чем выховходом переноса. первого одноразрядного сумматора группы. ды переносов старших р-разрядных сумматоров могут быть соединены с входами переносов младших разрядов. Этопозволяет синтезировать прямоуголь 5 ную матрицу сумматоров с горизонтальной цепью распространения сигналапереноса.На выходе матрицы сумматоров должен быть блок свертки, назначение которого состоит в преобразовании входного (р+1) разрядного кода в р-разрядный остаток,Устройство для формирования остатков по модулю (фиг. 1 и 2) работаетследующим образом,Рассмотрим работу устройства напримере формирования остатка от 32 разрядного числа по модулям числаМ, = 7.Исходное 32-разрядное число (фиг.1)разбито на трехразрядные числа А,А. В этом случае устройство содержит группы 2,1-2.10, в каждой изкоторых находится по три сумматора251.1-1,3, а в группе 2.10 - два сумматора, так как число А - двухразрядное. В первой группе 2,1 получают сумму А, + А. В последующих группах складывают полученный результат со следующим числом А, .при этом единицу переноса суммируют с младшим разрядом.В блоке 3 элемент И 8 не препятствует прохождению сигналов с входа 4 через элементы И 6 на входы сумматоров 9, так как при наличии хотя бы одного нулевого сигнала на входе элемента И 8 на выходе его будет единичный сигнал. Только код со всеми единичными сигналами поступит на входы сумматоров 9 в виде нулевых сигналов, 11 равомерность такого преобразования вытекает из того, что оотаток "111" по модулю М, = 7 = 111, равен "000", 1305684