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

: Изобретение относится к области автоматики и вычислительной техник и может быть использовано в быстродействующих процессорах и кодирующих декодирующих устройствах. Известно матричное вычислительное устройство ИВУ для выполнения операции деления f , состоящее из матрицы ячеек, кахшая из которых содержит одноразрядный сумматор-вычитатель и имеет четыре входа:делимого, делителя, переноса-заема из одноразрядного сумматора-вычитателя последующей ячейки строки матрицы в одноразрядный сумматор (вычитатель предыдущей ячейки этой же строки матрицы, входа управления, и четыре выхода: частичного остатка, переноса-заема из одноразрядного сумматора) вычитателя данной ячейки строки матрицы в одноразрядный сумматор-вычитатбль предыдущей ячейки этой же строки матрицы, делителя, выхода управления. Основным его недостатком являются ограниченные функциональные возможности, т.е. при данном наборе узлов и связей между ними указанное устройство позволяет выполнять толь.ко одну арифметическую операцию, а именно операцию деления двоичных чисел. Наиболее близким по технической сущности к предлагаемому устройству является матричное вычислительное устройство (МВУ), каходая ячейка которого содержит одноразрядный сумматор и элемент И, причем первые входы элементов И ячеек i-ой (, где а - разрядность элементов поля Галуа) строки матрицы подключены к первому входу устройства, вторые входы элементов И ячеек j-oro () столбца матрицы - ко второму входу устройства, а выход элемента И ячейки - к первому входу сложения одноразрядного сумматора этой же ячейки 2. Однако, как видно из описания данного матричного вычислительного устройства, оно как и предыдущее, обладает ограниченными функциональными возможностями, так как позволяет выполнять лишь одну арифметическую операцию умножения двоичных операндов и имеет неоднородную структуру. Целью изобретения является расширение функциональных возможностей устройства за счет выполнения умножения элементов поля Галуа. Поставленная цель достигается тeм что в устройство, каждая ячейка кото рого содержит одноразрядный сумматор и элемент И, причем первые входы эле ментов И ячеек i-ой (, где а разрядность элементов поля Галуа) стр.оки матрицы подключены к первому входу устройства, вторые входы эле; 1ентов И ячеек j-oro ) столбца матрицы подключены ко второму вхо ду устройства, а выход элемента И ячеек подключен к первому входу слож ния одноразрядного сумматора этой же ячейки, в каждую ячейку матрицы устройства дополнительно введены сумматор по модулю два, два элемента И, причем первый вход второго элемента ячеек -ой строки матрицы подключе к первому управляющему входу устройства, второй вход второго элемента И ячеек j-oro столбца матрицы подключен к третьему входу устройства, выход второго элемента И ячейки матрицы подключен к первому входу сумматора по модулю два этой же ячейки, выход сумматора по модулю два подклю чен ко второму входу сложения одноразрядного сумматора ячейки, выход переноса которого подключен к одному . из входов третьего элемента И ячейки, другой вход которого подключен к второму управляющему входу устройства, а выход третьего элемента И каждой ячейки i-ой строки матрицы под ключен к входу переноса одноразрядного сумматора (+1)-ой ячейки этой же строки матрицы, выход суммы одноразрядного сумматора ячейки подключен ко второму входу сумматора по г модул 0 два i+1, j+1 ячейки матрицы. Операция умножения элементов поля Галуа GF ( 2°) выполняется по правилу умножения представляющих эти элементы многочленов, степень которых (а-1) меньше по модулю заданного мно гочлена(м)х степени а. Например, если представить элемен ты поля GF(2°) и в виде многочленов в (х) и с(х) , то результат операции умножения запишется в виде f(х)Ь(х) -с(х) modH(x), где, f(X) - многочлен, представляющий также элемент 8т поля GF(2). Таким образом, при выполнении операции умножения элементов поля GF(2°) необходимо осуществлять операции умножения и деления двоичных многочленов. На чертеже представлена схема пре ложенного устройства. Устройство содержит одноразрядные сумматоры 1, элементы 2 И, элементы И 3, сумматоры по модулю два 4, элементы И 5, входные устройства б, 7, 8, управляющий вход 9, вход 10 устройства, выходы устройства 11, 12). вход 13 устройства и управляющий вход 14 . Устройство МВУ работает следующиг, образом. При выполнении операции умножения элементов поля Галуа GF(2) под действием сигналов управления элементы 2 И всех ячеек МВУ разомкнуты, в реЬультате чего одноразрядный суммаtrop 1 каждой ячейки выполняет операцию сложения по модулю два. На входв устройства 7, 13 и управляющий вход 9 первой строки матрицы подается код О. Сигнал с выхода устройства 12 каждой предыдущей строки подается на управляющий вход 9 каждой последующей строки матрицы. На вход устройства 10 поступает код элемента поля В , разрядности а, составленный из коэффициентов многочлена с (х). На входы 6 поступает код элемента поля Р; , разрядности а, составленный из коэффициентов многочлена в(х). Число строк матрицы, а также число ячеек в строке, определяются разрядностью перемножаемых элементов поля и равны а. . На вход 8 поступает код разрядности а, составленный из а-младших коэффициентов заданного многочлена М(х) степени а. Элементы 3 И ячеек каждой строки матрицы управляются соответствующим разрядом кода элемента поля , на вторые же входы указанных элементов поступают соответствующие разряды кода элемента поля р- . Таким образом, элементы 3 И каждой строки матрицы формируют частичные произведения кода элемента поля pj на соответствующий разряд кода элемента поля f. , начиная от старших разрядов кода элемента поля р . В первой строке матрицы частичное произведение передается на выход одноразрядных сумматоров 1 ячеек и с соответствующим сдвигом на один разряд влево оно поступает на входы сумматоров по модулю два 4 ячеек второй строки. Старший разряд указанного частичного произведения является сигналом управления для элементов И 5 ячеек второй строки матрицы и поступает на управляющий вход 9. Во второй строке производится операция деления кода частичного произведения (делимое), на код многочлена М(х) (делитель), которая состоит в следующем. Если значение старшего разряда указанного частичного произведения равно единице, то из делимого производится операция вычитания делителя с помощью сумматоров по модулю два 4, так как операция вычитания по модулю два равносильна операции сложения по модулю два. Если же значение старшего разряда равно нулю, то производится передача делимого на выход сумматоров по модулю два 4 ячеек второй строки матрицы. Результат операции деления суммируется по модулю с помощью одноразрядных сумматоров 1 ячеек с частичным произведением, получаемым в данной строке матрицы и частичный результат операции умножения элемен тгов поля формируется на выходах ячеек второй строки матрицы. Аналогичным образом в последующих строках матрицы с необходимым сдвигом производится операция деления час тичных результатов на код многочлена М{х). Причем сигналом управления для ка;кдой строки матрицы является значение старшего разряда частичного результата, полученного в предыдущей стро ке, и операция суммирования с помощью одноразрядных сумматоров 1 ячеек результатов операции деления, образующихся на выходах сумматоров по модулю два 4 ячеек с соответствующими частичными произведениями. Результат операции умножения элементов поля GF{2°) формируется на вы ходы 12 ячеек последней строки матцы. При выполнении операции умножения а-разрядных двоичных операндов, начи ная от старших разрядов множителя, элементы 2 и всех ячеек матрицы под действием сигналов управления находя ся в открытом состоянии. На входы 8, 13 и управляющий вход 9 подается код О. На входы 10 каждой .(jj т рок и матрицы подаются разряды множителя, на входы б - разряды множимого. Сигналы с выхода 11 первых ячеек каждой строки, кроме первой ячейки первой строки, подаются на входы 7, а именно сигнал с выхода 11 первой ячейки второй строки подается на вход 7 первой ячейки первой строки, сигнал с выхода 11 первой ячейки вт рой строки подается на вход 7 перво ячейки первой строки, сигнал с выхо да 11 первой ячейки третьей строки на вход 7 второй ячейки первой стро ки и так далее. Результат операции - 2а - разряд ное произведение - формируется на в ходе 12 матрицы, а старший разряд п изведения образуется на выходе 11 первой строки матрицы. Таким образом, предлагаемое МВУ обладает более широкими функциональ ными возможностями, что достигнуто введением в каждую ячейкуустройства сумматора по модулю два, элемента И, ключа и новой организации свя зей. Описанное выше устройство было р ализовано также на микросхемах 133-о се.рии. Время выполнения операции ум ножения элементов поля GF (2) равно 4 МКС. Таким образом, предлагаемое МВУ бладает большими функциональными возожностями, позволяет повысить скоость выполнения операции умножения . лементов поля (приблизительно в 5 )a3) и перспективно для реализации виде больших интегральных схем, лагодаря однородности и регулярности структуры. - Формула изобретения Матричное вычислительное устройство, каждая ячейка которого содержит одноразрядный сумматор и элемент. И, причем первые входы элементов И ячеек i-ой (, где а - разрядность элементов поля Галуа) строки матрицы подключены к первому входу устройства, вторые входы элементов И ячеек j-oro (1та) столбца матрицы подключены ко второму входу устройства, а выход элемента И ячейки подключен к первому входу сложения одноразрядного сумматора этой же ячейки, о,тличающееся тем, что, с целью расширения функциональных возможностей, за счет возможности умножения элементов поля Галуа, в каждую ячейку матрицы устройства дополнительно введены сумматор по модулю два, два элемента И, причем первый вход второго элемента И ячеек i-ой строки матрицы подключен к первому управляющему входу устройства, второй вход второго элемента И ячеек j-oro столбца матрицы подключен к третьему входу устройства, выход второго элемента И ячейки матрицы подключен к первому входу сумматора по модулю два этой же ячейки, выход сумг-iaTopa по модулю два подключен ко второму входу сложения одноразрядного сумматора ячейки, выход переноса которого подключен к одноглу из входов третьего элемента И, другой вход которого подключен ко второму управляющему входу устройства, а выход третьегр элемента И подключен к входу переноса одноразрядного сумматора j-ой ячейки этой же строки матрицы, выход суммы одноразрядного сумматора ячейки подключен ко второму входу сумматора по модулю два i +1, j +1 ячейки матрицы. Источники информации, принятые во внимание при экспертизе 1. Radio and Electronic Eng, 1970, 39, 6, с.- 345-348. 2.Карцев М. A., Арифметика цифровых машин. М., Наука, 1969, с. 444.

t

П

2

n