Матричное устройство для умножения чисел по модулю 2 @ -1

Матричное устройство для умножения чисел по модулю 2 @ -1

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области вычислительной и технической кибернетики и может быть использовано в устройствах для цифровой обработки сигналов (в частности изображений), а также в системах кодирования, принцип действия которых базируется на теории полей Галуа. Целью изобретения является повышение быстродействия устройства . Поставленная цель достигается тем, что блок суммирования частичных произведений вьшолнен в виде древовидной группы линеек, блок коррекции результата содержит п-входовой элемент И-НЕ и группу п элементов И, введены группа элементов И и группа сумматоров по модулю два. Введение группы элементов И и группы сумматоров по модулю два и новых связей, а также новое вьшолнение блока суммирования частичных произведений и блока коррекции результата позволило повысить быстродействие устройства. 2 3. п. ф-лы, 6 ил. с SS (Л

СО)ОЗ СОВЕТСНИХ

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

РЕСПУБЛИК

А1 (19) (11) (51)4 G 6F 749

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

К ABTOPCHOIVlY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2 1) 3855609/24-24 (22) 11.02 ° 85 (46) 30,08.86. Бюл. ¹ 32 (72) Л.В.Вариченко, О.И.Гречникова

К.Н.Новиков, P.Á.Ïoïîâè÷ и Ю.А.Томин (53) 681.325(088.8) (56) Авторское свидетельство СССР № 900281, кл. G 06 F 7/52, 1979.

Авторское свидетельство СССР № 959068, кл. G 06 F 7/52, 1980.

Патент Японии № 54-20102, кл. G 06 F 7/39, опублик. 1979.

Авторское свидетельство СССР № 1160398, кл. С 06 F 7/49, 1983. (54) МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ 2"-1 (57) Изобретение относится к области вычислительной и технической кибернетики и может быть использовано в устройствах для цифровой обработки сигналов (в частности изображений), а также в системах кодирования, принцип действия которых базируется на теории полей Галуа. Целью изобретения является повышение быстродействия устройства. Поставленная цель достигается тем, что блок суммировайия частичных произведений выполнен в виде древовидной группы линеек, блок коррекции результата содержит и-входовой элемент И-НЕ и группу и элементов И, введены группа элементов И и группа сумматоров по модулю два. Введение группы элементов И и группы сумматоров по модулю два и новых связей, а а также новое выполнение блока суммиро- 8 вания частичных произведений и блока коррекции результата позволило повысить быстродействие устройства. С:

2 э. п. ф-лы, 6 ил.

1254471

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

Целью изобретения является повышение быстродействия устройства. !О

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

Матричное устройство для умножения чисел по модулю 2 — 1 (фиг.1) содержит блок 1 формирования частичных произведений, блок 2 суммирования 25 частичных произведений, и-разрядный сумматор 3, блок .4 коррекции результата, группу (и-1) элементов И 5 и группу сумматоров 6 по модулю два. В и-разрядном сумматоре 3 р — вход пе- 30 реноса, р — выход переноса, А — входы первого слагаемого,  — входы второго слагаемого, S — выходы суммы.

Блок 1 формирования частичных произведений (фиг.2) состоит из двухвхо- З5 довых элементов И 7.

Блок 2 суммирования частичных произведений (фиг.3) состоит из группы линеек 8 одноразрядных сумматоров, q,, ° . ° q „ — входные слова блока сум- 40 мирования частичных произведений, U, V — его выходные слова.

Блок 4 коррекции результата (фиг.4) состоит иэ и-входового элемента И-НЕ 9 и группы элементов И 10.

Линейка длины и (фиг.5) состоит из одноразрядных сумматоров 11, h,, h, h — входы линейки, U — выходы слова суммы линейки, V — - выходы слова переноса линейки, S — вьг од суммь одноразрядного сумматора, р — выход переноса одноразрядного сумматора.

Матричное устройство для умножения чисел по модулю 2 — 1 выполняет умножение двух п-разрядных двоичных чи55 сел по модулю 2" — 1.

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

Множимое А = а„ 2" + а„, " 2" +...

