Устройство для вычислений в конечных полях

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)л 6 06 F 7/60

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Ю

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4768438/24 (22) 27,10.89 (46) 30.11.91. Бюл. ¹ 44 (71) Московский институт связи (72) Т.В. Сидорова, А.И. Бегишев и А.3. Пономарев (53) 681.325(088.8) (56) Авторское свидетельство СССР

N 1051534, кл. G 06 F 7/49, 1982.

Патент ЕПВ N152702,,кл. Н 03 М 13/00, опублик. 28.08.85. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЙ В

КОНЕЧНЫХ ПОЛЯХ (57) Изобретение относится к автоматике и. вычислительной технике и может быть ис„„Я2„„1695299 А1 пол ьзовано при реализации устройств кодирования и декодирования корректирующих ошибки кодов, Устройство позволяет выполнять ряд вычислительных операций в поле

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

2 ил., 2 табл.

1695299

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

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

На фиг. 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 обращения, выход которого подключен к второму информационному входу второго мультиплексора 6, выход которого подключен к входу второго сомножителя умножителя и к второму информационному входу третьего мультиплексора 4, выход которого соединен с входом: второго слагаемого сумматора 5, выход которого является выходом 17 результата устройства и подключен к первому входу схемы 7 сравнения, выход которой является контрольным выходом 18 устройства, первый выход дешифратора 12 подключен к первым входам первого и второго элементов ИЛИ 9 и 10, второй выход дешифратора 12 подключен к второму входу первого элемента ИЛИ 9 и к первому входу третьего элемента ИЛИ 11, второй вход которого подключен к третьему выходу дешифратора 12, четвертый выход которого подключен к второму входу второго элемента ИЛИ 10, пятый выход дешифратора

12 подключен к третьим входам первого 9, второго 10 и третьего 11 элементов ИЛИ, 15

50 первым входом блока 2 элементов И, второй вход которого подключен к входу 15 третьего операнда устройства, вход константы которого соединен с вторым входом схемы 7 сравнения блок 8 обращения содержит группу элементов НЕ 19, группу элементов И 20 и группу элементов ИЛИ 21.

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

