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

 

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

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

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

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

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

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГННТ СССР (21) 4689561/24 (22) 11, 05 ° 89 (46) 15,03.91. Бюл. N 10 (72) Б.А.Савельев, В.А,Зиновьев, А. В. Толов, А.М. Дудкин и Б, А.Мигунов (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР

У 900281, кл. С 06 F 7/49, 1982. !

Авторское свидетельство СССР

В 1383338, кл . G 06 F 7/49, 1986. . Заявка Японии 11 - 60-14434, кл. G 06 F 11/1О, опублик. 1985. (54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО В ПОЛЕ

ГАЛУА GF {2 ) 2 (57) Изобретение относится к вычислительной технике. Цель изобретения упрощение устройства. Устройство позволяет производить умножение, деление, сложение и возведение в положительную и отрицательную степени любых элементов поля Галуа, представленных в нормальном базисе. В устройстве, содержащем три мультиплексора

1, 2 и 3, регистр 4 сдвига, регистр

5, умножитель 6, сумматор 8 по модулю два, блок 7 ключей, сумматор 8 выполнен накапливающим. Кроме того, в устройство введены новые связи, 2 ил, 1635193

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

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

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

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

3 подключен к входам умножителя 6.

Вход сумматора 8 соединен с выходом умножителя 6 и третьим входом мультиплексора 2. Выход блока 7 ключей является выходом данных F устройства, а выход сумматора 8 — выходом данных Е устройства. и-< д1 (Ь = А(Х) = а;Х 11) 1=0

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

Элементы поля Галуа GF (2 )

21 — 10101101 42—

22 — 00111000 43—

23 — 11000011 44

24 — 11100010 45—

25 — 00101010 46—

26 — 01101100 47

27 — 01000001 48

28 — 00111001 49 29 — 11101101 50

30 — 00101111 51

31 — 11100011 52

32 — 00000100 53—

33 — 10100001 54

34 — 10001000- 55—

35 — 01010001 56

36 — 00001101 57

37 — 10011110 58

38 - 01011111 59—

39 — 00100110 60

40 — 11011 100 61

41 — 110100110 — 11111111

1 — 10000000

2 — 01000000

3 — 00010111

4 — 00100000

5 — 11100110

6 — 10001011

7 — 11100100

8 — 00010000

9 — 00110100

i0 — 01110011

11 — 01110000

12 — 11000101

13 — 11011000

14 — 01110010

15 — 0101 I 110

16 — 00001000

17 — 0001000 1

18 — 0001 1010

19 — 10111110

20 — 10111001

Рассмотрим работу устройства при. основных операциях по фиг. 1 при использовании поля GF (28). Элементы поля образуются с помощью полинома

g(X) = X + X + X + K + 1 и их представление в нормальном базисе приведено ниже. Характерной особенностью элементов поля GF (2 ), представленTl ных в нормальном базисе, является их запись в виде где а; — коэффициенты, принимающие значение 0 и 1 для двоичного п.ля.

01011001

1) 100001

10011111

01110001

11101011

00010101

10111011

10111111

10010111

11110001

63

64

66

67

68

69

71

72

73

74

76

77

78

79

81

82

83

84

86

87

88

89

91

92

93

94

96

97

98

99

101

102

103

104

106

107

108

109

111

112

113

114

116

117

118

119

120

10101011

00000010

10011011

11010000

- o»oooo! — 01000100

10110110

10101000

10110111

10000110

01111010

01001111

00010010

10101111

10100011 — 00010011

10000001 — 01101110

11011010

11101001

1О00!1!0 — 01101011 — 01010101

10101100 — 00010110 — 00001110 — 00101011 — 01000010

10001100

11110000

10000101

11001111 — 01010010

10111000

10000011

11110101 — 00001010

10001010

11001010

11011101

1111! 101 — 00011011

10010000 — 01110100

01100100 — 01010000

00100011 — 01010011

10010110

01001110

00111100

01100010 — 01101010 — 01111011 — 01100001

11011111 — 01100110

11001011

121

122

123

124

126

127

128

129

130— ! з!—

132—

133—

134

136 !

З7—

138—

139—

140—

141

142—

143

-. 144—

145—

146—

147

148149—

150—

151

152

153

154

155—

156

157

158—

159

161

162

163— .164—

165—

166—

167—

168—

169

170—

171.—

172

173—

174—

175176—

177 !

78—

635193

11110011

00 110000

11010101

00000001

11001101

11001001

1011000>

01111101

01011011

100001 1 1

11011011

11000111

01000011

00111101

10100111

00001001

00111111

11010111

01110111

11010001

01001101

10001001

01111!11

01010111

00111111

01101101

01101111

01000111

00000011

10110101

00011101

00011001

00001011

00000111

10010101

179 — 11111011

180 — 00100001

181 — 11001000

182 — 01000110

183 — 00101101

184 — 01111000

185 — 1 1010100

186 — 11000010

187 — 11001100

188 — 11100111

189 — 10100101

190 — 00101001

191 — 11011001

192 — 01011100

193 — 10010011

194 — 11000001

195 — 01111001

196 — 11111010

197 — 00001111

198 — 00000101

199 — 10001111

200 — 01000101

201 — 1001 1000

202 — 01100101

203 — 01111110

204 — 11101110

205 — 1001 1010

206 — 11111110

207 — 10101110

208 — 10001 101

209 — 11011110

210 — 01001000

211 — 00000110

212 — 00111010

213 — 01011000

214 — 00110010

215 — 01001001

216 — 00101000

217 — 11110111

218 — 10010001

219 — 01011010

220 — 10101001

221 — 10011001

222 — 01001011

223 — 10110011

224 — 001001 1 1

225 — 11110010

226 — 00011110

227 — 00011111

228 — 00110001

229 — 11111100

230 — 00110101

231 — 01011101

232 — 10111101

233 — 00001100

234 — 10110000

235 — 10010010

236 — 1110 1111

1635193

247 — 11001110

248 — 01111100

249 — 01110101

250 — 01001010

251 — 10011101

252 — 11101010

253 — 00111011

254 — 01110110

255 — 11111111

237 — 10110100

238 — 001 10011

239 — 01100111

240 — 11100101

241 — 00111110

242 — 11111001

243 — 1011 1010

244 — 00011000

245 — 00100101

246 — 01101001

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

1, Умножение и сложение входных данных.

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

1

z где ф., g1, К" и О(— элементы поля

GF (2™).

Элементы поля подаются: на А — Ф, т

 — 0, С вЂ” 0, D - К . В начальный момент времени t управляющие сигналы S и S< которые подаются на управляющие входы мультиплексоров 1 и

2, соединяют входы А с входами регистра 4 сдвига и входы В с входами регистра 5. В результате этого на регистр 4 записывается элементМ, на регистр 5 — элемент К . В следующий момент времени t укаэанные элементы поступают на входы умножителя 6, на выходе которого получают произведение И 05 . Произведение поступает на сумматор 8, где складывается с нулевой комбинацией. В данном случае сумматор 8 по модулю два накапливающего типа (фиг, 2) построен на основе D-триггеров, инверсный выход которых подсоединен на свой

D-вход.

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

S изменяют свое значение и подклю2 чают на входы регистров 4 и 5 соответственно входы С и D устройства.

В результате на регистр 3 записывается элемент ф, а на регистр 4 — элемент g, В следующий момент t4 в умножителе 6 получается произведение

g < ° 0(, которое складывается в сумматоре 8 с С ., В результате на выходе Е получается,ф М + 0(Ф, Z

Укаэанные операции нужно производить при кодировании и декодировании помехоустойчивыми кодами, 2, Возведе..;ие в степень N элемента поля

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

И = Ь() 2 + Ь(2 + Ъ 2 + ...+

+ Ьт 2, (2) 25

Таким образом, и Ъ,а"Ь, г .Ь, г +„,+Ü, а р Ъо, рЪ|2 р b 2 л Ъ7 2 (3)

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

Из выражений (2) и (3) видно, что возведение в степень N можно заменить, перемножением сомножителей

Ь 2 " ° 2

Каждйй из сомножителей 3" получают путем сдвига содержимого регистра 4.

Работу схемы рассмотрим с помощью временной диаграммы на фиг. 2. На

40 линии А показаны синхронизирующие импульсы Т ° В начальный момент времени сигналы S< и S< (фиг, 2, линии S и S2) подключают входы А через мультиплексор 1 на входы регистра 4, а

45 входы В через мультиплексор 2 - иа входы регистра. 5, На входы А подается Р а на входы  — М, Таким образом, в момент t< на регистр 4 записан элемент поля (3, а на регистр

5 — (, Сигнал S (фиг. 2, линия S3) изменяется в соответствии с двоичнйм представлением N. Например, если р

211 то N = (11110001) — старший разряд слева, S> = 1 и выход регистра 4 че55 рез мультиплексор 3 подключается на вход умножителя 6, а S в момент вре2 мени t подключает выход умножителя

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

1635193

io выходе умножителя 6 появляется с задержкой ht. В результате в регистр 5 записывается P . В момент времени также подается сиг ал сдвига $5 на регистр 4, в результате чего его содержимое сдвигается циклически на один разряд вправо. Следовательно, при сдвиге на один разряд в регистре

4 появляется величина р . Далее на входах умножителя 6 появляются р с

-z выхода регистра 4 и Я с регистра 5. а

Произведение . по цепи обратной связи с выхода умножителя 6 (фиг. 2, линия 6) через мультиплексор 2 записывается в регистр 5. Далее работа схемы происходит аналогично в соответствии с временной диаграммой (фиг, 2). При появлении в двоичном представлении N нулевого разРяда Б = 20

0 (фиг, 2, линия S ) через мульти плексор 3 на входы умножителя 6 проходит О О с входа К (фиг. 2, линия 3) .

Следовательно, в регистр 5 переписыется его предыдущее значение. 25

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

Я4 и j выдается на выход F уст- II ройства, 3. Деление единичного элемента ф о

-1 на, т,е. операция Р

В поле GF (2О) произвольный эле255 мент поля (3 = 1, т.е. P = P .

254

Таким образом, операция (аналогична возведению в степень N = 254. В двоичном представлении N = (11111110) .

Далее процесс аналогичен предыдущему режиму.

4, Возведение в отрицательную степень

-N мы H 40

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

Дальще процесс a»anornweH процес- 45 су вычисления р по и. 2, 5. Вычисление произведения ) (3

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

6, Вычисление произведения

Процесс вычисления аналогичен п. 4, однако в момент t1 на вход В вместо ф подается элемент поля

О

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

Вычислительное устройство в поле

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

16 5193 ь, ь, ь, 9/d э Jz г гч++

f+gth+ Ф е Ф ч ефф

Фиг.?

Редактор А.Лежнина

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

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

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

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

Составитель В.Березкин

Техред А.Кравчук Корректор B.Гирняк и й