Устройство для вычислений в поле галуа gf (2 @ )

 

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

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

РЕСПУБЛИК (я) 5 G 06 F 7/49, 15/31

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

{21) 4796469/24 (22) 26.02.90 (46) 07.08.92. Бюл. М 29 (71) Научно-исследовательский институт вычислительной техники и Пензенский пол: итехнический институт (72) А.В.Толов, Б.А.Савельев, Н.Б.Залялов, С.Н»Комраков и Н.И.Басманов (56) Авторское свидетельство СССР

1Ф 1635193, кл. G 06 F 15/31, 1989.

Мак-Вильямс Ф.Дж., Слоэн Н,Дж,А, Теория кодов, исправляющих ошибки. — M.:

Связь, 1979, с, 95-98.:

Заявка ФРГ hh 3326044, кл. 6 06 F 15/31, опублик, 1984.

„,5U„, 1753470 А1 (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ В

ПОЛЕ ГАЛУА GF(2") (57) Изобретение относится к системам помехоустойчивого кодирования информации и может быть Mcfloilb30BBH0 в технике информации и вычислительной технике.

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

1 определения нуля, сумматор-вычитатель

2, схему 5 выдачи результата, модульный корректор 3 и блок 4 памяти, введен коммутатор 6, а в блок памяти 4 записана таблица логарифма Зеча. 2 ил.

1753470

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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что

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

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

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

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

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

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

1753470 модулю два. За счет замены двух блоков ректор; блок памяти исхемувыдачи резульпостоянной памяти логарифмов на один тата, выход которой соединен с выходом блок постоянной памятилогарифма Зечаус- . устройства, вход которого соединен с вхотройство выигрывает в объеме постоянной дом схемы определения нуля, первый выход памяти, что весьма ощутимо при испольэо- 5 которой соединен с управляющим входом вании йолей большой размерности, т.е. при схемы выдачи результата, выход сумматораувеличении показателя степени п для поля вычитателя соединен с входом модульного

GF(2") аппаратные затраты растут медлен- корректора, выход которогосоединен с вхонее по сравнению с аппаратными затратами дом памяти, о т л и ч а ю щ е е с я тем, что, протетипа. Напримердяя поляОЕ(2 обьем 10 с цепью расширения функционаяьных аоаЗУ прототипа как минимум 2 + 2 = 512 можностей эа счет выполнения операции в байтов или 0,5 К, а для предлагаемого уст- . сложения по модулю два и упрощения устройсТва 2 байтов или 0,25 К. Для поля Гйлуа ройства, в него введен коммутатор, первый

GF(2 6) объем памяти соответственно 2 + и второй.входы которого соединены соот2 16-разрядных слов или 256 К и 128 К для 15 ветственно с вторым входом схетмы опредеустройства с использованием логарифма. ления нуля и выходом блока памяти, а вйход

Зеча. Таким образом экономия памяти со- — сйнформационным входомсумматора-выставляет 50 jf, или 128 К. читателя, управляющий вход которого соеФ о рмул а изо брет-е н и я . динен .с первым выходом схемы

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

° ° °

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

Редактор И.Шмакова Техред М.Моргентал Корректор H.Ìèëþêoâà

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

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

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

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