Матричное вычислительное устройство

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

< 960803 (61) Дополнительное к авт. свид-ву (22) Заявлено 13. 02. 81(21) 3249639/18-24 с присоединением заявки ¹â€” (23) Приоритет—

Опубликовано 23Я982. Бюллетень №35

Дата опубликования описания 23.09.82 (51) М. Кл.

G 06 F 7/38

Государственный комитет

СССР по делам изобретений и открытий (531 УДК6 81. 3 (OS8. 8) (72) Авторы изобретения

Л. А. Зайкова, В. М. Деревянкин, В. П и Л. A. Шумилов

Институт электродинамики AH Украинско1 {; и Ворошиловградский машиностроительный институт (71) Заявители (84) МАТРИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО

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

;устройствах, Известно матричное вычислительное устройство для выполнения операции деления двоичных операндов L1).

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

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

cyMM opos $2 1.

Однако устройство обладает ограниченными Функциональными возможностя- ми, так как позволяет выполнять лишь одну ариФметическую операцию умноже15 ния двоичных операн„-ов и имеет неоднородную структуру.

Целью изобретения является расширение функциональных возможностей устройства за счет выполнения операции вычисления значения многочлена г(Р) где p — примитивный элемент поля Галуа.

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

9б0803 устройства, вторые входы первых элементов И ячеек каждой строки матрицы подключены к соответствуюцему разрядному входу второго операнда устройства, выход первого элемента И каждой ячейки подключен к первому входу одно-5 разрядного сумматора этой же ячейки, выход суммы одноразрядного сумматора каждой ячейки — ко второму входу одноразрядного сумматора ячейки следуюцей строки предыдущего столбца матрицы, в каждую ячейку дополнительно введены два элемента И и сумматор по модулю два, причем первый вход второго элемента И каждой ячейки матрицы подключен к выходу суммы одноразрядного сум 5 матора этой же ячейки, вторые входы вторых элементов И ячеек каждой строки матрицы — к соответствующему разрядному входу кода коэффициента многочлена r(P>) устройства, выход второго элемента И каждой ячейки — к пер. вому входу сумматора по модулю два этой же ячейки, выход сумматора по модулю два каждой ячейки — ко второму входу сумматора по модулю два ячайки следующей строки того же столбца матрицы, выход переноса одноразрядного сумматора каждой ячейки — к первому входу третьего элемента И этой же ячейки, вторые входы третьих элементов И ячеек каждой строки матрицы— к управляющему входу операции устройства, а выход третьего элемента И каждой ячейки — ко входу переноса одноразрядного сумматора той же строки предыдущего столбца. 35

На чертеже представлена схема вычислитель ного устройства.

Устройство содержит ячейки, каждая из которых состоит из элементов И

1 и 2, одноразрядного сумматора 3, 4g элемента И 4 сумматора 5 по модулю два, входы 6 первого операнда, входы 7, на которые поступают значения из предыдущей строки, входы 8 соединены с выходами сумматоров 5 по модулю два 4 ячеек предыдущей строки, входы 9 второго операнда, выходы 10, соединенные со входами переноса сумматоров 3 ячеек предыдущего столбца той же строки,,управляющие входы 11 операции, выходы 12 сумматоров 3, входы 13 кода коэффициента многочлена г(Pj),входы 14 переноса сумматоров 3.

Первые входы элементов И 1 ячеек матрицы подключены к соответствующе- му входу 6 устройства, вторые входы элементов H 1 ячеек матрицы подключены к соответствующему входу 9 устройства, выход элемента И 1 каждой ячейки матрицы подключен к первому входу одноразрядного сумматора 3 той же -60 ячейки, выход суммы одноразрядного сумматора 3 подключен ко второму входу одноразрядного сумматора ячейки следующей строки предыдущего столбца матрицы. Первый вход элемента И .4 каждой ячейки подключен к выходу суммы одноразрядного сумматора 3 этой же ячейки, вторые входы элементов И 4 ячеек матрицы — к соответствующему входу 13, выход элемента И 4 ячейки к первому входу сумматора 5 по модулю два этой же ячейки, выход сумматора 5 по модулю два каждой ячейки — ко второму входу сумматора 5 по модулю два ячейки следующей строки того же столбца, выход переноса одноразрядного сумматора 3 ячейки — к первому входу элемента И 2 этой же ячейки, вторые входы элементов И 2 ячеек матрицы— к соответствуюцему входу 11, выход элемента И 2 каждой ячейки — ко входу переноса одноразрядного сумматора 3 ячейки той же строки предыдущего столбца матрицы.

Для выполнения операции вычисления значения многочлена r(х) при х, равном примитивному элементу р поля

Галуа GF(Z ), необходимо в многочлен вида

r(x) = r + r x + г х + ... + r

i = О, t, r;BGF(2) подставить элемент р е. GF(2 ), воз" вести элемент в степень j, j = 2, t, причем (3 е GF (2 ), и осуществить суммирование по модулю два слагаемых многочлена r (9 ), у которых коэффициенты г не равны нулю. Результат опеCt рации — элемент поля Галуа GF(2 ).

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

При выполнении операции вычисления значения многочлена r(ф), где примитивный элемент поля Галуа GF (2 ), на управляющие входы 11, входы 8 (исключая вход 8 ячейки первой строки последнего столбца матрицы) входы 13 и вход 9 первой строки матрицы подается код "0" . Сигнал с выхода 12 каждой предыдущей строки подается на вход 9 первой строки матрицы подает ся код "0" .

Сигнал с выхода 12 каждой предыдущей строки подается на вход 9 каждой последующей строки матрицы. На входы 7 устройства поступает код элемента поля р разности а. На входы б устройства поступает код разрядности а, составленный из а младших коэффициентов минимального многочлена М(х) для элемента

На вход 8 ячейки первой строки последнего столбца матрицы поступает на код коэффициента r . На входы 13 устройства подается код разрядности составленный из коэффициентов многочлена г (P ) q причем код коэффициента

r поступает на вход 13 первой стро1 ки матрицы ..

В первой строке матрицы производится умножение коэффициента r на элемент поля с помощью одноразрядного сумматора 3, элемента И 4 и суммирование с коэффициентом r ÷òî осуществляется сумматором 5 по модулю два

960803

1 5

55 ячейки первой строки последнего столбца матрицы.

В последующих строках матрицы производится операция возведения элемента 1з в степень j по модулю минимального лногочлена М(х), которая осуществляется последовательным сдвигом элемента ф на один разряд влево. Это равносильно выполнению операции р p=

Деление полученных степеней элемента ф на многочлен М(х) производится с помощью элементов И 1 и одноразрядных сумматоров 3 ячеек каж- . дой строки латрицы. Значение старшего разряда элемента поля в данной строке матрицы служит сигналом управления для элементов И 1 ячеек последующей строки.

Элементы поля умножаются на соответствующие коэффициенты r с noj мощью элементов И 4 и произведения суммируются сумматорами 5 по модулю два ячеек каждой строки матрицы.

Окончательный результат операции— значение многочлена г(ф - формируется на выходах устройства.

При выполнении операции умножения двоичных операндов от старших разрядов множителя на управлякв ие входы

11 устройства подается код "1", на входы 7, 8, 13 и 14 — код "0". На входы 9 каждой строки матрицы подает ся разряд множителя, на входы б разряды множимого.

Сигналы с выхода 10 первых ячеек каждой строки, кроме первой ячейки первой строки, подаются на входы 7 устройства, а именно сигнал с выхода

10 первой ячейки второй строки— на вход 7 первой ячейки первой строки, сигнал с выхода 10 первой ячейки третьей строки — на вход 7 второй ячейки первой строки и так далее.

Результат операции — произведение двоичных операндов — формируется на выходах 12 матрицы, старший разряд произведения образуется на выходе 10 первой строки матрицы.

Таким образовал, введение в каждую ячейку устройства двух элементов И и сумматора по лодулю два позволяет расширить его функциональные возможности, Устройство перспективно для реализации в виде больших интегральных схем благодаря однородности структуры.

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

Матричное вычислительное устройство, каждая ячейка которого содержит одноразрядный сумматор и первый. элемент И, причем первые входы первых элементов И ячеек каждого столбца матрицы подключены к соответствующе лу разрядному. входу первого операнда устройства, вторые входы первых элементов И ячеек каждой строки матрицы подключены к соответствующему разрядному входу второго oneранда устройства, выход первого элемента И каждой ячейки подключен к первому входу одноразрядного сумматора этой же ячейки, выход суммы одноразрядного сумматора каждой ячейки — ко второму входу одноразрядного сумматора ячейки следующей строки предыдущего столбца матрицы, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства эа счет выполнения операции вычисления значения многочлена: r(p ), где p — примитивный элемент поля Галуа, в каждую ячейку дополнительно введены два элемента И и сумматор по модулю два, 25 бричек перв и вход второго элемента

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

З5 лодулю два каждой ячейки — ко второму входу сумматора по модулю два ячей ки следующей строки того же столбца матрицы, выход переноса одноразрядного сумматора каждой ячейки — к пер40 вому входу третьего элемента И этой же ячейки, вторые входы третьих элементов И ячеек каждой строки матрицы— к управляющему входу операции устройства, а выход третьего элемента И каждой ячейки — ко входу переноса одноразрядного сумматора той же строки предыдущего столбца, Источники информации, 50 принятые во внимание при экспертизе, ). guild.Í. И. Sone Cellular Logic

Arrays for Non-Restoring 13inary

Division. — "The Radio and Electronic Eng".-1970, 39, 9 б, р. 345-348.

2. Карцев Yi. A. Арифметика цифровых машин. М., "аука", 1969, с. 444 (прототип).

960803

ff

ft

13

Составитель В. Березкин

Редактор Л. Шишкина Техред E . Õàðèòoí÷èê Корректор С. Шекмар

Заказ 7282/58 Тираж 731. Подписное

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

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

Филиал ППП "Патент", г . Ужгород, ул. Проектная, 4