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

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 06 F 11/08

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHO1VIY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3968649/24-24 (22) 21.10.85 (46) 23.04.87. Бюл. Р 15 (71) Львовский политехнический инсти-. тут им. Ленинского комсомола (72) Н.В. Черкасский (53) 681.3(088. 8) (5e) Авторское свидетельство СССР

11- 1084798, кл. С 06 F 11/08, 1982.

Гаврилов Ю.В., Пучко А.М. Арифметические устройства быстродействующих ЭЦВМ. -М.: Советское радио,1970, с. 150, рис. 3.3.2. (54)(57) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

ОСТАТКОВ ПО МОДУЛЮ, содержащее (Х-1) группу одноразрядных сумматоров (I, = .гп1

= — ) где и — разрядность числа р—

t Э простое число), причем входы первого и второго слагаемых одноразрядных сумматоров первой группы соединены соответственно с первой и второй группами из р разрядов информационного входа устройства, выходы суммы одноразрядных сумматоров i-й группы соединены с входами первого слагаемого соответствующих одноразрядных сумматоров (i+1)-й группы i = 1-(1-2), входы второго слагаемого одноразрядных сумматоров (i+1)-й группы соединены со-, ответственно с разрядами (i+2)-й группы информационного входа устройства, о т л и ч а ю щ е е с.я тем, что, с целью расширения области применения за счет формирования остатков по модулю чисел Мерсенна, оно содержит блок свертки, содержащий группу одноразряднвх сумматоров, группу элементов И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и

„„SU„„1305684 д 1 элемент И, причем выход переносами-го одноразрядного сумматора i é группы соединен с входом переноса (k+1)-ro одноразрядного сумматора i-й группы, выход переноса р-го одноразрядного сумматора i-й группы соединен с входом переноса первого одноразрядного сумматора (i+1) é группы, выход переноса ш-го одноразрядного сумматора последней группы (ш=l-s-1; s=n-p(I-2) соединен с входом переноса (m+1)-го одноразрядного сумматора последней группы, выходы суммы одноразрядных сумматоров последней группы, выходы одноразрядных сумматоров с (s+1)-го по (р-и)-й предпоследней группы и выЯ ход переноса з-го одноразрядного сумматора последней группы соединено ,соответственно с первыми входами элементов И группы блока свертки, выходы С суммы одноразрядных сумматоров блока свертки являются выходом устройства, причем в блоке свертки выход переноса

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

1305684 Ао + A„+ Aà группы, выход переноса р-го одноразрядного сумматора группы соединен с

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

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 + A .2 +.. ° . (1) Остаток от деления многоразрядного числа А на модуль числа Мерсенна

М равен остатку от деления многоP члена (1) на этот модуль где Аа À„,А ... — последовательные группы двоичных чисел по р разрядов двоичных цифр, начиная с младших разрядов.

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

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

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

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

М, = 7.

Исходное 32 †разрядн число (фиг.1) разбито на трехразрядные числа А,...

А „ . H этом случае устройство содержит группы 2,1-2,10, в каждой из которых находится по три сумматора

1 . 1-1 . 3, а в группе 2. 10 — два сумматора, так как число А„— двухразрядное.

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

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

Правомерность такого преобразования вытекает из того, что оотаток "111" по модулю М, = 7„ = 111, равен "000".

1305684

0 gp 2Р-!

1305684

Составитель А, Клюев

Техред А.Кравчук

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

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

Тираж 673 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 1453/47

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