Матричное устройство для возведения в квадрат

 

Изобретение относится к вычислительной технике и позволяет возводить N-разрядное число в квадрат с учетом K отбрасываемых разрядов (K - четное число и K=4M, т.е. @ V) с контролем при большей достоверности функционирования. Устройство содержит элементы И ячеек усеченной матрицы, вычисляющие всевозможные конъюнкции разрядов операнда, сумматоры ячеек усеченной матрицы, определяющие взвешенную сумму полученных конъюнкций и разрядов операнда. Таким образом, вычисляется (2N-K) старших разряда результата. Первый блок свертки по модулю три формирует контрольный код (2N-K) старших разрядов результата, второй блок свертки по модулю три формирует контрольный код операнда и двухразрядные результаты свертки разрядов операнда с 1-го по 10-й, с 3-го по 10-й, с 3-го по 8-й и с 5-го по 8-й, последний сумматор по модулю два группы вычисляет первый разряд двухразрядного контрольного кода по модулю три полного квадрата (второй разряд этого кода всегда принимает значение логического нуля). Полная матрица конъюнкции разбита на ромбовидные фрагменты. Первые разряды контрольных кодов этих фрагментов определяются на сумматорах по модулю два группы (вторые разряды этих кодов принимают значение логического нуля), а конъюнкции, не вошедшие в указанные фрагменты, вычисляются на элементах И группы. Эти конъюнкции суммируются на одноразрядном сумматоре по модулю три. Полученный контрольный код сворачивается с контрольными кодами фрагментов на третьем узле свертки по модулю три, формирующем контрольный код K отбрасываемых разрядов. Блок сложения по модулю три компенсирует из контрольного кода полного квадрата контрольный код K отбрасываемых разрядов, формируя таким образом контрольный код (2N-K) старших разрядов результата. Схема сравнения 10 сравнивает этот код с кодом, полученным на первом блоке свертки по модулю три, и формирует сигнал контроля, указывающий на правильность функционирования устройства. 7 ил.

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

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

РЕСПУЬЛИН

01) (19) Р1)У С 06 Р 7/552

ГОС

Il0 И

ПРИ

