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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик оц 960803(23) Приоритет -Опубликовано 23 Я 982. Бюллетень М 35Дата опубликования описания 23,09,82 151 М. Кл.з С 06 Г 7/38 Государственный комитет СССР по делам изобретений и открытий(72) Авторы изобретени йкова, В. М. Деревянкин, В. П и Л. А, шумилов ов мики АН Украинско 1 машиностроительный лектрод вградск Институт и Вороши(71 ) Заявител ститут ИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО(54 10 Изобретение относится к автоматикеи вычислительной технике и может бытьиспользовано в быстродействуюШих процессорах и кодируюших-декодируюших ,устройствах,Известно матричное вычислительноеустройство для выполнения операцииделения двоичных операндов 11.Основным недостатком указанногоустройства являются ограниченные Функциональные возможности, т.е. приданном наборе узлов и связей междуними устройство позволяет выполнятьтолько одну ариФметическую операциюделения двоичных операндов.Наиболее близким к изобретениюпо технической сущности является матричное вычислительное устройство длявыполнения операции умножения двоичных операндов, содержшдее матрицуячеек и блок сумматоров, Каждая ячейка состоит из одноразрядного сумматора и элемента И, причем первые входыэлементов И ячеек каждого столбцаматрицы подключены к,одному из первыхвходов устройства, вторые входы элементов И ячеек каждой строки подключены к одному из вторых входов устройства, выход элемента И ячейки подключен к первому входу одноразрядного сумматора этой же ячейки, выход суммы одноразрядного сумматора каждой ячейки подключен ко второму входу одноразрядного сумматора ячейки следуюцвй строки предыдуШего столбца матрицы, выходы сумм и переносов одноразрядных сумматоров ячеек первого столбца матрйцсоединены соответствующими входами одноразрядных сумматоров блока суммторов 2 .Однако устройство обладает ограниченными Функциональными возможностя- ми, так как позволяет выполнять лишь одну ариФметическую операцию умножения двоичных операндов и имеет неоднородную структуру.Целью изобретения является расширение Функциональных возможностей устройства за счет выполнения операции вычисления значения многочлена Г( Р ), где р - примитивный элемент поля Галуа.Поставленная цель достигается тем, что в матричном вычислительном устройстве каждая ячейка которого содержит одноразрядный сумматор и первый элемент И, причем первые входы первых элементов И ячеек каждого столбца матрицы подключены к соответствуюшему разрядному входу первого операндаустройства, вторые входы первых элементов И ячеек каждой строки матрицы подключены к соответствуюцему разрядному входу второго операнда устройства, выход первого элемента И каждой ячейки подключен к первому входу одноразрядного сумматора этой же ячейки, выход суммы одноразрядного сумматора каждой ячейки - ко второму входу одноразрядного сумматора ячейки следуюцей строки предыдущего столбца матрицы,10 в каждую ячейку дополнительно введены два элемента И и сумматор по модулю два, причем первый вход второго элемента И каждой ячейки матрицы подключен к выходу суммы одноразрядного сум матора этой же ячейки, вторые входы вторых элементов И ячеек каждой строки матрицы - к соответствующему разрядному входу кода коэффициента многочлена гЪ ) устройства, выход второго элемента И каждой ячейки - к пер вому входу сумматора по модулю два этой же ячейки, выход сумматора по модулю два каждой ячейки - ко второму входу сумматора по модулю два ячайки следующей строки того же столбца матрицы, выход переноса одноразрядного сумматора каждой ячейки - к первому входу третьего элемента И этой же ячейки, вторые входы третьих элементов И ячеек каждой строки матрицы - к управляющему входу операции устройства, а выход третьего элемента И каж. дой ячейки - ко входу переноса одноразрядного сумматора той же строки предыдущего столбца. 35На чертеже представлена схема вычислительного устройства.Устройство содержит ячейки, каждая из которых состоит из элементов И 1 и 2, одноразрядного сумматора 3, 40 элемента И 4 сумматора 5 по модулю два, входы б первого операнда, входы 7, на которые поступают значения из предыдущей строки, входы 8 соединены с выходами сумматоров 5 по модулю два 4 ячеек предыдущей строки, входы 9 вторОго операнда, выходы 10, соединенные со входами переноса сумматоров 3 ячеек предыдущего столбца той же строкиуправляющие входы 11 операции, выходы 12 сумматоров 3, входы 13 кода коэффициента многочлена г( ф ),входы 14 переноса сумматоров 3.Первые входы элементов И 1 ячеек матрицы подключены к соответствующе- му входу 6 устройства, вторые входы 55 элементов И 1 ячеек матрицы подключены к соответствующему входу 9 устройства, выход элемента И 1 каждой ячейки матрицы подключен к первому входу одноразрядного сумматора 3 той же 60 ячейки, выход суммы одноразрядного сумматора 3 подключен ко второму входу одноразрядного сумматора ячейки следующей строки предыдущего столбца матрицы. Первый вход элемента И .4 каждой ячейки подключен к выходу суммы одноразрядного сумматора 3 этой же ячейки, вторые входы элементов И 4 ячеек матрицы - к соответствующему входу 13, выход элемента И 4 ячейки к первому входу сумматора 5 по модулю два этой же ячейки, выход сумматора 5 по модулю два каждой ячейки - ко второму входу сумматора 5 по модулю два ячейки следующей строки того же столбца, выход переноса одноразрядного сумматора 3 ячейки - к первому входу элемента И 2 этой же ячейки, вторые входы элементов И 2 ячеек матрицы - к соответствуюц 1 ему входу 11, выход элемента И 2 каждой ячейки - ко входу переноса одноразрядного сумматора 3 ячейки той же строки предыдущего столбца матрицы.Для выполнения операции вычисления значения многочлена г( х) при х, равном примитивному элементу 9 поля Галуа СР(2 ), необходимо в многочлен видаг(х) = го+ гх+ гх ++ гх,1- О, г, гАССР(2)подставить элемент /Ь 6 СР (2 ), воз" вести элемент Р в степень 1, 3 = 2, йпричем Р 6 СР(2 ), и осуществить суммирование по модулю два слагаемых многочлена г( В ), у которых коэффициенты г не равны нулю. Результат операции - элемент поля Галуа СР(2 ).Устройство работает следующим образом.При выполнении операции вычисления значения многочлена г( ф ), где Р примитивный элемент поля Галуа СР(2 ), на управляющие входы 11, входы 8 (исключая вход 8 ячейки первой строки последнего столбца матрицы) входы 13 и вход 9 первой строки матрицы подается код "О" . Сигнал с выхода 12 каждой предыдущей строки подается на вход 9 первой строки матрицы подает ся код "0" . Сигнал с выхода 12 каждой предыдущей строки подается на вход 9 каждой последующей строки матрицы. На входы 7 устройства поступает код элемента поля ф разности а, На входы б устройства поступает код разрядности а, составленный из а младших коэффициентов минимального многочлена М(х) дляэлемента 5На вход 8 ячейки первой строки последнего столбца матрицы поступаетна код коэффициента г . На входы 13 устройства подается код разрядности составленный из коэффициентов много- члена г(), причем код коэффициента г поступает на вход 13 первой строки матрицыВ первой строке матрицы производится умножение коэффициента г на элемент поля Ь с помощью одноразрядного сумматора 3, элемента И 4 и суммирование с коэффициентом г , что осуществляется сумматором 5 по модулю два10 15 45 Источники информации,50 принятые во внимание при экспертизе1. Сц 1 Ы.Н. Н. Зобе СеРРцРаг Ьод 1 с 55 ячейки первой строки последнего столбца матрицы.В последующих строках матрицы производится операция возведения элементав степень 1 по модулю минимального лногочлена М(х), которая осуществляется последовательным сдвигом элемента 5 на один разряд влево. Это равносильно выполнению операции р(З=Деление полученных степеней элемента Д на многочлен Мх) производится с помощью элементов И 1 иодноразрядных сумматоров 3 ячеек каждой строки матрицы. Значение старшего разряда элемента поля в данной строке матрицы служит сигналом управления для элементов И 1 ячеек последующей строки.Элементы поляумножаются на соответствующие коэффициенты г с по.1 мощью элементов И 4 и произведения суммируются сумматорами 5 по модулю два ячеек каждой строки матрицы.Окончательный результат операции -значение многочлена г.(ф - формируется на выходах устройства.При выполнении операции умножения двоичных операндов от старших разрядов множителя на управлякцие входы 11 устройства подается код "1 ф, на входы 7, 8, 13 и 14 - код "0". На входы 9 каждой строки матрицы подает ся разряд множителя, на входы б разряды множимого.Сигналы с выхода 10 первых ячеек каждой строки, кроме первой ячейки первой строки, подаются на входы 7 устройства, а именно сигнал с выхода 10 первой ячейки второй строки - на вход 7 первой ячейки первой строки, сигнал с выхода 10 первой ячейки третьей строки - на вход 7 второй ячейки первой строки и так далее,Результат операции - произведение двоичных операндов - формируется на выходах 12 матрицы, старший разряд произведения образуется на выходе 10 первой строки матрицы.Таким образом, введение в каждую ячейку устройства двух элементов И и сумматора по модулю два позволяет расширить его функциональные возможности, Устройство перспективно для реализации в виде больших интегральных схем благодаря однородности структуры.Формула изобретенияМатричное вычислительное устройство, каждая ячейка которого содержит одноразрядный сумматор и первый.элемент И, причем первые входы первых элементов.И ячеек каждого столбца матрицы подключены к соответствующему разрядному. входу первогооперанда устройства, вторые входыпервых элементов И ячеек каждой строки матрицы подключены к соответствующему разрядному входу второго операнда устройства, выход первого эле"мента И каждой ячейки подключен к первому входу одноразрядного сумматора этой же ячейки, выход суммы одноразрядного сумматора каждой ячейки - ко второму входу одноразрядного сумматора ячейки следующей строки предыдущего столбца матрицы, о т" л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства эа счет выполнения операции вычисления значениямногочлена. г( р ), где- примитивный элемент поля Галуа, в каждуюячейку дополнительно введены дваэлемента И и сумматор по модулю два, 25 буричем перв й вход второго элементаИ каждой ячейки матрицы подключенк выходу суммы одноразрядуого сумматора этой же ячейки, вторые входывторых элементов И ячеек каждой строки матрицы - к соответствующему раз.рядному входу кода коэффициента, многочлена г() устройства, выход второго элемента И каждой ячейки - к первому входу сумматора по модулю два этой же ячейки, выход сумматора по З 5 модулю два каждой ячейки - ко второму входу сумматора по модулю два ячейки следующей строки того же столбца матрицы, выход переноса одноразрядного сумматора каждой ячейки - к пер вому входу третьего элемента И этой же ячейки, вторые входы третьих элементов И ячеек каждой строки матрицы -к управляющему входу операции устройства, а выход третьего элемента Икаждой ячейки - ко входу переноса одноразрядного сумматора той же строкипредыдущего столбца,Аггауз Еог Иоп-йезйог 1 щ 131 пагу Л 1 ч 11 оп. - "ТЬе Кас 11 о ап 1 ЕРесйгоп 1 с Епд", 1970, 39, Р б, р, 345-348.2. Карцев М. А. Арифметика цифровых машин. М., "аука", 1969, с. 444 (прототип).Тираж 731, ПодписиИ Государственного комитета СССРделам изобретений и открытийИосква, Ж, Раушская наб д, 4/5 За Филиал ППП фПатент", г. Ужгород Проектная Составитель В. Березкин едактор Л. Шишкина Техред,Е.ХаритончикКорректор С. Шекма