Параллельное устройство для умножения в поле галуа gf (2 @ )

 

Изобретение относится к области вычислительной техники и может быть использовано в устройствах кодирования помехоустойчивыми кодами при передаче данных. Цель изобретения - упрощение устройства. Параллельное устройство для умножения в поле Галуа GF (2<SP POS="POST">N</SP>) содержит N блоков 1-1, 1-2,....,1-N ключей, в каждый из которых входят N элементов И 2-1, 2-2,...2-N и N групп сумматоров 3-1, 3-2,...,3-N по модулю два, соединенных между собой функционально. 2 ил. 1 табл.

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

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

РЕСПУБЛИК (51) 4 G 06 F 7/49

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

Ж с©

CQ

CA

4ь

/7 Ф

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

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

ПРИ ГКНТ СССР

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4277465/24-24 (22) 06.07.87 (46) 07.08.89. Бюл. М 29 (72) В.А.Зиновьев, В.В,Зяблов, Б.А.Савельев, О.Ф.Бузин, В.И.Михайлов, С.М.Додунеков (BU), В.М.Георгиева (BU), Н.Л.Манев (BU), П.А.Попов (BU) и В.Б.Стойнов (SU) (53) 681.325 (088,8) (56) Авторское свидетельство СССР

Р 900281, кл. G 06 Г 7/49, 1982.

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

Ф 1383338, кл. G 06 F 7/49, 1986, „„Я0„„1499334 А I (54) ПАРАЛЛЕЛЬНОЕ УСТРОЙСТЮ ДЛЯ УМНОЖЕНИЯ В ПОЛЕ ГАЛУА GF(2 ) (57) Изобретение относится к области вычислительной техники и может быть использовано в устройствах копирова- . ния помехоустойчивыми кодами при передаче данных. Цель изобретения — упрощение устройства. Параллельное устройство для умножения в поле Галуа

GF (2 ) .содержит и блоков 1-1,1-2,...

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

3 14993

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

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

