Матричное вычислительное устройство Советский патент 1982 года по МПК G06F7/38 

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

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

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

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

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

10 2 .

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

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

Поставленная цель достигается тем, что в матричном вычислительном уст25ройстве каждая ячейка которого содержит одноразрядный суглматор и первый элемент И, причем первые входы первых элементов И ячеек ка;кдого столбца матрицы подключены к соответствующему разрядному входу первого операнда устройства, вторые входы первы:г зл&ментов И ячеек каждой строки матрицы подключены к соответствующему разряд ному входу второго операнда устройства, выход первого элемента И каждо ячейки подключен к первому входу одно разрядного сумматора этой же ячейки, выход сум1« ы одноразрядного сумматора каждой ячейки - ко второму входу одн разрядного сумматора ячейки следующей строки предыдущего столбца матрицы, в каждую ячейку дополнительно введены два элемента И и сумматор по модулю двй, причем первый вход второго элемента И каждой ячейки матрицы подклю чен к выходу суммы одноразрядного сум матора этой же ячейки, вторые входы вторых элементов И ячеек каждой стро ки матрицы - к соответствующему разрядному входу кода коэффициента многочлена г ( (Ъ ) устройства, выход второго элемента И каждой ячейки - к пер вому входу сумматора по модулю два этой же ячейки, выход сумматора по модулю два каждой ячейки - ко второму входу сумматора по модулю два ячейки следующей строки того же столбца матрицы, выход переноса одноразрядного сумматора каждой ячейки - к первому входу третьего элемента И этой же ячейки, вторые входы третьих элементов И ячеек каждой строки матрицы к управляющему входу операции устройства, а выход третьего элемента И каж дой ячейки - ко входу переноса одноразрядного сумматора той же строки Предыдущего столбца. На чертеже представлена схема вычислительного устройства. Устройство содержит ячейки, каждая из которых состоит из элементов И 1 и 2, одноразрядного сумматора 3, элемента И 4 сумматора 5 по модулю два входы б первого операнда, входы 7, на которые поступают значения из предыдущей строки, входы 8 соединены с выходами сумматоров 5 по модулю два ячее1с предыдущей строки, входы 9 второго операнда, выходы 10, соединенные со входами переноса сумматоров 3 ячеек предьадущего столбца той же стро ки, , управляющие входы 11 операции, выходы 12 сумматоров 3, входы 13 кода коэффициента многочлена г(/),входы 14 переноса суглматоров 3. Первые входы элементов И 1 ячеек матрицы подключены к соответствуюием входу 6 устройства, вторые входы элементов И 1 ячеек матрицы подключены к соответствующему входу 9.устройства, выход элемента И 1 каждой ячейки матрицы подключен к первому входу одноразрядного сумматора 3 той же ячейки, выход суммы одноразрядного сумматора 3 подключен ко второму входу одноразрядного cyfiMaTopa ячейки следующей строки предыдущего столбца матрицы. Первый вход элемента И .4 каждой ячейки подключен к выходу суммы одноразрядного сумматора 3 этой же ячейки, вторые входы элементов и 4 ячеек матрицы - к соответствующему входу 13, выход элемента И 4 ячейки к первому входу сумматора 5 по модулю два этой же ячейки, выход сумматора 5 по модулю два каждой ячейки - ко второму входу сумматора 5 по модулю два. ячейки следующей строки того же столбца, выход переноса одноразрядного cy iматора 3 ячейки - к первому входу .элемента И 2 этой же ячейки, вторые входы элегтентов И 2 ячеек матрицы к соответствующему входу 11, выход элемента И 2 каждой ячейки - ко входу переноса одноразрядного сумматора 3 ячейки той же строки предыдущего столбца матрицы. Для выполнения операции вычисления значения многочлена г( х) при х, равном примитивному элементу поля Галуа GFCZ), необходимо в многочлен вида Г(х) Го -I- TfiX + i О, t, r.eGF(2) д подставить элемент /ьеСР(2 ), воз вести элеме.нт /ь в степень j, j 2, t, причем (2), и осуществить суммирование по модулю два слагаемых многочлена г ( |i ) , у которых коэффициенты г,- не равны нулю. Результат операции - элемент поля Галуа GF(2 ). Устройство работает следующим образом. При выполнении операции вычисления значения многочлена г( ), где Р „ примитивный элемент поля Галуа GF(2 ), на управляющие входы 11, входы 8 (исключая вход 8 ячейки первой строки последнего столбца матрицы) входы 13 и вход 9 первой строки матрицы подается код О . Сигнал с выхода 12 каждой претадущей строки подается на вход 9 первой строки матрицы подается код О . Сигнал с выхода 12 каждой предыдущей строки подается на вход 9 каждой последующей строки матрицы. На входы 7 устройства поступает код элемента поля |Ъ разности а. На входы 6 устройства поступает код разрядности а, составленный из а младших коэффициентов минимального многочлена М(х) для элемента (Ь . На вход 8 ячейки первой строки последнего столбца матрицы поступает 1на код коэффициента г . На входы 13 устройства подается код разрядности t , составленный из коэффициентов многочлена г С (i ) / причём код коэффициента г поступает на вход 13 первой строки матрицы.В первой строке матрицы производится умножение коэффициента г на элемент поля Ь с помощью одноразрядного сумматора 3, элемента И 4 и cyм /Iиpoвание с коэффициентом Гд,-что осуществляется сумматором 5 по модулю два ячейки первой строки последнего стол ца матрицы. В последующих строках матрицы про изводится операция возведения элемен та /S в степень j по модулю минималь ного многочлена М(х), которая осущес вляется последовательным сдвигом эле мента I) на один разряд влево. Это равн.осильно выполнению операции . Деление полученных степеней элемента (Ь на многочлен М(х) производится с помощью элементов И 1 и одно эазрядных сумматоров 3 ячеек каж дой строки матрицы. Значение старшег | азряда элемента поля в данной строк матрицы служит сигналом управления для элементов И 1 ячеек последующей строки.. Элементы поля ft умножаются на соответствующие коэффициенты г j с по мощью элементов И 4 и произведения суммируются сумматорами 5 по модулю два ячеек каждой строки матрицы. Окончательный результат операции значение многочлена r(|i) - формирует ся на выходах устройства. При выполнении операции умножения двоичных операндов от старших разрядов множителя на управляклчие входы 11 устройства подается код 1, на входы 7, 8, 13 и 14 - код О, На входы 9 каждой строки матрицы подае ся разряд множителя, на входы 6 разряды множимого. Сигналы с выхода 10 первых ячеек каждой строки кроме первой ячейки первой строки, подаются на входы 7 устройства, а именно сигнал с выхода 10 первой ячейки второй строки на вход 7 первой ячейки первой строки, сигнал с выхода 10 первой ячейки третьей строки - на вход 7 второй ячейки первой строки и так далее, Результат операции - произведение двоичных операндов - формируется на выходах 12 матрицы, старший разряд произведения образуется на выходе 10 первой строки матрицы. Таким образом, введение в каждую ячейку устройства дву-х элементов И и сумглатора по модулю два позволяет расширить его функциональные возможности. Устройство перспективно для реализации в виде больших интегральных схем благодаря однородности стру туры. Формула изобретения Матричное вычислительное устройство, каткдая ячейка которого содержит одноразрядный сумматор и первый элемент И, причем первые входы первых э.г1ементов . И ячеек каждого столбца матрицы подключены к соответствующему разрядному входу первого операнда устройства, вторые входы первых элементов И ячеек каждой строки матрицы подключены к соответствующему разрядному входу второго операнда устройства, выход первого элемента И каждой ячейки подключен к первому входу одноразрядного сумматора этой же ячейки, выход суммы одноразрядного сумматора каждой ячейки - ко второму входу одноразрядного cy лмaтopa ячейки следующей строки предыдущего столбца матрицы, о тл и ч а ю щ е е с я тем, что, с целью раоаирения функциональных возмэжнрстей устройства .за счет выполнения операции вычисления значения многочлена- r(fi ) , где (Ь - примитивный элемент поля Галуа, в каждую ячейку дополнительно введены два .элемента И и сумматор по модулю два, Ьричем первый вход второго элемента И каждой ячейки матрицы подключен к выходу суммы одноразрядного сумматора этой же ячейки, вторые входы вторых элементов И ячеек каждой строки матрицы - к соответствующему разрядному входу кода коэффициента, многочлена r{(i) устройства, выход второго элемента И каждой ячейки - к первому входу сумматора по модулю два этой же ячейки, выход сумматора по модулю два каждой ячейки - ко второглу входу сумматора по модулю два ячейки следующей строки того же столбца матрицы, выход переноса одноразрядного сумматора каждой ячейки - к первому входу третьего элемента Н этой же ячейки, вторые входы третьих элементов И ячеек каждой строки матрицы к управляющему входу операции устройства, а выход третьего элемента И каждой ячейки - ко входу переноса одноразрядного сумматора той же строки предыдущего столбца. Источники информации, принятые во внимание при экспертизе I 1. Guild-Н. И. Some Cellular Logic Arrays for Non-Restoring Binary Division. - The Radio and Electronic Eng. 1970, 39, № 6, p, 345-348. 2. Карцев M. A. Арифметика цнФроВЫХ машин. М., аука, 1969, с. 444 (прототип).