Устройство для умножения элементов конечного поля GF @ (2 @ ) Советский патент 1992 года по МПК G06F7/49 

сл

с

и

VJ о о со о о

Изобретение относится к специализированным устройствам вычислительной техники и может использоваться в устройствах передачи данных, в кодирующих и.декодирующих устройствах, работающих с элементами конечного поля полиномов GF(2), которое является одним из полей ГалуаСР()прит 2,

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

При замене в таком устройстве блока вычитания блоком суммирования это устройство деления преобразуется в устройство умножения двух полиномов над конечным полем GF{2 ).

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

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

В этом устройстве производятс1Я как операция умножения, так и операция определения обратного элемента над конечным полем Галуа.

Недостатком такого устройства являют ся его большие аппаратурные затраты.

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

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

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

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

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

0 первой rpyrtne входов второй группы блоков элементов И, выходы которой подсоединены к входам первого блока сумматоров по модулю два, при этом выходы первого мультиплексора подсоединены к информационным входам второгорегистра, выходы которого подсоединены к входам матричного преобразования, выходы которого подсоединены к ;; 5ъединенным группам входов первой и второй группы блоков элементов

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

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

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

Блок синхронизации содержит триггер, {т-1)разрядный регистр сдвига, блок элементов задержки, четыре элемента И, два элемента ИЛИ-НЕ и инвертор.

Недостатком такого устройства являются, его большие аппаратурные затраты.

Цель изобретения - уменьшение аппаратурных затрат устройства для умножения эл ементов конечных полей GF(2 ).

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

На чертеже изображена cтpyкtypнaя схема устройства умножения над полем

GF(2).: .

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

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

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

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

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

При описании принципа действия устройства умножения над полем GF(2 ) выбирают в качестве параметра сигналов на

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

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

Кроме того, термины полином и элемент0 поля - идентичны.

Устройство умножения над полем GF(2) работает следующим образом.

Исходное состояние устройства не определяется и состояние первого и второго

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

0 для ненулевого элемента поля.

При выполнении устройством операции умножения двух элементов поля GF(2) на тактрвый вход и вход режима работы устройстваподаются сигналы низкого уровня,

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

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

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

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

Следовательно, по переднему фронту тактового импульсного сигнала, поступающего на тактовый вход устройства, первый и второй регистры 1 и 2 установятся в состояния, соответствующие значениям коэффициентов первого и второго полиномовсомножителей соответственно. На выходах блока б сумматоров по модулю два и, следовательно, на выходах устройства коэффициентов результирующего полинома сформируются сигналы, соответствующие коэффициентам полинома-произведения первого и второго полиномов-сомножителей. Операция умножения двух элементов поля GF(2) выполняется предлагаемым устройством, как и прототипом, за один такт его работы. При выполнении предлагаемым устройством операции определения обратного элемента для ненулевого элемента поля GF(2) на тактовый вход устройства подается сигнал низкого уровня, на вход режима работы устройства - сигнал высокого уровня, на входы устройства коэффициентов первого полинома-сомножителя - сигналы, соответствующие обращаемому полиномуэлементу поля GF{2), при этом сигналы на входах устройства коэффициентов второго полинома-сомножителя могут быть произвольными, а затем на тактовый вход устройства подается тактовый импульсный сигнал высокого уровня, после чего на входы устройства коэффициентов первого и второго полиномов и вход режима работы устройства можно подавать сигналы произвольных уровней.

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

входах второго регистра 2 сформируются

сигналы, равные сигналам на входах первой группы информационных входов мультиплексора 4. а значит, равные сигналам на информационных входах первого регистра

1,

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

Если обозначить через В значение обращаемого элемента поля GF(2). где m s N. то обратный ему элемент 8 из этого поля может быть вьнислен по формуле Bl . В нашем случае m 2. значит, обратный

элемент для ненулевого элемента из поля GF(2 ) может быть вычислен по следующей зависимости:

1OfTl - О9

В В В, и следовательно, как квадрат обращаемого

полинома из поля GF(2).

Предлагаемое устройство выполняет операцикгрпределения обратного элемента для ненулевого элемента поля GF(2). как и прототип, за-один такт его работы. Таким

образом, работоспособность устройства не нарушается.

Работоспособность предлагаемого устройства по сравнению с прототипом при m 2 обеспечивается меньшимиаппаратурными затратами.

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

Аппаратурные затраты предлагаемого устройства составляют два регистра, один мультиплексор на две группы информационных входов, один матричный преобразователь, одну группу блоков элементов И, один блок сумматоров по модулю два и инвертор. По сравнению с прототипом предлагаемое устройство по аппаратурным затратам имеет меньше на один регистр, два мультиплексора на три группы информационных входов каждый, одну группу блоков элементов И, один блок сумматоров по модулю два и блок синхронизации без инвер-. тора. Рассмотрим состав функциональных элементов прототипа. Регистр прототипа при m 2 состоит из двух 1К-триггеррв и двух инверторов. Мультиплексор на три труппы информационных входов состоит из шести двухвходовых эле.ментов И и двух трехвходовых элементов ИЛИ. Группа блоков элементов И состоит из четырех двухвходовых элементов И. Блок сумматоров по модулю два состоит из двух двухвходовых сумматоров по модулю два. Блок синхронизации состоит из инвертора, трех D-триггеров, пяти двухвходовых элементов И и двух двухвходовых элементов ИЛИ-НЕ. Таким образом, предлагаемое устройство по сравнению с прототипом имеет в своем составе меньше на два Ж-триггера. три D-триггера. два инвертора, два сумматора по модулю два. два двухвходовые элемента ИЛИ-НЕ. двадцать один д&ухвходовый элемент Ии четыре трехвходовых элемента ИЛИ. т.е. всего на 36 логических элемент меньше. . Уменьшением аппаратурных затрат предлагаемого устройства по сравнению с прототипом при сохранении его функциональных возможностей достигается цель изобретения. Формула из.обретения Устройство для умножения элементов конечного поля GF(2 ), содержащее первый и второй регистры, мультиплексор, матричный преобразователь, группу элементов И. блок сумматоров по модулю два и элемент НЕ. причем выхЬды разрядов первого регистра соединены с соответствующими входами матричного преобразователя, выходы которого соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с соответствующими входами сумматоров по модулю два блока, а вторые входы - с соответствующими выходами разрядов второго регистра, тактовый вход которого соединен с тактовыми входами первого регистра и устройства, информационные входы первой и второй групп мультиплексора соединены соответственно с входами коэффициентов первого и второго полиномов-сомножителей, отличающееся тем. что. с целью сокращения аппаратурных затрат, вход элемента НЕ соединен с входом признака режима устройства и первым управляющим входом мультиплексора, второй управляющий вход которого соединен с выходом элемента НЕ. а выходы соответственно с информационными входами второго регистра, информационные входы первого регистра - с входами коэффициентов первого полинома-сомножителя устройства, выходы коэффициентов результирующего полинома которого соединены с выходами сумматоров по модулю два блока.