Устройство для формирования остатков по модулю Советский патент 1987 года по МПК G06F11/08 

следней группы, выходы одноразрядных сумматоров группы блока свертки являются выходом устройства, выходы суммы одноразрядных сумматоров последней группы и выход переноса s-ro одноразрядного сумматора последней группы соединены соответственно с первыми входами элементов И группы блока свертки, причем в блоке свертки первые входы (р+1)-го и (s+1)-ro элементов И группы соединены соответственно с первым и вторым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого и первые входы элементов И, кроме (р+1)-го и (s+1)-го,группы соединены соответственно с входами элемента И,

1

Изобретение относится к вычислительной технике и предназначено для формирования остатков по модулям чисел Мерсенна, которые имеют вид Мр 2-1, где р - простое число, и ис- пользуются при цифровой обработке сигналов.

Целью изобретения является расширение области применения за счет формирования остатков по модулю чисел Мерсенна.

На фиг. 1 представлена схема устройства для формирования остатков по модулю; на фиг. 2 представлена схема блока свертки.

Устройство для формирования остатков по модулю (фиг. 1) содержит одноразрядные сумматоры 1.1-l.p, объединенные в группы 2.1-2(1-1), блок 3 свертки, вход 4 блока 3 свертки,выход 5 устройства. Блок 3 свертки (фиг. 2) содержит группу элементов И 6.1-б.р, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 7, элемент И 8, группу одноразрядных сумматоров 9.1-9.р.

В основу принципа работы положены следующие соображения.

Исходное число А может быть представлено в виде многочлена

А А

А .

+ А, 2 + . , .

(1)

Остаток от деления многоразрядного числа А на модуль числа Мерсенна Мр равен

инверсный выход которого соединен с вторыми входами элементов И группы, - выходы которых, кроме (р+1)-го, соединены с входами первого слагаемого соответствующих одноразрядных сумматоров группы, выход (р+1)-го элемента И группы соединены с входом второго слагаемого (s+1)-ro одноразрядного сумматора группы, выход переноса р-го одноразрядного сумматора группы соединен с входом переноса первого одноразрядного сумматора группы, выход переноса k-ro одноразрядного сумматора группы соединен с входом переноса (k+1)-ro одноразрядного сумматора группы.

А МР :АО+А,

+А,

м

р

S

0

5

0

где Ад,А,А2... - последовательные группы двоичных чисел по р-разрядов, начиная с младших.

В соответствии с (1) и (2) вес р-ого разряда суммы (2) равен весу младшего разряда, в связи с чем выходы переносов старших р-разрядов сумматоров могут быть соединены с входами переносов младших разрядов, что позволяет синтезировать прямоугольную матрицу сумматоров с диагональной цепью распространения сигнала переноса. На выходе матрицы сумматоров должен быть блок свертки, назначение которого состоит в преобраз овании входного (р+О-разрядного кода в р- разрядный остаток.

Устройство для формирования остатков по модулю (фиг. 1 и 2) работает следующим образом:

Рассмотрим работу устройства на примере формирования остатка от 32- разрядного числс по модулям числа Из 7.

Исходное 32-разрядное число (фиг.1) развито на трехразрядные числа А ... ... . В этом случае устройство содержит группы 2.1-2.16, в каждой из которых по три сумматора 1.1-1.3, а в группе 2.9 - два сумматора,так как число двухразрядное. В первой группе 2.1 наблюдается сумма чисел Ар + , в коде с сохранением переносов, в последующих группах складываются полученный результат со следующим числом Л также в коде с сохранением переносов, при этом единицу

ров 9, так как при наличии хотя бы одного нулевого сигнала на входе элемента И 8, на входе его будет единичный сигнал. Только код со всеми

переноса из старшего сумматора сумми- ; единичными сигналами поступит на входы cvMMaTODOB 9 в виде нулевых сигналов. Правомерность такого преобразования вытекает из того, что остаток 111 по модулю Mj 114 равен

с младщим разрядом следующей группы.

В блоке 3 элемент И 8 не препятствует прох-ождению сигналов с входа 4 через элементы И 6 на входы суммато- Ш 000.

/li

бл-f--- QLP

/А2 ffjp-; ... fl 2p

ров 9, так как при наличии хотя бы одного нулевого сигнала на входе элемента И 8, на входе его будет единичный сигнал. Только код со всеми

/If

flzp-/ Qp

Ao flo

Сгя АО

Ai Лг

.

I

Li / Х ГТ у1ф|/

ф ф l

Afi

Pu2j

«.Р

. V.5

V eVт

Фиг

Редактор Г. Гербер

Составитель В. Клюев Техред А.Кравчук

Заказ 1453/47Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

J

Фиг.2

Корректор Л. Патай