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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Сощналнстнчесннх Республик(22) Заявлено 05.06.78 (21) 2624217/18-24с присоединением заявки Йо -(Я)м,С 06 Р 7/38 Государственный комитет СССР по делам изобретений и открытий(72) Авторы изобретения Л. А. Шумилов, Л. А. Зайкова и С. М. Тентиева Ленинградский ордена Ленина электротехнический институт им. В, И. Ульянова (Ленина)(54) МАТРИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО Изобретение относится к области автоматики и вычислительной техники и может быть использовано в быстродействующих процессорах и коцирующихдекодирующих устройствах.5Известно матричное вычислительное устройство МВУ для выполнения операции деления 11, состоящее из матрицы ячеек, каждая из которых содержит одноразрядный сумматор-вычитатель и имеет четыре входа:делимого, делителя, переноса-заема из одноразрядного сумматора-вычитателя последующей ячейки строки матрицы в одноразрядный сумматор (вычитатель предыдущей 15 ячейки этой же строки матрицы, входа управления, и четыре выхода: частичного остатка, переноса-заема из одноразрядного сумматора) вычитателя данной ячейки строки матрицы в одно разрядный сумматор-вычитатель предыдущей ячейки этой же строки матрицы, делителя, выхода управления. Основным его недостатком являются ограниченные функциональные возможности, т.е. при данном наборе узлов и связей между ними укаэанное устройство позволяет выполнять толь-. ,ко одну арифметическую операцию, а З 0,именно операцию деления двоичных чисел.Наиболее близким по технической сущности к предлагаемому устройству является матричное вычислительное устройство (МВУ), каждая ячейка которого содержит одноразрядный сумматор и элемент И, причем первые входы элементов И ячеек 1-ой (1=1-:а, где а - разрядность элементов поля Галуа) строки матрицы подкзпочены к первому входу устройства, вторые входы элементов И ячеек )-ого =1-:а) столбца матрицы - ко второму входу устройства, а выход элемента И ячейки - к первому входу сложения одноразрядного сумматора этой же ячейки 121 .Однако, как видно из описания данного матричного вычислительного устройства, оно как и предыдущее, обладает ограниченными функциональными возможностями, так как позволяет выполнять лишь одну арифметическую операцию умножения двоичных операндов и имеет неоднородную структуру.Целью изобретения является расширение функциональных возможностей устройства за счет выполнения умножения элементов поля Галуа.Поставленная цель достигается темчто в устройство, каждая ячейка которого содержит одноразрядный сумматори элемент И, причем первые вхбды элементов И ячеек 1-ой =1-:а, где аразрядность элементов поля Галуа)строки матрицы подключены к первомувходу устройства, вторые входы эле",ментов И ячеек )-ого =1-:а) столб"ца матрицы подключены ко второму входу устройства, а выход элемента Иячеек подключен к первому входу сложения одноразрядного сумматора этой жеячейки, в каждую ячейку матрицы устройства дополнительно введены сумматор по модулю два, два элемента И,причем первый вход второго элемента И 15ячеек (-ой строки матрицы подключенк первому управляющему входу устройства, второй вход второго элемента Иячеек )-ого столбца матрицы подключен к третьему входу устройства, выход второго элемента И ячейки матрицы подключен к первому входу сумматора по модулю два этой же ячейки,выход сумматора по модулю два подключен ко второму входу сложения одноразрядного сумматора ячейки, выходпереноса которого подключен к одному. из входов третьего элемента И ячейки, другой вход которого подключен ковторому управляющему входу устройства, а выход третьего элемента И каждой ячейки -ой строки матрицы подключен к входу переноса одноразрядного сумматора +1)-ой ячейки этойже строки матрицы, выход суммы одноразрядного сумматора ячейки подключен ко второму входу сумматора помодулю два +1, 1+1 ячейки матрицы.Операция умножения элементов поляГалуа СГ ( 2) выполняется по правилу умножения представляющих эти элементы многочленов, степень которых(а) меньше по модулю заданного многочлена(М)х степени а.Например, если представить элементы поля СГ(2) и Рк в виде многочленов в (х) и с(х) , то результатоперации умнокения запишется в видеГ(х)=Ь(х) с(х) щодй(х),где, Г(х) - многочлен, представляющийтакже элемент 8 поля 50ОГ(2 ),Таким образом, при выполненииоперации умножения элементов поляСГ(2 О) необходимо осуществлять операции умножения и деления двоичныхмногочленов,На чертеже представлена схема предлокенного устройства.Устройство содержит одноразрядныесумматоры 1, элементы 2 И, элементыИ 3, сумматоры по модулю два 4, элементы И 5, входные устройства б, 7,8, управляющий вход 9, вход 10 устройства, выходы устройства 11, 12вход 13 устройства и управляющийвход 14, 65 Устройство МВУ работает следующим,образом,При выполнении операции умноженияэлементов поля Галуа 6 Е(2) под действием сигналов управления элементы2 И всех ячеек МВУ разомкнуты, в результате чего одноразрядный сумматор 1 каждой ячейки выполняет операцию сложения по модулю два. На входь;устройства 7, 13 и управляющий вход9 первой строки матрицы подается код"О". Сигнал с выхода устройства 12каждой предыдущей строки подается науправляющий вход 9 каждой последующей строки матрицы,На вход устройства 10 поступаеткод элемента поля В, разрядностиа, составленный из коэффициентов многочлена с (х),На входы б поступает код элементаполя В разрядности а, составленныйиз коэффициентов многочлена в(х).Число строк матрицы, а также число ячеек в строке, определяются разрядностью перемножаемых элементов поля и равны а.На вход 8 поступает код разрядности а, составленный из а-младших коэффициентов заданного многочлена М(х)степени а. Элементы 3 И ячеек каждойстроки матрицы управляются соответствующим разрядом кода элемента поляна вторые же входы указанных элементов поступают соответствующие разряды кода элемента поля р;,Таким образом, элементы 3 И каждойстроки матрицы формируют частичныепроизведения кода элемента поля Р, насоответствующий разряд кода элементаполя ( начиная от старших разрядов кода элемента поляВ первой строке матрицы частичноепроизведение передается на выход одноразрядных сумматоров 1 ячеек,и ссоответствующим сдвигом на одий разряд влево оно поступает на входы сумматоров по модулю два 4 ячеек второйстроки. Старший разряд указанного частичного произведения является сигналом управления для элементов И 5 ячеек второй строки матрицы и поступаетна управляющий вход 9. Во второй строке производится операция деления кода частичного произведения (делимое), на код многочлена М(х) (делитель), которая состоит в следующем. Если значение старшего разряда указанного частичного произведения равно единице, то из делимого производится операция вычитания делителя с помощью сумматоров по модулю два 4, так как операция вычитания по модулю два равносильна операции сложения по модулю два, Если же значение старшего разряда равно нулю, то производится передача делимого на выход сумматоров по модулю два 4 ячеек второй строки матрицы.Результат операции деления суммируется по модулю с помощью одноразрядных сумматоров 1 ячеек с частичным произведением, получаемым н .данной строке матрицы и частичный результат операции умножения элемен пов поля формируется на выходах ячеек второй строки матрицы,Аналогичным образом н последующих строках матрицы с необходимым сдвигом производится операция деления частичных результатов на код многочлена М(х). Причем сигналом управления для каждой строки матрицы является значение старшего разряда частичного результата, полученного в предыдущей строке, и операция суммирования с помощью одноразрядных сумматоров 1 ячеек результатов операции деления, образующихся на выходах сумматоров по модулю,цва 4 ячеек с соответствующими частичными произведениями.Результат операции умножения элементов поля 6 Е(2 о) формируется на выходы 12 ячеек последней строки матцы.25При выполнении операции умножения а-разрядных двоичных операндов, начиная от старших разрядов множителя, элементы 2 И всех ячеек матрицы под действием сигналов управления находятся в "открытом" состоянии, На входы 8, 13 и управляющий вход 9 подается код "0".На входы 10 каждой.1 троки матрицы 35подаются разряды множителя, на входы б - разряды множимого.Сигналы с выхода 11 первых ячееккаждой строки, кроме первой ячейкипервой строки, подаются на входы 7, 40а именно сигнал с выхода 11 первойячейки второй строки подается навход 7 первой ячейки первой строки,сигнал с выхода 11 первой ячейки второй строки подается на вход 7 первой 45ячейки первой строки, сигнал с выхода 11 первой ячейки третьей строкина вход 7 второй ячейки первой строки и так далее,Результат операции - 2 а - разряд 50ное произведение - формируется на выходе 12 матрицы, а старший разряд произведения образуется на выходе 11первой строки матрицы.Таким образом, предлагаемое МВУобладает более широкими Функциональными возможностями, что достигнутовведением н каждую ячейкуустройства сумматора по модулю два, элемента И, ключа и ноной организации связей. 60Описанное выше устройство было реализовано также на микросхемах 133-ойсерии. Время выполнения операции умножения элементов поля СЕ (2 ) равно 4 мкс,Таким образом, предлагаемое МВуобладает большими функциональными возможностями, позноляет повысить скорость выполнения операции умноженияэлементов поля (приблизительно н 5раз) и перспективно для реализациин виде больших интегральных схем,благодаря однородности и регулярности структуры,Формула изобретенияМатричное вычислительное устройство, каждая ячейка которого содержит одноразрядный сумматор и элемент, И, причем первые входы элементов И ячеек 1-ой (1=1-;а, где а - разрядность элементов поля Галуа) строки матрицы подключены к первому входу устройства, вторые входы элементов И ячеек )-ого (=1-;а) столбца матрицы подключены ко второму входу устройства, а выход элемента И ячейки подключен к первому входу сложения одноразрядного сумматора этой же ячейки, о,т л и ч а ю щ е е с я тем, что, с целью расширения Функциональных возможностей, за счет возможности умножения элементов поля Галуа, в каждую ячейку матрицы устройства дополнительно введены сумматор по модулю два, два элемента И, причем первый вход второго элемента И ячеек 1-ой строки матрицы подключен к первому управляющему входу устройства, второй вход второго элемента И ячеек -ого столбца матрицы подключен к третьему входу устройства, выход второго элемента И ячейки матрицы подключен к первому входу сумматора по модулю дна этой же ячейки, выход сумматора по модулю дна подключен ко нторому входу сложения одноразрядного сумматора ячейки, выход переноса которого подключен к одному из входов третьего элемента И, другой вход которого подключен ко второму управляющему входу устройства, а выход третьего элемента И подключен к входу переноса одноразрядного сумматора 1-ой ячейки этой же строки матрицы, выход суммы одноразрядного сумматора ячейки подключен ко второму входу сумматора по модулю два 1 +1, ) +1 ячейки матрицы.Источники информации,принятые во внимание при экспертизе1. "ТЬе Над 1 о апд Е 1 ессгоп 1 с Епц",1970, 39, 9 б, с. 345-348,2. Карцев М. А., Арифметика цифровых машин. М "Наука", 1969,с. 444.в Составительва Тех ед Ж. К Го ь ак Кор екто С. Шекма Подписно филиал ППП "Патент", г. Ужгород, ул. Проектная аз 4650/38ЦНИИПИ Госпо делам 113035 Москв арс изо ЖТираж 751енного комиетений и оРаушская тета СССРкрытийнаб. д. 4 5