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

(5)5 6 06 Р 7 ПИСАНИЕ ИЗОБРЕТЕНИ ф Дщфма в с ааМЕЛЬСТВУ ВТОРСКОМУ С ЫЧИСЛЕНИЙ В я к автоматике и может быть исГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР(71) Московский институт связи(56) Авторское свидетельство СССРМ 1051534, кл, 6 06 Р 7/49, 1982,Патент ЕПВ М 152702, кл. Н 03 М 13/00,опублик. 28.08,85.(54) УСТРОЙСТВО ДЛЯ ВКОНЕЧНЫХ ПОЛЯХ(57) Изобретение относитсвычислительной технике и пол ьзовано при реализации устройств кодирования и декодирования корректирующих ошибки кодов, Устройство позволяет выполнять ряд вычислительных операций в поле Галуа, Целью изобретения является повышение быстродействия. Устройство содержит умножитель 3, схему 7 сравнения, блок 2 элементов И, сумматор 5, три мультиплексора 1, 4 и 6, блок 8 обращения со связями. Повышение быстродействия обусловлено выполнением всех операций за один такт. Более высокая достоверность работы устройства достигается вследствие организации режима контроля, осуществляемого совокупностью блоков устройства. 2 ил 2 табл.Х10 15 Изобретение относится к вычислительной технике и может быть применено припостроении кодирующих и декодирующихустройств корректирующих кодов, предназначенных для передачи информации свысокой достоверностью,Целью изобретения является повышение быстродействия.На фиг. 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 элементов ИЛИ,20 25 30 35 40 45 50 55 шестой выход дешифратора 12 подключен к четвертым входам второго и третьего элементов ИЛИ 10 и 11, седьмой выход дешифратора 12 подключен к управляющему входу первого мультиплексора 1 и к пятому входу третьего элемента ИЛИ 11, выход которого соединен с управляющим входом второго мультиплексора 6, выход первого элемента ИЛИ 9 подключен к управляющему входу третьего мультиплексора 4, выход второго элемента ИЛИ 10 соединен с первым входом блока 2 элементов И, второй вход которого подключен к входу 15 третьего операнда устройства, вход константы которого соединен с вторым входом схемы 7 сравнения.блок 8 обращения содержит группу элементов НЕ 19, группу элементов И 20 и группу элементов ИЛИ 21.Устройство работает следующим образом.Элементарные арифметические операции в полях Галуа ОЕ (2") выполняются специализированными блоками умножителя, сумматора и обращения. Все эти блоки построены на основе комбинационно-логических схем, поэтому время выполнения операций определяется быстродействием логических элементов, входящих в их состав. Управление работой указанных блоков осуществляется логическими элементами ИЛИ, И и мультиплексорами, состояния которых определяются комбинацией выходных сигналов дешифратора кода операции.Приведенная структура устройства позволяет выполнять следующие операции: умножение, сложение, обращение, деление, умножение со сложением, деление со сложением, обращение со сложением и контроль работоспособности устройства, Все операции выполняются за один такт.В табл, 1 приведены коды операций, поступающие на вход 16 устройства, соответствующего им типы операций и состоя- ния выходов дешифратора кода операции,Операнды, используемые при вычислениях, подаются на входы 13, 14 и 15; результат вычисления снимается с выхода 17, а результат контроля - с выхода 18,Контроль работоспособности устройства основан на следующем; Число умножается на обратное ему и произведение суммируется с нулем; по условию равенства результата единице делается вывод об исправности всех блоков устройства.Операция умножения осуществляется при поступлении на.управляющие входы кода "000" (см. табл, 1). При этом на выходах элементов ИЛИ 9. 11 и 10 появляются сиг 1695299налы логического нуля, которые подаются на управляющие входы мультиплексоров 4 и б и на первый вход блока 2 элементов И соответственно. На управляющий вход мультиплексора 1 поступает сигнал логиче ского нуля с седьмого выхода дешифратора 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 элемен тов И для прохождения второго слагаемого с входа 15 устройства на первый вход сум. матора 5. Результат сложения операндов, действующих на входах 14 и 15, поступает на выход 17 устройства, 40Обращение числа А, действующего на входе 14 устройства, происходит при поступлении на вход 16 устройства кода операции обращения "010" (см, табл, 1).Сигнал логической единицы с второго 45 выхода дешифратора 12 через элементы ИЛИ 9 и 11 поступает на управляющие входы мультиплексоров 4 и 6, переключая их для прохождения обращенного числа А с выхода блока 8 обращения на второй вход 50. сумматора 5, Сигнал логического нуля, действующий на выходе элемента ИЛИ 10, закрывает блок 2 элементов И для прохож- дения числа с входа 15 устройства на пер- . вый вход сумматора; таким образом,.в 55 сумматоре 5 происхо 1 дит суммирование обращенного числа А с нулем и результат поступает на выход 17 устоойства.Нахождение числа А, обратного числу, действующему на входе 14 устройства,происходит в блоке 8 обращения. Проиллюстрируем его работу на примере выполнения данной операции над элементами конечного поля ОР (2 ) с порождающим многочленом о(х) = х + х + 1.аВ табл. 2 приведены все ненулевые элементы А поля ОР (2") и соответствующие им обратные элементы А, удовлетворяющие-1условию А А = 1,а также их двоичные представления:А = (а 1, а, аз, аа) и А = (а 1, а 2; аз, аа ), Примитивный элемент поля ОР (2 ) в табл, 2 обозначен через а,Аналитические выражения, с помощью которых строится схема блока 8 обращения," в данном случае имеют следующий вид;а = азаа Ч а 1 а 2 аз Ч а 1 аяаз ЧЧ аа 2 аа Ч а 1 агазаа;а 2 = а 1 а 2 аа Ч а 1 азаа Ч а 1 а 2 аа ЧЧ аа 2 азаа Ч а 1 а 2 азаа,аз = а 1 азаа Ч а 1 а 2 аз Ч а 1 а 2 аа ЧЧ а 1 азаа Ч а 2 азаа;аа = а 1 аз Ч а 1 аа Ч а 2 азаа ЧЧ а 2 азаа Ч а 1 а 2 азаа.Схема, представленная на фиг, 2, реализует за один такт указанные функции обращения числа, действующего на входе второго операнда 14 устройства.Появление на входе 16 кода операции комбинации "011" переводит устройство в режим выполнения операции деления операнда, действующего на входе 13 устройства, на операнд, действующий на входе 14, Поскольку В/А = В А, то устройство реа лизует операцию деления путем умножения числителя В с входа 13 первого операнда на число, обратное знаменателю А, действующему на входе 14 второго опе-. ранда. Единичный сигнал с третьего выхо- . да дешифратора 12 через элемент ИЛИ 11 поступает на управляющий вход мультиплексора 6, устанавливая его в такое состояние, при котором на второй вход умножмтеля 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), Если устройство 35 40 45 50 55 5 10 15 20 25 1, 4 и 6, управление которыми осуществляется так же, как и при операции деления. Длительность выполнения операции деления со сложением равна одному такту.Переключение устройства в режим контроля осуществляется кодом операции "111". Сигнал логической единицы с седьмого выхода дешифратора 12 (см, табл. 1) действует непосредственно на управляющем входе мультиплексора 1 и через элемент ИЛИ 11 на управляющем входе мультиплексора 6. Число А с входа 14 устройства через мультиплексор 1 поступает на первый вход умножителя 3, на второй вход которого через мультиплексор 6 подается число А с выхода блока 8 обращения. Результат умножения А А = 1 с выхода блока 3 через мультиплексор 4, на управляющем входе которого действует логический нуль с выхода элемента ИЛИ 9, поступает на второй вход сумматора 5, Так как сигнал на выходе элемента ИЛИ 10 равен нулю, то блок 2 элементов И закрыт и на первый вход сумматора 5 поступает нулевое слагаемое. Результат сложения, равный единице (представляемый в поле Галуа ОЕ (2") как и - , разрядное число 001), подается на первый вход схемы 7 сравнения, на втором входе которой постоянно действует число,функционирует исправно, то сигналы навходах схемы 7 сравнения равны и сигналравенства с ее выхода подается на выход 18устройства. Дополнительный положительный эффект устройства обуславливается организацией режима контроля, при котором осуществляется проверка работоспособности всех входящих в его состав блоков. Формула изобретения Устройство для вычислений в конечных полях, содержащее с первого по третий мультиплексоры, блок элементов И, умно- житель, сумматор и блок обращения, причем входы первого и второго операндов устройства соединены соответственно с первыми информационными входами первого и второго мультиплексоров, выходы которых соединены соответственно с входами первого и второго сомножителей умножителя, выход блока элементов И соединен с входом первого слагаемого сумматора, выход которого является выходом результата устройства, с первого по четвертый входы задания режима которого соединены соответственно с управляющими входами с первого по третий мультиплексоров и с первым входом блока10 1695299 Таблица 1 Таблица 2 элементов И, отл ич а ю щееся тем, что, с целью повышения быстродействия, оно содержит схему сравнения, причем вход второго операнда устройства соединен с вторым информационным входом первого мультиплексора и с входом блока обращения; выход которого соединен с вторым информационным входом второго мультиплексора, выходы умножителя и второго мультиплексора соединены соответственно с первым и вторым информационными входами третьего мультиплексора, выход которого соединен с входом второго слагаемого сумматора, выход которого соеди нен с первым входом схемы сравнения,второй вход и выход которой являются соответственно входом константы и контрольным выходом устройства, вход третьего операнда которого соединен с вторым вхо дом блока элемента И.1695299 т в с а итель А. Клюеведактор Э, Слиган Техред М.Моргентал Корректор Т, Пали Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 10 Заказ 4162 Тираж ВНИИПИ Государственного комите 113035, МоскваПодписноепо изобретениям и открытиям при ГКНТ СС35, Раушская наб 4/5