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

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

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

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

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

Однако это устройство достаточно сложно и громоздко.

Наиболее близким по технической сущности к предлагаемому является устройство для умножения и деления в поле Галуа.

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

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

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

антилогарифмов замены на таблицу логарифма Зеча.

На фиг. 1 представлена структурная схема предлагаемого устройства для вычислений в поле Галуа GF(2n) с использованием

0 логарифма Зеча; на фиг. 2 - один из вариантов функциональной схемы устройства.

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

5 второй вход которого подключен к второму выходу схемы 1 определения нуля, выход коммутатора 6 соединен с входом сумматора-вычитателя 2, к управляющему входу которого подключен первый выход схемы 1

0 определения нуля.

Устройство (фиг. 2) содержит схему 7 определения нуля, состоящую из дешифратора 8 нуля и триггера 9, блок 10 постоянной памяти логарифма Зеча, коммутатор 11, со5 стоящий из мультиплексора-регистра 12 и регистра 13, сумматор-вычитатель 14 и схему 15 выдачи результата, состоящую из схемы 16 совпадения, логической схемы 17 управления выдачей 2И-14ЛИ-НЕ, инверто0 ра 18 и ключей 19. Выход переноса CN сумматора-вычитателя 14 соединен с его входом переноса МО и образует модульный корректор.

Существует возможность производить

5 кодирование и декодирование информации (и другие вычисления в поле Галуа GF(2n)) в показательной форме, т.е. считая, что информация представлена в показательной форме, операции умножения и деления в

0 поле Галуа GF(2) выполняются как операции сложения и вычитания по модулю (2П -1). Операция сложения по модулю два выполняется в показательной форме как совокупность операций сложения и вычитания по

5 модулю (2П - 1) с использованием таблицы логарифма Зеча.

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

модулю два. За счет замены двух блоков постоянной памяти логарифмов на один блок постоянной памяти логарифма Зеча устройство выигрывает в объеме постоянной памяти, что весьма ощутимо при использовании полей большой размерности, т.е. при увеличении показателя степени п для поля GF(2n) аппаратные затраты растут медленнее по сравнению с аппаратными затратами прототипа. Например, для поляСР(2уобъем ЗУ прототипа как минимум 28 + 2 - 512 байтов или 0,5 К, а для предлагаемого ус т- оойства 28 байтов или 0,25 К. Для поля Гйлуа GF(2 ®) объем памяти соответственно 21 + 2 16-разрядных слов или 256 К и 128 К для устройства с использованием логарифма Зеча. Таким образом экономия памяти составляет 50% или 128 К.

Формула изобрет-ения Устройство для вычислений в поле Га- луа GF(2n), содержащее схему определения нуля, сумматор-вычитатель, модульный корректор, блок памяти и схему выдачи результата, выход которой соединен с выходом устройства, вход которого соединен с входом схемы определения нуля, первый выход

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

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

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

«-- 2