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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Сощналнстнчесннх

Республик

<„>750484 (61) Дополнительное к авт, свид-ву (22) Заявлено 05.06.78 (21) 2624217/18-24 с присоединением заявки Йо— (23) Приоритет (опубликовано 23.0780. Бюллетень М 27

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

С 06 7/38

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

СССР по делам изобретений и открытий (53) УДК681. 325 (088. 8) (72) Авторы изобретения

Л. A. Шумилов, Л. А. Зайкова и С. М. Тентиева

Ленинградский ордена Ленина электротехнический институт им. В. И. Ульянова (Ленина) (71) Заявитель (54) МАТРИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО

Изобретение относится к области

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

Известно матричное вычислительное устройство МВУ для выполнения операции деления (1), состоя>цее из матрицы ячеек, каждая из которых содержит одноразрядный сумматор-вычитатель и имеет четыре входа:делимого, делителя, переноса-заема из одноразрядного сумматора-вычитателя последующей ячейки строки матрицы в одноразрядный сумматор (вычитатель предыдущей 1з ячейки этой >ке строки матрицы, входа управления, и четыре выхода: частичного остатка, переноса-заема из одноразрядного сумматора) вычитателя данной ячейки строки матрицы в одно- 20 разрядный сумматор-вычитатель предыдущей ячейки этой же строки матрицы, делителя, выхода управления.

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

Наиболее близким по те .нической сущности к предлагаемому устройству является матричное вычислительное устройство (МВУ), каждая ячейка которого содержит одноразрядный сумматор и элемент И, причем первые входы элементов И ячеек i-ой (i=1-:а, где а — разрядность элементов поля Галуа) строки матрицы подкзпочены к первому входу устройства, вторые входы элементов И ячеек j-ого (j=1-:à) столбца матрицы — ко второму входу устройства, а выход элемента И ячейки — к первому входу сложения одноразрядного сумматора этой же ячейки 12 .

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

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

750484

Поставленная цель достигается тем> что в устройство, каждая ячейка которого содержит одноразрядный сумматор и элемент И, причем первые вхбды элементов И ячеек !-ой ((=1-:а, где аразрядность элементов поля Галуа) строки матрицы подключены к первому входу устройства, вторые входы эле,ментов И ячеек j-oro (j=1-:а) столбца матрицы подключены ко второму вхо ду устройства, а выход элемента И ячеек подключен к первому входу сложения одноразрядного сумматора этой же ячейки, в каждую ячейку матрицы устройства дополнительно введены сумматор по модулю два, два элемента И, причем первый вход второго элемента H ячеек i-ой строки матрицы подключен к первому управляющему входу устройства, второй вход второго элемента И ячеек J-oro столбца матрицы подключен к третьему входу устройства, вы- 20 ход второго элемента И ячейки матрицы подключен к первому входу сумматора по модулю два этой же ячейки, выход сумматора по модулю два подключен ко второму входу сложения одноразрядного сумматора ячейки, выход переноса которого подключен к одному . из входов третьего элемента И ячейки, другой вход которого подключен ко второму управляющему входу устройства, а выход третьего элемента И каждой ячейки i-ой строки матрицы подключен к входу переноса одноразрядного сумматора (j+1) ой ячейки этой же строки матрицы, выход суммы одноразрядного сумматора ячейки подключен ко второму входу сумматора по модулю два i+1, j+1 ячейки матрицы.

Операция умножения элементов поля

Галуа GF (2 ) выполняется по правилу умножения представляющих эти эле- 40 менты многочленов, степень которых (а-1) меньше по модулю заданного многочлена(М)х степени а.

Например, если представить элементы поля GF(2o)! и Р в виде многочленов в (х) и с(х), то результат операции умно>кения запишется в виде

f(x)=b(x) -c(x) modN(x), где, f(x) — многочлен, представляющий также элемент В„„поля 50

GF(2 ).

Таким образом, при выполнении операции умножения элементов поля

GF(2о) необходимо осуществлять операции умножения и деления двоичных многочленов.

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

Устройство содержит одноразрядные сумматоры 1, элементы 2 И, элементы

И 3, сумматоры по модулю два 4, эле- 60 менты И 5, входные устройства б, 7, 8, управляющий вход 9, вход 10 устройства, выходы устройства 11, 12 > вход 13 устройства и управляющий вход 14 °, 65

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

При выполнении операции умножения элементов поля Галуа GF(2 ) под действием сигналов управления элементы

2 И всех ячеек МВУ разомкнуты, в результате чего одноразрядный сумматор 1 каждой ячейки выполняет операцию сложения по модулю два. На входь; устройства 7, 13 и управляющий вход

9 первой строки матрицы подается код

"0". Сигнал с выхода устройства 12 каждой предыдущей строки подается на управляющий вход 9 каждой последующей строки матрицы.

На вход устройства 10 поступает код элемента поля В, разрядности а, составленный из коэффициентов многочлена с (х).

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

Число строк матрицы, а также число ячеек в строке, определяются разрядностью перемножаемых элементов поля и равны а.

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

Таким образом, элементы 3 И каждой строки матрицы формируют частичные произведения кода элемента поля р! на соответствующий разряд кода элемента поля (>,, начиная от старших разрядов кода элемента поля

В первой строке матрицы частичное произведение передается на выход одноразрядных сумматоров 1 ячеек,и с соответствующим сдвигом на одий разряд влево оно поступает на входы сумматоров по модулю два 4 ячеек второй строки. Старший разряд указанного частичного произведения является сигналом управления для элементов И 5 ячеек второй строки матрицы и поступает на управляющий вход 9.

Во второй строке производится операция деления кода частичного произведения (делимое), на код многочлена

М(х) (делитель), которая состоит в следующем. Если значение старшего разряда указанного частичного произведения равно единице, то из делимого производится операция вычитания делителя с помощью сумматоров по модулю два 4, так как операция вычитания по модулю два равносильна операции сложения по модулю два. Если же значение старшего разряда равно нулю, то производится передача делимого на выход сумматоров по модулю два 4 ячеек второй строки матрицы.

750484

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

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

М(х). Причем сигналом управления для каждой строки матрицы является значение старшего разряда частичного результата, полученного в предыдущей строке, и операция суммирования с помощью одноразрядных сумматоров 1 ячеек результатов операции деления, образующихся на выходах сумматоров по модулю,цва 4 ячеек с соответствующими частичными произведениями.

Результат операции умножения элементов поля GF(2o) формируется на выходы 12 ячеек последней строки матцы.

При выполнении операции умножения а-разрядных двоичных операндов, начиная от старших разрядов множителя, элементы 2 И всех ячеек матрицы под действием сигналов управления находят-3Р ся в "открытом" состоянии. На входы

8, 13 и управляющий вход 9 подается код "0".

На входы 10 каждой, троки матрицы 35 подаются разряды множителя, на входы 6 — разряды множимого.

Сигналы с выхода 11 первых ячеек каждой строки, кроме первой ячейки первой строки, подаются на входы 7, 4р а именно сигнал с выхода 11 первой ячейки второй строки подается на вход 7 первой ячейки первой строки, сигнал с выхода 11 первой ячейки второй строки подается на вход 7 первой 45 ячейки первой строки, сигнал с выхода 11 первой ячейки третьей строки на вход 7 второй ячейки первой строки и так далее.

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

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

Описанное выше устройство было реализовано также на микросхемах 133-ой серии. Время выполнения операции умножения элементов поля GF ) равно 4 мкс.

Таким образом, предлагаемое МВу обладает большими функциональными возможностями, позноляет повысить скорость выполнения операции умножения элементов поля (приблизительно н 5 раз) и перспективно для реализации

s виде больших интегральных схем, благодаря однородности и регулярности структуры. формула изобретения

Матричное вычислительное устройство, каждая ячейка которого содержит одноразрядный сумматор и элемент.

И, причем первые входы элементов И ячеек i-ой (i=1-:а, где а — разрядность элементов поля Галуа) строки матрицы подключены к первому входу устройства, вторые входы элементов И ячеек j-oro (j=1-:à) столбца матрицы подключены ко второму входу устройства, а выход элемента И ячейки подключен к первому входу сложения одноразрядного сумматора этой же ячейки, о .т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей, за счет возможности умножения элементов поля Галуа, в каждую ячейку матрицы устройства дополнительно введены сумматор по модулю два, два элемента И, причем первый вход второго элемента И ячеек i-ой строки матрицы подключен к первому управляющему входу устройства, второй вход второго элемента И ячеек j-ого столбца матрицы подключен к третьему входу устройства, выход второго элемента И ячейки матрицы подключен к первому входу сумматора по модулю дна этой же ячейки, выход сумматора по модулю дна подключен ко нторому входу сложения одноразрядного сумматора ячейки, выход переноса которого подключен к одному из входов третьего элемента И, другой вход которого подключен ко второму управляющему входу устройства, а выход третьего элемента И подключен к входу переноса одноразрядного сумматора )-ой ячейки этой же строки матрицы, выход суммы одноразрядного сумматора ячейки подключен ко второму входу сумматора по модулю два +1, ) +1 ячейки матрицы.

Источники информации, принятые во внимание при экспертизе

1. "The Radio and Electronic Eng", 1970, 39, Р б, c.. 345-348.

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

750484

Составитель Г. Плешев Редакто П. Го ькова Тех ед Ж. Кастелевич Кор екто С. шекмар

Заказ 4650/38 Тираж 751 Подписное

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

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

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