Матричное устройство для возведения в квадрат Советский патент 1990 года по МПК G06F7/552 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычксли- телях.

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

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

Матричное устройство содержит усеченную матрицу, из пятнадцати строк и восьми столбцов ячеек, каждая из которых состоит из элемента И 1, сумматора 2, а, также блоки 3-,5 свертки по модулю три, группу элементов И 6; 1-6.3, одноразряд :мй сумматор 7 по модулю три., группу сумматоров 8.1- 8.6 по модулю два, : блок 9 сложения по модулю три и схему 10 сравнения.

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

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

И 1.

Конъюнкции столбца I вычисляется на элементах И 1 первого столбца усеченной матрицы ячеек, на первые

входы которых подается первый раз-.

ряд 1р опеданда. На вторые входы элементов И 1 первого столбца поступают разряды операнда соответственно с -12р по 16р. На выходах элементов И 1 первого столбца образуются конъюнкции 1р 12р, 1р 13р, 1р 14р, и 1р 1бр, которые поступают на вторые входы сумматоров 2 этих же ячеек. Через первые входы и выкоды этих сумматоров 2, как и сумматоров 2 всех последующих столбцов, распространяется сигнал переноса (кроме первого входа сумматоров 2: 1-го CTOji6- ца П-й строки, 2-го столбца 9-й

0

5

0

5

0

5

0

5

строки, З-го столбца 7-й строки,...., 5-го столбца 3-й строки, 6-го,7-го и 8-го столбцов 1-й строки, которые занулены, а также кроме первого выхода сумматоров 2 пятнадцатой строки столбцов с 1-го по 7-й, с выходов которых сигнал переноса поступает на третьи входы сумматоров 2 четырнад- о цатой строки столбцов с 2-го по 8-й соответственно). Третьи входы сумматоров 2 четных строк 1-го столбца занулены, а на третьи входы сумматоров 2 11-й, 13-й и 15-й строк 1-го столбца поступают разряды операнда соответственно 7р, 8р и 9р. Сигналы суммы с вторых выходов сумматоро;в 2 1-го столбца 11-й, 12-й, 13-й, 1 4-й, и 15-й строк поступают на третьи входы сумматоров 2 2-го столбца соответственно 9-й, 10-й, 11-и, 12-й и 13-й строк.

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

поступают на третьи входы су ммато- ров 2 3-го столбца соответственно 7-й, 8-й,...,12-й и 13-й строк.

Аналогичным образом конъюнкции столбцов III, IV,...VII и Vlil вычисляются на элементах И 1 3-го, 4-го,.. .,7-го и 8-го столбцов усечен- ной матрицы ячеек соответственно. С выходов элементов И 1 каждого столбца соответствующая конъюнкция поступает на второй вход сумматора 2 этого же столбца. На третий вход сумматора 2 семнадцатой строки 3-го,4-го,... 7-го и 8-го столбца поступает соот- . „етственно 11-и, 12-й,...,15-й и 16-й разряды операнда. При этом вторые выходы сумматоров 2 б-го столбца 1-й и 2-й строки являются 13-м. и 14-м выходами 1 результата устройства соответственно, вторые выходы сумматоров 2 7-го и 8-гб столбцов 1-й и 2-й строк являются 15-м,- 16-м, 17-м и 18-м выходами результата устройства

соотЕетственно, Втбрые выходы сумматоров 2 8-го столбца 3-й, 4-й,.,.,14-й и 15-й строк являются 19-м, 20-м,..., 30-м и 31-м выходами результата устрой- ства соответственно, а первый выход cyMMiTopa 2 8-го столбца 15-й строки является 32-м выходом резул зтата устр5Йства. Номера выходов 12 результата устройства являются соответст- вую1щми разрядами результата.

