Устройство для умножения двух чисел Советский патент 1991 года по МПК G06F7/52 

On

8, In

вп+i

О

ON

О СЛ Ю

Р

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

Целью изобретения является расширение функциональных возможностей за счет обеспечения умножения двоичных чисел по трем взаимно простым модулям: MI 2, М2-2п-1,Мз 2п + 1.

На фиг. 1 представлена структурная схема устройства для умножения двух чисел; на фиг. 2 - структурная схема блока анализа сомножителей; на фиг. 3 - структурная схема блока приведения по модулю.

Устройство для умножения двух чисел (фиг. 1) содержит регистры множимого 1 и множителя 2, блок 3 формирования частичных произведений, регистры младших 4 и старших 5 разрядов произведения, элемент НЕ 6, первую 7 и вторую 8 группы элементов И, n-разрядный сумматор 9, блок 10 коррекции результата, блок 11 синхронизации, (п + 1)-разрядный мультиплексор 12, элемент ИЛИ 13, блок 14 анализа сомножителей, блок 15 приведения по модулю.

Блок 14 анализа сомножителей (фиг. 2) содержит n-разрядный мультиплексор 16, элементы НЕ 17, 18, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 19, элементы И 20 - 23. п-разряд- ный мультиплексор 24, элементы ИЛИ 25 - 27.

Блок 15 приведения по модулю (фиг. 3) содержит элемент НЕ 28, элемент ИЛИ 29, n-разрядные мультиплексоры 30,31, п-раз- рядные сумматоры 32, 33, элементы И 34 - 37.

Работа устройства для умножения двух чисел в зависимости от уровней сигналов на входах выбора режима возможна в одном из трех режимов: при 1 на входах Режим 1м и Режим 2 устройство производит умножение по модулю Mi 2П; при О на входе Режим Г и 1 на входе Режим 2 устройство производит умножение по модулю М2 - при О на входах Режим 1 и Режим 2 устройство производит умножение по модулю Мз .

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

Разряды at,.... ап множимого и bi,.... bn множителя поступают на регистры 1 и 2 соответственно. Далее они передаются на входы сомножителей блока 3, на выходах которого формируется, результат обычного умножения, представляющий собой число с

2п-двоичными разрядами. По сигналу приема младшие разряды заносятся в регистр 4, а старшие в регистр 5.

В режиме вычислений по модулю Mi на выходах элементов И первой группы появляются сигналы О. Тогда на выходах СИ, ..., Qn n-разрядного мультиплексора 12 появляются младшие разряды произведения, а на выходах элемента ИЛИ 13 и эле0 ментов И второй группы, начиная со второго Qn+i,.... Q2n - старшие разряды.

В режиме вычисления по модулю М2 на выходах элементов И первой группы появляются сигналы 1, соответствую5 щие старшим разрядам произведения, а на выходах элементов И второй группы сигналы О. Сумматор 9 производит сложение чисел, образованных младшими и старшими разрядами. За время двух сложений (сложе0 ние слагаемых и прибавление переноса) на выходах СИQn сумматора 9 формируются разряды умножения по модулю М2 . После коррекции в блоке 10 через вторые входы n-разрядного мультиплексора 12 ре5 зультат умножения появляется на выходах

ОГQ устройства.

В оежиме умножения по модулю Мз р 2П +1 работа устройства происходит по правилам модульной арифметики для чисел

0 Ферма.

Так как кольцо ZM чисел, участвующих в операциях по модулю М 2п+1, имеет порядок п, то для представления n-го числа из ZM необходимо (п+1) разрядов. Из структуры

5 модуля Мз 2п+1 вытекает равенство Мз-1 2 (-1) mod Мз, с учетом которого при умножении числа, равного Мз -1, кольца ZM на любое число Ь|( -1) из этого кольца результат получается в виде отрицательного

0 числа Ь. При умножении двух чисел, равных Мз - 1, с учетом указанного равенства результат получается равным единице по модулю Мз, так как (-1) (-1) 1. Умножение О 0 по модулю Мз соответствует результату

5 обычного умножения. При умножении лю- бых чисел ai(ai 1,Мз-2)и bi(bi 1 , Мз-2) из кольца ZM алгоритм умножения следующий: сначала производится обычное умножение, затем инвертированные старшие

0 разряды произведения с младшими. Если в результате сложения перенос из старшего разряда равен единице, то результат корректируется прибавлением единицы, если перенос из старшего разряда равен нулю 5 к результату прибавляется двойка.

В режиме умножения по модулю Мз 2 + 1 устройство работает следующим образом.

На входах элементов И второй группы

присутствуют сигналы О, что приводит к

нулевым сигналам на выходах Qn+2Q2n.

О с входа Режим 2 переключает мультиплексор 12 на вывод результата из блока 15

приведения по модулю на выходы QiQn

устройства и первый вход элемента ИЛИ 13, выход которого является выходом Qn+1 разряда устройства. Таким образом, результат умножения с выходов регистров 4 и 5, приведенный по модулю Мз 2п+1 в блоке 15, появляется на выходах QiQn+i устройства. Блок 14 анализа сомножителей предназначен для анализа разрядов сомножителей и выработки сигналов управления блоком 15 приведения по модулю.

