Устройство для умножения элементов конечного поля gf (2 )

(5)5 6 06 Г 7/49 Е ИЗОБРЕТЕН ВИДЕТЕЛ ЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССРОПИСАН ИК АВТОРСКОМУ С(71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И,И.Ковалив(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ ОГ(2 )(57) Изобретение относится к специализированным устройствам вычислительной техники и может использоваться в устройствах передачи данных, в кодирующих и декодирующих устройствах, работающих с элементами конечного поля полиномов ОГ(2) при е = 2, Цель изобретения - уменьшение аппаратурных затрат, Устройство содержит первый 1 и второй 2 регистры, матричный преобразователь 3, мультиплексор 4 с двумя группами информационных входов, группу 5 блоков элементов И, блок 6 сумматоров помодулю два и элемент НЕ 7. 1 ил,Изобретение относится к специализированным устройствам вычислительнойтехники и может использоваться в устройствах передачи данных, в кодирующих и.декодирующих устройствах, работающих сэлементами конечного поля полиномовОГ(2 ), которое является одним из полей Галуа ОГ(2") при в = 2,Известно устройство деления полиномов над конечным полем ОГ(2 ), содержащее два блока логарифмирования, блоквычитания и блок антилогарифмирования,при этом выходы блоков логарифмированияявляются входами коэффициентов полиномов-сомножителей, выходы блоков логарифмирования подсоединены к двумгруппам входов блока вычитания соответственно, выход которого подсоединен к входублока антилогарифмирования, выходы которого являются выходами коэффициентовполинома-произведения соответственно.При замене в таком устройстве блокавычитания блоком суммирования это устройство деления преобразуется в устройство умножения двух полин омов надконечным полем ОР(2 ),Недостатком такого устройства являются большие аппэратурные затраты и сложность реализации.Известно также устройство для деленияэлементов полей Галуа, содержащее первый и второй сдвиговые регистры;один элемент И, один элемент ИЛИ-НЕ, декодер,кодер и умножитель, при этом информационные входы первого и второго сдвиговыхрегистров являются входами устройства коэффициентов полинома-делителя и полинома-делимого соответственно, выходыподсоединены к входам декодера и к первой группе входов умножителя соответственно, а тактовые входы - объединены иподсоединены к выходу элемента И, первыйвход которого является тактовым входом устройства, а второй вход - подсоединен квыходу элемента ИЛИ-НЕ, входы которогообьединены с второй группой входов умножителя и подсоединены к выходам кодера,входы которого подсоединены к выходамдекодера, при этом выходы умножителя являются выходами коэффициентов результирующего полинома.В этом устройстве производятся какоперация умножения, так и операция определения обратного элемента над конечнымполем Галуа.Недостатком такого устройства являются его большие аппаратурные затраты,Наиболее близким к изобретению является устройство для умножения элементовконечных полей, содержащее первый и вто рой регистры, первый, второй и третий мультиплексоры, матричный преобразователь, первую и вторую группы элементов И, первый и второй блоки сумматоров по модулю два, шину единицы поля и блок синхронизации, причем первые группы входов первого и второго мультиплексоров обьединены и являются входами коэффициентов первого полинома-сомножителя или обращаемого полинома, вторая. группа входов первогомультиплексора является группой входов коэффициентов второго полинома-сомножителя, вторая группа второго мультиплексора подсоединена к шине единицы поля, третья группа входов первого мультиплексора обьединена с первой группой входов третьего мультиплексора и подсоединена квыходам первого блока сумматоров по модулю два, третья группа входов второгомультиплексора обьединена с первой группой входов первой группы блоков элементов И и подсоединена к выходам первогорегистра, информационные входы которого подсоединены к выходам второго мульти 25 плексора, при этом, выходы первой группы блоков элементов И подсоединены к входам 30 35 40 45 50 55 второго блока сумматора по модулю двэ, выходы которого подсоединены к второй группе входов третьего мультиплексора и к первой группе входов второй группы блоков элементов И, выходы которой подсоединены к входам первого блока сумматоров по модулю два. при этом выходы первого мультиплексора подсоединены к информационным входам второгорегистра, выходы которого подсоединены к входам матричного преобразования, выходы которого подсоединены к -5 ьединенным группам входов первой и второй группы блоков элементов И, причем выходы третьего мультиплексора подсоединены к информационным входам третьего регистра, выходы которого являются выходами устройства коэффициентов результирующего полинома, при этом, первый вход блока синхронизации является входом признака режима устройства, второй вход блока синхронизации объединен с тактовыми входами первого и второго регистров и является тактовым входом устройства, третий входблока синхронизации является входом готовности устройства к выполнению вычислений, тактовый выход блока синхронизации подсоединен к тактовому входу третьего регистра, а первая, вторая и третья группы управляющих выходов блока подсоединены к группам управляющих входов первого, второго и третьего мультиплексоров соответственно.Блок синхронизации содержит триггер. (гл)-разрядный регистр сдвига, блок злементов задержки, четыре элемента И, дваэлемента ИЛИ-НЕ и.инвертор,Недостатком такого устройства являются его большие аппаратурные затраты,Цель изобретения - уменьшение аппаратурных затрат устройства дляумножения элементов конечных полей 6 Г(2 ).Для достижения поставленной цели в устройстве для умножения элементов конечного поля ЬЕ(2), содержащим первый и второй регистры, мультиплексор, матричный преобразователь, группу элементов И, блок сумматоров по модулю два и элемент НЕ, причем выходы разрядов первого регистра соединены с соответствующими входами матричного преобразователя, выходы которого соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с соответствующими входами сумматоров помодулю два блока, э вторые входы - с соответствующими выходами разрядов второго регистра, тактовый вход которого соединен с тактовыми входами первого регистра и устройства, информационные входы первой и второй группы мультиплексора соединены соответственно с входами коэффициентов первого и второго полиномов-сомножителей, вход элемента НЕ соединен с входом признака режима устройства и первым управляющим входом мультиплексора, второй управляющий вход которого соединен с выходом элемента НЕ, а выходы - соответственно с информационными входами второго регистра, информационные входы первого регистра соединены с входами коэффициентов первого полинома-сомножителя устроиствэ, выходы коэффициентов результирующего полинома которого соединены с выходами сумматоров по модулю два блока.На чертеже изображена структурная схема устройства умножения над полем ОР(2),Устройство умножения над полем ОГ(2 ) содержит первый и второй регистры 1 и 2 соответственно, матричный преобразователь 3, мультиплексор 4 с двумя группами информационных входов, группу 5 блоков элементов И, блок 6 сумматоров по модулю два и инвертор 7, причем два выхода первого регистра 1 подсоединены к одноименным двум входам матричного преобразователя 3. четыре выхода которого подсоединены к соответствующим четырем входам первой группы входов группы 5 блоков элементов И, четыре выхода которой подсоединены к соответствующим четырем входам блока б сумматоров по модулю два, при этом дваКроме того, термины папином и элемент, 40 поля - идентичны.Устройство умножения над полем 6 Г(2 )гработает следующим образом.Исходное состояние устройства не определяется и состояние первого и второго 45 регистров 1 и 2 могут быть произвольными.Устройство может выполнять две операции над конечным полем полиномов 6 Ц 2 ): операцию умножения двух элементов поля и операцию определения обратного элемента 50 для ненулевого элемента поля.При выполнении устройством операцииумножения двух элементов поля 6 Г(2 ) на тактовый вход и вход режима работы устройстваподаются сигналы низкого уровня, 55 на входы устройства коэффициентов первого и второго полиномов-сомножителей подаются сигналы, соответствующие значениям коэффициентов первого и второго полиномов-сомножителей соответственно, а затем на тактовый вход устройства 101520 253035 выхода второго регистра 2 подсоединены к одноименным двум входам второй группы входов группы 5 блоков элементов.И, а тактовые входы регистров 1 и 2 - объединеныи являются тактовым входом устройствапричем информационные два входа первого регистра 1 объединены с одноименнымидвумя информационными входами первой группы информационных входов мультиплексора 4 и являются входами устройства коэффициентов первого полинома.-сомножителя, два информационные входы второй группы информационных входов мультиплексора 4 являются входами устройствакоэффициентов второго полинома-сомножителя, э два выходы подсоединены к двум одноименным информационным входам второго регистра 2, при этом первый управляющий вход мультиплексора 4 обьединен е входом инвертора 7 и является входом признака режима работы устройства, а второй управляющий вход мультиплексора 4 подсоединен к выходу инвертора 7, причем два выхода блока 6 сумматоров по модулю два являются выходами устройства коэффициентов результирующего полинома,При описании принципа действия устройства умножения над полем 6 Г(2.) выбиг рают в качестве параметра сигналов насоответствующих входах и выходах устройства или его функциональных элементов напряжение, уровни которого определяются как для "положительной логики". Таким образом, высокий уровень сигнала определяетистинное значение в булевой алгебре величины, приписываемой данному сигналу, а низкий уровень - ложное.1709300 5 10 15 20 25 30 подается тактовый импульсный сигнал высокого уровня, после чего на входы устройства коэффициентов первого и второго полиномов-сомножителей и на вход режима работы устройства можно подавать сигналы произвольных уровней, например, соответствующие полиномам при следующей операции над полем 6 Е(2 ).При сигнале низкого уровня на входе режима работы устройства, а значит, и на первом управляющем входе мультиплексора 4 и входе инвертора 7, на выходе инвертора 7, а значит, и на втором управляющем входе мультиплексора 4, формируется сигнал высокого уровня,При такам сочетании сигналов на управляющих входах мультиплексора 4 на его выходах сформируются сигналы, равные сигналам на одноименных входах второй группы информационных входов мультиплексора 4.Следовательно, по переднему фронту тактового импульсного сигнала, поступающего на тактовый вход устройства, первый и второй регистры 1 и 2 установятся в состояния, соответствующие значениям коэффициентов первого и второго полиномовсомножителей соответственно. На выходах блока б сумматоров по модулю два и, следовательно, на выходах устройства коэффициентов результирующего пол и нома сформируются сигналы, соответствующие коэффициентам полинома-произведения перво го и второго полиномов-сомножителей, Операция умножения двух элементов поля 35 6 Е(2 ) выполняется предлагаемым устройством, как и прототипом, за один такт его работы,При выполнении предлагаемым устройством операции определения обратного элемента для ненулевого элемента поля 40 6 Е(2 ) на тактовый вход устройства подается сигнал низкого уровня, на вход режима работы устройства - сигнал высокого уровня, на входы устройства коэффициентов первого полинома-сомножителя - сигналы, 45 соответствующие обращаемому полиномуэлементу поля 6 Е(2 ); при этом сигналы на входах устройства коэффициентов второго полинома-сомножителя могут быть произвольными, а затем на тактовый вход устрой ства подается тактовый импульсный сигнал высокого уровня, после чего на входы устройства коэффициентов первого и второго полиномов и вход режима работы устройства можно подавать сигналы произвольных 55 уровней.При сигнале высокого уровня на входережима работы устройства на первый и второй управляющие входы мультиплексора 4 поступят сигналы высокого и низкого (благодаря инвертору 7) уровней соответственно. При таком сочетании сигналов на управляющих входах мультиплексора 4 на его выходах. а значит, и на информационных входах второго регистра 2 сформируются сигналы, равные сигналам на входах первой группы информационных входов мультиплексора 4, а значит, равные сигналам на информационных входах первого регистра 1. Следовательно. по переднему фронту тактового импульсного сигнала высокого уровня,. поступающего на тактовый вход устройства, регистры 1 и 2 установятся в одинаковые состояния, соответствующие коэффициентам обращаемого полинома, и, значит, по аналогии с операцией умножения устройством двух элементов поля 6 Е(2 ), на выходах устройства коэффициентов результирующего полинома сформируются сигналы, соответ.твующие полиному, равному квадрату обращаемого полинома - ненулевого элемента поля 6 Е(2 ),Если обозначить через В значение обращаемого элемента поля 6 Е(2"), где т й, то обратный ему элемент В из этого поля может быть вычислен по формулеВ =ВВ нашем случае п 1 = 2, значит, обратный элемент для ненулевого элемента из поля 6 Е(2 ) может быть вычислен по следующей за виси мост;В 1 В -2 В 2и следовательно, как квадрат обращаемого полинома из поля 6 Е(2 ).Предлагаемое устройство выполняет операцию определения обратного элемента для ненулевого элемента поля 6 Е(2), как и прототип, за-один такт его работы. Таким образом, работоспособность устройства ненарушается,Работоспособност предлагаемого устройства по сравнению с прототипом при гп = 2 обеспечивается мен ь шими ап паратурными затратами.Аппаратурные затраты прототипа составляют три регистра, два мультиплексора на три группы информационных входов каждый, один мультиплексор на две группы информационных входов, один матричный преобразователь, две группы блоков элементов И, два блока сумматоров по модулю два и блок синхронизации, включающий инвертор.Аппаратурные затраты предлагаемого устройства составляют два регистра, один мультиплексор на две группы информационных входов, один матричный преобразователь, одну группу блоков элементов И, один блок сумматоров по модулю два и ин10 1709300 Таким образом, предлагаемое устройство по сравнению с прототипом имеет в своем составе меньше на два 1 К-триггера, три О-триггера, два инвертора, два сумматора по модулю два, два двухвходовые элемента ИЛИ-НЕ, двадцать один двухвходовый элемент И и четыре трехвходовых элемента ИЛИ, т.е. всего .на 36 логических элемента меньше.Уменьшением аппаратурных затрат предлагаемого устройства по сравнению с прототипом при сохранении его функциоСоставитель И.КоваливТехред М.Моргентал Редактор М.Товтин Корректор Т.Малец Заказ 425 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101 вертор. По сравнению с прототипом предлагаемое устройство по аппаратурным затратам имеет меньше на один регистр, два мультиплексора на три группы информационных входов каждый, одну группу блоков элементов И, один блок сумматоров по модулю два и блок синхронизации без инвертора.Рассмотрим состав функциональных элементов прототипа.Регистр прототипа при а -2 состоит из двух 1 К-триггеррв и двух инверторов. Мультиплексор на трй,группы информационных входов состоит из шести двухвходовых эле,ментов И и двух трехвходовых элементов ИЛИ,Группа блоков элементов И состоит из четырех двухвходовых элементов И. Блок сумматоров по модулю два состоит из двух двухвходовых сумматоров по модулю два. Блок синхронизации состоит из инвертора, трех О-триггеров, пяти двухвходовых элементов И и двух двухвходовых элементов ИЛИ-НЕ. нальных возможностей достигается цельизобретения.Формула изобретенияУстройство для умножения элементов5 конечного поля СЕ(2 ), содержащее первыйи второй регистры, мультиплексор, матричный преобразователь, группу элементов И,блок сумматоров по модулю два и элементНЕ, причем выходы разрядов первого реги 10 стра соединены с соответствующими входами матричного преобразователя, выходыкоторого соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с соответствующими15 входами сумматоров по модулю два блока,а вторые входы - с соответствующими выходами разрядов второго регистра, тактовыйвход которого соединен с тактовыми входами первого регистра и устройства, информа 20 цион.ные входы первой и второй группмультиплексора соединены соответственнос входами коэффициентов первого и второгополиномов-сомножителей, о т л и ч а ю щее с я тем, что, с целью сокращения аппара 25. турных затрат, вход элемента НЕ соединенс входом признака режима устройства ипервым управляющим входом мультиплексора, второй управляющий вход которогосоединен с выходом элемента НЕ, а выходы -30 соответственно с информационными входами второго регистра, информационные входы первого регистра - с входамикоэффициентов первого полинома-сомножителя устройства, выходы коэффициентов35 результирующего полинома которого соединены с выходами сумматоров по модулюдва блока,