Пэлученные таким образом двадцать старпих разрядов результата устройства поступают на входы первого блока 3 свертки по модулю три, который формирует их контрольный код по моду- . Этот код поступает на входы первого операнда блока 10 сравнения. Шестнадцатиразрядный операнд поUI сч. ifn/a.j fi- fiutx -- .-- -- ...ступает также на соответствующие вхо- 20 разрядный результат свертки разрядов

,глгТ1 1.пО1-1-гт 41ч1« ГЧ1-Ъ 1| ч1 О-и TTnTJT о Г

та, и их контрольный код по модулю три должен быть учтен при контроле данного устройства. В полной матрице конъюнкций выделены ромбовидные фраг- менты, которые обозначены в порядке убывания площадей через a,b,c,d и е. Конъюнкции lip-IP, 9р-3р, 7р-5р, , Эр«9р и IP lip объединены во

Q фрагмент .f. Контрольный код тре- ,. угольной матрицы А отбрасываемых раз- рядов вычисляется как алгебраическая сумма контрольных кодов по модулю тр фрагментов: (a-b+c-d+e-f).

5 Контрольный код фрагмента а матри цы определяется на сумматоре 8.1 по модулю два группы, на входы которого с выходов А1 и А2 второго блока 4 свертки по модулю три поступает дву

ды BJTOporo блока 4 свертки по модулю три, который формирует его контрольный код. Этот контрольный код с поспел вей па;ры лыходов второго блока 4 свертки по модулю три поступает на сумматора 8.6 по модулю два гругпы, который вычисляет первый раз- ряд двухразрядного контрольного кода по кодулю три полного квадрата. Второй разряд двухразрядного кснтроль- Hort кода полного квадрата всегда имеет значение логического нуля. Сфо мированный таким.образом контрольный код полного квадрата поступает на I хода первого операнда блока 9 слоя ения по модулю три.

1 торой блок 4 свертки по модулю три формирует также двухразрядные результаты свертки по .модулю три разрядов операнда с 1-го по 10-й, с 3-го по 0-й, с 3-го по 8-:й, с 5-го по. 8-й которые подаются соответственно на Цары выходов А1 и А2, В1 и В2, , С1 и С2 и Dl и D2. Пара выходов Е1 и Е2 второго блока 4 свертки по мод;глю три является выходами 5-го и 6-то разрядов операнда соответственно.

На фиг.3 показана полная матрица кон .юнкций разрядов операнда. Номера ста1бцов и строк матрицы являются номер 1ми разрядов операнда, а на пере- этих столбцов и строк символом X обозначены соответствующие

КОНЪЮНКЦИИ. В полной матрице конъюнк- 55 «о одинаковые конъюнкции (llp.Ip ций выделена треугольная матрица А и 1р:Пр, 9р Зр и Зр 9р, 7р.5р и отбрасываемых разрядов. Конъюнкции 5р-7р), то достаточно учесть только матрицы А не участвуют в вычислении половину из них, а именно llp-Ip, двадцати старших разрядов результа- 9р 3р и 7р.5р с весом, равным 2.

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

30 .Контрольный код фрагмента в матри це определяется на сумматоре .8.2 по модулю два группы, на входа которого со следующей пары выходов (т.е. В1 и В2) второго блока 4 свертки по мо дулю три поступает двухразрядный результат свертки разрядов операнда с 3-го по 10-й. При этом с выхода сумматора 8.2 по модулю два.группы снимается лервый разряд двухразрядного дп контрольного кода по модулю гри фраг мента b с весом, равным 1.

Аналогично определяются контрольные коды фрагментов с,и е матрицы - соответственно на сумматорах 8.3-8.5 е по модулю два группы, на входа которых с выходов С1 и С2, D1 и D2 и Е1, Е2 второго блока 4 свертки по мо дулю три поступают двухразрядные ре- .зультаты свертки разрядов операнда с 3-го по 8-й, с 5-го по 8-й и 5-й и 6-й разряды соответственно.

Конъюнкции, фрагмента f имеют оди наковый вес по модулю три, равный 1 Но так как Во фрагмент f входят попа

