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

О П И С А Н И Е ( )750485ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскикСоциалистическихРеспубликОпубликовано 23.0.80, Бюллетень27Дата опубликования описания 27.07.80 по делам изобретений и открытий(72) Авторы изобретения Л. А. Шумилов, С. М. Тентиева и Л. А. Зайкова Ленинградский ордена Ленина электротехнический институт им. В. И. Ульянова (Ленина)(54) МАТРИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОИСТВО 1Изобретение относится к автоматике и вычислительной технике и может быть использовано в цифровых арифметических и кодирующих-декодирующих устройствах.Известно матричное вычислительное устройство (МВУ) для выполнения операции деления, состоящее из матрицы вычислительных ячеек, каждая из которых содержит одноразрядный сумматор (вычитатель и имеет четыре входа: делимого, делителя, переноса) заема из одноразрядного сумматора (вычитателя последующей вычислительной ячейки строки в одноразрядный сумматор), вычитатель предыдущей вычислительной ячейки этой же строки матрицы, входа управления, и четыре выхода: частичного остатка, переноса (заема из одноразрядного сумматора) вычитателя данной базовой ячейки строки в одноразрядный сумматор (вычитатель предыдущей вычислительной ячейки этой же строки матрицы), делителя, выхода управления 11). Недостаток устройства - ограниченные функциональные возможности, т. е. при данном наборе узлов и связей между ними указанное устройство позволяет выполнять 2только одну арифметическую операцию, а именно операцию деления двоичных чисел.Наиболее близким по технической сущности к предлагаемому устройству является матричное вычислительное устройство для 5 выполнения операции умножения, содержащее входные регистры, матрицу вычислительных ячеек и блок сумматоров 2 .Выходы первого входного регистра соединены с соответствующими первыми входами вычислительных ячеек первого столбца 1 О матрицы, а первые выходы вычислительныхячеек строк матрицы соединены последовательно с первыми входами последующих вычислительных ячеек тех же строк матрицы, выходы второго входного регистра соединены с соответствующими вторыми входами вычислительных ячеек первой строки матрицы, вторые выходы вычислительных ячеек строк матрицы соединены последовательно со вторыми входами вычислительных ячеек последующих строк тех же столбцов матри О цы, третьи выходы вычислительных ячеексоединены с третьими входами вычислительных ячеек предыдущих столбцов последующих строк матрицы, третьи входы вычислительных ячеек первой строки и последнегостолбца матрицы свободны, а третьи выходы вычислительных ячеек последней строки матрицы являются выходами МВУ, четвертые выходы вычислительных ячеек строк матрицы соединены последовательно с четвертыми входами предыдущих вычислительных ячеек тех же строк матрицы, а четвертые выходы вычислительных ячеек первого столбца матрицы соединены с одними из входов соответствующих одноразрядных сумматоров блока сумматоров, в котором выход переноса каждого одноразрядного сумматора соединен со входом переноса предыдущего одноразрядного сумматора, а выходы, сумм всех одноразрядных сумматоров блока сумматоров являются выходами устройства.Каждая вычислительная ячейка матрицы МВУ содержит элемент И и одноразрядный сумматор,Данное устройство также обладает ограниченными функциональными возможностями, так как позволяет выполнять лишь одну арифметическую операцию умножения двоичных чисел.Цель изобретения - расширение функциональных возможностей устройства за счет выполнения операции деления полиномов, которая необходима при кодировании и декодировании информации.Поставленная цель достигается тем, что матричное вычислительное устройство, содержащее входные регистры, матрицу вычислительных ячеек и блок сумматоров, причем первые выходы вычислительных ячеек каждой строки матрицы соединены с первыми входами последующих вычислительных ячеек той же строки матрицы, вторые выходы вычислительных ячеек каждой строки матрицы соединены со вторыми входами соответствующих вычислительных ячеек последующей строки матрицы, третьи выходы вычислительных ячеек каждой строки матрицы соединены с третьими входами предыдущих вычислительных ячеек последующей строки матрицы, третьи выходы вычислительных ячеек последней строки матрицы являются выходами устройства, четвертые выходы вычислительных ячеек каждой строки соединены с выходами предыдущих вычислительных ячеек той же строки, четвертые выходы вычислительных ячеек первого столбца матрицы подключены к первым входам соответствующих сумматоров блока сумматоров, выходы переноса которых подключены ко входам переносов предыдущих сумматоров того же блока, а выходы суммы являются выходами устройства, содержит входные коммутаторы, матричные коммутаторы, элементы ИЛИ, причем входы первого входного коммутатора подключены к выходам первого входного регистра, а входы второго входного коммутатора к выходам старших разрядов второго входного регистра, первая группа выходов первого входного коммутатора подключена к первым входам соответствующих элементов ИЛИ первой. группы, а первая группавыходов второго входного регистра - кпервым входам соответствующих элементовИЛИ второй группы, вторые входы которыхсоединены соответственно со второй группойвыходов первого входного коммутатора;второй вход первого элемента ИЛИ первойгруппы подключен к первому выходу второйгруппы выходов второго входного коммутатора, остальные выходы второй группы10 выходов которого подключены к третьимвходам предыдущих вычислительных ячеекпервой строки матрицы, третьи входы вычислительных ячеек последнего столбцаматрицы подключена соответственно к выходам младших разрядов второго входного1регистра, выходы элементов ИЛИ второйгруппы подключены ко вторым входам соответствующих вычислительных ячеек первойстроки матрицы, выходы элементов ИЛИпервой группы подключены к первым входамц соответствующих вычислительных ячеекпервого столбца матрицы, третьи выходыкоторых подключены ко входам соответствующих матричных коммутаторов, первыевыходы которых подключены ко вторымвходам последующих сумматоров блока5сумматоров, а вторые выходы - ко вторымвходам последующих элементов ИЛИ второйгруппы.Указанная цель достигается также тем,что вычислительная ячейка матрицы содержит элемент И, однораздярный сумматори ключ, причем первый и второй входыячейки соединены соответственно с первыми вторым входами элемента И и первыми вторым выходами ячейки, третий и четвертый входы которой и выход элемента Изз подключены ко входам одноразрядного сумматора, выход суммы которого соединенс третьим выходом ячейки, а выход переносачерез ключ - с четвертым выходом ячейки.Теория циклических кодов строится на40основе положений алгебры полиномов. Кодовый полином а (х) степени (п - 1) циклического (п, к) - кода делится без остаткана образующий полином ц(х) степени гп,равной п - Е, Это свойство используетсяпри кодировании и декодировании циклизм ческого (п, 1) - кода,Один из методов кодирования информации разделимым циклическим кодом заключается в следующем. Информационный полином )1(х) степени 1 - 1 умножается назох (гп = п - к) и делится на образующийполином д(х). Результат операций получаемв видехф к(х) = д(х) д(х) + г(х),где д(х) - частное; г(х) - остаток:Полином а (х) = х 1 (х) + г(х) кодовый,поскольку он делится на д(х) бех остатка.Остаток г(х) представляет собой полиномпроверочных символов степени в - 1, коэффициенты которого записаны-в гп-младшихразрядах кодового слова.При декодировании циклического (п, 1) кода кодовый полином а(х) делится на образующий полином д(х). Если не произошло искажение символов в кодовом слове, соответствующем кодовому полиному, то остаток от деления равен нулю, в противном случае, он отличен от нуля. Полином з(х), полученный в результате деления а(х) на д(х) имеет степень, меньшую гп и является синдромом ошибки.Из вышесказанного следует, что основной операцией, выполняемой в процессе кодирования и декодирования циклического (п, М) в ко является вычисление остатка от деления некоторого полинома на образующий полином.На фиг. 1 представлена блок-схема устройства; на фиг. 2 - схема вычислительной ячейки,Устройство содержит два входных регистра 1, 3, два входных коммутатора 2, 4, матрицу 5 вычислительных ячеек, блок 6 сумматоров, элементы ИЛИ 7 первой группы, матричные коммутаторы 8, элементы ИЛИ 9 второй группы.Внутри матрицы 5 вычислительные ячейки соединены следующим образом. Первые выходы вычислительных ячеек каждой строки матрицы соединены последовательно с первыми входами последующих базовых ячеек этой же строки, вторые выходы базовых ячеек строк матрицы соединены последовательно со вторыми входами базовых ячеек последующих строк тех же столбцов матрицы, третьи выходы базовых ячеек соединены с третьими входами базовых ячеек предыдущих столбцов последующих строк матрицы, а третьи выходы базовых ячеек последней строки матрицы являются выходами МВУ, червертые выходы базовых ячеек строк матрицы соединены последовательно с четвертыми входами предыдущих базовых ячеек тех же строк матрицы, а четвертые выходы базовых ячеек первого столбца матрицы соединены с соответствующими входами сумматоров блока 6 сумматоров, причем выход переноса каждого сумматора указанного блока соединен со входом переноса предыдущего сумматора этого же блока, а выходы сумм всех сумматоров блока являются выходами МВУ,Выходы входного регистра 1 соединены с информационными входами входного коммутатора 2, первые выходы которого соединены с соответствующими вторыми входами элементов ИЛИ 7, вторые выходы указанного коммутатора соединены с соответствующими первыми входами элементов ИЛИ 9, выходы входного регистра 3 соединены с информационными входами входного коммутатора 4, первые выходы которого соединены с соответствующими вторыми входами элементов ИЛИ 9, второй выход старшего разряда указанного коммутатора соединен с первым входом первого элемента ИЛИ 7, остальные вторые выходы входного комму 1 о2 о 2 ь зо 4045зо На входной регистр 1 подается произведение х 1(х) (операция умножения информационного полинома 1(х) на х равносильна его сдвигу на гп в разряд влево). Старший разряд входного регистра 3 через второй выход входного коммутатора 4 и первый элемент ИЛИ 7 управляет элементами И 10 вычислительных ячеек первой строки матрицы 5, третьи выходы вычислительных ячеек первого столбца каждой строки матрицы 5 через соответствующие матричные коммутаторы 8 и элементы ИЛИ 7 управляют элементами И 10 вычислительных ячеек каждой последующей строки матрицы 5; в - следующих, после старшего, разрядов входного. регистра 3 через вторые выходы входного коммутатора 4 поступают иа входы одноразрядных сумматоров 11 вычислительных ячеек (третьи входы вычислительных ячеек) первой строки матрицы 5. Остальные разряды входного регистра 3 поступают на входы одноразрядных сумматоров 11 вычислительных ячеек последнего столбца матрицы 5.В первой строке матрицы производится операция вычитания по модулю 2 (равнотатора 4 соединены с соответствующими третьими входами вычислительных ячеек первой строки матрицы 5, а третьи входы вычислительных ячеек последнего столбца матрицы 5 соединены с соответствующими выходами входного регистра 3, первые входы остальных элементов ИЛИ 7 соединены с соответствующими вторыми выходами матричных коммутаторов 8, информационные входы которых соединены с соответствующими третьими выходами вычислительных ячеек первого столбца матрицы 5, а первые выходы матричных коммутаторов 8 соединены с одними из входов сумматоров блока сумматоров 6, выходы элементов ИЛИ 7 соединены с соответствующими первыми входами вычислительных ячеек первого столбца матрицы 5, выходы элементов ИЛИ 9 соединены с соответствующими вторыми входами вычислительных ячеек первой строки матрицы 5. Вычислительная ячейка содержит элемент И 10, одноразрядный сумматор 11 и ключ 12.Устройство работает следующим образом При выполнении операции кодирования входные коммутаторы 2, 4 подсоединяют выходы (1 - гп) входных регистров 1, 3 к своим вторым выходам (1 - т). Ключи 2 всех вычислительных ячеек матрицы 5 разомкнуты, в результате чего одноразрядные сумматоры 11 всех вычислительных ячеек выполняют операцию сложения по модулю 2.На выходной регистр 1 подаются т - младших разрядов образующего полинома д(х), имеющего разрядность гп + 1, которые через вторые выходы (1 - п) входного коммутатора 2 и элементы ИЛИ 9 поступают на входы элементов И 1 О выислительных ячеек каждой строки матрицы 5.сильная операции сложения по модулю 2) полинома д(х) - делителя из полинома х 1(х) - делимого, так как все элементы И 10 вычислительных ячеек первой строки матрицы 5 управляются старшим разрядом полинома х 1(х), равным единице. Получим первый частичный остаток.В последующих строках матрицы 5 с необходимым сдвигом частичных остатков производится либо операция вычитания по модулю 2 делителя из предыдущего частичного остатка, если значение старшего разряда указанного частичного остатка, управляющее элементами И 10 вычислительных ячеек данной строки матрицы 5, равно единице, либо операция сложения по модулю 2 предыдушего частичного остатка с нулем, если значение старшего разряда указанного частичного остатка равно нулю.Результат операции - остаток от деления полиномов - образуется на выходах г 1 - густройства и представляет собой полином проверочных символов г(х).При выполнении операции декодирования на входной регистр 3 поступает кодовый полином а(х), на входной регистр 1 образующий полином д(х) . Производится операция деления полинома а(х) на полином д(х) описанным способом. Результат операции - остаток от деления полиномов - образуется на тех же выходах г - густройства и представляет собой синдром ошибки з(х).При выполнении операции умножения гп-разрядных двоичных операндов под действием соответствующих сигналов управления входные коммутаторы 2, 4 подсоединяют выходы (1 - гп) входных регистров 1, 3 к своим первым выходам (1 - в). Ключи 12 всех вычислительных ячеек матрицы 5 замкнуты.На входной регистр 1 подается множитель, в старшие - разрядов входного регистра 3 - множимое, а в остальные разряды регистра 3 подаются нули. Операция умножения выполняется таким же образом, как и в известном устройстве.Таким образом, данное матричное вычислительное устройство обладает более широкими функциональными возможностями по сравнению с известным.Формула изобретения1. Матричное вычислительное устройство, содержащее входные регистры, матрицу вычислительных ячеек и блок сумматоров, причем первые выходы вычислительных ячеек каждой строки матрицы соединены с первыми входами последующих вычислительных ячеек той же строки матрицы, вторые выходы вычислительных ячеек каждой строки матрицы соединены со вторыми входами соответствующих вычислительных ячеек последующей строки матрицы, третьи выходы вычислительных ячеек каждой строки матрицы соединены с третьими входами предыдущих вычислительных ячеек последующей строки матрицы, третьи выходы вычислительных ячеек последней строки матрицы являются выходами устройства, четвертые выходы вычислительных ячеек каждой строки соединены с выходами предыдущих вычислительных ячеек той же строки, четвертые выходы вычислительных ячеек первого столбца матрицы подключены к 10 первым входам соответствующих сумматоров блока сумматоров, выходы переноса которых подключены ко входам переносов предыдущих сумматоров того же блока, а выходы суммы являются выходами устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет выполнения операции деления полиномов, устройство содержит входные коммутаторы, матричные коммутаторы, элементы ИЛИ, причем входы первого входного р коммутатора подключены к выходам первоговходного регистра, а входы второго входного коммутатора - к выходам старших разрядов второго входного регистра, первая группа выходов первого входного коммутайтора подключена к первым входам соответствующих элементов ИЛИ первой группы, а первая группа выходов второго входного регистра - к первым входам соответствующих элементов ИЛИ второй группы, вторые входы которых соединены соответственно со второй группой выходов первого входного коммутатора, второй вход первого элемента ИЛИ первой группы подключен к первому выходу второй группы выходов второго входного коммутатора, остальные выходы второй группы выходов которого подключены к з 5 третьим входам предыдущих вычислительных ячеек первой строки матрицы, третьи входы вычислительных ячеек последнего столбца матрицы подключены соответственно к выходам младших разрядов второго входного регистра, выходы элементов ИЛИ второй группы подключены,ко вторым входам соответствующих вычислительных ячеек первой строки матрицы, выходы элементов ИЛИ первой группы подключены к первым входам соответствующих вычислительных 4 з ячеек первого столбца матрицы, третьи выходы которых подключены ко входам соответствующих матричных коммутаторов, первые выходы которых подключены ко вторым входам последующих сумматоров блока сумматоров, а вторые выходы - ко вторым зовходам последующих элементов ИЛИ второй группы.2. Устройство по п. 1, отличающеесятем, что вычислительная ячейка матрицы содержит элемент И, одноразрядный сумматор и ключ, причем первый и второй входы ячейки соединены соответственно с первым и вторым входами элемента И и первыми вторым выходами ячейки, третий и четвертый входы которой и выход элемента И750485 10 иг подключены ко входам одноразрядного сумматора, выход суммы которого соединен с третьим выходом ячейки, а выход переноса через ключ - с четвертым выходом ячейки.Источники информации,принятые во внимание при экспертизе 1. бц 1 с 1 Н. Н. Боте Сец 1 аг 1 орс Аггауз аког Моп-Кез 1 ог 1 пд Впагу Р 1 чзоп. ТЬе Кайо апд Е 1. Епд., 1970, 39,6, рр. 345 - 348.2. Карцев М. А. Арифметика цифровых машин, М Наука, 1969, с. 444 (прототип).750485г.ЛСоставитель В. Березкин Редактор М.,Ликович Техрсд К. Шуфрич Корректор Г. Решетник Заказ 4467/19 Тираж 751 Г 1 одписное ЦНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж - 35, Раушская наб., д. 4/5Филиал ППП Патент, г. Ужгород, ул. Проектная, 4