На фиг.1 представлена структурная схема параллельного устройства для 1О умножения в поле Галуа СР (2"); на фиг.2 и 3 — функциональная схема параллельного устройства для умножения в поле Галуа GF (20),варианты.

Параллельное устройство для умно- I5 жения в поле Галуа GP (2") содержит и блоков 1-1, 1-2,...,1-п ключей, в каждый из которых входят п элементов

И 2-1, 2-2,...,2-п и п групп 3-1, 3-2,...,3-п сумматоров по модулю два, 20 соединенные между собой функциональ" но.

Параллельное устройство для умножения в поле Галуа GP (28) элементов, представленных в нормальном базисе с помощью полинома g(х)=х"+х +х +х +1, 6 содержит восемь блоков 1-1, 1-2,..., 1-8 ключей, в каждый из которых входит по восемь элементов И 2-1 2-2, ...,2-8, причем каждая входная цель множимого А(х) соединена соответственно с первыми входами элементов И блоков 1- 1, 1-2,...,1-8 ключей, и восемь групп 3-1,3-2,...,3-8 сумматоров по модулю два, при этом вы- 35 ходы 4,5,...,67 элементов И блоков

1-1, 1-2,...,1-8 ключей соединены с входами сумматоров групп 3-1,3-2,..., 3-3 следующим образом: входы сумматора 3-1-1 соединены соответственно 40 с выходами 6,18,19,20,22,30,32,33 и

39 элементов И, входы сумматора 3-1-2 соединены соответственно с выходами

10,17,21,24,38,45,50 и 57 элементов

И, входы сумматора 3-2-1 соединены 45 соответственно с выходами 15,27,38, 48,56 и 62 элементов И, входы сумматора 3-3-1 соединены соответственно а выходами 7,24,28,29,38,4),50,51 и 57 элементов И, входы сумматора 50

3-5-1 соединены соответственно с выходами 11,19,25,33,42,46,47,56 и 59 элементов И, входы сумматора 3-7-2 соединены соответственно с выходами

5,10,12,14,15,21,39,43 и 52 элемен- 55 тов И, входы сумматора 3-7-1 соединены соответственно с выходами 20, 34,55,60 и 65 элементов И, входы сумматора 3-1-3 соединены соответствен34 4 но с выходами 9,14,34,44,47,53,55,61 и 67 элементов И, и с выходами 68 и

69 сумматоров 3-1-1,3-1-2, входы сумматора 3-2-2 соединены .соответственно с выходами 4,27,29,41,43,47,53, 54,59,61,64 и 66 элементов И и с выходами 68 и 70 сумматоров 3-1-1, 3-2-1, входы сумматора 3-3-2 соединены соответственно с выходами 6,9,11, 13,20,32,35,39,44,60,63 и 65 элементов И и с выходами ?О и 71 сумматоров

3-2" 1, 3-3-1, входы сумматора 3-4 соединены соответственно с выходами

5,8,10,12,15,!6,18,22,33,36,37,47, 48,52,53,59,65 и бб элементов И и с выходом 7! сумматора 3-3-1,входы сумматора 3-5-2 соединены соответственно с выходами 14,16,27,32,37,60, 61,62 и 66 элементов И и с выходами

69 и 72 сумматоров 3-1"2,3-5-1, входы сумматора 3"б соединены соответственно с выходами 5.,6,7,12,23,26, 28,30,40,52,54,6! и 66 элементов И и с выходами 72 и ?4 сумматоров 3-5-1, 3-7-1, входы сумматора 3-7-3 соединены соответственно с выходами 6,11, 16,32,35,37,39,44,49,52,57,63 и 64 элементов И и с выходами 73 и 74 сумматоров 3-7-2,. 3-7-1, входы сумматора 3-8 соединены соответственно с выходами 8,9,19,23,24,25,30,36, 38,41,44,46,48,52,58,61,64 и 65 эле- ментов И и с выходом 73 сумматора

3-7-2, вторые входы элементов И блоков 1-1, 1-2,...,1-8 ключей соединены с соответствующими входами множителя В(х), выходы групп сумматоров являются выходами С(х) устроиства.

Устройство работает следующим образом.

Множимое А{х) и множитель В(х), как и в известном устройстве, представляются в виде выражений

n-(((1-( (!

А(х)=, а;х и В(х)=, Ь х, (1) (=О !=о

Произведение имеет вид

О-(n-(!

А(х) В(х) =,, а; Ъ х, (2)

;-о !=о

В данном случае а; и Ь> равно двоичной 1 или О. Величину х всегда можно представить через примитивный элемент поля GP (2"), т.е.

1 к х * » еС, (3) к-о

Тогда (2) ппедст <вляется так

А(х) В(х)аа,, а, Ь о, (4)

i=o Jao Ieo <+23

Конкретное преДставление х в виде (3) зависит от полинома, по- 5

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

В полинома g (x) =х +х +х +х + 1. Элементы поля представлены в таблице.

14993

А(х) ° В(х) = (/aob + a

+ a b> + а4Ьь/ + /а,b6 + а,Ь5 + агЬ, + агЬ4 + а4Ьг + а Ь, + а Ь +

+ аоЪо + а6Ь / + аоЬ + а<Ьг + а Ь6 + 5Ъо + а5Ьз + agb< + а Ь +

+ а Ьг + а Ь5 + а4Ьз/ + /а,b> + гЬ7 + a4b4, + a>b4 + абЬ4 + aãb2

+ аоЬо + агЬь + азЬ, + а4Ь + a4bz + а Ьз + аьЬ, + абЬг + а6Ь7 +

+ а4Ь + а Ье + а5Ь7 + а Ь5/+/а<Ь + агЬ7 + а4Ьб + а Ь4 + а Ь4 +

+ а<Ъг/ + аоЬг + аоЪ + aob + а(Ь, + агЬо + а Ь4 + а Ь7 + а4Ь +

+ а4Ьг + a4b> + а Ь + а Ьт + а Ь / + а,Ь, + аоЬ4 + а Ь6 + а,Ь +

+ а,b> + а,Ъ4 + а(Ь6 + агЬ + a b> + а4Ь + а4Ь, + а Ь 3 + 5Ь +

+ saba + aab, + ааЬ + а Ьа + а Ьа). х + (/ааЬ + а,b» + aaba +

+ азЬ + а4Ь + а Ьг + а Ьз + a<;b4 + а Ьг/+/аоЬ6 + a + агЬ, +

+ а Ь4 + а4Ьг + а Ь, + а Ь + aabo + а Ъ /+ а<Ь + а<Ь4 + a b + (б

+ агЪ + а Ь + а4Ь6 + а Ьг + а Ъ + а Ь4 + а6Ь /+/агЬ + а Ь6 +

+ аьЬ + агЬо + а Ь / + aob< + aob«. + а,b> + а,Ьо + à b> + агЬа + м

+ а Ь, + a4bz + аВЬт + оЬг + aob7 + а,Ь4 + агЬо + a>b< + азЬт +

+ а4Ъ, + a4b> + а4 е + а Ь + а6Ъо + a6b> + абЪ, + агЬо + à. b3 +

+ а1Ъа + a ba). х + (/ааЬ, + aaba + а,Ьа + а,Ьа + а Ь + ааЬ, +

+ а Ь< + а4Ьг + а Ът/ + а,Ь4 + оЬ + а,Ьт + а Ъз + а Ь+ + агЪ +

+ а Ьг + а Ь, + а4Ьг + а4Ьs + а Ьо + а Ь + a/4 + а6Ь + аеЬ6

4 0

+ ab< + а7Ь4 + а,Ъ J х.

28 (5) 55

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

В соответствии с полученной формулой синтезировано устройство для умножения двух элементов поля Галуа

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

34 6

Десятичные числа представляют собой степени о

В данном случае множитель и множимое можно представить в виде

7 7, S

A(x)aa 0 а, х; B(x)aa Ь х

;=о <=о

С помощью уравнения (4) и таблицы произведение А(х) В(х) приводится к виду суммы в круглых скобках совпадают и это уменьшает количество сумматоров по модулю два.

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

1О

Галуа GF (2 )

Элементы поля

36

01010001

00001)01

10011110

01011111

00100110

38

40

11011100

11010011

110!0110

0l011001

11100001

10011111

01110001

)1101011

00010101

10111011

00110110

11)01000

10111111

10010111

11110001

10101011

1,0011011

01100011 — 01000100

10110110

10010!01

1I)11011

OOI0OOOl

1)001000

01000100

105 - 10010000

106 - 011)0100

107 — 01100100

108 — 01010000

109 — 00)00011

)10 — 01010011

11011011

110001)l — 010000))

- 00111101

177

178 179

180 .181

182

141

)42

143

)44

146

О

2

4

6

8

ll

12

13

14

l6

17

18

19

21

22

23

24

26

27

28

29

3)

