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

группы, выход переноса р-го одноразрядного сумматора группы соединен с

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

+ Aj .2

2Р

+

(1)

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

(1) на этот модуль

А Мр АО + А, + AJ Мр , (2)

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

В соответствии с (1) и (2) вес р-го разряда суммы (2) равен весу кпадшего разряда, в связи с чем выховходом переноса первого одноразрядного сумматора группы.

ды переносов старших р-разрядных сумматоров могут быть соединены с входами переносов младших разрядов. Это позволяет синтезировать прямоугольную матрицу сумматоров с горизонтальной цепью распространения сигнала переноса.

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

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

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

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

В первой группе 2.1 получают сумму А + А. В последующих группах складывают полученньй результат со следующим числом А, .при этом единицу переноса суммируют с младщим разрядом.

В блоке 3 элемент И 8 не препятствует прохождению сигналов с входа 4 через элементы И 6 на входы сумматоров 9, так как при наличии хотя бы одного нулевого сигнала на входе элемента И 8 на выходе его будет единичный сигнал. Только код со всеми единичными сигналами поступит на входы сумматоров 9 в виде нулевых сигналов. Правомерность такого преобразования вытекает из того, что остаток 111

0

5

0

5

0

5

по модулю М,

ю

111, равен 000.

/It

flft-f - OLP

Ai

АО

Oyp.f ... OZP QZP-t Op 0

Ai

АО

Ко /4,

Аг

/At-/

Ki

Ц.Р

V. () .$ ,,/

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

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

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

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

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

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

Корректор Л. Пнлипенко