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

(54) МАТРИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО

I

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

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

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

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

J выполнения операции умножения, содержащее входные регистры, матрицу вычислительных ячеек и блок сумматоров 2. Выходы первого входного регистра соединены с соответствующими первыми входами вычислительных ячеек первого столбца

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

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

Каждая вычислительная ячейка матрицы МВУ содержит элемент И и одноразрядный сумматор.

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

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

Поставленная цель достигается тем, что матричное вычислительное устройство, содержащее входные регистры, матрицу вычислительных ячеек и блок сумматоров, причем первые выходы вычислительных ячеек каждой строки матрицы соединены с первыми входами последующих вычислительных ячеек той же строки матрицы, вторые выходы вычислительных ячеек каждой строки матрицы соединены со вторыми входами соответствующих вычислительных ячеек последующей строки матрицы, третьи выходы вычислительных ячеек каждой строки матрицы соединены с третьими входами предыдущих вычислительных ячеек последующей строки матрицы, третьи выходы вычислительных ячеек последней строки матрицы являются выходами устройства, четвертые выходы вычислительных ячеек каждой строки соединены с выходами предыдущих вычислительных ячеек той же строки, четвертые выходы вычислительных ячеек первого столбца матрицы подключены к первым входам соответствующих сумматоров блока сумматоров, выходы переноса которых подключены ко входам переносов предыдущих сумматоров того же блока, а выходы суммы являются выходами устройства, содержит входные коммутаторы, матричные коммутаторы, элементы ИЛИ, причем входы первого входного коммутатора подключены к выходам первого входного регистра, а входы второго входного коммутатора - к выходам старших разрядов второго входного регистра, первая группа выходов первого входного коммутатора, подключена

К первым входам соответствующих элементов ИЛИ первой группы, а первая группа выходов второго входного регистра - к первым входам соответствующих элементов ИЛИ второй группы, вторые входы которых

соединены соответственно со второй группой выходов первого входного коммутатора; второй вход первого элемента ИЛИ первой группы подключен к первому выходу второй группы выходов второго входного коммутатора, остальные выходы второй группы

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

0 соответствующих вычислительных ячеек первого столбца матрицы, третьи выходы которых подключены ко входам соответствующих матричных коммутаторов, первые выходы которых подключены ко вторым входам последующих сумматоров блока сумматоров, а вторые выходы - ко вторым входам последующих элементов ИЛИ второй группы.

Указанная цель достиг ается также тем, что вычислительная ячейка матрицы содерP жит элемент И, однораздярный сумматор и ключ, причем первый и второй входы ячейки соединены соответственно с первым и вторым входами элемента И и первым и вторым выходами ячейки, третий и четвертый входы которой и выход элемента И

подключены ко входам одноразрядного сумматора, выход суммы которого соединен с третьим выходом ячейки, а выход переноса через ключ - с четвертым выходом ячейки. Теория циклических кодов строится на основе положений алгебры полиномов. Кодовый полином а(х) степени (п-1) циклического (п, k) - кода делится без остатка на образующий полином g(x) степени ш, равной п - k. Это свойство используется при кодировании и декодировании циклического (п, k) - кода.

Один из методов кодирования информации разделимым циклическим кодом заключается в следующем. Информационный полином k(x) степени k-1 умножается на х (т п - k) и делится на образующий

полином g(x). Результат операций получаем в виде

x-.k(x) g(x).g(x) +г(х), где g(x) - частное; г(х) - остаток.Полином а (х) (x) + г(х) кодовый,

