Пристрій для формування залишків по модулю

СОЮЗ СОВЕТСНИХ СОЦИАЛИСТИЧЕСНИХ РЕСПУБЛИН (19) (51) S I L 1449986 4 G 06 F А1 11/10 ГОСУДАРСТВЕННЫЙ НОМИТЕТ ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ ПРИ ГННТ СССР ОПИСАНИЕ И: (21) 4118342/24-24 (22) 1 2 . 0 9 , 8 6 (46) 07.01 . 8 9 . Бюл. И 1 " (71) Львовский политехнический институт им. Ленинского комсомола (72) Н.В. Черкасский > (53) 6 8 1 . 3 ( 0 8 3 . 8 ) ' (56) Авторское свидетельство СССР № 1397918; 1397919, • кл. G 06 F 11/10, 1985. Авторское свидетельство СССР №1305684; 1*305685, к л . G 06 F 11/10, 1985, (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКОВ ПО МОДУЛЮ (57) Изобретение о т н о с и т с я к вычислительной технике и может быть и с п о л ь з о в а н о при п о с т р о е н и и к о н т р о л и руемых арифметических у с т р о й с т в . Цель и з о б р е т е н и я - повышение коэффициента и с п о л ь з о в а н и я о б о р у д о в а н и я за с ч е т формирования о с т а т к о в по м о дулю о д и н н а д ц а т ь . Контролируемое с л о во р а з б и в а е т с я на группы по п я т ь р а з рядов в к а в д о й . Эти г р ц п п ы . р а з р я д о в соединяются с входами одноразрядных CD СО 00 О) -.іРГіК. 1.449986 сумматоров 1, объединенных в (1-1) группу 2 (1= — торов I каждой предыдущей группы 2 соединены с инверсными входами первого слагаемого одноразрядных сумматоров I последующей группы 2. Прямые входы одноразрядных сумматоров I каждой группы 2, кроме первой, соединены с соответствующими группами разрядов контролируемого слова. Затем с помощью восьми одноразрядных сумматоров 3.1-3.8 из пятиразрядного . кода образуется четырехразрядный, , который с помощью блока 4 свертки преобразуется в код остатка, поступающий на выходы группы 6 устройства. 2 ил.,1 табл. где п - разрядность контролируемого с л о в а ) . Первые две группы разрядов контролируемого слова соединяются соо гветственно с инверсными входами первого слагаемого и прямыми входами второго слагаемого соответствующих одноразрядных сумматоров 1 первой группы 2 . ! . Выход п е реноса каждого предыдущего одноразрядного сумматора I каящой группы 2 соединен с входом переноса последующего одноразрядного сумматора 1. Выходы результата одноразрядных сумма Пусть А(п) исходное число, заданное в следующей двоичной системе счисления Изобретение относится к вычислительной технике и может быть использовано при построении контролируемых арифметических устройств. Цель изобретения - повышение коэффициента использования оборудования за счет формирования остатков по модулю одиннадцать. На фиг. 1 приведена функциональная схема устройства; на фиг. 2 функциональная схема блока свертки. Устройство для формирования остатка по модулю ( ф и г . ! ) рассчитано на контроль 32-разрядного числа и содержит одноразрядные сумматоры 1.1-1.5, объединенные в шесть групп 2.1-2.6» одноразрядные сумматоры 3 . 1 - 3 . 8 , блок 4 свертки, входы 5 блока 4 свертки и группу выходов 6 устройства. где А ,А,,А £ - группы последовательных двоичных цифр с одинаковым количеством разрядов. Остаток от деления числа А(п) на модуль го равен (2) где Коэффициенты Sj определяют сложность вычисления остатков по выражению '2). Наименьшее число вычислений при 5,=SZ=...=1, что имеет место для модулей чисел Мерсенна и Ферма. В обоих этих случаях количество разрядов в группах 1 равно степени р или V. Для отыскания минимальных значений S; таблица положительных и отрицательных остатков от длеения последовательного разряда степени двойки на модуль 1 имеет следующий вид. 1 Блок 4 свертки (Фиг. 2) содержит одноразрядные сумматоры 7 . 1 - 7 . 4 , элемент И-НЕ 8, элемент Н 9, групЕ пу 10 элементов И-ИЛИ, элементы И П.1-11.4. Устройство работает следующим образом. 2f .Модуль 11 + 1 2 -10 9 2* 4 2' 8 7 2* 25 2й 5 3 О) А«Ав+А,- 2 1 09 6 1 27 2 28 7 4 3 8 2* 6 5 2 *° 1 п 2 l\ 2 1 0 4 8 . 9 7 3 . 1449986 входов ых сумматоров с горизонтальной цепью распространения сигнала переноса , содержащей ряд ступеней. 3 этой матрице не происходит увеличения р а з рядной сетки сумматоров по мере накопления результата. В целях исключе(3) г = ния операции вьїчитания использовано Выражение (3) позволяет свернуть сочетание прямых кодов частей исходмногоразрядное число до 5-разрядного 10 ного числа и инвертирование отрицавычета по модулю I I . тельных слагаемых и всех промежуточДля отыскания остатка г (наименьных результатов путем дополнения их шего вычета) необходима дополнительпо модулю. Выбранный способ инвертиная свертка, так как вычет гР имеет рования суммируемых чисел позволяет 5 разрядов, а вычет г-4 разряда для взаимно компенсировать все отрица15 модуля 1 1 , 6 = 1 0 1 ! г . Переход от г ' к г тельные и положительные значения о . производится на сумматорах 3. Вычет В сумматорах 3 производится перег ' можно разбить на две группы, кажход от 5-разрядного вычета к 4-раздая из которых содержит определенрядночу. Для этого содержимое сумманое число разрядов, например 2 и 3 20 торов последней группы 2.6 и сумматоили 1 и 4 . Наиболее экономичным с ра 1,4 группы 2.5 складывается со точки зрения аппаратной реализации значением сумматора 1.5 группы 2 . 5 , является второй вариант. Присоединеумноженным на 5 Ю = Ю 1 2 . На входах 5 ние старшего разряда к младшим должно образуется вычет г согласно ( 4 ) . В производиться с определенным коэффи- 25 блоке 4 свертки получают наименьший циентом , который определяется по табположительный вычет. Для получения лице. Так, при 2 коэффициент равен положительного г прибавляем к г до+5, поэтому полнение й=4 в сумматорах 7. Если возникает при этом перенос (что соот-іь (4) ЗО ветствует случаю, когда выполняется неравенство m ^ r ' t l S ) » то наименьший где B O , S ( - четыре младших и один остаток снимается с выходов сумматостарший разряд г ' . ров 7 через элемент И-ИЛИ 10. Если При использовании выражения '4) сигнала переноса на сумматоре 7.4 возможно получение отрицательного о с не возникает, тогда остаток подается 35 на выход схемы, минуя сумматоры 7, с т а т к а . Переход от отрицательного к положительному остатку несложен. Так выходов сумматоров 3 . 5 - 3 . 8 из-за накак личия сигнала ' ' ] " на выходе инвертора 9. Исключение составляет случай, "r=rA«i modra» (5) когда r'=m=M, o =101Г 2 . Для получения где Гд оП - дополнение г до модуля ш, 40 г =0 служат элементы И-НЕ 8 и И 1 I . то При г'=1011 на входе элемента И-НЕ 8 установятся все " I м , а на выходе обгде г - обратный код значения о с разуется ' ' О 1 . Этот сигнал закрывает татка г, все элементы И 11 и на выходах 6 оба разуется код 0000 независимо от с о с S =m-(r+ro6p )/t-^ro6p