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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

<1997039

Сеез Саветских. Социалиетичвснии

Республик (61) Дополнительное к авт. свид-ву(22) Заявлено 02.06. 81 (21) 3295580/18-24 с присоединением заявки ¹

Р М g+ з

G 06 F 15/31

Государственный комитет

СССР ио делам изобретений и открытий (23) Приоритет 28. 07. 80

)$3) УДК681. 3 (088. 8)

Опубликовано 1502.83. Бюллетень № 6

Дата опубликования описания 15.0283, (72) Авторы изобретения

A.Ä. Широков и В . A . .Василье в

I (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИНОМОВ НАД КОНЕЧНЫМИ

ПОЛЯМИ G F (2m) ПО МОДУЛЮ НЕПРИВОДИМОГО

МНО ГО ЧЛЕНА

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

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

GF(2). В этом случае операции над полиномами производятся по модулю неприводимого многочлена И(x) степени

m, который является образующим поля

GF(2 ) °

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

2. поля GF(2 ) (13.

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

Однако для получения многочлена над полем GF(2 ) необходимо после этого устройства ставить делитель на неприводимый многочлен t1(х), что существенно усложняет устройство.

Наиболее близким к предлагаемому является устройство для умножения полиномов над конечными полями GF(2 ) по модулю неприводимого многочлена, состоящее из регистра сдвига с обратной связью, содержащего m элементов памяти, m элементов ИЛИ, первые вхощю которых соединены с выходами соответствующих элементов памяти, вторые входы которых подключены к первой группе входов устройства, выход п-го, 9970 39 элемента памяти, являющийся выходом регистра, подключен к первым входам элементов И, вторые входы которых подключены к выходам блока умножения на х по модулю неприводимого многочлена М (х), содержащего m элементов памяти,m элементов ИЛИ и К =Qft(x)3- 1 (Щ(М (x)) — вес многочлена М (х) сумматоров по модулю два, причем выход

i-го элемента ИЛИ (i=1,...,m) подключен к входу i-го элемента памяти, выход j-го элемента памяти — к входу (j+1)-ro элемента ИЛИ непоспедственно, если коэффициент при х> в многочлене М (x) равен нулю, или через сумматор по.модулю два, если коэффициент при х в многочлене И(х) отличен от нуля (j 1,...,m-1), выход

m-ro элемента памяти подключен ко входу первого элемента ИЛИ и ко вторым входам сумматоров по модулю два, вторые входы элементов ИЛИ подключены ко второй группе входов устройства, выходы элементов памяти,являющиеся выходами блока умножения на х по модулю неприводимого многочлена M(x) подключены ко вторым входам элементов И, выходы которых подключены к первым входам следующих

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

Однако данное устройство имеет большое количество элементов, что в значительной степени усложняет его.

При этом количество элементов пропорционально величине m2.

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

Поставленная цель достигается тем, что устройство для умножения полиномов над конечными .полями СГ(2 ) по модулю неприводимого многочлена, содержащее генератор импульсов, m элементов И, блок умножения на х по модулю неприводимого многочлена И(x), который состоит из m элементов памяти, m элементов ИЛИ и К сумматоров по модулю два (где К=.иф (х))- 1; (1, )M(x)) - вес многочлена И(х), при-. чем выход i-го элемента ИЛИ подключен к информационному входу i-го элемента памяти (i =1, .; ., m), выход j-го элемента памяти подключен соответственно к одному из входов (j+1) — го элемента ИЛИ (j=1, ° ...m-1) непосредственно, если коэффициент при х > в многочлене М (х) равен нулю, или через один из сумматоров по модулю два, если коэффициент при х1 в многочлене

М (x) отличеН от нуля, выход m-ro элемента памяти подключен к вторым входам сумматоров по модулю два и к первому входу первого элемента ИЛИ, вторые входы элементов ИЛИ подключены к первой группе входов устройства соответственно, содержит дешифратор и блок деления на х по модулю неприводимого многочлена й(х), который состоит из m элементов памяти, m элементов ИЛИ и К сумматоров пО модулю два, причем информационный вход 1-ro элемента памяти подключен к выходу

i-го элемента ИЛИ, выход J-го эле® мента памяти подключен к входу (j-1)го элемента ИЛИ непосредственно, если коэффициент при х) в многочлене М(.х) равен нулю, или через один из сумматоров по модулю два, если

15 коэффициент при х > в многочлене

11(х) отличен от нуля, выход первого элемента памяти подключен ко вторым входам сумматоров по модулю два и к первому входу m-го элемента ИЛИ, Я вторые входы элементов ИЛИ подключены ко второй группе входов устройства соответственно, к управляющим вхо.дам элементов памяти блока деления на х по модулю неприводимого много25 члена М(х) и блока умножения на х по модулю неприводимого многочлена М(х).. подключен выход генератора импульсов, выходы элементов памяти блока умножения на х по модулю неприводимого многочлена M(x) подключены к первым входам элементов И соответственно, вторые входы которых подключены к выходам дешифратора, входы которого подключены к выходам элементов памяти блока деления на х по модулю неприводимого многочлена M(x), выходы элементов И соединены с группой выходов устройства соответственно. о

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

4О конечными полями GF (2+ по модулю неприводимого многочлена, на фиг.2 схема блока умножения на х по модулю неприводимого многочлена М(х); на фиг.3 — схема блока деления на х по

45 модулю неприводимого многочлена M(x).

Устройство содержит блок 1 деления на х по модулю неприводимого многочлена М(х), блок 2 умножения на х по модулю неприводимого многочлена M(x) генератор 3 импульсов, дешифратор 4, элементы И 51,5<,..., 5 . Блок 2 содержит m элементов или 6,1,6,...,6 >

m элементов 71,7,,..., 7 ламяти, и К сумматоров .по модулю два 8, при55 чем выход элемента ИЛИ 6 подключен к входу элемента 7„ памяти, выход элемента 7 памяти подключен к одному из входов элемента ИЛИ 6 + непосредственно, если коэффициент при х > в

МНОГОЧЛЕНЕ M(x) раВЕН НУЛЮ, ИЛИ ЧЕРЕЗ

60 сумматор по модулю два 8, если коэффициент при х> в многочлене M(x) отличен от нуля, выход элемента 7„„ памяти подключен ко вторым входам сумматоров 8„,8, ..., 8, по модулю два

65 и к одному из входов элемента ИЛИ 6.(, 997039 вторые входы элементов ИЛИ б, 6<,..., 6 подключены к входам блока 2, выходы элементов 7, 7,..., 7„памяти являются выходами блока 2.

Блок 1 содержит m элементов 9(, 9у, ..., 9) памяти, в элементов ИЛИ

10, 10, ..., 10 и и К сумматоров 11 по модулю два, причем вход элемента

9 памяти подключен к выходу элемента ИЛИ 10, выходы элементов 9 памяти) подключен к входам элементов

ИЛИ .10 4 неподредственно, если коэффициент при хМ " в многочлене M(x) равен- нулю, или через один из суммато-, ров 11< 11д, ..., 11к, если коэффициент при x в миогочлене И(х) отличен от нуля, выход элемента 9 памяти подключен ко вторым входам сумматоров 11, 11 . .. °, 11 по модулю два и ко входу элемента ИЛИ 10 вторые входЫ элементов ИЛИ 10(, 10в, подключены к входам блока 1, вы- 20 ходы элементов 9, 9,, ..., 9„ памяти, являющиеся выходами. блока 1, под.ключены к входам дешифратора 4 комбинации "10...000", выход которого подключен к первым входам элементов .И 54, 5, ..., 5 „ко вторым входам которых подключейы выходы блока 2, к управляющим входам элементов памяти

7, 9 блоков 1 и 2 подключен выход генератора 3 импульсов, выходом устройства являются выходы элементов И 5, 5ur ° ... 5в1. устройствн работает следующим образом.

3S

В исходном состоянии элементы памяти 7, .9 блоков 1 и 2 обнулены.

С первым нагом работы в элементы памяти 9, 9, ..., 9 блока 1 записываются коэффициенты одного полиномасомножителя, а в элементы памяти 7(, 7, ..., 7 л блока 2 — коэффициенты второго полинома-сомножителя, причем как в блоке 1 так и в блоке 2 ко ффициенты при старших степенях помещаются в правые элементы памяти

7, 9. Со вторым шагом работы устройства под воздействием управляющих импульсов генератора 3 осуществляется сдвиг содержимого блоков 1 и 2, т.е. в блоке 1 осуществляется деление на х по модулю неприводимого полинома

И(х), а в блоке 2 — умножение на х по модулю неприводимого многочлена й(х).

Второй шаг повторяется до тех пор, пока в блоке 1 не будет сформирован полином нулевой степени, т.е. комбинация "10...000". К этому моменту в блоке 2 сформировано произведение полиномов по модулю неприводияого многочлена М(х). Дешифратор 4, 6О обнаружив наличие комбинации "10...000" в блоке 1, своим выходным импульсом разрешает выдачу произведения из блока 2 через элементы

5<, 5, ..., 5 И на выход устройст- g$ ва. после чего устройство приводится в исходное состояние

Введение в устройство блока дейения на х по модулю неприводимого многочлена позволяет уменьшить число элементов в устройстве почти в два раза.

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

Устройство для умножения политкомов над конечными полями GF(t ) по модулю неприводимого многочлена, содержащее генератор импульсов m элементов И, блок умножения íà g по модулю неприводимого многочлена ph,(X) которнй состоит из rn элементов памяти, vn элементов ИЛИ и К сумматоров по иодулю два (где К = Cv (M(X) ) -1;

Opjfh(X) ) — вес многочлена ф(Х) причем выход 1-го элемента ИЛИ под-. ключен к информационному входу е -го элемента памяти { j = g, .", ы ), выход у-го элемента памяти подключен соответственно к одному из входов ()4-4)го элемента ИЛИ ()=4..., wl-1) непосредственно, если коэффициент при Х)

s многочлене М(Х) равен нулю, или через один из сумматоров по.модулю два, если коэффициент при t(> в многочлене М(Х) отличен от нуля, выход ro элеиента памяти подключен к вторым входам сумматоров по модулю два и к первому входу первого элемента

ИЛИ, вторые входы элементов ИЛИ подключены к первой группе входов устройства соответственно, о т л и ч аю щ е е е с я тем, что, с целью упрощения устройства, оно содержит дешифратор и блок деления на К по иодулю неприводимого многочлена Щ(Х), который состоит из уп элементов памяти, Wl элементов ИЛИ и K сумматоров по иодулю два, причем информационный вход i--го элемента памяти подключен к выходу < -го элемента ИЛИ, выход g-ro злеиента памяти подключен к входу (f-<)-ro элемента ИЛИ непосредственно, если коэффициент при Х " в многочлене М(Ч) равен нулю, нли через один из сумматоров по модулю два, если коэффициент при х " a многочлене М(Ч) отличен от нуля, выход первого элемента памяти подключен к вторым входам сумматоров по модулю два и к первому входу Ю - ro злеме нт а ИЛИ, вторые входы злеме нтов

ИЛИ подключены к второй . группе входов устройства соответственно, к управляющим входам элементов памяти блока деления на И по иодулю неприводимого многочлена /Й(Х) и блока умножения на )(по модулю неприводимого многочлена и(v) подключен выход генератора импульсов, выходы элементов памяти блока умножения на Х по модулю неприводимого многочлена ." . (х) подключены к первым входам элементов М со,997039 фиг.2

ВНИИПИ Заказ 935/67 Тираж 704 Подписное

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4 ответственно, вторые входы которых подключены к выходам дешифратора, входы которого подключены к выходам элементов памяти блока деления на Х по модулю неприводимого многочлена

N(x) выходы элементов И соединены с группой выходов устройства соответственно.

Источники информации, принятые во внимание при экспертизе

1. 8artee Th.Ñ. et а1. Computation with F ini te Fields.-" Inform. and

Control" > 1963, Ю 6, р. 85.

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

Р 538364, кл, 6 06 F 7/52, 1975 °

3. Блох З.Л. и др. Обобщенные каскадные коды. М., "Связь", 1976, с. 99 (прототип).