Устройство для умножения двух чисел

 

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

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

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

РЕСПУБЛИК (я)з G 06 F 7!52

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

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

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

0 (Ь

О

Ql

Ре

Ре

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1179322 (21) 4718328/24 (22) 11.07.89 (46) 30.07.91. Бюл. М 28 (71) Научно — исследовательский институт бытовой радиоэлектронной аппаратуры (72) Л.В. Вариченко и В.И. Кодров (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Q 1179322, кл. G 06 F 7/52, 1984, (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ

ДВУХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и радиотехнике и может быть .использовано в устройстве цифровой обработки сигналов, например, изображений и в устройствах, работающих в системе остаBfl аю+

„„Я2,„, 1667059 А2 точных классов, а также в системах кодирования, принцип действия которых базируется на теории полей Галуа. Цель изобретения — расширение функциональных возможностей за счет обеспечения умножения двоичных целых чисел по трем взаимно простым модулям: М1 = 2", М2 = 2" — 1, Мз = 2" + 1.

Устройство содержит регистры множимого

1 и множителя 2; блок 3 формирования частичных произведений, регистры младших 4. и старших 5 разрядов произведения, элемент НЕ 6, первую 7 и вторую 8 группы элементов И, и — разрядный сумматор 9, блок

10 коррекции результата, блок 11 синхронизации, блок 14 анализа сомножителей, блок

15 приведения по модулю, (и+ 1)-разрядный мультиплексор 12 и элемент ИЛИ- 13. 3 ил.

1667059

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

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

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

Устройство для умножения двух чисел ! (фиг, 1) содержит регистры множимого 1 и множителя 2, блок 3 формирования частичных произведений, регистры младших 4 и старших 5 разрядов произведения; элемент

НЕ 6, первую 7 и вторую 8 группы элементов

И, п-разрядный сумматор 9, блок 10 коррекции результата, блок 11 синхронизации, (п + 1)-разрядный мультиплексор 12, элемент ИЛИ 13, блок 14 анализа сомножите, лей, блок 15 приведения по модулю.

Блок 14 анализа сомножителей (фиг. 2)

, содержит п-разрядный мультиплексор 16,, элементы НЕ 17, 18, элемент ИСКЛЮЧАЮ, ЩЕЕ ИЛИ 19, элементы И 20 — 23, и-разрядный мультиплексор 24, элементы ИЛИ 25—

27.

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

37.

Работа устройства для умножения двух чисел в зависимости от уровней сигналов на входах выбора режима возможна в одном из трех режимов: при "1" на входах "Режим 1" и "Режим 2" устройство производит умно"жение по модулю M1 = 2"; при "О" на входе

"Режим 1" и "1" на входе "Режим 2" устройство производит умножение по модулю М2- 2" 1; при "О" на входах "Режим 1" и

"Режим 2" устройство производит умножеwe по модулю Мз = 2"" ..

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

РаэрядЫ а1, ..., an МНОжИМОГО И b1, ..., bn множителя поступают на регистры 1 и 2 соответственно, Далее они передаются на входы сомножителей блока 3, на выходах которого формируется. результат обычного умножения, представляющий. собой число с

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

4, а старшие в регистр 5.

В режиме вычислений по модулю М15 =2" на выходах элементов И первой группы появляются сигналы "О", Тогда на выходах

Q1, ..., Qn и — разрядного мультиплексора 12 появляются младшие разряды произведения, а на выходах элемента ИЛИ 13 и элементов И второй группы, начиная со второго

Qn+1i ..., Q2n — старшие разряды.

В режиме вычисления по модулю М2 =

=2"" на выходах элементов И первой группы появляются сигналы "1". соответствующие старшим разрядам произведения, а на выходах элементов И второй группы сигналы "О". Сумматор 9 производит сложение

«О по модулю Мз соответствует результату

55 обычного умножения. При умножении любых чисел at(at= 1,Мз-2) и bt(bt= 1, Мз-2) иэ кольца Z алгоритм умножения следующий: сначала производится обычное умножение, звтем инвертированные старшие разряды произведения с младшими. Если в результате сложения перенос из старшего разряда равен единице, то результат корректируется прибавлением единицы, если перенос из старшего разряда равен нулю— к результату прибавляется двойка.

В режиме умножения по модулю Мз =

=2" + 1 устройство работает следующим образом.

На входах элементов И,второй группы присутствуют сигналы "О", что приводит к чисел, образованных младшими и старшими разрядами. 3а время двух сложений (сложе20 we слагаемых и прибавление переноса) на выхоДах Q1, ..., Qn сУмматоРа 9 фоРмиРУются разряды умножения по модулю М2=2" 1.

После коррекции в блоке 10 через вторые входы и — разрядного мультиплексора 12 ре25 зультат умножения появляется на выходах

Q1",..., Q" уСтрсйСтва, .В оежиме умножения по модулю Мз =

2" + 1 работа устройства происходит по правилам модульной арифметики для чисел

30 Ферма.

Так как кольцо Zt«чисел, участвующих в операциях по модулю M = 2"+1, имеет порядок и, то для представления и-го числа из

Z< необходимо (и+1) разрядов. Из структуры

35 модуля Мз=2"+1 вытекаетравенство Мз-1=

- 2" = (-1) mod Мз, с учетом которого при умножении числа, равного Мз - 1, кольца Z на любое число bt(bt "Ìç - 1) из этого кольца результат получается в виде отрицательного

40 числа Ь. При умножении двух чисел, равных

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

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

"0" с входа "Режим 2" переключает мультиплексор 12 на вывод результата из блока 15 приведения по модулю на выходы 01, ..., Q> устройства и первый вход элемента ИЛИ 13, ВЫХОД КОтсрОГО яВЛяЕтСя ВЫХОДОМ Ол+1 раэряда устройства, Таким образом, результат умножения с выходов регистров 4 и 5, приведенный по модулю Мз = 2"+1 в блоке 15, ПОяВЛяЕтСя На ВЫХОдаХ Q1, ..., Оп+1 уСтрсйСтва. Блок 14 анализа сомножителей предназначен для анализа разрядов сомножителей и выработки сигналов управления блоком

15 приведения по модулю.

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

На входы I1, „., 1 и d1, ..., d> блока поступают младшие и разрядов множимого и множителя соответственно. На входы а +1 и Ьп+1 поступают старшие разряды множимого и множителя соответственно. При "1"

На ВЫХОдаХ ал+1 И bn+1, т. Е. ПрИ уМНОжЕНИИ чисел, каждое из которых равно (М+1), на выходе элемента И 21 формируется сигнал

"1", который через элемент ИЛИ 27 формирует на выходе К блока сигнал блокировки данных, а через элемент ИЛИ 26 поступает на вход адреса разрядного мультиплексора

16. что поиводит к появлению на выходах

h1 ...„h " блока сигналов "0". "1" на выходе элемента И 21 является также сигналом коррекции по старшим разрядам на выходе f блока. При этом на выходе g блока форми1 руется сигнал блокировки по нулю в виде

"1". ПрИ "1" На ОДНОМ ИЗ ВХОДОВ ал+1 ИЛИ Ьп+1

- (например О»+1 =1,0ь„ 1 =О, т. е. при умножении чисел а1 = (M-1) и 0 < bl < М-1) элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 19 через элемент ИЛИ 27 формирует на выходе К блока сигнал блркировки данных в виде "1".

При этом на выходе g . блока формируется сигнал блокировки по нулю в виде "1". Так как на входах элемента И 20 присутствуют сигналы "0", то на входе адреса и — разрядного мультиплексора 24 появится сигнал "0", что приводит к передаче на выходы h1, ..., h>

1 1. блока инвертированных значений разрядов множителя b1, ..., b>, так как на входе адреса и-разрядного мультиплексора 16 также присутствует "0" с выхода элемента ИЛИ 26. При обратной комбинации сигналов (0»+ = 0 и UbÄ+ g = 1, т. е, при умножении чисел 0 < a1 < M-1 и Ь| = (М-1) на выходах

h1, ..., hn появятся инвертированные эна1 1 чения разрядов множимого а1, ..., a>, так как на входе адреса и — разрядного мультиплексора 24 присутствует с выхода элемента И

20 сигнал "1". На выходе f1 блока при этом . присутствует сигнал "0".

При "0" во всех разрядах множимого ("0" на входах I1, ..., 4 и а +1 блока) или множителя (0 на входах d1, „., dn и bn+1) при

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

5 ("1" хотя бы на одном из входов d1, ..., d или

Ьл+1 блока) или множимого ("1" хотя бы на одном из входов (1, „., In или bn+1 блока), т, е. при умножении чисел 0 ° bi при 0 < bi М-1 или а 0 при 0 < а М-1 на выходе элемента

10 И 23 (во втором случае, элемента И 22) появляется сигнал "1", который формирует сигналы блокировки по нулю ("0") и блокировки данных (."1") на соответствующих выходах блока, а также обеспечивает появление сиг15 налов "0" на выходах h1 ..., hn блока, так как на входе адреса п — разрядного мультиплексора 16 присутствует сигнал "1". На выходе f блока при этом присутствует сигнал

"0".

20 При "О" на всех входах блока, т. е. при отсутствии входных данных, на выходах g, 1

f1., h1, ..., hn блока присутствуют сигналы

1 1 1

"0", а на выходе К блока — сигнал "1". Блок

15 приведения по модулю работает следую25 щим образом, При "1" на входе К блока n — разрядные мультиплексоры 30, 31 переключаются в положение, обеспечивающее поступление сигналов с входов h1, „„h блока на входы

30 первого слагаемого третьего и — разрядного сумматора 32 и сигналов "0" — на входы второго cnaraeMoro и — разрядного сумматора 31. При "0" на входе К блока п — разрядные мультиплексоры 30, 31 пе35 реключаются в положение, обеспечивающее поступление сигналов с входов m1, ..., mï и р1, ..., рп блока на входы соответственно первого и второго слагаемых п.— разрядного сумматора 32, т. е. на входы

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

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

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

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

1667059

ЮЩЕЕ ИЛИ, входом первого элемента НЕ и 45 гистра множителя и инверсными входами 50

Формула изобретения

Устройство для умножения двух чисел по авт. св, М 1179322, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения умножения двоичных целых чисел по трем взаимно простым модулям М1=2, М2=2п

Мз = 2", в него введеНы (n+1) — разрядный мультиплексор, элемент ИЛИ, блок анализа сомножителей, сг лежащий два элемента, НЕ, четыре элемента И, элемент ИСКЛЮЧА1

ЮЩЕЕ ИЛИ, три элемента ИЛИ и два и — разрядных мультиплексора, и блок приведения по модулю, содержащий два и — разрядных ! сумматора, четыре элемента И, элемент ИЛИ и элемент НЕ, причем в устройстве выход элемента ИЛИ соединен с выходом, первого старшего разряда произведения ус-!, тройства, выходы младших разрядов произ ведения которого соединены соответственно с выходами разрядов (n+1)-разрядного, мультиплексора, выход (n+1) — го разряда ко торого соединен с первым входом элемента, ИЛИ, второй вход которого соединен с вы ходом первого элемента И второй группы, второй вход установки режима работы устройства соединен с входом адреса ; (и+1) — разрядного мультиплексора, вход стробмрования которого соединен с соот ветствующим выходом блока синхрониза, ции, вход нулевого потенциала устройства соединен с информационным входом (п+1)— го разряда первой группы (n+1)-го разрядного мультиплексора, информационные входы и разрядов первой группы которого соединены соответственно с и выходами блока коррекции, а в блоке анализа сомножителей информационные входы первой группы первого и — разрядного мультиплек, сора соединены cOQTBBTGTBBHHQ с выходами регистра множимого и и инверсными входами первого элемента И, (и+1) — и инверсный вход которого соединен с первыми входами, второго элемента И и элемента ИСКЛЮЧАвходом (и+1) — ro разряда множимого устройства, информационные входы второй группы первого п — разрядного мультиплексора соединены соответственно с выходами ретретьего элемента И, (и+1) — и инверсный вход которого соединен с вторыми входами второго элемента И и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, входом (и+1)-ro разряда множителя устройства и первым входом четвертого элемента И, второй вход которого соединен с выходом первого элемента

Н Е, а выход — cвходом адрес:а первого и-разрядного мультиплексора, выходы которого

Соединены соответственно с информацион5

40 ными входами первой группы второго n— разрядного мультиплексора, информационные входы второй группы которого соединены с входом единичного потенциала устройства, а вход адреса — с выходом первого элемента ИЛИ, первый вход которого соединен с первым входом второго элемента ИЛИ, входом второго элемента НЕ и входом третьего элемента ИЛИ, первый и второй входы которого соединены с выходами первого и третьего элементов И, второй вход первого элемента ИЛИ соединен с вторым входом второго элемента ИЛИ и выходом второго элемента И, выход элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с третьим входом второго элемента ИЛИ, входы стробирования первого и второго и-разрядных мультиплексоров соединены с соответствующими выходами блока синхронизации, а в блоке приведения по модулю информационные входы первой группы первого n— - разрядного мультиплексора соединены соответственно с инверсными выходами второго п — разрядного мультиплексора блока анализа сомножителей, информационные входы второй группы первого и-разрядного мультиплексора соединены соответственно с выходами регистра младших разрядов произведения, вход адреса первого и — разрядного мультиплексора соединен с выходом второго элемента ИЛИ блока анализа сомножителей и входом адреса второго и-разрядного мультиплексора, информационные входы первой группы которого соединены с входом единичного потенциала устройства, выходы регистра старших разрядов произведения соединены соответственно с информационными входами второй группы второго n — разрядного мультиплексора, инверсные выходы которого соединены соответственно с входами первого слагаемого первого и — разрядного сумматора, входы второго слагаемого которого соединены соответственно с выходами первого п — разрядного мультиплексора, а выходы суммы — соответственно с входами первого слагаемого второго и-разрядного сумматора, выходы суммы которого соединены соответственно с инверсными входами первого элемента И и информационными входами п разрядов второй группы (п+1)-разрядного мультиплексора, информационный вход (n+1) — го разряда второй группы которОго соединен с выходом второго элемента И, первый вход которого соединен с выходом первого элемента И, а второй вход — с выходом переноса второго и-разрядного сумматора, вход первого разряда второго слагаемого которого соединен с выходом элемента ИЛИ, первый вход которого

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

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

1667059

Составитель Е. Мурзина

Редактор О., Спесивых Техред M.Ìîðãåíòàë Корректор .О. Кравцова

Заказ 2524 Тираж 396 Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101