Устройство для вычислений в конечных полях Советский патент 1991 года по МПК G06F7/60 

со

с

Изобретение относится к автоматике и вычислительной технике и может быть ис. n/J пользовано при реализации устройств кодирования и декодирования корректирующих ошибки кодов. Устройство позволяет выполнять ряд вычислительных операций в поле Галуа. Целью изобретения является повышение быстродействия. Устройство содержит умножитель 3, схему 7 сравнения, блок 2 элементов И, сумматор 5, три мультиплексора 1, 4 и 6, блок 8 обращения со связями. Повышение быстродействия обусловлено выполнением всех операций за один такт. Более высокая достоверность работы устройства достигается вследствие организации режима контроля, осуществляемого совокупностью блоков устройства. 2 ил., 2 табл. п#

о о ел ю ю ю

Фиг. f

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

Целью изобретения является повышение быстродействия.

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

Устройство содержит первый мультиплексор 1, блок 2 элементов И, умножитель 3, третий мультиплексор 4, сумматор 5, второй мультиплексор 6, схему 7 сравнения, блок 8 обращения, с первого по третий элементы ИЛИ 9-11, дешифратор 12, входы 13-15 первого, второго и третьего операндов устройства соответственно, вход 16 кода операции устройства, выход 17 результата устройства , контрольный выход 18 устройства. Выход блока 2 элементов И соединен с входом первого слагаемого сумматора 5, вход дешифратора 12 является входом 16 кода операции устройства, вход 13 первого операнда которого под- ключей к первому информационному входу первого мультиплексора 1, выход которого соединен с входом первого сомножителя умножителя 3, выход которого подключен к первому информационному входу третьего мультиплексора 4, вход 14 второго операнда устройства подключен к второму информационному входу первого мультиплексора 1, к первому информационному входу второго мультиплексора 6 и к входу блока 8 обращения, выход которого подключен к второму информационному входу второго мультиплексора б, выход которого подключен к входу второго сомножителя умножителя и к второму информационному входу третьего мультиплексора 4, выход которого соединен с входом второго слагаемого сумматора 5, выход которого является выходом 17 результата устройства и подключен к первому входу схемы 7 сравнения, выход которой является контрольным выходом 18 устройства, первый выход дешифратора 12 подключен к первым входам первого и второго элементов ИЛИ 9 и 10, второй выход дешифратора 12 подключен к второму входу первого элемента ИЛИ 9 и к первому входу третьего элемента ИЛИ 11, второй вход которого подключен к третьему выходу дешифратора 12, четвертый выход которого подключен к второму входу второго элемента ИЛИ 10, пятый выход дешифратора 12 подключен к третьим входам первого 9, второго 10 и третьего 11 элементов ИЛИ,

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

входу первого мультиплексора 1 и к пятому входу третьего элемента ИЛИ 11, выход которого соединен с управляющим входом второго мультиплексора 6, выход первого элемента ИЛИ 9 подключен к управляюще0 му входу третьего мультиплексора 4, выход второго элемента ИЛИ 10 соединен с первым входом блока 2 элементов И, второй вход которого подключен к входу 15 третьего операнда устройства, вход константы ко5 торого соединен с вторым входом схемы 7 сравнения.

Блок 8 обращения содержит группу элементов НЕ 19, группу элементов И 20 и группу элементов ИЛИ 21.

0 Устройство работает следующим образом.

Элементарные арифметические операции в полях Галуа GF (2П) выполняются спе- L циализированными блоками умножителя,

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

Приведенная структура устройства позволяет выполнять следующие операции: умножение, сложение, обращение, деление, умножение со сложением, деление со сло0 жением, обращение со сложением и контроль работоспособности устройства. Все операции выполняются за один такт.

В табл. 1 приведены коды операций, поступающие на вход 16 устройства, соот5 ветствующего им типы операций и-состояния выходов дешифратора кода операции. Операнды, используемые при вычислениях, подаются на входы 13,14 и 15; результат вычисления снимается с выхода 17, а

0 результат контроля - с выхода 18.

Контроль работоспособности устройства основан на следующем: Число умножается на обратное ему и произведение суммируется с нулем; по условию равенства