50

8653

.-- -- ...та, и их контрольный код по модулю три должен быть учтен при контроле данного устройства. В полной матрице конъюнкций выделены ромбовидные фраг- менты, которые обозначены в порядке убывания площадей через a,b,c,d и е. Конъюнкции lip-IP, 9р-3р, 7р-5р, , Эр«9р и IP lip объединены во

Q фрагмент .f. Контрольный код тре- ,. угольной матрицы А отбрасываемых раз- рядов вычисляется как алгебраическая сумма контрольных кодов по модулю три фрагментов: (a-b+c-d+e-f).

5 Контрольный код фрагмента а матрицы определяется на сумматоре 8.1 по модулю два группы, на входы которого с выходов А1 и А2 второго блока 4 свертки по модулю три поступает двухразрядный результат свертки разрядов

глгТ1 1.пО1-1-гт 41ч1« ГЧ1-Ъ 1| ч1 О-и TTnTJT о Г

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

0 .Контрольный код фрагмента в матрице определяется на сумматоре .8.2 по модулю два группы, на входа которого со следующей пары выходов (т.е. В1 и В2) второго блока 4 свертки по модулю три поступает двухразрядный результат свертки разрядов операнда с 3-го по 10-й. При этом с выхода сумматора 8.2 по модулю два.группы снимается лервый разряд двухразрядного п контрольного кода по модулю гри фрагмента b с весом, равным 1.

Аналогично определяются контрольные коды фрагментов с,и е матрицы - соответственно на сумматорах 8.3-8.5 е по модулю два группы, на входа которых с выходов С1 и С2, D1 и D2 и Е1, Е2 второго блока 4 свертки по модулю три поступают двухразрядные ре- .зультаты свертки разрядов операнда с 3-го по 8-й, с 5-го по 8-й и 5-й и 6-й разряды соответственно.

Конъюнкции, фрагмента f имеют одинаковый вес по модулю три, равный 1. Но так как Во фрагмент f входят попар0

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

Первые разряды контрольных кодов фрагментов а,b,C5d и е (вторые разряды их контрольных кодов принимают зна чение логического нуля) с выхода сум- матЬра 8 по модулю два группы, а также . код S фрагмента f с выхода одноразрядного сумматора 7 по модулю три с учетом знака (контрольные коды фраг- ментов а, с, е - со знаком плюс, а контрольные коды фрагментов b,d,f - со знаком минус) поступают на входы третьего блока 5 свертки по модулю три. Блок 5 формирует контрольный код с выходов третьего блока 5 свертки по модулю три инвв сно подается (т.е с первого выхода третьего бло- ка 5 свертки по модулю три на второй вход второго операнда блока 9 сложе- ния по модулю три и с второго выхода блока 5 на первый вход-второго one- : ранда блока 9) на входы второго операнда блока 9 сложения по модулю три Блок 9 сложения по модулю три компен- сирует из контрольного кода по модулю три полного квадрат-а контрольный код по модулю три отбрасываемых разрядов, получая таким образом конт- рольный код по модулю три двадцати старших разрядов результата. Этот код поступает на вход второго операнда схемы 10 сравнения, выход которого является выходом 13 неисправности устройства.

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

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

Матричное устройство для возведения в квадрат, содержащее усеченную матрицу ячеек из п-1 строк и п/2 столбцов с ячейками для первой и вто- рой строк в столбцах с К/2-го по n/2-й, для (К-21)-й и (К-21-1)-й строк в столбцах с (1+1)-го по n/2-й для строк с (К-1)-й по (п-1)-ю

в столбцах сг первого по п/2-й, где п - .разрядность операнда, четное число, К - количество отбрасываемых разрядов результата, четное число и

К 4т, , 1 1,К/2-2, причем каждая ячейка содержит сумматор и элемент И, первый выход сумматора i-й строки j-ro столбца, j Г, п/2, соединен с первым ВХОДОМ сумматора (1+1)-й строки этого же столбца i