+ а 2 + а, и множитель В = b 2 +

+Ь„, 2" + ... +Ь 2+b поступают на входы блока 1 формирования частичных произведений. Блок 1 образует попарные произведения а;Ь; (i

1, 2, ..., n; j = 1, ... n) Произведения разрядов множимого на младший разряд множителя а„Ь образуют слово q, частичных произведений первой ступени, произведения разрядов множимого на второй разряд множителя а;Ъ обрузуют слово qz частичных произведений второй ступени, ..., произведения разрядов множимого на старший (п-й) разряд множителя а;Ь „ образуют слова q частичных произведений и-й л ступени, причем в k-м разряде слова (k = 1, ... и) стоит произведение а ° Ъ;, где k = (j — i + 1) Mod„((A) х х Modn =- п при и кратном и, (А) Modn равно целому положительному остатку от деления А на и при А не кратномп).

Другими словами, блок 1 формирует циклически сдвинутые по сравнению со случаем обычного множителя слова, так

СС как умножение на число вида 2 равносильно циклическому сдвигу влево на к разрядов п-разрядной двоичной записи множимого (потому что 2 сов- л

h падает с единицей по модулю 2 — 1) .

Таким образом, блок формирования частичных произведений образует следующие слова:

q =аь а.,ь, а Ь аb(° о =. ал, Ь, а„Ь,..., а Ъ,ab,, с = а„.,Ь, а„Ъ, ...,а Ь,а„,Ь

q = а<Ь„, а„Ь„, ..., а Ь„, а Ьл

Блок 2 суммирования частичных произведений представляет собой древовидную структуру из группы линеек 8 одноразрядных сумматоров. Число с линеек одноразрядных сумматоров в первой группе линеек задается соотноГ и шением с - —" где обоэнача(3) ет целую часть числа. На первые третьи входы всех линеек первой группы линеек блока 2 суммирования частичных произведений поступают Зс слов с блока 1 формирования частичных произведений (по три слова на каждую линейку). Каждая линейка 8.состоит иэ и одноразрядных сумматоров 11. В ней происходит поразрядное сложение трех п-разрядных слов h,, h, h> и обра1254471.эуется два и-разрядных результирующих слова U u V. Слово U состоит из значений на выходах суммы одноразрядных сумматоров, причем j-й разряд слова (j = 1, 2, ..., и) совпадает со значением на выходе суммы j-го сумматора, Слово V состоит из значений на выходах переноса одноразрядных сумматоров, причем j-й разряд этого слова (j = 2, ..., n) совпадает с 10 значением на выходе переноса (j-1)го сумматора, а первый разряд — с значением на выходе переноса и-го л сумматора (так как 2 совпадает с л единицей по модулю 2 — 1). На выхо- 15 дах линеек первой группы в результате сложения формируется 2с< слов. Кроме того, имеем и — Зс< входных слов блока 2 суммирования частичных произведений, которые не поступили .на вхо- 20 ды линеек первой группы. <.<бщее число слов после прохождения первой группы линеек древовидной структуры равно

2с„ + n — Зс, = n — с<. Число сг линеек во второй группе линеек задается25 и — с, выражением с = — — — — - т. е. на входы линеек второй группы поступают

3с слов из числа n — с, слов. На выходах линеек второй группы после сложения образуется 2сг слов. Сбщее число слов после прохождения второй группы линеек равно 2с + и — с,— — Зсг = и — с, — с . Число сэ линеек 3 в третьей группе задается соотношении с< сг ем с = - — — — — — — -„т. е, на

:входы линеек третьей группы поступают

3c cJIoH H3 числа n — <- — <-2 cJIGB °

4О

На выходах линеек третьей группы после сложения образуется 2с слов. Общее число слов после прохождения третьей группы линеек равно 2cI+ и — .

-с -с -Зс =и — с -с -с

2 (г Э

Число с4 линеек в четвертой группе линеек задается выражением с.<

Г и с< с с>

= — — — — — - — — и т. д.

Число k групп линеек выбирается таким образом, чтобы после прохождения k группы образовалось два слова, которые являются выходными словами

U u V блока 2.

Результирующие слова U и V складываются с помощью и-разрядного сумматора 3.

Если перенос при сложении не возникает, то на выходах всех элементов

И 5 †нулевые значения. На выходы сумматоров 6 по модулю два пропускается код с выходов блока 4 коррекции результата. В случае, когда хотя бы один из разрядов суммы на выходах сумматора 3 отличен от единицы, на выходе элемента 9 И-НЕ логическая единица, и полученная сумма проходит на выходы элементов И 10 и далее на ,выходы устройства.

В случае равенства всех разрядов суммы на выходах сумматора 3 единице на выходе элемента И-НЕ 9 — логический нуль, и на выходах блока 4 все нули, которые проходят на выходы устройства.

Таким образом, происходит устранение неоднозначности представления нуля в устройстве, возникающее из-за равенства слов 0...00 и 1 ° ..11 и-разрядов и-разрядов по модулю 2" -1.

Если возникает перенос при сложении результирующих слов U и V, то его необходимо прибавить в младший разряд полученной суммы, Заметим, что, так как каждое из слагаемых, поступающих на сумматор 3 не превышаh

У ет 2 -1, то полученная сумма с учетом йереноса не больше 2" +, л

+ (2 — 2), а сумма без учета пел реноса не больше 2 — 2. Это означает, что хотя бы один разряд сум-.

\ мы отличен от единицы, и она проходит на выходы блока 4 коррекции результата. Элемент S;(i = 1, ..., n — 1) формирует перенос из i-го в (i+1)-й разряд при добавлении единицы к полученной на выходах сумматора 3 суммы.

Перенос из i-го в (i+1) и разряд равен единице, если разряды S S;, суммы равны единице, Сумматоры б по модулю два прибавляют образованные переносы к соответствующим разрядам полученной суммы.

На выходах устройства получаем произведение А В по модулю 2"-1, Формула изобретения

1. Матричное устройство для умнол кения чисел по модулю 2 -1, содержацее блок формирования частичных произведений, выполненный в виде матрицы и х и элементов И (n — разрядность множимого и множителя), блок суммирования частичных произведений, 5 1254 и-разрядный сумматор, блок коррекции результата, причем первые входы элементов И i-й строки матрицы (i

1, 2... n) соединены с входом i-го разряда множителя устройства, вторые входы (i, j)-х элементов И (j-номер столбца матрицы, j = 1, 2 ° .. n) соединены с k-м разрядом входа множимого устройства, где k = (j — i + 1) Modn ((A) Mod n = n при А кратном и, (А) Modn равно положительному остатку от деления А/и при А не кратном и), выходы элементов И i-й строки матрицы соединены с информационными входами j-x разрядов i-го слова блока 15 суммирования частичных произведений, выходы разрядов первого и второго результирующих слов которого соединены с информационными входами первого и второго слагаемых п-разрядного сумма- gp тора, вход переноса которого соединен .с шиной логического нуля, группа выходов суммы которого соединена с группой входов блока коррекции результата, о т л и ч а ю щ е е с я тем, 25 что, с целью повышения быстродействия устройства, в него введена группа из (и-1) элементов И, р-й (р = 1, 2... и-1) элемент И имеет (р+1) входов и группа п сумматоров по модулю два, причем q-й (q = 1, 2... р) вход рго элемента И группы соединен с q-м выходом суммы и-разрядного сумматора, выход переноса которого соединен..с (р+1)-ми входами элементов И группы 35 и первым входом первого сумматора по модулю два группы, выходы элементов

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

2. Устройство по п.1, о т л и ч аю щ е е с я тем, что блок коррекции результата содержит и-входовый элемент И-НЕ и группу и элементов И, причем входы элемента И-НЕ, являющиеся входами блока коррекции результата, соединены соответственно с первыми входами элементов И группы, вторые входы которых соединены с выходом элемента И-НЕ, а выходы элементов И: группы являются выходами блока кор-. рекции результата.

3. Устройство по п.1, о т л и ч аю щ е е с я тем, что блок суммирова471 ния частичных произведений состоит из групп линеек длиной п одноразрядных тре ходовых сумматоров, причем число линеек с в m-й группе линеек задается соотношением (m= 2 — k), с

fll 3 где () — целая часть числа ;

k — - число групп линеек, число . линеек в первой группе

Г и 1 линеек равно с, = ††),1

r-й вход (r = 1, 2, 3) j-го. (j = 1, 2... n) трехвходового одноразрядного сумматора 3-й линейки ((— номер линейки) первой группы линеек соединен с входом j-го разряда i-го частичного произведения (где

= 3(E — 1) + r) блока суммирования частичных произведений, первый вход

j-ro (j = 1, ... п) сумматора Р-й линейки (Р— нечетное) та-й группы линеек соединен с выходом суммы

3 Х-1

j -го сумматора

2 и линейки (m-.1)-й группы линеек, второй вход первого сумматора Х-й линейки (— нечетное) m-й группы линеек соединен с выходом переноса п-го сумматора

311 — — — — -й линейки (m-1)-й группы

2 линеек, второй вход р-го сумматора: (р-2... n) E-й линейки (E — нечетное)

m-й группы линеек соединен с выходом переноса (р-1)-ro сумматора

39-1 линейки (m-1)-й группы линеек, третий вход

j-ro сумматора М-й (6 — нечетное) линейки m-й группы линеек соединен с выходом суммы j-ro

3E — 1 сумматора — — — — — -й линейки (m-1)-й

2.

/ группы линеек, первый вход р-го сумма-. тора h-й линейки (2 — четное) ш-й группы линеек соединен с выходом пе=

30 — 2 реноса (j-1) -ro сумматора — — — — -й

2 линейки (m-1)-й группы линеек, первый вход первого сумматора E-й линейки (F — четное) и m-й группы линеек соединен с выходом переноса иек, третий вход р-го сумматора 50

У-й линейки (Р— четное) m-й группы линеек соединен с выходом переноса

Елок

СДММЦР.

77,РОБЕЮ.

7 1

30 — 2

t o сумматора — — — — -й линейки

2 (m-1)-й группы линеек, второй вход

j-ro сумматора 0-й линейки (Р— четное) m-й группы линеек соединен с выходом суммы j-го сумматора

32 . — — — -й линейки (ш-1)-й группы лине2

ЗР (j-1)-ro сумматора — — -й линейки

2 (m-1)-й группы линеек, третий вход первого сумматора 2-й (Р— четное) линейки m-й группы линеек соединен с выходом переноса и-го сумматора

3Š— — -й линейки (m-1)-й группы лине2

254471 8 ек, свободные входы сумматоров последней линейки m-группы линеек соединены с выходами суммы или переноса сумматоров линеек группы линеек предыдущих 1 (m-l)-,é группе линеек, либо с входами разрядов соответствующих слов (из оставшихся (и — Зс )) блока суммирования частичных произведений, выход суммы j-го сумматора линейки

k-й группы линеек является выходом

j-го разряда первого результата блока суммирования частичных произведений, выход переноса р-го сумматора k-й группы линеек является выходом (р+1)15 го разряда второго результата блока суммирования частичных произведений, выход переноса и-го сумматора линейки, k-й группы линеек является выходом первого разряда второго результата блока суммирования частичных произведений.

1254471

gr anbr an-r br ... а Ь, a,br .дл а„,б аул ... а,д а„б

,-а„g б, а„. д ... а„ба д»

° ° ° ° ° 1 1 ° ° ° ° ° ° ° ° ° ° ° ° ° ° °

gn = ать а„д„... ash„azbn

an-r br авда

abbr

ar br

a . а„.,4, anbg

arbor

an.SbS an.gbS

an- r bs a„bs д ° ° e e° ° ° 1 ° ° ° ° ° ° ° ° e ° ° 1 ° e e° 1 ° 1

anbn а И

1254471

) 254471 и 13

П =ФЯ

Фиа. О

Составитель Н.Маркелова, Техред Л.Сердюкова :Корректор JI.öàòàé

Редактор Н.Слободяник

Тираж 671 Подписное

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

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

Заказ 4721/52

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4