Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться при построении декодирующих устройств двоичных циклических кодов.
При декодировании циклических кодов приходится выполнять операции умножения произвольных элементов конечного поля GF(2), которые обычно представляются полиномами степени не более т-1 с коэффициентами из поля. GF(2). В этом случае операции над полиномами производятся по модулю неприводимого многочлена м(х) степени т, который является образующим поля GF(.
Известны устройства для .умножения полиномов по модулю неприводимого многочлена М(х), содержащие параллельно включенные по входу два накопителя на m разрядов каждый, выходы которых подключены к входам третьего накопителя на m разрядов непосредственно или через элементы И и сумматоры по модулю два. При этом общее количество сумматоров по модулю два и элементов И пропорционально величине т, т.е. квадрату степени расширения поля GF(2) Cl.
Известно также устройство для умножения полиномов, схема которого содержит регистр, выход которого подключен к входам первого из сумматоров по модулю два, вход устройства подключен к входу регистра и к входу второго сумматора по модулю два, выход которого подключен к одному из входов третьего сумматора по модулю два,
10 элемент задержки,вход которого подключен к выходу первого сумматора по модулю два, а выход подключен к второму входу третьего сумматора по модулю дэа 2.
15
Однако для получения многочлена над полем GFCZ) необходимо после этого устройства ставить делитель на неприводимый многочлен М(х), .что существенно усложняет устройство.
20
Наиболее близким к предлагаемому является устройство для умножения полиномов над конечными полями GF(2 по модулю неприводимого многочлена, состоящее чэ регистра сдвига с обрат25ной связью, содержащего m элементов памяти, m элементов ИЛИ, первые входгл которых соединены с выходами соответствующих элементов памяти, вторые входы которых Подключеньл к первой
30 группе входов устройства, выход п-го i
элемента памяти, являющийся выходом регистра, подключен к первым входам элементов И, вторые входы которых подключены к выходам блока умножения на X по модулю неприводимого многочлена М(х), содержащего m элементов памяти ,т элементов ИЛИ и К ufl(x)J- 1 (U;(M(X) - вес многочлена М(х) сумматоров по модулю два, причем эыход i-ro элемента ИЛИ (,.,.,m) подключен к входу i-ro элемента памяти, выход J-ro элемента памяти - к входу (j+l)-ro элемента ИЛИ непоспедственно, если коэффициент при х в многочлене М(х) равен нулю, или через сумматор по.модулю два, если коэффициент при х в многочлене М(х) отличен от нуля (j 1,.,.,т-i) выход т-го элемента памяти подключен ко входу первого элемента ИЛИ и ко вторым входам сумматоров по модулю два, вторые входы элементов ИЛИ подключены ко второй группе входов устройства, выходы элементов памяти,являющиеся выходами блока умножения на X по модулю неприводимого многочлена М(х), подключены ко вторым входам элементов И, выходы которых подключены к первым входам следующих m сумматоров по модулю два, выхода которых подключены к входам m элементов памяти, выходы- которых подключен ко вторым входам сумматоров по модул два и к выходам устройства, продвижение информации осуществляется генератором продвигающих импульсов, выход которого подключен к управляющим входам элементов памяти З.
Однако данное устройство имеет большое количество элементов, что в значительной степени усложняет его. При этом количество элементов пропорционсшьно величине т,
Целью изобретения является упрощение устройства.
Поставленная цель достигается тем что устройство для умножения полиномов над конечными .полями GF(2) по модулю неприводимого многочлена, содержащее генератор импульсов, m элементов И, блок умножения на х по модулю неприводимого многочлена М(х), который состоит иэ m элементов памяти, m элементов ИЛИ и К сумматоров по модулю два (где К. (х) -1 ; (ttlCx) - вес многочлена М(х) , причем выход i-ro элемента ИЛИ подключе к информационному входу i-ro элемент памяти (is1,..,,m), выход J-ro элемента памяти подключен соответственно к одному из входов (j4-1)-го элемента ИЛИ (j 1m-1) непосредственно, если коэффициент при х в многочлене М(х) равен нулю, или через один из сумматоров .по модулю два если коэффициент при xJ в многочлене м(х) отличен от нуля, выход т-го элемента памяти подключен к вторым входам cy 1 1aтopoв по модулю два и к первому входу первого элемента ИЛИ, вторые входы элементов ИЛИ подключены к первой группе входов устройства соответцтвенно, содержит дешифратор и блок деления на х по модулю неприводимого многочлена М{х), который состоит иэ m элементов памяти, m элементов ИЛИ и К сумматоров по модулю .два, причем информационный вход 1-го элемента памяти подключен к выходу 1-го элемента ИЛИ, выход j-ro элемента ламяти подключен к входу (j-1)го элемента ИЛИ непосредственно, есля коэффициент при хЗ в многочлене Н(х) равен нулю, или через один иэ сумматоров по модулю два, если коэффициент при х в миогочлене И(х) отличен от нуля, выход первого элемента памяти подключен ко вторим входам сумматоров по модулю два и к первому входу т-го элемента ИЛИ, вторые входы элементов ИЛИ подключены ко второй группе входов устройства соответственно, к управляющим вхо- элементов памяти блока деления на X по модулю неприводимого многочлена М(х) и блока умножения на х по модулю неприводимого многочлена М(х) подключен выход генератора импульсов, выходы элементов памяти блока умножения на X по модулю неприводимого многочлена М(х) подключены к первым входам элементов И соответственно, вторы входы которых подключены к выходам дешифратора, входа которого подключены к выходам элементов памяти блока деления на х по модулю неприводимого многочлена М(х), выходы элементов И соединены с группой выходов устройства соответственно. °
На фиг.1 представлена структурная схема устройства для умножения над конечными полями GF( по модулю неприводимого многочлена; на фиг.2 схема блока умножения на х по модулю неприводимого многочлена М(х); на фиг.З - схема блока деления на х по модулю неприводимого многочлена М(х).
Устройство содержит блок 1 деления на X по модулю неприводимого многочлена М(х), блок 2 умножения на х по модулю неприводимого многочлена М(х), генератор 3 импульсов,дешифратор 4, элементы И 5 ,5,..., 5уу. Клок 2 содержит m элементов или 6j( ,6,. .. , т элементов 7yj , Тг., .. . , Т ламяти, и К сумматоров .по модулю два 8, при.чем выход элемента ИЛИ подключен к входу элемента памяти, выход элемента 7; памяти подключен к одному из входов элемента ИЛИ л. непосредственно, если коэффициент при х1 в многочлене м(х} равен нулю, или через сумматор по модулю два 8, если коэффициент при X в многочлене М(х) отличен от нуля, выход элемента 7 памяти подключен ко вторым входам сумматоров 8,, ..,, 8 по модулю два и к одному из входов элемента ИЛИ 6j , вторые входы элементов ИЛИ 6, 6, 6уу) подключены к входам блока 2, выходы элементов 7 ,72,..., 7 памяти являются выходами блока 2. Блок 1 содержит m элементов 9, 9 , .... , 9j памяти, m элементов ИЛИ 10, 10, ..., lOfyjH К сумматоров 1 по модулю два, причём вход элемента 9 памяти подключен к выходу элемен та ИЛИ , выходы элементов 9 памяти) подключен к входам элементов ИЛИ .10; нвпоср едственно, если козффициент при уЛ в многочлене М(х) р вен нулю, или через один из сукмато ров 11, 111, ...f UK/ если коэффи циент при многочлене М(х) отл чен от нуля, выход элемента 9 памяти подключен ко вторым входам сум маторов 11, 11, ... lljt по модулю два и ко входу элемента ИЛИ вторые входы ИЛИ 10 , ... Юуу, подключены к входам блока 1, вы ходы элементов 9 , 9, ..., памя ти , являющиеся выходамиблока 1, по .ключе{Ш к входам дешифратора 4 комбинации 10...000, выход которого подключен к первым входам элементов И 5 , 5, ,,., 5,у,,ко вторым входам которых подключены выходы блока 2, управляющим входам элементов памяти 7, 9 блоков 1 и 2 подключен вьаход генератора 3 импульсов, выходом устройртва являются выходы элементов И 5| , 5g, . .. , 5й1. Устройство работает следующим образом. В исходном состоянии элементы памяти 7, .9 блоков 1 и 2 обнулены. С первым нагом работы в элементы памяти , 9q, 9 блока 1 записываются Коэффициенты одного полиномасомножителя, а в элементы памяти 7 7, ..., 7j блока 2 - коэффициенты второго полинома-сомножителя, причем как в блоке 1 так и в блоке 2 коэффициенты при старших степенях помещаются в правые элементы памяти 7, 9. Со вторым шагом работы устройства под воздействием управляющих им пульсав генератора 3 осуществляется сдвиг содержимого блоков 1 и 2, т.е в блоке 1 осуществляется деление на X по модулю неприводимого полинома М(х) , а в блоке 2 - умножение на У, п модулю Неприводимого многочлена м(х) Второй шаг повторяется до тех пор, пока в блоке 1 не будет оформирован полином нулевой степени, т.е. комбинация 10...000. К этому моменту в блоке 2 сформировано произве дение полиномов по модулю неприводимого многочлена н(х). Дешифратор 4, обнаружив наличие комбинации 10...00О в блоке 1, своим выходным импульсом разрешает выдачу произведения из блока 2 через элементы 5 , S, ...г , Н на выход устройст ва. После чего устройство приводится в исходное состояниег Введение в устройство блока деления на X по модулю неприводимого многочлена позволяет уменьшить число элементов в устройстве почти в два 1эаза. Формула изобретения Устройство для умножения полиномов над конечными полями QF ) по модулю неприводимого киогочлена, содержащее генератор импульсов, W элементов И, блок умножения на Я по модулю неприводимого многочлена МСх) , который состоит из W элементов памяти, и элементов ИЛИ и К cy waтopoв по модулю два (где K.-OuCMWl-i; (4)j - вес многочлена МС) , причем выход -го элемента ИЛИ под-. ключей к информационному входу 4 -то элемента памяти (i 1,.-, w ) , выход j-ro элемента памяти подключен соответственно к одному из входов tj4--)) го элемента ИЛИ (j-f... wt-l) непо- , средственно, если коэффициент при у,} в многочлене АЛ(Х) равен нулю, или через один из сумматоров по.модулю два, если коэффициент при Х в многочлене M.Clt) отличен от нуля, выход уи-го элемента памяти подключен к вторым входам сумматоров по модулю два и к первому входу первого элемента ИЛИ, вторые входы элементов ИЛИ подключены к первой группе входов устройства соответствэнно, о т л и ч аю щ е е е с я тем, что, с целью упрощения устройства, оно содержит дешифратор и блок деления на X. по гюдулю неприводимого многочлена МСХ) г который состоит из in элементов памяти ,W элементов ИЛИ « К сумматоров по гюдулк два, причем информационный вход i-го элемента памяти подключен к выходу -i -го элемента ИЛИ, выход -го элемента памяти подключен к входу (j-i)-ro элемента ИЛИ непоспедственно, если коэфОициент при в многочлене M{V) равен нулю, или через один из сумматоров по модулю два, если коэффициент при в многочлене М{У) отличен от нуля, выход первого элемента подключен к вторым входам сумматоров по модулю два и к первому входу W-ro элемента ИЛИ, вторые входы элементов ИЛИ подключены к второй . группе входов устройства соответственно, к управляющим входам злементов памяти блока деления на У. по модулю неприводимого многочлена М(() и блока умножения на X по модулю неприводимого многочлена ( подключен выход генератора импульсов, вьдход.. элементов памяти блока умножения на X по модулю неприводимого многочлена f.(х) подключены к первым входам элементов И соответственно, вторые входы которых подключены к выходам дешифратора, входы которого подключены к выходам элементов памяти блока деления наХ по модулю неприводимого многочлена М(х), выходы элементов И соединены группой выходов устройства соответственно.
Источники информации, принятые во внимание при экспертизе
/v
1.Bartee Th.C. et el. Computation with Finite Flelds.- Inform. and Control, 1963, 6, p. 85i
2.Авторское свидетельство СССР 538364, кл. 6 06 F 7/52, 1975.
З.лох Э.Л. и др. Обобщенные каскадныекоды. М., Связь, 1976, с. 99 (прототип),
тт