K-2J + 1 , п-2 для j : К/2 и i 1, п-2 , выход -элемента И каждой ячейки . соединен с вторым входом сумматора той же ячейки, первый выход сумматор а (п-1)-и строки j-столбца, -j 1, n/2-l, соединен с третьим входом сумматора :(п-2)-й строки ()-ro столбца, второй выход сумматора i-й строки j-ro столбца соединен, с-третьим входом сумматора (1-2)-й строки (j+l)-ro столбца,

i .K-2j + l, п-1 для j К/2 и ,п-1 для jb:K72, первы.е входы элементов И j-ro столбца, j 1, п/2, первых n-K+j. строк для j К/2 и первых n-j строк для , объединены между собой и .подключены к входу, j-ro разряда операнда, второй вход элемента И i-й сТ роки j-ro столбца, + l,n-j

для j «i К/2 и ,n-j для j К/2 5 соединен с входом (i+j)-ro разряда операнда, первые входы элементов И последних (j-)-x строк j-ro столбца для j- 1 объединены между собой и под- ключены к входу (n/2+j)-ro разряда операнда, второй вход элемента И i-й строки j-ro столбца, i n-j+l п-1,- для j 1, соединен с входом j+i-n/2)-ro разряда операнда, третий вход сумматора (2j-l)-й строки первого столбца подключен к входу (j+l)-ro разряда операнда для , а третьи входы сумматоров четных строк первого столбца, первый вход сумматора (K-2J+1) -и строки j-ro столбца (для ) и первые входы, сумматоров первой строки всех столбцов (для j5:K/2) подключены к нулевсй шине, третий вход сумматора (п-1)-и строки j-ro столбца (для соединен с входом (j+n/2)-ro разряда операнда, вторые выходы сумматоров- первой и вТо- рой строк j-ro столбца, , подключены к (2j+l)-My и (2j+2)-My выходам результата устройства соответственно , второй выход сумаатора i-й

ко

лю ка

строки, , п/1, П/2-ГО столбца соединен с (i+n)-M выходом результата ус ройства, 2п-й выход которого соединен с первым выходом сумматора (п-1)- ст;)оки П/2-ГО столбца, отличающ ij е с я тем, что, с целью повыше- ни I достоверности функционирования, lero введены с первого по третий блоки свертки по модулю три, группа из К/2 сумматоров по модулю два, группа из К/А элементов И, одноразрядный сумматор по модулю три, блок сложение по модулю три и схема сравнения, пр:1чем входы первого блока свертки по МО, лулю три подключены к выходам результата устройства, а первый и вто- ро i выхода - к первому и второму входам схемы сравнения соответственно, вх со ка

}да1 разрядов операнда соединены с 1тветствующими входами второго бло- свертки по модулю три, первый и

ВТ рой выходы последней пары выходов горого подключены к входам К/2-го

.су 1матора по модулю два группы, выход которого соединен с первым входом во го операнда блока сложений по моду- три, а-я пара выходов второго блосвертки по модулю три соединена

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

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

55SO I

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

т Ж Ж Ж Ж Ж Л I

П 31 3029282726 25 Z 2322ZJ 20Ю 18 17 16 5/ /J

Разряды результата Фиг.г

ХХХХХХХХХЛХХХЛ

хххххххххххххххх хххххххххххххлхх хххххххххххххххх хххххххххххххххх хххххххххххххххх

32 З;X23 S2726ZS2 lZ3ZZglWS}8 П 16JS}4J3

Разряд ы

Раз/)лды

IS IS 1 13

операнда

ОтбрасыВа eMctt) Vffcmb

ю3 8 т В s ii :s I 1

Ю

О л

е Г2Р 13 а

;4 N и а /б а

e 3 у ФигЗ

jt ь т a ft) &

.

1 €41Ь -

io«o t-« iRSa 52St

ОЗиг.б