5 результата единице делается вывод об исправности всех блоков устройства.

Операция умножения осуществляется при поступлении на управляющие входы кода 000 (см. табл. 1), При этом на выходах элементов ИЛИ 9. 11 и 10 появляются сигналы логического нуля, которые подаются на управляющие входы мультиплексоров 4 и Б и на первый вход блока 2 элементов И соответственно. На управляющий вход мультиплексора 1 поступает сигнал логического нуля с седьмого выхода дешифратора 12. Под действием нулевых управляющих сигналов на выходы мультиплексоров поступают данные с их первых информационных входов. Тогда операнд с входа 13 через мультиплексор 1 поступает на первый вход умножителя 3. На второй вход умножителя 3 через мультиплексор 6 поступает второй операнд с входа 14. Результат умножения через мультиплексор 4 поступает на второй вход сумматора 5, на первом входе которого действует нулевой сигнал с выхода блока 2 элементов И. После сложения с нулем результат умножения поступает на выход 17 устройства.

Операция сложения осуществляется при поступлении на вход 16 устройства кода 001. Сигнал уровня логической единицы с первого выхода дешифратора 12 поступает на входы элементов ИЛИ 9 и 10. Сигнал логического нуля с выхода элемента ИЛИ 11 обеспечивает прохождение на выход мультиплексора 6 слагаемого с входа 14 устрой ства. С второго информационного входа мультиплексора 4, на управляющем входе которого действует сигнал единичного уровня с выхода элемента ИЛИ 9, слагаемое, в свою очередь, поступает на второй вход сумматора 5, Логическая единица с выхода элемента ИЛИ 10 открывает блок 2 элементов И для прохождения второго слагаемого с входа 15 устройства на первый вход сум матора 5. Результат сложения операндов, действующих на входах 14 и 15, поступает на выход 17 устройства.

Обращение числа А, действующего на входе 14 устройства, происходит при поступлении на вход 16 устройства кода операции обращения 010 (см. табл. 1).

Сигнал логической единицы с второго выхода дешифратора 12 через элементы ИЛИ 9 и 11 поступает на управляющие входы мультиплексоров 4 и 6, переключая их для прохождения обращенного числа с выхода блока 8 обращения на второй вход сумматора 5. Сигнал логического нуля, действующий на выходе элемента ИЛИ 10, закрывает блок 2 элементов И для прохождения числа с входа 15 устройства на первый вход сумматора; таким образом, .в сумматоре 5 происходит суммирование обращенного числа А с нулем и результат поступает на выход 17 устоойства.

Нахождение числа , обратного числу, действующему на входе 14 устройства,

происходит в блоке 8 обращения. Проиллюстрируем его работу на примере выполнения данной операции над элементами конечного поля GF (2 ) с порождающим мно- гочленом q(x) х4 + х + 1.

В табл. 2 приведены все ненулевые элементы А поля GF (24) и соответствующие им обратные элементы , удовлетворяющие условию А А 1 ,а также их двоичные пред- ставления:

А (ai, за, аз, Э4) и - (а Г1, , , ). Примитивный элемент поля GF (2 ) в табл. 2 . обозначен через а.

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

а Г1 Ј334 V гмазаз V а 1а2аз V

V а V 31323334;

a ia234 V гйаза4 V V

V 31323334 V 31323334;

33 313334 V 313233 V 313234 V

V «мазану Э2ЭЗЭ4;

Л- %о / -ъ л л

34

3133 V el34 V 323334 V

ац - о iaj v aiaq v V 323334 V 31323334.

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

второго операнде 14 устройстве.

Появление нэ входе 16 кодэ операции комбинэции 011 переводит устройство в режим выполнения оперзции деления опе- рэндэ, действующего на входе 13 устройства, на операнд, действующий на входе 14, Поскольку В/А В , то устройство реализует операцию деления путем умножения числителя В с входа 13 первого операнда на число, обратное знамензтелюА, действующему на входе 14 второго one- . Единичный сигнэл с третьего выхода дешифратора 12 через элемент ИЛИ 11 поступает на управляющий вход мультиплексора 6, уст.знзвливая его в такое состояние, при котором на второй вход умножителя 3 поступэет число А (обрэт- ное знаменателю А) с выхода блока 8 обращения. Числитель В с входа первого .операнда 13 через мультиплексор 1, на управляющем входе которого действует сигнал логического нуля с седьмого выхода дешифратора 12 (см. табл. 1), поступает на первый вход умножителя 3. Так как входные сигналы элементов ИЛИ 9 и 10 равны нулю,

