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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных цифровых вычислительных устройствах, а также в устройствах контроля выполнения операций умножения и деления, в сигнатурных анализаторах. Целью изобретения является расширение функциональных возможностей за счет обеспечения получения результатов деления двоичных чисел и полиномов. Для достижения цели в устройство, содержащее регистр 1 делимого, регистр 2 делителя, первую и вторую схемы сравнения 6-6, вычитатель 7, триггер 11 и три элемента И 13-15, дополнительно введены регистр 3 частного, регистр 4 сдвига, сумматор 8 по модулю два, два коммутатора 9-10, элемент или 17, элемент И 16 и триггер 12 задания режима работы устройства. В зависимости от состояния триггера режима устройство осуществляет деление двоичных чисел или двоичных полиномов. Частное формируется в регистре частного, остаток от деления - в регистре делимого. 1 ил.

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

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

РЕСПУБЛИК

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4651564/24-24 (22) 15.02.89 (46) 07.12.90. Бюл. N 45 (72) В.И.Язневич (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М 1396281, кл. Н 03 М 7/18, 1986, Авторское свидетельство СССР

М 1432783, кл. Н 03 М 7/18, 1987. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ

ОТ ЧИСЛА (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных цифровых вычислительных устройствах, а также в устройствах контроля выполнения операций умножения и деления, в сигнатурных анализаторах. Ю„„1612296 А1 (я) s G 06 F 7/52, Н 03 M 7/18, G 06 F 11/08

Целью изобретения является расширение функциональных воэможностей за счет обеспечения получения результатов деления двоичных чисел и полиномов. Для достижения цели в устройство, содержащее регистр 1 делимого, регистр 2 делителя, первую и вторую схемы сравнения 6-6, вычиТатель 7, триггер 11 и три элемента И 13 — 15, дополнительно введены регистр 3 частного, регистр 4 сдвига, сумматор 8 по модулю два, два коммутатора 9 — 10, элемент ИЛИ 17, элемент И 16 и триггер 12 задания режима работы устройства. В зависимости от состояния триггера режима устройство осуществляет деление двоичных чисел или двоичных полиномов. Частное формируется в регист ре частного, остаток от деления - в регистре делимого. 1 ил.

1612296

20 и информация с выхода регистра 2, При едие- яичном состоянии триггера 11 и наличии е- 35 сигнала на втором выходе схемы 5 сравней ния, свидетельствующего о том, что значение с выхода регистра 1 больше или равно значению с входа 20 делителя, и сигнала на первом выходе схемы c(эвнения, свиде40 тел ьствующего о том, что значение с выхода коммутатора 10 больше значения регистра

1, сигнал с тактового входа 22 через элемент

И 14 поступает на входы регистров 2 и 4 и осуществляет сдвиги вправо их разрядов до

45 тех пор, пока на втором выходе схемы 6 сравнения не появится сигнал, свидетельствующий о том, что значение с выхода коммутатора 10 меньше или равно значению регистра 1, Этот сигнал через элементы И 15

50 и ИИИ 17 поступает на управляющий вход регистра 1 и осуществляет запись в регистр

1 информации с выхода коммутатора 9— разность состояний регистров 1 и 2 при делении чисел (значение C1 - В . 2 (ьд2С1/В) или результат поразрядного суммирования по модулю два состояния регистров 1 и 2 при делении полиномов (эначение «1.С+В

2 (ь 2с в).По этому же сигналу с выхода элемента ИИИ 17 осуществляется установка

Изобретение относится к вычислительнОй технике и может быть использовано в сПециализированных вычислительных машинах, в устройствах контроля правильности выполнения операций умножения и деления, в сигнатурных анализаторах.

Целью изобретения является расширение функциональных возможностей за счет обеспечения получения деления двоичных

Ч1)ОСЕЛ И ПОЛИНОМОВ.

На чертеже представлена структурная схема устройства.

Устройство содержит регистр 1 делимог, регистр 2 делителя, регистр 3 частного, р гистр 4 сдвига, первую 5 и вторую 6 схемы с авнения, вычитатель 7, сумматор 8 по модулю два, первый 9 и второй 10 коммутаторы, триггер 11, триггер 12 режима, первый 13, второй 14, третий 15 и четвертый 16 элементы

И(элемент ИЛИ 17, вход18установки режимв работы устройства, вход 19 делимого, вход 20 делителя, вход 21 запуска, тактовый вход 22 устройства, выход 23 окончания раб ты устройства, выход 24 частного и выход

2 остатка устройства.

В устройстве при делении полиномов используется их представление в виде двоичного числа (последовательности двоичнЫх цифр, задающие коэффициент при слагаемых полинома). Например, для деления полинома Х + X + 1 на полином X + X в качестве делимого задается двоичное числб 100011, в качестве делителя 1010, Пр э1ом вычисление полинома остатка С от д линия полинома-делителя А на полином д литель В основывается на рекуррентно формуле

C„, С. ®В. 2 (1og2ci, в) гДе(+1- суммирование по модулю два, При делении двоичных чисел вычисление остатка С от деления делимого А на делитель В основывается на рекуррентной формуле ,+, = С, - В. 2 (ьц2с /в) (2

В обоих случаях вычисление частного D от деления А на В основывается на рекуррЕнтной формуле ()н1 = О(+ 2 (1оЯ2с(/ В) (3) где)=0, 1,2, ..., n-1;

Со = А;

Do = 0; и выбирается таким, что «n < В С -1;

С= Cn, D=Dn, Устройство работает следующим образом.

С входа 18 в триггер 12 записывается состояние, задающее режим работы устройства: 0 — для деления двоичных чисел, 1 — для деления двоичных полиномов, С входа 19 в регистр 1 делимого записывается число А, По сигналу с входа 21 запуска осуществляется сброс триггера 11 в нулевое состояние, запись числа В с входа 20 устройства в регистр 2 делителя, сброс регистра 3 частного в нулевое состояние, установка в единичное состояние младшего разряда и в нулевое состояние остальных разрядов регистра 4 сдвига. После этого тактовые сигналы с входа 22 через элемент И 13 поступают на входы регистров 2 и 4 и осуществляют сдвиг влево их разрядов до тех пор, пока в крайнем слева (старшем) разряде регистра 2 не появится единичный уровень, который с выхода регистра 2 поступает на вход триггера

11 и осуществляет установку его в единичное состояние. которое запрещает поступление сигналов через элемент И 13 на вход сдвига влево регистров 2 и 4. Коммутаторы

9 и 10 работают так, что при делении полиномов (единичное состояние триггера 12) на их выходы передается информация с выхода сумматора 8 по модулю два, осуществляющего поразрядное суммирование поступающих на его информационные входы чисел, а при делении чисел на выход коммутатора 9 — информация с выхода вычитателя 7, а на выход коммутатора 10—

1612296 в единичное состояние аз я а р р д регистра 3, схемы сравнения, вычитатель, триггер и три соответствующего стан овленном у е ному в еди- элемента И, причем входделителя устройстничное состояние аз я ги р р ду ре стра 4, в то ва соединен с информационным входом ревремя как остальные разряды регистра 3 не гистра делителя и первым входом первой изменяются (что соответствует добавлению 5 схемы сравнения, второй вход которой соек состоянию егист а (ьд2с бв) р р 3 значения динен с первым входом второй схемы срав2 ) нения, с входом уменьшаемого вычитателя, г1роцесс сдвига регистров 2 и q, сравне- . выходом остатка УстРойства и выходом Рения на схемах 5 и 6 сравнения и при появ- гистРа делимого, Установочный вход котолении сигнала на втором выходе схемы 6 10 Рого сое4инен с вхо4ом делимого сравнения записи новых значений в регист- УстРойства, вхоД запУска УстРойства соеДирах 1 и 3. родолжается до тех пор, пока на нен с входом установки в "0" тРиггеРа и первом выходе схемы 5 сравнения не поя- вхо4ом РаэрешениЯ записи РегистРа деливится сигнал, свидетельствующий о том, что телЯ, выход котоРого соеДинен с входом вызначениеделителя с входа 20больше значе- 15 читаемого вычитателЯ, тактовый вход ния с выхода регистра 1. Это означает, что Устройс а сое4инен с пеРвыми входами в регистре 1 завершается формирование ос- пеРвого и втоРого элементов И, выходы котатка, а в регистре 3 — частного от деления. торых соединены с входами ддвига влево и

При этом сигнал завершения формирова- вправо соответственно регистра делителя, ния с выхода 23 при делении полиномов 20 выход старшего РазРяда которого сое4инен принимается с задержкой(не показана), ве- с входом установки в "1" триггера, инверсличина которой должна быть равна суммар- ный выход котррого соединен с вторым вхоному времени прохождения сигналов через дом первого элемента И, выход "Больше" коммутатор 10 элементы И 15 и ИпИ 17 и первой схемы сРавнениЯ соединен с выховремени записи в регистр 1 (3). Дто связано 25 дом окончаниЯ Работы УстРойства, выхо4 стем, что при делении пелиномов сигнал на "Мен ше или равно" второй схемы сравнепервом выходе схемы 5 сравнения может ниЯ соединен с первым входомтретьегоэлепоявиться до завершения последнего этапа .мента И, второй вход которого соединен с формирования частного и остатка, если сте- прямым выходом триггера и вторым входом пень полинома, содержащегося в регистре 30 втоРого элемента И, тРетий и четвертый вхорааНа степени полинома — делителя „а ды ко оро о сое4инены с Выходами "Менвходе 20(например, если на после нем шаге ше или Равно" первой и "Больше" второй необходимо разделить X + 1 íà X + X + 1) схем сравнени соответственно, 0 т л и ч а юг

Частное от деления поступает на выход 24, щ е е с Я тем, что, с целью РасшиРениЯ фУнкостаток — на выход 25 устройства. 35 ционалbíûх возможностей устройства за сли для деления на входы 19 и 20 по- счет обеспечениЯ полУчениЯ Результатов Дедаются коды чисел такие, что код делимого лениЯ ДВОичных чисел и полиномов, в него меньше кода делителя, то после поступле- ВВЕ4ЕНЫ РЕГИСТРЫ СДВИГа И ЧаСтНОГО, СУММа- ния на вход 21 сигнала запуска с выхода тор по мо4улю 4ва, тРиггер Режима, 4ва схемы 5 сравнения на выход 23 поступает 40 комму а ора, четвеРтый элемент И и элесигнал окончания работы устройства, на вы- мен ИЛИ, пРичем вход запуска Устройства ход 2.1 — значение частного(нулевое состоя- сое4инен с вхо4ами начальной Установки ние регистра 3) и на Выход 25 значение PerHcrPos сдВигэ и частного, ВыхоДы пеРво остатка, равного делимому. 1ри этом при го к, второго элементов И соединены с входелении полиномов сигнал с выхода 23 при 45 дами сдвига влево и впРаво соответственно нимается с задержкой, так как, если степень РегистРа сдвига, выход которого соединен с подаваемых на входы 19 и 20 кодов полино- информационным ходом РегистРа час™омов равны, сигна с выхода схемы 6сравне- го, выхо4 котоРо о соеДинен с выхоДом часния через элементы И 16 и ИЛИ 17 тного УстРойства вхоД Установки Режима поступает на управляющие входы регистров 50 Работы Ус ройства сое4инен с вхоДом тРиг1 и 3 и осуществляет запись в регистр 1 repa Режима, Выхо4 котоРого соеДинен с значение А + д и в регистр 3 единицу из первым входом четвеРтого элемента И и Упрегистра 4. равляющими входами первого и второго коммутаторов, первые информационные

Формула изобретения 55 входы которых соединены с выходом сумматора по модулю два, первый вход которого

Устройство для формирования остатка соедине с выхо4ом Регистраделимого, втопо произвольному модулю От числа, содер- Рой вхОД вЂ” с выхОДом РегистРа ДелителЯ и с кащее регистры делимого и делителя две вторым инфОРмэЦионным Вх040м Второго коммутатора, выход которого соединен с

1612296

Составитель Н.Маркелова

Редактор Н.Рогулич Техред М.Моргентал Корректор О.Кравцова

Заказ 3831 Тираж 566 Подписное

8НИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 вторым входом второй схемы сравнения, выход "Меньше или равно" которой соединен с вторым входом четвертого элемента

И, третий вход которого соединен с выходом

"Больше" первой схемы сравнения, инверсный выход триггера соединен с четвертым входом четвертого элемента И, выход кото,рого соединен с первым входом элемента

ИЛИ, второй вход которого соединен с выходом третьего элемента И, выход элемента

ИЛИ соединен с входами разрешения записи регистра частного и регистра делимого, 5 информационный вход которого соединен с выходом первого коммутатора, второй информационный вход которого соединен с выходом вычитателя.