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

,.)т",и т;. ;-.,; ВИДЕТЕЛЬСТВ К АВТОРСКл1 етельство СССР М 7/18, 1986,етельство СССР М 7/18, 1987. ДЛЯ ФОРМИРОВА ЗВОЛЬНОМУ МОДИЯ Ю О О (5 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(54) УСТРОЙСТВОСТАТКА ПО ПРОИТ ЧИСЛА7) Изобретение отной технике и можеспециализированнтельных устройствахконтроля выполнении деления, в сигна носится к вычислительт быть использовано в ых цифровых вычисли, в также в устройствах я операций умножения турных анализаторах. Р 7/52, Н 03 М 7/18Г 11/08 Целью изобретения является расширение функциональных воэможностей за счет обеспечения получения результатов деления двоичных чисел и полиномов. Для достижения цели в устройство, содержащее регистр 1 делимого, регистр 2 делителя, первую и вторую схемы сравнения 6-6, вычиТатель 7, триггер 11 и три элемента И 13 - 15, дополнительно введены регистр 3 частного, регистр 4 сдвига, сумматор 8 по модулю два, два коммутатора 9 - 10, элемент ИЛИ 17, элемент И 16 и триггер 12 задания режима работы устройства, В зависимости от состояния триггера режима устройство осуществляет деление двоичных чисел или двоичных полиномов. Частное формируется в регистре частного, остаток от деления - в регистре делимого. 1 ил.10 15 20 и информация с выхода регистра 2, При едие- яичном состоянии триггера 11 и наличии е сигнала на втором выходе схемы 5 сравней ния, свидетельствующего о том, что значение с выхода регистра 1 больше или равно значению с входа 20 делителя, и сигнала на первом выходе схемы с. звнения, свиде 40 тел ьствующего о том, что значение с выходакоммутатора 10 больше значения регистра 1, сигнал с тактового входа 22 через элемент И 14 поступает на входы регистров 2 и 4 и осуществляет сдвиги вправо их разрядов до45 тех пор, пока на втором выходе схемы 6сравнения не появится сигнал, свидетельствующий о том, что значение с выхода коммутатора 10 меньше или равно значению регистра 1, Этот сигнал через элементы И 1550 и ИИИ 17 поступает на управляющий входрегистра 1 и осуществляет запись в регистр 1 информации с выхода коммутатора 9 - разность состояний регистров 1 и 2 при делении чисел (значение С - В .2 1 оогС 1/В или результат поразрядного суммирования по модулю два состояния регистров 1 и 2 при делении полиномов (эначение СьС+В2 Оо 92 с в,По этому же сигналу с выходаэлемента ИИ И 17 осуществляется установка Изобретение относится к вычислительнОй технике и может быть использовано в сПециализированных вычислительных машинах, в устройствах контроля правильности выполнения операций умножения и деления, в сигнатурных анализаторах.Целью изобретения является расширение функциональных возможностей за счет обеспечения получения деления двоичных Ч 11 СЕЛ И ПОЛИНОМОВ.На чертеже представлена структурная схема устройства.Устройство содержит регистр 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 остатка устройства.В устройстве при делении полиномое используется их представление в виде двоичного числа (последовательности двоичнЫх цифр, задающие коэффициент при слагаемых полинома). Например, для дэеленИя полинома Х + Х + 1 на полином Х + Х в качестве делимого задается двоичное числб 100011, в качестве делителя 1010, Пр э 1 ом вычисление полинома остатка С от д ления полинома-делителя А на полином д литель В основывается на рекуррентно формулеС В. 2 ьгсв где(3+ - суммирование по модулю деа,При делении двоичных чисел вычисление остатка С от деления делимого А на делитель В основывается на рекуррентной формулеС,+, С, В. 2 ьцгс/в (2 В обоих случаях вычисление частного О от деления А на В основывается на рекуррЕнтной формулеОн 1 = О + 2 1 о 92 с/ В (3) где = О, 1, 2, ., и -1;Со=А;Оо = 0и выбиРаетсЯ таким, что СоВСо; С= Сп,О=Оо,Устройство работает следующим образом. С входа 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 -в единичное состояние аз я ар р д регистра 3, схемы сравнения, вычитатель, триггер и трисоответствующего стан овленному е ному в еди- элемента И, причем входделителя устройстничное состояние аз я гир р ду ре стра 4, в то ва соединен с информационным входом ревремя как остальные разряды регистра 3 не гистра делителя и первым входом первой изменяются (что соответствует добавлению 5 схемы сравнения, второй вход которой соек состоянию егист аоддс/в)р р 3 значения динен с первым входом второй схемы срав 2 ) нения, с входом уменьшаемого вычитателя,Процесс сдвига регистров 2 и 4, сравне- . выходом остатка устройства и выходом рения на схемах 5 и 6 сравнения и при появ- гистра делимого, установочный вход котолении сигнала на втором выходе схемы 6 10 рого соединен с входом делимого сравнения записи новых значений в регист- устройства, вход запуска устройства соедирах 1 и 3 .родолжается до тех пор, пока на нен с входом установки в "0" триггера и первом выходе схемы 5 сравнения не поя- входом Разрешения записи регистра деливится сигнал, свидетельствующий о том, что теля, выход которого соединен с входом вызначениеделителя с входа 20 больше значе 15 читаемого вычитателя, тактовый вход ния с выхода регистра 1. Это означает, что устройства соединен с первыми входами в регистре 1 завершается формирование ос- первого и второго элементов И, выходы котатка, а в регистре 3 - частного от деления. торых соединены с входами сдвига влево и При этом сигнал завершения формирова- вправо соответственно регистра делителя, ния с выхода 23 при делении полиномов 20 выход старшего разряда которого соединен принимается с задержкой(не показана), ве- с входом Установки в "1" триггера, инверсличина которой должна быть равна суммар- ный выход котОРого соединен с вторым вхоному времени прохождения сигналов через дом пеРвого элемента И, выход "Больше" коммутатор 10, элементы И 15 и ИДИ 17 и первой схемы сравнения соединен с выховремени записи в регистр 1(3), Это связано 25 дом окончания работы устройства, выход с тем, что при делении пелиномов сигнал на "Меньше или равно" второй схемы сравнепервом выходе схемы 5 сравнения может ниясоединенспервымвходомтретьегоэлепоявиться до завершения последнего этапа, мента И, второй вход которого соединен с формирования частного и остатка, если сте- пРямым выходом триггера и вторым входом пень полинома, содержащегося в регистре 30 второгоэлемента И,третийичетвертыйвхо; равна степени полинома - делителя на ды котоРого соединены с выходами "Меньвходе 20(например,если на посленем шаге ше или Равно" первой и "Больше" второй необходимо разделить Х + 1 на Х + )(+ 1) схем сравнения соответственно, о т л и ч а югЧастное от деления поступает на выход 24, щ е е с я тем, что, с целью расширения функостаток - на выход 25 устройства, 35 циональных возможностей устройства засли для деления на входы 19 и 20 по- счетобеспечениЯ полУчениЯ Результатовдедаются коды чисел такие, что код делимого ления двоичных чисел и полиномов, в него меньше кода делителя, то после поступле- введены регистры сдвига и частного, сумма- ния на вход 21 сигнала запуска с выхода тор по модулю два, триггер режима, два схемы 5 сравнения на выход 23 поступает 40 коммутатора, четвертый элемент И и элесигнал окончания работы устройства, на вы- мент ИЛИ, причем вход запуска устройства ход 24 - значение частного(нулевое состоя- соединен с входами начальной установки ние регистра 3) и на выход 25 - значение регистров сдвига и частного, выходы перво- остатка, равного делимому, При этом при го к, второго элементов И соединены с входелении полиномов сигнал с выхода 23 при дами сдвига влево и вправо соответственно нимается с задержкой, так как, если степень РегистРа сдвига, выход которого соединен с подаваемых на входы 19 и 20 кодов полино- информационным входом регистра частномов равны, сигна с выхода схемы 6 сравне- го, выход которого соединен с выходом часния через элементы И 16 и ИЛИ 17 тного Усройства, вход установки режима поступает на управляющие входы Регистров 50 Работы устройства соединен с входом триг и 3 и осуществляет запись в регистр 1 гера режима, выход которого соединен с значение А + В и в регистр 3 единицу из первым входом четвертого элемента И и упрегистра 4. равляющими входами первого и второгокоммутаторов, первые информационныеФормула изобретения 55 входы которых соединены с выходом сумматора по модулю два, первый вход которогоустройство для формирования остатка соедине с выходом Регистраделимого, втопо произвольному модулю от числа, содер Рой вход - с выходом регистра делителя и с жащее регистры делимого и делителя, две втоРым информационным входом второгокоммутатора, выход которого соединен с1612296 Составитель Н.МаркеловаРедактор Н.Рогулич Техред М.Моргентал Корректор О.Кравцова Заказ 3831 Тираж 566 Подписное 8 НИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101 вторым входом второй схемы сравнения, выход "Меньше или равно" которой соединен с вторым входом четвертого элемента И, третий вход которого соединен с выходом "Больше" первой схемы сравнения, инверсный выход триггера соединен с четвертым входом четвертого элемента И, выход кото,рого соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, выход элемента ИЛИ соединен с входами разрешения записи регистра частного и регистра делимого, 5 информационный вход которого соединен свыходом первого коммутатора, второй информационный вход которого соединен с выходом вычитателя.