К QTOPCHQtAf СВИДЕТЕЛЬСТВУ (21 (22 (46 (71 тут (72 и Ю (53 (56

У 1 эобретение относится к вычислиьной технике и может быть испольт

9 8 (54

ДЕН (57 тел . n"ð

К о чи при ров ты ляю дов ной су дов етс та. три ста

5ло кон

))ые

АРСТВЕННЫЙ НОМИТЕТ

БРЕТЕНИЯМ И ОТНРЫТИЯМ

НТ СССР

4610062/24-24

22.11. 88

23.11.90. Бюл. Р 43

Одесский политехнический инстиА.В.Дрозд, Е.Л.Полин, А.С.Попов

В.Дрозд

68I.325(088.8)

Авторское свидетельство СССР

36469, кл. G 06 Р 7/552, 1985. торское свидетельство СССР

2804, кл. G 06 Р 7/552, 1979.

МАТРИЧНОЕ УСТРОЙСТВО,ДЛЯ ВОЗВЕВ КВАДРАТ

Изобретение относится к вычислиной технике и позволяет возводить эрядное число в квадрат с учетом брасываемых разрядов (К вЂ” четное о и К = 4m, т.е.gV) с контролем большей достоверности функциониния; Устройство содержит элемен" ячеек усеченной матрицы, вычисе всевозможные конъюнкции раэряоперанда, сумматоры ячеек усеченматрицы, определяющие взвешенную полученных конъюнкций и разряоперанда. Таким образом, вычисля(2n-К) старших разряда результаПервый блок свертки по модулю формирует контрольный код (2п-К) ших разрядов результата, второй свертки по модулю три формирует рольный код операнда и двухразрядрезультаты свертки разрядов one2 ранда с 1-ro по 10-й, с 3-го по 10-й, с 3-го по 8-й и с 5-го по 8-й, последний сумматор по модулю два груп" пы вычисляет первый разряд двухразрядного контрольного кода по модулю три полного квадрата (второй разряд этого кода всегда принимает значение логического нуля). Полная матрица конъюнкции разбита на ромбовидные фрагменты. Первые разряды контрольных кодов этих фрагментов определяются на сумматорах по модулю два группы (вторые разряды этих кодов принимают значение логического нуля), а конъюнкции, не вошедшие в указанные фрагмен" ты, вычисляются на элементах И груп» пы. Эти конъюнкции суммируются на одноразрядном сумматоре по модулю три.

Полученный контрольный код сворачивается с контрольными кодами фрагментов на третьем узле свертки по модулю три, формирующем контрольный код Я

К отбрасываемых разрядов. Блок сложе ния по модулю три компенсирует из контрольного кода полного квадрата контрольный код К отбрасывае)ыс разрядов, формируя таким образом контрольный код (2п-К) .старших разрядов результата, Схема сравнения сравнивает этот код с кодом, полученным на первом блоке свертки по модулю три, и формирует сигнал контроля, указывающий на правильность функционирования устройства. 6 ил. зовано в специализированных вычислителях.

1608653

Цель изобретения - повышение достоверности функционирования.

На фиг.1 представлена структурная схема устройства для слуЧая раз яд5 ности операнда n=16 и отбрасываемых разрядов К=12; на фиг.2 - упрощенная усеченная матрица конъюнкции разрядов операнда, необходимых для получения двадцати старших разрядов ре" зультата; на фиг.3 — полная матрица

-конъюнкций разрядов операнда; на фиг.4 — схемы блоков 3-5 свертки по модулю три; на фиг.5 и 6 — схемы блока сложения по модулю три и сравнения.15

Матричное устройство содержит усеченную матрицу из пятнадцати строк и восьми столбцов ячеек, каждая из которых состоит из элемента И 1, сумматора 2, а также блоки 3-5 сверт- 20 ки по модулю три, группу элементов

И 6.1-6.3, одноразрядт:лй сумматор 7 по модулю три,, группу сумматоров 8.18.6 по модулю два, блок 9 сложения по модулю три и схему 10 сравнения.

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

В начальный момент времени на входы 11 разрядов операнда поступает шестнадцатиразрядный операнд. Матричное устройство для возведения в квадрат определяет возведение в квадрат и-разрядного числа (п=16) без К=12 младших разрядов результата, что обеспечивает получение в этом результате и точных старших разрядов. Уп35 рощенная усеченная матрица конъюнкций (фиг.2) разделена на столбцы с

I no VIII конъюнкции в ней реализованы на соответствующих элементах

И 1.

Конъюнкции столбца Х вычисляется на элементах И 1 первого столбца усеченной матрицы ячеек, на первые входы ксторых подается первый раз-. ряд 1р операнда. На вторые входы элементов И 1 первого столбца поступают разряды операнда соответственно с 12р по 16р. На выходах элементов

И 1 первого столбца образуются

50 конъюнкции 1р ° 12р, 1р ° 1Зр, 1р ° 14р, 1р ° 15p и 1р 16р, которые поступают на вторые входы сумматоров 2 этих же ячеек. Через первые входы и выходы этих сумматоров 2, как и сумматоров 2 всех последующих столбцов, распрост55 раняется сигнал переноса (кроме первого входа сумматоров 2: 1-го столбца 11-й строки, 2-ro столбца 9-й строки, 3-ro столбца 7-й строки,...., 5-ro столбца 3"й строки, 6-.ro,7-ro и 8-ro столбцов 1-й строки, которые занулены, а также кроме первого выхода сумматоров 2 пятнадцатой строки столбцов с 1-го по ?-й, с выходов которых сигнал переноса поступает на третьи входы сумматоров 2 четырнад» цатой строки столбцов с 2-го по 8-й соответственно). Третьи входы сумматоров 2 четных строк 1-го столбца занулены, а на третьи входы сумматоров 2 11-й, 13-й и 15-й строк 1-го столбца поступают разряды операнда соответственно 7р, 8р и 9р. Сигналы сумгж с вторых выходов сумматоров 2

1-го столбца 11-й, 12-й, 13-й, 14-й, и 15-й строк поступают на третьи входы сумматоров 2 2-го столбца соответственно 9-й, 10-й, 11-й, 12-й и 3-й строк.

Конъюнкции столбца II упрощенной усеченной матрицы конъюнкций вычисляются на элементах И 1 второго столбца усеченной матрицы ячеек, на входы которых заведены соответствующие (фиг.2) разряды операнда. Получение конъюнкции 2р 11р, 2р ° 12р,...,2р 16р и 9р 10р поступают на вторые входы сумматоров 2 этого же столбца. На третий вход сумматора 2 пятнадцатой строки 2-го столбца поступает 10-й разряд операнда. Сигнал суммы с вторых выходов сумматоров 2 2-ro столбца 9-й, 10-й,...,14-й и 15-й строк поступают на третьи входы сумматоров 2 3-го столбца соответственно

7-й, 8-й,...,12-й и 13-.й строк.

Аналогичным образом конъюнкции столбцов III, IV,...VII u VIII вычисляются на элементах И 1 З-ro, 4-ro,...,7-ro и 8-го столбцов усеченной матрицы ячеек соответственно. С выходов элементов И 1 каждого столбца соответствующая конъюнкция поступает на второй вход сумматора 2 этого же столбца. На третий вход сумматора 2 семнадцатой строки 3-го,4 -го,...

7-го и 8-го столбца поступает соотетственно 11-й, 12-й,...,15-й и

16-й разряды операнда. При этом вторые выходы сумматоров 2 6-ro столбца

1-й и 2-й строки являются 13-м.и 14-м выходами(результата устройства со ответственно, вторые выходы сумматоров 2 7-ro .и 8-ro столбцов 1"й и 2-й строк являются 15-м, 16-м, 17-м и

18-м выходами результата устройства соот ров и 15

30-м ства сумм ки я устр тата вую

П стар ва п ка 3

Фор лю т пер сту ды три, ный сле све вхо

rpy. ряд по ,рой ног . име

Сфо иь|й на сло три зул дов по

8-й . иа

Cl

El и 6 . вен

zO ст мер сыч лом ко ций отб мат дв

5 160 етственно. Втбрые выходы суммато8-ro столбца З-й, 4-й,...,14-й и строк являются 19"м, 20-м,..., и 31 "м выходами результата устройсоответственно, а первый выход тора 2 8-го столбца 15-й. строляется 32-м выходом результата йства. Номера выходов 12 резуль" устройства являются соответстми разрядами результата. лученные таким образом двадцать их разрядов результата устрайстступают на входы первого блосвертки по модулю три, который рует их контрольный код по модуи. Этот код поступает на входы

ro операнда блока 10 сравнения. стнадцатиразрядный операнд поет также на соответствующие вхоорого блока 4 свертки по модулю который формирует его контролькод. Этот контрольный код с поей пары выходов второго блока 4 тки по модулю три поступает на сумматора 8.6 по модулю два пы, который вычисляет первый раз"" двухразрядного контрольного кода одулю три полного квадрата. Втораэряд двухраэрядного кснтролькода полного квадрата всегда т значение логического нуля. мированный таким, образом контролькод полного квадрата поступает . ходы .первого операнда блока 9 ения по модулю три, торой блок 4 свертки по модулю формирует также двухразрядные ретаты свертки по .модулю три разряоперанда с I-го по 10-й, с 3-го

О-й, с 3-.го по 8-.й, с 5-ro no . которые подаются соответственно ары выходов AI и А2,. BI и В2, С2 и Dl и D2, Пара выходов

Е2 второго блока 4 свертки по лю три является выходами 5-го го разрядов операнда соответст-Ое а фиг.3 показана полная матрица юнкций разрядов операнда. Номера бцов и строк матрицы являются номи разрядов операнда, а на пере" нии этих "толбцов.и строк симво-.

Х обозначены соответствующие юикции. В полной матрице конъюнквыделена треугольная матрица А асываемых разрядов. Конъюнкции ицы А не участвуют в вычислении ати старших разрядов результа8653

6 та, и их контрольный код по модулю три должен быть учтен при контроле данного устройства. В полной матрице

5 конъюнкций выделены ромбовидные фрагменты, которые обозначены в порядке убывания площадей через а,b,с,d и е.

Конъюнкции 1 Ip ° lр, 9р Зр, 7р ° 5p, 5р 7р, Зр 9р и lp llр объединены во фрагмент .f Контрольный код треугольной матрицы А отбрасываемых pBs рядов вычисляется как алгебраическая сумма контрольных кодов по модулю три фрагментов. {а"Ь+с-d+e-f).

Контрольный код фрагмента а матрицы определяется на сумматоре 8.1 по модулю два группы, на входы которого с выходов А1 и А2 второго блока 4 свертки по модулю три поступает двух20 разрядный результат свертки разрядов операнда с 1-го по 10-й. При этом с выхода сумматора. 8.1 по модулю два группы снимается первый разряд двухразрядного контрольного. кода по моду25 лю три фрагмента а с весом, равным (второй разряд двухразрядного контрольного кода по модулю три квадрата всегда принимает значение логического нуля).

3р Контрольный код фрагмента в матрице определяется на сумматоре .8.2 по модулю два группы, на входы которого со следующей пары выходов (т.е. Вl и В2) второго блока 4 свертки по мо"

35 дулю три поступает двухразрядный результат свертки разрядов операнда с

3-го па 10-й. При этом с выхода сумматора 8.2 по модулю два.группы снимается первый разряд двухраэрядного

40 контрольного кода по модулю гри фраг" мента Ь с весом, равным 1.

Аналогично определяются контрольные коды фрагментов с,и е матрицы— соответственно на сумматорах 8.3-. 8.5

45 по модулю два группы, на входы которых с выходов Сl и С2, DI и D2 и

Еl, Е2 второго блока 4 свертки по модулю три поступают двухразрядные ре.зультаты свертки разрядов операнда с

50 3"го по 8-й, с 5-ro по 8-й и 5-й и 6-й разряды соответственно. ь

Конъюнкции, фрагмента f имеют одинаковый вес по модулю три, равный I.

Но так как во фрагмент Г входят попар55 но одинаковые конъюнкции (11ð ° Iр и .Iр ° Ilр, Яр Зр и Зр 9р, 7р 5р и

5р 7р), то достаточно учесть только половину из них, а именно 11р Ip, 9р Зр и.7р 5р . с весом, равным 2.

1608653. Эти конъюнкции определяются на элементах И 6 группы, на входы которых подаются соответствующие разряды операнда, и складываются на одноразряд5

НоМ сумматоре 7 Uo. модулю три, который формирует код суммы S.

Первые разряды контрольных кодов фрагментов а,b,ñ,d и е (вторые разряды их контрольных кодов принимают зна- р чение логического нуля) с выхода сумматора 8 по модулю два группы, а также.код $ фрагмента f с выхода одноразрядного сумматора 7 по модулю три с учетом знака (контрольные коды фраг" ментов а, с, е - со знаком плюс, а

1 контрольные коды фрагментов Ь,d f— со знаком минус) поступают на входы третьего блока 5 свертки по модулю три. Блок 5 формирует контрольный Zp код с выходов третьего блока 5 свертки no модулю три инве. сно подается (т.е с первого выхода третьего блока 5 свертки по модулю три на второй вход второго операнда блока 9 сложе- 25 ния по модулю три и с второго выхода блока 5 на первый вход второго опе-: ранда блока 9) на входы второго операнда блока 9 сложения по модулю,три.

Блок 9 сложения по модулю три компен- 30 сирует из контрольного кода по модулю три полного квадрата контрольный код по модулю три отбрасываемых разрядов, получая таким образом контрольный код по модулю три двадцати 35 старших разрядов результата, Этот код поступает на вход второго операнда схемы 10 сравнения,. выход которого является выходом 13 неисправности устройства.

При правильном функционировании устройства на входы операндов схемы 10 сравнения поступают одинаковые по модулю три контрольные коды и выход 13 устройства принимает значение 45

"ИСПРАВНО". Инверсное значение выхода 13 устройства указывает на непра. вильное функционирование устройства, Формула изобретения

Матричное устройство для возведения в квадрат, содержащее усеченную матрицу ячеек из п-1 строк и п/2

-столбцов с ячейками pna nepsoH и a ro- 55 рой строк в столбцах с К/2-ro no и/2-й, для (К-21)-й и (K-21-1)-й строк в столбцах с (1+1)-го по

n/2-й для строк с (К-l)-й по (п-1)-ю в столбцах с первого по n/2-й, где

n — - разрядность операнда, четное число, К вЂ” количество отбрасываемых разрядов результата, четное число и

К = 4m, m E (V, 1 I,K/2-2, причем каждая ячейка содержит сумматор и элемент И, первый выход сумматора i-й строки j-то столоиа, j = 1, п72, соадинен с первым входом сумматора (i+I)-й строки этого же столбца i

= К-2j+1 и-2 для j а К/2 и

1, и-2 дпя j К/2, вьжод элемента И каждой ячейки . соединен с вторым входом сумматора той же ячейки, первый выход сумматора (n-1)-й строки

j. — ñòîëáöà, j = 1, и/2-.1, соединен с третьим входом сумматора (n-2)-й строки (j+1)-го .столбца, второй выход сумматора i-й строки j-го столбца соединен с третьим входом сумматора (i-2)-й строки (j+1)-ro столбца, = К-2j+I, и-1 для ) (К/2 и 1=3,n-l для 1»- К/2, первые входы элементов И

j-го столбца, j = 1, п/2, первых и-К+) строк для 1 сК/2 и первых

n-j строк для j K/2, объединены между собой и подключены к входу.j-го разряда операнда, второй вход элемента И

i-й строки j-го столбца, i=K-2j+l,n-j для j а К/2 и i=1,n-j для j К/2,соединен с входом (i+j)-ro разряда операнда, первые входы элементов И по-! следних (j-I)-х строк j-го столбца для j> 1 объединены между собой и под ключены к входу (n/2+j)-ro разряда операнда, второй вход элемента И

i-й строки j-ro столбца, i=n +1р и-), для jw 1, соединен с входом

j+i-и/2)-rn разряда операнда, третий вход сумматора (2j — 1)-й строки первого столбца подключен к входу ()+1)-Fo разряда операнда для j) К/2, а третьи входы сумматоров четных строк первого столбца, первый вход сумматора (K-Zj+I)-й строки j-го столбца (для j (K/Z) и первые входы. сумматоров первой строки всех столбцов (для

j К/2) подключены к нулевсй шине, третий вход сумматора (и-I)-й строки

j-ro столбца (для j ) 1) соединен с входом (j+n/2)-го разряда операнда, вторые выходы сумматоров первой и второй строк j-го столбца, )Э К/2, подключены к (2j+I)-му н (2j+2)-му выходам результата устройства соответственно, второй выход сумаатора i-й ст ди ус не ст

Щ ни в бл из па су ни пр зу ро да вх со ка вт к

l0 с входами а-го сумматора. по модулю даа группа, à = l, Kll--1, апкод а-го сумматора по модулю два группы соединен с (а+2)-м входом третьего блока свертки по модулю три, первый вход

Ь"го элемента И группы соецинен с входом {К-2Ь+1)"го разряда операнда, Ь1, К/4, второй вход Ь-го элемента И группы соединены с входом (2Ь- l)-го разряда операнда, выход Ь-ro элемента И группы соединен с Ь-м входом одноразрядного сумматора по модулю три, первый и второй выходы которого соединены соответственно с вторым и первым входами третьего блока свертки по модулю три, первый и второй выходы которого соединены соответственно с вторым и первым входами второго операнда блока сложения по модулю три, второй вход первого операнда которого соединен с шиной логического нуля устройствау первый и второй выходы блока сложения по модулю три соединены соответственно с первым и вторым входами второго входа схемы сравнения, выход которого является выходом неисправности устройства.

160865 окп, тЗ,,п7Г, и/2-го столбца сосен с (i+n)-м выходом результата ройства, 2п-й выход которого соедис первым выходом сумматора (п"l)5 оки n/2-ro столбца, о т л и ч а ю— е с я тем, что, с целью повышедостоверности функционирования, его введены с первого по третий ки свертки по модулю три, группа

К/2 сумматоров по модулю два, групиа К/4 элементов И, одноразрядный матор по модулю три, блок сложепо модулю три и схема сравнения, чем входы первого блока свертки по улю три подключены к выходам реьтата устройства, а первый и втовыходы . — к первому и второму вхосхемы сравнения соответственно, ды разрядов операнда соединены с тветствующими входами второго блосвертки по модулю три, первый и рой выходы последней пары выходов

oporo подключены к входам К/2-го атора по модулю два группы, выход 25 рого соединен с первым входом пе операнда блока сложений по модури, а-я пара выходов второго блосвертки по модулю три соединена

1608653

1608653

ИГ .ИГ Ж Х Х .Л Х 2

И Л Ю292827Ж 25 Я 2Ю # 21 Ю 5 И Л 1Е 15 /4 15

Ра.зряо ы р ез ул ьmama

Фиг. 2 операж3 у

Разряды! х хх ххх хххх ххххх

ХХХХХХ ххххххх хххххххх ххххххххх хххххххххх

Ы 3! 30 О В2726 25202ЮИ р а 3 р я д ь/

О4 ф а . .

Э а

ЯЪ

> ф ъ

Ф фр

Ф <р а

8.3 с р е 3 у ль т а та

@@8. Л

I 608653

1608653

Составитель А.Дрозд

Техред М.Ходанич

Корректор JI.Бескид ор А.Шандор

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

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

1 13035, Москва, Ж-35, Раушская наб., д. 4/5 одственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

2

1 г

2