то выходные сигналы указэнных элементов обеспечивают прохождение результата ум-, ножения В -Ам с выхода умножителя 3 через первый информационный вход мультиплексора 4 на второй вход сумматора 5, где происходит суммирование с нулем (поскольку блок 2 элементов И закрыт сигналов логического нуля, действующим на его первом входе). Таким образом, результат деления В/А, выполненного за один такт, поступает на выход 17 устройства,

В отличие от изложенных выше операций умножения, обращения и деления операции умножения со сложением А-В + С, обращения со сложением А + С и деление со сложением В/А + С выполняются с участием третьего операнда.

Операция умножения двух операндов, действующих на входах 13 и 14 устройства, и сложение результата с операндом с входа 15 устройства А -В + С осуществляется при коде операции 100. Мультиплексоры 1, 4 и 6, на управляющих входах которых действуют сигналы логического нуля с седьмого выхода дешифратора 12 и с выходов элементов ИЛИ 9 и 11, соответственно, обеспечивают поступление на входы умножителя 3 чисел с входом первого и второго операндов и подачу результата умножения на вход сумматора 5. Сигнал логической единицы с четвертого выхода дешифратора 12 через элемент ИЛИ 10 открывает блок 2 элементов И и число с входа 15 третьего операнда поступает на другой вход сумматора 5. Таким образом, операция умноже- ния со сложением выполняема за один такт.

Код 101 вызывает выполнение операции обращения со сложением + С (где А и С - числа, действующего на входах 14 и 15 устройства соответственно). Логическая единица с пятого выхода дешифратора 12 (см. табл. 1) через элементы ИЛИ 9 и 11 переключает мультиплексоры для прохождения обращенного числа А с выхода блока 8-обращения на второй вход сумматора 5, на первый вход которого через блок 2 элементов И, открытый сигналом логической единицы с выхода элемента ИЛИ 10, поступает число с входа 15 устройства. Выполнение операции + С длится один такт.

Для выполнения операции деления со сложением В/А + С на вход 16 устройства необходимо подать код операции 110. Единичный сигнал с шестого выхода дешифратора 12 через элемент ИЛИ 10 открывает блок 2 элементов И и разрешает прохождение слагаемого с входа 15 устройства-на первый вход сумматора 5. Поступление на его второй вход результата деления числителя с входа 13 устройства на знаменатель, действующий на входе 14, обеспечивается работой мультиплексоров

1,4 и 6, управление которыми осуществляется так же, как и при операции деления. . Длительность выполнения операции деления со сложением равна одному такту.

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

входе мультиплексора 1 и через элемент ИЛИ 11 на управляющем входе мультиплексора 6. Число А с входа 14 устройства через мультиплексор 1 поступает на первый вход умножителя 3, на второй вход которого через мультиплексор 6 подается число с выхода блока 8 обращения. Результат умножения 1 с выхода блока 3 через мультиплексор 4, на управляющем входе которого действует логический нуль с

выхода элемента ИЛИ 9, поступает на второй вход сумматора 5. Так как сигнал на выходе элемента ИЛИ 10 равен нулю, то блок 2 элементов И закрыт и на первый вход сумматора 5 поступает нулевое слагаемое. Результат сложения, равный единице (представляемый в поле Галуа GF (2°) как п - разрядное число 0..01), подается на первый вход схемы 7 сравнения, на втором входе которой постоянно действует число,

равное единице (0,.01). Если устройство функционирует исправно, то сигналы на входах схемы 7 сравнения равны и сигнал равенства с ее выхода подается на выход 18 устройства.

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

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

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

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

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

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

Таблица 1

Таблица 2

Вход