J поскольку он делится на g(x) бех остатка. Остаток г(х) представляет собой полином проверочных символов степени m -1, коэффициенты которого записаныв т-младщих разрядах кодового слова. При декодировании циклического (п, k) кода кодовый полином а(х) делится на образующий полином g(x). Если не произошло искажение символов в кодовом слове, соответствующем кодовому полиному, то остаток от деления равен нулю, в противном случае он отличен от нуля. Полином s(x), полученный в результате деления а(х) на g(x) имеет степень, меньщую m и является.синдромом ощибки. Из вышесказанного следует, что основной операцией, выполняемой в процессе кодирования и декодирования циклического (п, k)-кода является вычисление остатка от деления некоторого полинома па образующий полином. На ФРГ. 1 представлена блок-схема устройства; на фиг. 2 - схема вычислительной ячейки. Устройство содержит два входных регистра 1, 3, два входных коммутатора 2, 4, матрицу 5 вычислительных ячеек, блок 6 сумматоров, элементы ИЛИ 7 первой группы, матричные коммутаторы 8, элементы ИЛИ 9 второй группы. Внутри матрицы 5 вычислительные ячейки соединены следующим образом. Первые выходы вычислительных ячеек каждой строки матрицы соединены последовательно с первыми входами последующих базовых ячеек этой же строки, вторые выходы базовых ячеек строк матрицы соединены последовательно со вторыми входами базовых ячеек последующих строк тех же столбцов матрицы, третьи выходы базовых ячеек соединены с третьими входами базовых ячеек предыдущих столбцов последующих строк матрицы, а третьи выходы базовых ячеек последней строки матрицы являются выходами МВУ, червертые выходы базовых ячеек строк матрицы соединены последовательно с четвертыми входами предыдущих базовых ячеек тех же строк матрицы, а четвертые выходы базовых ячеек первого столбца матрицы соединены с соответствующими входами сумматоров блока б сумматоров, причем выход переноса каждого сумматора указанного блока соединен со входом переноса предыдущего сумматора этого же блока, а выходы сумм всех сумматоров блока являются выходами МВУ. Выходы входного регистра 1 соединены с информационными входами входного коммутатора 2, первые выходы которого соединены с соответствующими вторыми входами элементов ИЛИ 7, вторые выходы указанного коммутатора соединены с соответствующими первыми входами элементов ИЛИ 9, выходы входного регистра 3 соединены с информационными входами входного коммутатора 4, первые выходы которого соединены с соответствующими вторыми входами элементов ИЛИ 9, второй выход старщего разряда указанного коммутатора соединен с первым входом первого элемента ИЛИ 7, остальные вторые выходы входного коммутатора 4 соединены с соответствующими третьими входами вычислительных ячеек первой строки матрицы 5, а третьи входы вычислительных ячеек последнего столбца матрицы 5 соединены с соответствующими выходами входного регистра 3, первые входы остальных элементов ИЛИ 7 соединены с соответствующими вторыми выходами матричных коммутаторов 8, информационные входы которых соединены с соответствующими третьими выходами вычислительных ячеек первого столбца матрицы 5, а первые выходы матричных коммутаторов 8 соединены с одними из входов сумматоров блока сумматоров 6, выходы элементов ИЛИ 7 соединены с соответствующими первыми входами вычислительных ячеек первого столбца матрицы 5, выходы элементов ИЛИ 9 соединены с соответствующими вторыми входами вычислительных ячеек первой строки матрицы 5. Вычислительная ячейка содержит элемент И 10, одноразрядный сумматор 11 и ключ 12. Устройство работает следующим образом При выполнении операции кодирования входные коммутаторы 2, 4 подсоединяют выходы (1-т) входных регистров 1, 3 к своим вторым выходам (1 -т). Ключи 12 всех вычислительных ячеек матрицы 5 разомкнуты, в результате чего одноразрядные сумматоры 11 всех вычислительных ячеек выполняют операцию сложения по модулю 2. На выходной регистр 1 подаются m- младших разрядов образующего полинома g(x), имеющего разрядность ш + 1, которые через вторые выходы (-ш) входного коммутатора 2 и элементы ИЛИ 9 поступают на входы элементов И 10 выислительных ячеек каждой строки матрицы 5. На входной регистр 1 подается произведение k(x) (операция умножения информационного полинома k(x) на х равносильна его сдвигу на гп-разрядов влево). Старший разряд входного регистра 3 через второй выход входного коммутатора 4 и первый элемент ИЛИ 7 управляет элементам.и И 10 вь1числительных ячеек первой строки матрицы 5, третьи выходы вычислительных ячеек первого столбца каждой строки матрицы 5 через соответствующие матричные коммутаторы 8 и элементы ИЛИ 7 управляют элементами И 10 вычислительных ячеек каждой последующей строки матрицы 5; m-следующих, после старшего, разрядов входного.регистра 3 через вторые выходы входного коммутатора 4 поступают на входы одноразрядных сумматоров 11 вычислительных ячеек (третьи входы вычислительных ячеек) первой строки матрицы 5. Остальные разряды входного регистра 3 поступают на входы одноразрядных сумматоров 11 вычислительных ячеек последнего столбца матрицы 5. В первой строке матрицы производится операция вычитания по модулю 2 (равносильная операции сложения по модулю 2) полинома g(x)-делителя из полинома (x)-делимого, так как все элементы И 10 вычислительных ячеек первой строки матрицы 5 управляются старшим разрядом полинома (x), равным единице. Получим первый частичный остаток.

В последующих строках матрицы 5 с необходимым сдвигом частичных остатков производится либо операция вычитания по модулю 2 делителя из предыдущего частичного остатка, если значение старшего разряда указанного частичного остатка, управляющее элементами И 10 вычислительных ячеек данной строки матрицы 5, равно единице, либо операция сложения по модулю 2 предыдущего частичного остатка с нулем, если значение старшего разряда указанного частичного остатка равно нулю.

Результат операции - остаток от деления полиномов - образуется на выходах П - г, устройства и представляет собой полином проверочных символов г(х).

При выполнении операции декодирования на входной регистр 3 поступает кодовый полином а(х), на входной регистр 1 - образующий полином g(x). Производится операция деления полинома а(х) на полином g(x) описанным способом. Результат операции - остаток от деления полиномов - образуется на тех же выходах п -г, устройства и представляет собой синдром ощибки s(x).

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

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

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

Формула изобретения

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

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

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

расширения функциональных возможностей за счет выполнения операции деления полиномов, устройство содержит входные коммутаторы, матричные коммутаторы, элементы ИЛИ, причем входы первого входного

коммутатора подключены к выходам первого входного регистра, а входы второго входного коммутатора - к выходам старщих разрядов второго входного регистра, первая группа выходов первого входного ком.мутатора подключена к первым входам соответствующих элементов ИЛИ первой группы, а первая группа выходов второго входного регистра - к первым входам соответствующих элементов ИЛИ второй группы, вторые входы которых соединены соответственно

со второй группой выходов первого входного коммутатора, второй вход первого элемента ИЛИ первой группы подключен к первому выходу второй группы выходов второго входного коммутатора, остальные выходы второй группы выходов которого подключены к

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

входам соответствующих вычислительных

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

входам последующих элементов ИЛИ второй группы.

подключены ко входам одноразрядного сумматора, выход суммы которого соединен с третьим выходом ячейки, а выход переноса через ключ - с четвертым выходом ячейки.

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

Фи2. i

Фи2,2