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

Изобретение относится к вычислительной технике.

Целью изобретения является упрощение устройства.

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

Вычислительное устройство в поле Галуа GF (2П) содержит мультиплексоры 1-3, регистр 4 сдвига, регистр 5, умножитель 6, блок 7 ключей и сумматор 8 по модулю два накапливающего типа.

При этом на первые входы мультиплексоров 1-3 поданы соответственно входы данных (А, В, К), на каждый из мультиплексоров 1-3, регистр 4 сдвига и блок 7 ключей по соответствующему входу - свой управляющий сигнал S, а на вторые входы мульти- I

плексоров 1 и 2 - соответственно входы данных ( С, D) . Мультиплексор 1, регистр 4 сдвига и мультиплексор 3 соединены последовательно. Мультиплексор 2, регистр 5, умножитель 6 и блок 7 ключе также соединены последовательно i Выход мультиплексора 3 подключен к входам умножителя 6. Вход сумматора 8 соединен с выходом умножителя 6 и третьим входом мультиплексора 2. Выход блока 7 ключей является выходом данных F устройства, а выход сумматора 8 - ных Е устройства.

выходом данЭлементы поля Галуа GF

О 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20

11111111 10000000 01000000 00010111 00100000 111001 10 10001011 11100100 00010000 00110100 01110011 01110000 11000101 11011000 01110010 01011110 00001000 00010001 00011010 10111110 10111001

