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

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

Иллюстрации

Показать все

Реферат

 

О П И С А Н И Е (750485

ИЗОБРЕТЕН ИЯ

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

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

Социалистических

Республик (61) Дополнительное к авт. свид-ву— (22) Заявлено 30.05.78 (21) 2654012/18-24 с присоединением заявки №вЂ” (23) Приоритет— (51) М. Кл.з

G 06 F 7/38

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

СССР (53) УДК 681 325 (088.8) Опубликовано 23.0?.80. Бюллетень № 27

Дата опубликования описания 27.07.80 ло делам изобретений и открытий (72) Авторы изобретения

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

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

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

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

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

2 только одну арифметическую операцию, а именно операцию деления двоичных чисел.

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

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

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

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

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

Каждая вычислительная ячейка матрицы

МВУ содержит элемент И и одноразрядный сумматор.

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

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

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

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

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

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

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

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

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

Теория циклических кодов строится на

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

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

sc х (m = n — k) и делится на образующий полином g(x). Результат операций получаем в виде х k(x) = g(x) . g(x) + г(х), где g(x) — частное; r(x) — остаток:

Поли ном а (х) = x k (x) + r (x) кодовый, поскольку он делится на g (x) бех остатка.

Остаток r (х) представляет собой полином проверочных символов степени m — 1, коэффициенты которого записаны-в m-младших разрядах кодового слова.

750485

1о

1s

2о

2s зо

45

ss

При декодировании циклического (n, k) кода кодовый полином а(х) делится на образующий полином g(x). Если не произошло искажение символов в кодовом слове, соответствующем кодовому полиному, то остаток от деления равен нулю, в противном случае, он отличен от нуля. Полином з(х), полученный в результате деления а(х) íà g(x) имеет степень, меньшую m и является синдромом ошибки.

Из вышесказанного следует, что основной операцией, выполняемой в процессе кодирования и декодирования циклического (n, k) †ко является вычисление остатка от деления некоторого полинома на образующий полином.

На фиг. 1 представлена блок-схема устройства; на фиг. 2 — схема вычислительной ячейки.

Устройство содержит два входных регистра 1, 3, два входных коммутатора 2, 4, матрицу 5 вычислительных ячеек, блок 6 сумматоров, элементы ИЛИ 7 первой группы, матричные коммутаторы 8, элементы ИЛИ 9 второй группы.

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

Выходы входного регистра 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 — m) входных регистров 1, 3 к своим вторым выходам (1 — m). Ключи !2 всех вычислительных ячеек матрицы 5 разомкнуты, в результате чего одноразрядные сумматоры 11 всех вычислительных ячеек выполняют операцию сложения по модулю 2.

На выходной регистр 1 подаются m— младших разрядов образующего полинома

g(x), имеющего разрядность m + 1, которые ь через вторые выходы (1 — m) входного коммутатора 2 и элементы ИЛИ 9 поступают на входы элементов И 10 выислительных ячеек каждой строки матрицы 5.

На входной регистр 1 подается произведение х - k(x) (операция умножения информационного полинома k(x) на х равносильна его сдвигу íà m — разрядов влево).

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

7 управляют элементами И 10 вычислительных ячеек каждой последующей строки матрицы 5; m — следующих, после старшего, разрядов входного. регистра 3 через вторые выходы входного коммутатора 4 поступают иа входы одноразрядных сумматоров 11 вычислительных ячеек (третьи входы вычислительных ячеек) первой строки матрицы 5. Остальные разряды входного регистра 3 поступают на входы одноразрядных сумматоров 11 вычислительных ячеек последнего столбца матрицы 5.

В первой строке матрицы производится операция вычитания по модулю 2 (равно750485 сильная операции сложения по модулю 2) полинома g(x) — делителя из полинома х k(x) — делимого, так как все элементы

И 10 вычислительных ячеек первой строки матрицы 5 управляются старшим разрядом полинома х k(x), равным единице. Получим первый частичный остаток.

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

Результат операции — остаток от деления полиномов — образуется на выходах

r> — r óñòð0éñòâà и представляет собой полином проверочных символов r(x).

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

g(x) описанным способом. Результат операции — остаток от деления полиномов— образуется на тех же выходах г — г„устройства и представляет собой синдром ошибки s(x).

При выполнении операции умножения

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

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

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

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

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

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

>о со второй группой выходов первого входного коммутатора, второй вход первого элемента

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

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

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

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

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

750485

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

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

1. Guild Н. Н. «Some Cellular logic

Arrays for Non-Restoring Binary Division».

«The Кайо and El. Eng», 1970, 39, № 6, рр. 345 — 348.

2. Карцев М. А. Арифметика цифровых машин. М., «Наука», 1969, с. 444 (прототип).

750485 г.Л

Составитель В. Березкин

Редактор М.,Ликович Техрсд К. Шуфрич Корректор Г. Решетник

Заказ 4467/19 Тираж 751 Г1одписное

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

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

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