32

33

11111111

00010111

lll0O1l0

100010!1

01110011

11000101

00010001

10lllll0

10111001

10101101

11000011

1I10O010

01000001

00111001

11101101

00101111

11)00011

10100001

10001000

41

42

43

44

46

47

48

49

51

52

53

54

56

57

58

59

61

62

63

64

66

67

68

71

72

73

74

76

77

78

79

81

82

83

84

86

87

88

89

91

92

93

94

95 . 96

97

98

99

)00

101

102

103

104

l0l01000

10110111

l0000110

0)11101Î

О!001111

10101)11

10100011

00010011

l000000I

11101001

10001!!О

01101011

01010101

00010))0

OOI0)0ll

)I110000

10000.101

1IO0I111

10))1000

I0OQ001 1

1111010)

IlO0)O)0

11011101

llll1101

00011011

10 таблицы

183

184

186

187

188

189

191

192

193

147

148

149

151

152

153

154

156

157

194

»0000О0

158

195

159

196

197

198

001101»

»000»0

0»0»01

161

162

199

O»Oj»I

)63

201

»»OIO0

00100100

164

165

128

129

202

203

010001 »

00000О»

166

167

131

132

133

134

136

137

138

139

204

205

10»0101

0001 »01

168

169

206

207

208

209

210

l0101010

0010»00

01010»0

000»001

00001011

171

172

173

174

10100100

211

175

212

176

01010100

I40

100»001

217

218

219

235

213

214

2)5

216

226

227

228

229

231

232

233

234

10110011

00100» 1

00100101

01101001

»001»0

Oj1 » 100

0lll0101

100lll0I

» 101010

001110»

01 »011О

111111 I1

224

245

10101001

10010010

246

247

236

237

1) 101111

10110100

248

249

251

252

238

239

241

242

253

254

255

)0111010

00011000

243

244

»1

»2

»3

»4

»5

»6

»7

»8

»9

121

122

123

124

125.

)26

127

10010»0 — 0100 1» Π— OO» 1100 — 0»00010

01»10» — 0»00001

»0»» l

0» 00110

11001011

1»1001 I — 00110000

»010010

»»1000

»010101

» 101100 — O000000l — 0010» TO

- IIOO»Oi

»0О1О01

» 100000

10»0001

10» 1100 — 00100010 — 0»11101

010110»

10000» l — Ol011000 — 00110010 — 01001001

0001» l0 — 000111 »

ОО))ООО)

11» I 100 — 00110101

0101 »01

IO» 1101 — 0000» 00

l0»0000

1499334

Продолжение

0100» ОО

10100» 1

10»0010

00001001 — 00»»»

»010» 1

0» 101»

»010001

0100»0l

10001001

01»»11 — 01010111 — 00000» 1

11110111 221

l0010001 222

01011010 223 — 00»00» — 01100) »

11100101 — 00»»10

11» 100) 00101101

0» I 1000

»010100

» 100111

1O10010l

00101001

»011001

010 » 100

100100»

»000001

0»»001

1) 111010

00001» 1

00000101

j000j)jI

Oi00010l

100»000

01 100101

01»1»О

» lO» lO

100» 010

»1»»0

1010» 10

1000»01

110»»0

00000» 0

00j1101O! 499334

Составитель В. Гусев

Техред А,Кравчук Корректор 3,Лончакова

Редактор Л. Гратилло

Заказ 4694/47

Тираж 668

Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР. 113035, Москва, Ж-35, Раушская наб., д. 4/5

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