Устройство для вычисления остатка по модулю от двоичного числа Советский патент 1988 года по МПК H03M7/18 

.,

f: ITST

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

Целью изобретения является повьше - ние быстродействия,.

На фиг.1 приведена схема устройст ва для вычисления остатка по модулю от двоичного числа; на фиг.2 - схема блока свертки по модулю (для m 4, Р 3),,

Устройство (фиг. 1) содержит входной регистр 1, блоки 2 и 3 свертки по модулю, блок 4 умножения на константу по модулю, сумматор 5 по модулю регистры 6 JI. 7, коммутаторы 8 и 9 . устройства, выход 10 устройства, группу тактовых входов И. 1-Й.5 устройства. -

Блок . (3) свертки по модулю

(фиг.2) содержит дешифратор 12 и группу элементов ИЛИ 13.1 и13.2. Входной регистр 1 имеет 1т разрядов с О по (1т-1)-й управляющий вход, при подаче сигнала на который содержимое регистра 1 сдвигается на m разрядов влево. Блоки 2 и 3 свертки по модулю одинаковы и преобразуют т-разрядное входное число в остаток по модулю Р. Блок 4 умножения осуществляет опера цию умножения входного п-разрядного кода на константу, по модулю Р, Раз- рядность регистров 6 и 7 коммутато : ров 8 и 9 равна п.

Устройство в своей работе использу ет следующее,.

Двоичное К-разрядное число X может быть представлено в виде

X а., z +,,,+а,2 + . (О

Используя схему Горнера преобразу ем (1) к виду, удобному для нахожде- ния остатка х от числа X по модулю Ps

X JX|; /.,./а«., 2/J + .., + a,|;x

2|J+ ajp

Пусть выбранный модуль Р имеет разрядность п. Разобьем двоичное представление числа X на группы по m двоичных разрядов, причем m п. С учетом разбиения преобразуем (2) к 55 виду

x /-./Aj;-2 i;+,., ЧА.|;|;;

(3/

А; а;„2 -Ч .,, 4 а

irrt - 1ГЦ-

2 +

t- а

I m - VT1 J

где / i 1 , 1.

Обозначая В; « А;|р и (Ь , приведем (3) к виду:

X |,,,|Bj-p|; + .p +,.,+

B.I;.

(4)

При этом ft является константой, вычисленной заранее.

Устройство работает следующим образом.

В исходном состоянии в регистре 1 находится код преобразуемого числа X, Коммутатор 8 подключает выход блока 2 к входу блока 4, а коммутатор 9 под ключает выход регистра 6 к входу коммутатора 9. Содержимое регистров 6 и 7 произвольно.

На первом такте число А., определяемое m старшими разрядами преобразуемого числа X, преобразуются блоком 2 в остаток Bj по модулю Р.

Аналогично на выходе блока 3 получается остаток Bj,, от числа А, по модулю Р, Значение числа В через коммутатор В поступает на вход блока 4 где оно умножается на константу р по модулю Р и складьшается с B, в сумматоре 5.

Таким образом, по окончании переходных процессов на выходе сумматора 5 имеем

/|ве-рГр Ве-1/;.

Р е-1 / Р

Результат суммирования записьшает- ся в момент поступления импульса по входу 11,4 в регистр 6,

На втором такте преобразования в момент поступления импульса по входу 11,4 в регистр 6,

На втором такте преобразования в момент поступления импульса по входу 11,1 содержимое регистра 1 сдвигается на m разрядов влево. Изменяется потенциал на входе 11,2, под действием которого коммутатор 8 подключает к входу блока 4 коммутатора 9. В этом состоянии коммутатор 8 остается до конца преобразования. Содержимое регистра 6 через коммутаторы 9 и 8 nor- ступает на вход блока 4, в котором умножается на константу j) по модулю Р, 1 - I

Одновременно число АО , представленное третьей группой из разрядов, преобразуемых по модулю Р блоком 3,

2 fPue.2 /Z

Изобретение относится к вычисли тельно.й технике и может быть использовано для сопряжения вычислительных устройств, функционирующих в системе остаточных классов, а также в составе средств передачи данных, использующих модулярные коды. Целью изобретения является повышение быстродействия. Поставленная цель достигается тем, что устройство для вычисления остат ка по модулю от двоичного числа, со держащее входной регистр , блок 4 умножения на константу по модулю, сумматор 5 по модулю, регистры 6,7 и коммутаторы 8,,9, дополнительно со-- держит блоки 2,3 свертки по модулю с соответств тощими связями, 2 ил ///