Блок 14 анализа сомножителей (фиг.2) работает следующим образом.

На входы И, .... 1П и di dn блока

поступают младшие п разрядов множимого и множителя соответственно. На входы ап+1 и bn+1 поступают старшие разряды множимого и множителя соответственно. При 1 на выходах ап-м и bn-и, т. е. при умножении чисел, каждое из которых равно (М+1), на выходе элемента И 21 формируется сигнал 1, который через элемент ИЛИ 27 формирует на выходе К блока сигнал блокировки данных, а через элемент ИЛИ 26 поступает на вход адреса разрядного мультиплексора 16. что поиволит к появлению на выходах hi1,..., hn1 блока сигналов О. Г на выходе элемента И 21 является также сигналом коррекции по старшим разрядам на выходе f1 блока. При этом на выходе д1 блока формируется сигнал блокировки по нулю в виде Г. Лри Г на одном из входов ап+1 или Ьп+1 (например Uan 1 . 0, т. е. при умножении чисел ai (М-1) и 0 bi М-1) элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 19 через элемент ИЛИ 27 формирует на выходе К1 блока сигнал блокировки данных в виде 1. При этом на выходе д1 блока формируется сигнал блокировки по нулю в виде 1. Так как на входах элемента И 20 присутствуют сигналы О, то на входе адреса п-раэрядного мультиплексора 24 появится сигнал О, что приводит к передаче на выходы hi , ..., hn блока инвертированных значений разрядов множителя bi, ..., bn, так как на входе адреса n-разрядного мультиплексора 16 также присутствует О с выхода элемента ИЛИ 26. При обратной комбинации сигналов (Uan+ OnUbn-M 1.т.е. приумножении чисел 0 ai М-1 и bi (М-1) на выходах hi1hn1 появятся инвертированные значения разрядов множимого aiап, так как

«а входе адреса n-разрядного мультиплексора 24 присутствует с выхода элемента И 20 сигнал 1. На выходе f1 блока при этом присутствует сигнал О.

При О во всех разрядах множимого

(О на входах И п и ап+1 блока) или

множителя (О на входах didn и Ьп-и)при

1 хотя бы в одном из разрядов множителя

5 (1 хотя бы на одном из входов didn или

bn+1 блока) или множимого (1 хотя бы на

одном из входов Н1П или bn+1 блока), т. е.

приумножении чисел 0 bi при 0 bi М-1 или ai 0 при 0 ai М-1 на выходе элемента

10 И 23 (во втором случае, элемента И 22) появляется сигнал 1, который формирует сигналы блокировки по нулю (О) и блокировки данных (1) на соответствующих выходах блока, а также обеспечивает появление сиг15 налов О на выходах hi hn блока, так

как на входе адреса n-разрядного мультиплексора 16 присутствует сигнал Г. На выходе f1 блока при этом присутствует сигнал О.

0При О на всех входах блока, т. е. при

отсутствии входных данных, на выходах д,

fi1, hi1 hn1 блока присутствуют сигналы

0й, а на выходе К блока - сигнал 1. Блок 15 приведения по модулю работает следую5 щим образом.

При 1 на входе К блока п-разрядные мультиплексоры 30, 31 переключаются в положение, обеспечивающее поступление сигналов с входов hi, ..., hn блока на входы

0 первого слагаемого третьего п-разрядного сумматора 32 и сигналов О - на входы второго слагаемого n-разрядного сумматора 31. При О на входе К1 блока n-разрядные мультиплексоры 30, 31 пе5 реключаются в положение, обеспечивающее поступление сигналов с входов mi, ..., mn и pi, ..., pn блока на входы соответственно первого и второго слагаемых п- разрядного сумматора 32, т. е. на входы

0 n-разрядного сумматора 32 поступают младшие и инвертированные старшие разряды произведения. Результат сложения в n-разрядном сумматоре 32 поступает на входы первого слагаемого п-разрядного

5 сумматора 33, на входы второго слагаемого поступают сигналы переносов из п-разрядного сумматора 32 или с выхода элемента И 21 блока 14 анализа сомножителей при 1 на входе g блока 15. При

0 сигнале переноса из n-разрядного сумматора 32 О на вход второго слагаемого n-разрядного сумматора 33 поступает число, равное двойке, при 1 на выходе переноса n-разрядного сумматора 32 (или

5 выходе элемента И 21 блока 14 анализа сомножителей) на вход второго слагаемого n-разрядного сумматора 33 поступает число, равное единице. При О на входе g блока переносы запрещены.

Формула изобретения Устройство для умножения двух чисел по авт. св. Ns 1179322, отличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения ум- ножения двоичных целых чисел по трем взаимно простым модулям Mi 2n, M2 2 , Мз 2 , в него введены (п+1)-разрядный мультиплексор, элемент ИЛИ, блок анализа сомножителей, сг ржащий два элемента НЕ, четыре элемента И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, три элемента ИЛИ и два п-раз- рядных мультиплексора, и блок приведения по модулю, содержащий два п-разрядных сумматора, четыре элемента И, элемент ИЛИ и элемент НЕ, причем в устройстве выход элемента ИЛИ соединен с выходом первого старшего разряда произведения устройства, выходы младших разрядов произведения которого соединены соответственно с выходами разрядов (п+1)-разрядного мультиплексора, выход (п+1)-го разряда которого соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом первого элемента И второй группы, второй вход установки режима работы устройства соединен с входом адреса (п+1)-разрядного мультиплексора, вход стробмрования которого соединен с соответствующим выходом блока синхрониза- ции, вход нулевого потенциала устройства соединен с информационным входом (п+1)- го разряда первой группы (п+1)-го разрядного мультиплексора, информационные входы п разрядов первой группы которого соединены соответственно с п выходами блока коррекции, а в блоке анализа сомножителей информационные входы первой группы первого n-разрядного мультиплексора соединены соответственно с выходами регистра множимого и п инверсными входами первого элемента И, (п+1)-й инверсный вход которого соединен с первыми входами второго элемента И и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, входом первого элемента НЕ и входом (п+1)-го разряда множимого устройства, информационные входы второй группы первого n-разрядного мультиплексора соединены соответственно с выходами регистра множителя и инверсными входами третьего элемента И, (п+1)-й инверсный вход которого соединен с вторыми входами второго элемента И и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, входом (п-М)-го разряда множителя устройства и первым входом четвертого элемента И, второй вход которого соединен с выходом первого элемента НЕ, а выход -с входом адреса первого п-раз- рядного мультиплексора, выходы которого соединены соответственно с информационными входами первой группы второго п- разрядного мультиплексора, информационные входы второй группы которого соединены с входом единичного потенциала устройства, а вход адреса - с выходом первого элемента ИЛИ, первый вход которого соединен с первым входом второго элемента ИЛИ, входом второго элемента НЕ и входом третьего элемента ИЛИ, первый и второй входы которого соединены с выходами первого и третьего элементов И, второй вход первого элемента ИЛИ соединен с вторым входом второго элемента ИЛИ и выходом второго элемента И, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с третьим входом второго элемента ИЛИ, входы стро- бирования первого и второго п-разрядных мультиплексоров соединены с соответствующими выходами блока синхронизации, а в блоке приведения по модулю информационные входы первой группы первого п-раз- рядного мультиплексора соединены соответственно с инверсными выходами второго n-разрядного мультиплексора блока анализа сомножителей, информационные входы второй группы первого n-разрядного мультиплексора соединены соответственно с выходами регистра младших разрядов произведения, вход адреса первого n-разрядного мультиплексора соединен с выходом второго элемента ИЛИ блока анализа сомножителей и входом адреса второго n-разрядного мультиплексора, информационные входы первой группы которого соединены с входом единичного потенциала устройства, выходы регистра старших разрядов произведения соединены соответственно с информационными входами второй группы второго п-разряд- ного мультиплексора, инверсные выходы которого соединены соответственно с входами первого слагаемого первого п-разряд- ного сумматора, входы второго слагаемого которого соединены соответственно с выходами первого n-разрядного мультиплексора, а выходы суммы - соответственно с входами первого слагаемого второго п-раз- рядного сумматора, выходы суммы которого соединены соответственно с инверсными входами первого элемента И и информационными входами п разрядов второй группы (п+1)-разрядного мультиплексора, информационный вход (п+1)-го разряда второй группы которого соединен с выходом второго элемента И, первый вход которого соединен с выходом первого элемента И, а второй вход - с выходом переноса второго п-раз- рядного сумматора, вход первого разряда второго слагаемого которого соединен с выходом элемента ИЛИ, первый вход которого

соединен с выходом третьего элемента И, первый вход которого соединен с выходом переноса первого n-раэрядного сумматора и входом элемента НЕ, выход которого соединен с первым входом четвертого элемента И, второй вход которого соединен с вторым входом третьего элемента И и выходом второго элемента НЕ блока анализа сомножителей, выход второго элемента И которого соединен с вторым входом элемен0

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

Изобретение относится к вычислительной технике и радиотехнике и может быть использовано в устройстве цифровой обработки сигналов, например, изображений и в устройствах, работающих в системе остаточных классов, а также в системах кодирования, принцип действия которых базируется на теории полей Галуа. Цель изобретения - расширение функциональных возможностей за счет обеспечения умножения двоичных целых чисел по трем взаимно простым модулям: M₁ = 2^N, M₂ = 2^N - 1, M₃ = 2^N + 1. Устройство содержит регистры множимого 1 и множителя 2, блок 3 формирования частичных произведений, регистры младших 4 и старших 5 разрядов произведения, элемент НЕ 6, первую 7 и вторую 8 группы элементов И, N-разрядный сумматор 9, блок 10 коррекции результата, блок 11 синхронизации, блок 14 анализа сомножителей, блок 15 приведения по модулю, (N + 1)-разрядный мультиплексор 12 и элемент ИЛИ 13. 3 ил.

Фиг. 2