Рассмотрим работу устройства при основных операциях по фиг. -1 при использовании поля GF (2е). Элементы поля образуются с помощью полинома g(X) X3 + X7+X( + X+ 1 и их представление в нормальном базисе приведено ниже. Характерной особенностью элементов поля GF (2П), представленных в нормальном базисе, является их запись в виде

п-1

21

(1)

6 А(Х) 21 а; X

5 где - коэффициенты, принимающие

значение 0 и 1 для двоичного поля.

GF

Важной особенностью элементов в нормальном виде является пррстота возведения в степень 21 или 2 любого элемента поля А , Это осуществляется путем циклического сдвига соответственно вправо или влево полинома А(Х), помещенного в регистр сдвига, на i разрядов. Сдвиг можно также осуществить путем соответствующего переключения выходных цепей регистра. В предлагаемом устройстве используется сдвиг содержимого регистра при возведении в степень. Этим обеспечивается уменьшение количества умножений и, следовательно, числа умножителей. Работа рассматривается при основных операциях, используемых в системах помехоустойчивого кодирования.

(28)

42

43

44

45

46

4

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

11010110 01011001 00011100 10000100 11100001 10011111 01110001 11 101011 00010101 10111011 00110110 11101000

ююоооо

10100110 10011100 1 1000100 11110110 101111 1 1 10010111 01100000 11110001

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

44 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163

164 165 166 167 168 169 70 71 72 73 74 75 76 77 78

1635193

-11110011

-00110000

-11010010

-11111000

-10010100

-11010101

-11101100

-00000001

-00101110

-11001101

-11001001

-01101000

-11100000

-1011000Д

-10111100

-00100010

-01111101

-01011011

-10000111

-01010100

-10000010

-11011011

-11000111

-01000011

-10100010

-00111101

-01001100

-10100111

-10110010

-00001001

-00111111

-11010111

-01110111

-11010001

-01001101

-10001001

-01 111111

-11000000

-01010111

-00111111

-11000110

-01101101

-01101111

-11110100

-00100100

-01000111

-00000011

-10110101

-00011101

-10101010

-00101100

-01010110

-00011001

-00001011

-10100100

-00000111

-00010100

-10010101

10110100 00110011 01100111 11100101 00111110 11111001 10111010 00011000 00100101 01101001

11001110 01111100 01110101 01001010 10011101 11101010 00111011 01110110 11111111

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

Здесь десятичные числа являются степенью оЈ

Требуется произвести следующие действия:

tf;- odW-ci2,

гдеЫ1, # , # и оЈ - элементы поля

GF (2).

Элементы поля подаются: на А -# В - ot, С - oJ , D - &Т . В начальный момент времени tt управляющие сигналы S и S, которые подаются на управляющие входы мультиплексоров 1 и 2, соединяют входы А с входами ре- гистра 4 сдвига и входы В с входами регистра 5. В результате этого на регистр 4 записывается элемент 1, на регистр 5 - элемент K.J. В следующий момент времени t2 указанные элементы поступают на входы умножителя 6, на выходе которого получают произведение ot1 ci . Произведение поступает на сумматор 8, где складывается с нулевой комбинацией. В дан- ном случае сумматор 8 по модулю два накапливающего типа (фиг. 2) построен на основе D-триггеров, инверсный выход которых подсоединен на свой

D-вход. i

В момент времени t- сигналы S и

S изменяют свое значение и подключают на входы регистров 4 и 5 соответственно входы С и D устройства. В результате на регистр 3 записывается элемент Ы. , а на регистр 4 - элемент tf. В следующий момент t в умножителе 6 получается произведение 0Ја 0(z , которое складывается в сумматоре 8 cod1. oij В результате на выходе Е получается . + 0( Хг.

Указанные операции нужно производить при кодировании и декодировании помехоустойчивыми кодами.

Указанную операцию опишем на примере поля GF (28). Степень N в двоичном представлении записывается как

N Ь0 2° + Ь,« Ьт- 27,

2 +

Ь2 2

. . .+ (2)

5

5

0

5

0

5

Таким образом,

,Н 1- п°

„ V2Mv2 4b2 2V, + b7 2%

(3)

.рЬо.рЬ.

Коэффициенты Ь0, Ь,, ..., Ь7 принимают значение 0 или 1.

Из выражений (2) и (3) видно, что возведение в степень N можно заменить .. перемножением сомножителей .2. Каждый из сомножителей р 1 2 получают путем сдвига содержимого регистра 4.

Работу схемы рассмотрим с помощью временной диаграммы на фиг. 2. На линии А показаны синхронизирующие импульсы Т. В начальный момент времени сигналы S и S2 (фиг. 2, линии S и S) подключают входы А через мультиплексор 1 на входы регистра 4, а входы В через мультиплексор 2 - на входы регистра. 5. На входы А подается А , а на входы В - о °. Таким образом, в момент t, на регистр 4 записан элемент поля (3 , а на регистр

5-сЈ°. Сигнал S (фиг. 2, линия Sj) изменяется в соответствии с двоичным представлением N. Например, если R2 , то N (11110001) - старший разряд слева, 5 и выход регистра 4 через мультиплексор 3 подключается на вход умножителя 6, а 5„ в момент времени t. подключает выход умножителя

6на вход регистра 5, г.е. замыкает цепь обратной связи. Произведение на

выходе умножителя 6 появляется с задержкой it. В результате в регистр 5 записывается А . В момент времени t2 также подается сигнал сдвига Sj на регистр 4, в результате чего его содержимое сдвигается циклически на один разряд вправо. Следовательно, при сдвиге на один разряд в регистре 4 появляется величина |32 . Далее на входах умножителя 6 появляются А с выхода регистра 4 и Р с регистра 5. Произведение р по цепи обратно связи с выхода умножителя 6 (фиг. 2, линия 6) через мультиплексор 2 записывается в регистр 5. Далее работа схемы происходит аналогично в соответствии с временной диаграммой (фиг. 2). При появлении в двоичном представлении N нулевого разряда S 0 (фиг. 2, линия S3) через мульти- плексор 3 на входы умножителя 6 проходит М° с входа К (фиг, 2, линия 3) Следовательно, в регистр 5 переписы- ется его предыдущее значение.

В конце цикла вычислений открывается блок 7 ключей с помощью сигнала М

Л выдается на выход F устройства.

В поле GF (2е) произвольный элемент поля р255 1, т.е. Таким образом, операция р аналогична возведению в степень N 254, В двоичном представлении N (11111110 Далее процесс аналогичен предыдущему режиму.

,-N „zss-N

пень В

В данном случае ft В

Ве

личина 255-N представляется в двоичном виде, в соответствии с которой управляет мультиплексором 3 сигнал

Б. Дальше процесс аналогичен процес- ход первого мультиплексора подключен

су вычисления В по п. 2,

Процесс вычислений аналогичен п. 2, за исключением момента Ц, в который на вход В подается вместо (Xе элемент поля у .

50

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

п. 4, однако в момент t, на вход В

I

вместо сЈи подается элемент поля

У

зар 5 t2 на соо, стре на JQ с а 5. атной . 2, апитаотомS 20 ьти- роя 3). сы- 25

ыванала

15

0

еstгичВ1110), ему

сте-

30

35

е40

ичйл

Формула изобретения

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

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

Ь-J ь, X ь, X ьг X I ьг

У г я Х

Г «g X Э м ж ята уяу /l f2 Vj ,J l + Wtwni

X c X V