Элементарные арифметические операции в полях Галуа GF (2") выполняются спе-,. циализированными блоками умножителя, сумматора и обращения. Все эти блоки построены на основе комбинационно-логических схем, поэтому время выполнения операций определяется быстродействием логических элементов, входящих в их состав. Управление работой указанных блоков осуществляется логическими элементами

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

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

B табл. 1 приведены коды операций, поступающие на вход 16 устройства, соответствующего им типы операций и состоя- ния выходов дешифратора кода операции.

Операнды, используемые при вычислениях, подаются на входы 13, 14 и 15; результат вычисления снимается с выхода 17, а результат контроля — с выхода 18.

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

Операция умножения осуществляется при поступлении на.управляющие входы кода "000" (см. табл. 1). При этом на выходах элементов ИЛИ 9. 11 и 10 появляются сигшестой выход дешифратора 12 подключен к четвертым входам второго и третьего элементов ИЛИ 10 и 11, седьмой выход дешифратора 12 подключен к управляющему входу первого мультиплексора 1 и к пятому входу третьего элемента ИЛИ 11, выход которого соединен с управляющим входом второго мультиплексора 6, выход первого элемента ИЛИ 9 подключен к управляюще10 му входу третьего мультиплексора 4. выход второго элемента ИЛИ 10 соединен с

1695299 налы логического нуля, которые подаются на управляющие входы мультиплексоров 4 и б и на первый вход блока 2 элементов И соответственно. На управляющий вход мультиплексора 1 поступает сигнал логиче- 5 ского нуля с седьмого выхода дешифратора

12. Под действием нулевых управляющих сигналов на выходы мультиплексоров поступают данные с их первых информационных входов. Тогда операнд с входа 13 через 10 мультиплексор 1 поступает на первый вход умножителя 3. На второй вход умножителя

3 через мультиплексор 6 поступает второй операнд с входа 14, Результат умножения через мультиплексор 4 поступает на второй 15 вход сумматора 5, на первом входе которого действует нулевой сигнал с выхода блока 2 элементов И. После сложения с нулем результат умножения поступает на выход 17 устройства. 20

Операция сложения осуществляется при поступлении на вход 16 устройства кода

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

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

Сигнал логической единицы с второго 45 выхода дешифратора 12 через элементы .

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

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

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

-1 условию А А = 1 а также их двоичные представления

А = (а1, а2, аз, а4) и А = (а1, аг; аз, а4 ).

Примитивный элемент поля GF (2 ) в табл. 2 обозначен через а.

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

a1 = аза4 V а1агаз V a1a2a3 V.

V а1агаа V а1агазаа; а2 = а1а2а4 V a1a3a4 V a1a2a4 V

V а1а2а3а4 V ala2a3a4;аз = а1азаа V a1a2a3 ч a1a2a4 V

V а1а3а4 V а2аза4;

a4 = а1аз V а1а4 V агазаа V

V агаза4 U а1агаза4.

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

Появление на входе 16 кода операции комбинации "011" переводит устройство в режим выполнения операции деления операнда, действующего на входе 13 устройства, на операнд, действующий на входе 14, Поскольку В/А = В.А, то устройство реа-1 лизует операцию деления путем умножения числителя В с входа 13 первого операнда на число, обратное знаменателю.

А, действующему на входе 14 второго опе-. райда. Единичный сигнал с третьего выхо- . да дешифратора 12 через элемент ИЛИ 11 поступает на управляющий вход мультиплексора 6, устанавливая его в такое состояние, при котором на второй вход умнож1ателя 3 поступает число А (обратное знаменателю А) с выхода блока 8 обращения, Числитель В с входа первого операнда 13 через мультиплексор 1, на управляющем входе которого действует сигнал логического нуля с седьмого выхода дешифратора 12 (см. табл. 1), поступает на первый вход умножителя 3. Так как входные сигналы элементов ИЛИ 9 и 10 равны нулю, то выходные сигналы указанных элементов обеспечивают, прохождение результата ум-. ножения В А с выхода умножителя 3 через первый информационный вход мультиплексора 4 на второй вход сумматора 5, где про1695299 исходит суммирование с нулем (поскольку блок 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 переключает мультиплексоры 4 и для про-. хождения обращенного числа А с выхода блока 8.обращения на второй вход сумматора 5, на первый вход которого через блок 2 элементов И, открытый сигналом логической единицы с выхода элемента ИЛИ 10, поступает число с входа 15 устройства. Выполнение операции А + С длится один такт.

Для выполнения операции деления со сложением В/А + С на вход 16 устройства необходимо подать код операции "110".

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

30 равное единице (0,.01). Если устройство

40

50

5

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

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

Переключение устройства в режим контроля осуществляется кодом операции

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

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

А с выхода блока 8 обращения. Результат умножения А А = 1 с выхода блока 3 через мультиплексор 4, на управляющем входе которого действует логический нуль с выхода элемента ИЛИ 9, поступает на второй вход сумматора 5, Так как сигнал на выходе элемента ИЛИ 10 равен нулю, то блок 2 элементов И закрыт и на первый вход сумматора 5 поступает нулевое слагаемое. Результат сложения, равный единице (представляемый в поле Галуа GF (2") как n —, разрядное число 0..01), подается на первый вход схемы 7 сравнения, на втором входе которой постоянно действует число, функционирует исправно, то сигналы на входах схемы 7 сравнения равны и сигнал равенства с ее выхода подается на выход 18 устройства.

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

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

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

1695299

Таблица 1

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

1695299

Составитель А. Клюев

Техред M.Ìîðãåíòàë

Редактор Э, Слиган

Корректор Т. Палий

Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101

Заказ 4162 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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