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

)5 0 06 Е 7/49 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИ гг,У СВ ож ания мен- ного ды 5, мень- ения ка 1, е по- пеци 3 и, ил. М(56) Авторское свидетельство СССР М 1476614, кл. Н 03 М 7/04, 1986.Авторское свидетельство СССР ЬВ 1160398, кл. 6 06 Г 7/49, 1983. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ К(57) Изобретение относится к вычислительной технике и может быть использовано при проектировании устройств, выполняющих Изобретение относится к вычислительной технике и может быть использовано при проектировании устройств, выполняющих модульные операции.Цель изобретения - упрощение устройства и расширение функциональных возможностей за счет умножения чисел по произвольному модулю.На фиг.1 показана схема устройства умножения по модулю К = 5; на фиг.2 - схема устройства умножения по модулю К = 11.Устройство умножения по модулю К содержит блок 1 формирования частичных произведений, группу элементов ИЛИ 2, преобразователь 3 двоичного кода в код по модулю К, входы 4 и выходы 5, Блок 1 формирования частичных произведений соединен входами с входными шинами 4 устройства, а выходами - с входами группы 2 элементов ИЛИ и преобразователя 3 двомодульные операции. Цель изобретен упрощение устройства и расширение ф циональных возможностей за счет умн ния чисел по произвольному мод Устройство содержит блок формиров частичных произведений 1, группу эле тов ИЛИ 2, преобразователь 3 двоич кода в код по модулю К, входы 4 и выхо Группа элементов ИЛИ 2 позволяет у шить разрядность кода за счет объедин выходов одного веса элементов И бло на которых невозможно одновременно явление единичных сигналов, что обес вает упрощение преобразователя соответственно, устройства в целом. 2 ичного кода в код по модулю К, соединенно евайго также входами с выходами элементовИЛИ группы 2, а выходами - с выходами 5 Оустройства. Блок 1 формирования частич- Оных произведений содержит Р элементов И, - фгде 1 - разрядность входных. кодов. Каждый Соиз элементов соединен первым входом с(Додной из входных шин первого сомножите-Д,ля, а вторым входом - с одной из входныхшин второго сомножителя таким образом,что на входах элементов И образуются всенеповторяющиеся комбинации пар входных, дшин сомножителей,Преобразователь 3 двоичного кода вкод по модулю К может иметь любую иэизвестных схемных реализаций, в том числеможет быть выполнен в виде блока 6 весо-вого суммирования, входы которого являются входами преобразователя, а выходысоединены с входами узла 7 суммированияпо модулю К, Блок 6 весового суммирования выполнен на сумматорах двоичных чисел, соединенных параллельна-последовательно, причем выходы каждого из сумматоов, кроме последнего, с весом в соединены с входами последующих сумматоров с весами о такими, что их сумма равна в) пос К. На выходах блока 6 суммирования формируется=- )о 92(К+1)" + 1-разрядный код. Узел 7 суммирования по модулю К выполнен в виде порогового блока 9, соединенного выходами с первой группой входов выходного сумматора 8, вторая группа вхоцов которого соединена с входами порогового блока 9 и входами узла суммирования, причем с входами выходного сумматора 8 соединяктся входы узла 7, соответствующие (1-1) младшим разрядам входного кода, а с входами порогового блока все 1 входов узла, Когда код на входах узла 7 суммирования по модулю К менее 2 К, пороговый блок 9 выполняют в виде порогового элемента с весами входов а = 2 ( = 11) и порогом К на последоваь 1тельно соединенных элементах И и ИЛИ. Выход блока соединен с входами разрядов выходного сумматора 8 с номерами, равными номерам единичных разряцов в двоичном представлении числа С = 2 - Кчто при К=5 составляет С=2 -5=:3, Всоответствииэ,- " этим выход порогового блока соединен с входами первого и второго разрядов сумматора 8, Если входной код узла 7 суммирования па модулк К равен или превышает 2 К, пороговый блок выполняют в виде мнагопорогового элемента 10, соединенного выходами с входами блока 11 формирования вычетов. Многопороговый блок элемент 10 имеет входы с весами 2 ( == О, 11-1) и порогами выходов А = К, 2 К а К (где а = - , гп - максимальное значение хода на входах многопорагового элемента 10), Блок 11 формирования вычетов в общем случае содержит (а) элементов запрета, выходы которых соединены с входами 1 элементов ИЛИ. )-й элемент запрета соединен прямым входом с выходом многопороговога элемента с порогом )К, а инверсным входом - с его выходом с порогом+ 1) К, р-й элемент ИЛИ соединен выходом - с входом р-го разряда выходного сумматора 8, а входами - с выходами элементов запрета с номерами ), для которых в двоичном представлении числа В =- 2 - 1 К в о-м разряде имеется единица ( =- 0,1; В0), а также с выходом мнагопорогового элемента с порогом а К, если в р-м разряде числа В = 2 - а К имеется единица, Для К =- 11 В = 5, В 2 =10,5 10 15 20 25 30 35 40 45 50 55 Каждый элемент ИЛИ группы 2 соединен входами с выходами блока 1, имеющими одинаковые веса, на которых невозможно одновременное появление единичных сигналов,Устройство работает следующим образом.Коды сомножителей Х и У поступают на входы блока 1 формирования частичных произвеуений, на выходах которого формируется т -разрядный двоичный код, где т = =3092 (К+ 1)1, имеющий веса разрядов, равные произведениям весов разрядов входного кода.Сигналы с части выходов блока 2, на которых возможно одновременное появление единичных сигналов поступают на входы блока 6 весового суммирования преобразователя 3 двоичного када в код по моцулю К, аостальные- на входы элементов ИЛИ группы 2, а с их выходов - также на входы блока б, При этом элементы ИЛИ 2 сокращают разрядность кода на входах преобразователяя 3. Преобразователь 3 формирует кад остатка входного када по модулю К, Сначала блок б весового суммирования формирует на своих выходах путем последовательной свертки= 1 о 92(К+ Я+ 1-разрядный двоичный код, остаток по модулю К которого равен остатку па модулю К произведения входных кодов. Сигналы (1-1) младших разрядов кода с выходов блока 6 поступают на первую группу входов узла 7 суммирования па модулю К, кроме того - на входы порогового блока, на выходах которого формируются сигналы кода вычета, поступающие на вторую группу входов вьходного сумматора 8, причем код на выхоцах блока 9 формируется таким образом, что, суммируясь с кодом. поступающим на другую группу входов сумматора 8, он формирует,на его выходах суммы код остатка по модулю К входного кода блока 7, т,е, код остатка по модулю К произведения входных кодов Х и У.Формула изобретения Устройство для умножения па модулю К, содержащее блок формирования частичных произведений, состоящий из т элементов И, где т = 11 о 92(К+1), и преобразователь двоичного кода в код по модулю К, выходы которого соединены с выходами разрядов результата устройства, входы разрядов первого и второго сомножителей устройства соединены с первыми и вторыми входами соответствующих элементов И блока формирования частичных произведений, выходы которых соединен ы с входами соответствующих весов преобразователя двоичного кода в код по модулю К, о т л и -ча ю щееся тем,что,сцельюупрощения устройства и расширения функциональных возможностей эа счет умножения чисел по произвольному модулю, в него введена группа элементов ИЛИ, причем входы каж дого элемента ИЛИ группы соединены с выходами одного веса соответствующих элементов И блока формирования частичных произведений, а выходы элементов ИЛИ группы - с входами соответствующих весов преобразователя двоичного кода в код по модулю К,