Устройство для деления полиномов над конечными полями GF(2 @ ) по модулю неприводимого многочлена Советский патент 1983 года по МПК G06F17/10 G06F7/544 

дов устройства, блока умножения на X по модулю неприводимого многочлена (х) W входов которого подключены к соответствующим щ выходам блока вычисления обратного многочлена, генераторй импульсов, выход которого параллельно подключен к управляющим цепям блока вычисления обратного многочлена, регистра сдвига, блока умножения на X по модулю неприводимого многочлена АД tX) и накопителя на элементов поля G|F(2), W1 входов которого подключены к соответствующим выходам )vi элементов И, первые входы которых подключены к выходу регистра сдвига, а вторые - к WI выходам блока умножения на X по модулю неприводимого многочлена- J ЗД. Недостатком этого устройства является его сложность. Цель изобретения - упрощение устройства. Поставленная цель достигается тем что в устройство., содержащее Ш элементов И, генератор импульсов, первый блок умножения на Х по модулю неприводимого многочлена М(х) степени т, который состоит из ки элементов ИЛ W элементов памяти и К сумматоров по модулю два ( M6t}}-btJ8 C V(x) вес многочлена/Л(Х)), при этом выход i(-ro элемента памяти подключен к одному из входов (i+O-ro элемента ИЛИ непосредственно, если коэффициент при yi в многочлене МСк) равен нулю, или через один из сумматоров по модулю два, если коэффициент при Х в многочлене М(х) отличен от нуля ( 1 1,. ..,W-l), выход hi-го элемента памяти подключен ко вторым входам сумматоров по модулю два и к первому входу первого элемента ИЛИ, выход j-ro элемента ИЛИ подключен к входу соответствующего j-ro элемента памят (j 1,... ,y)i), входы блока умножения на X .по модулю неприводимого многочлена /Л(у) соединены со вторыми входами элементов ИЛИ соответственно, выходы элементов памяти соединены с выходами, первого блока умножения на X по модулю неприводимого многочлена /Л()С) введен второй блок умножения на X по модулю неприводимого многочлена М()С) и дешифратор, входы которого подключены к выходам первого блока умножения на X по модулю неприводимого .многочлена М(Х входы которого подключены к первой группе входов устройства, выход дешифратор; подключен к первым входам элементов И, вторые входы которых подключены к выходам второго блока умножения на X по модулю неприводимого многочлена ДД(Х, входы которого подключены ко второй группе входов устройства, выходы элементов И подключены к выходам устройства. На фиг. 1 представлена структурная схема устройства; на фиг. 2 конструктивное построение блока умножения на X по модулю неприводимого многочлена М (Х Устройство состоит из двух блоков 1 и 2 умножения на X по модулю неприводимого многочлена АЛ. (X), генератора 3 импульсов, дешифратора k, элементов И 5 , 52. Каждый из бло -W содержит ш элементов ков умножения 2- И1 № элементов 7j , .., 7 памяти и k. сумматоров 8,..., 8|, причем выход элемента 7;j памяти подключен к одному из входов элемента ИЛИ б;, , если коэффициент при х многочлене М(Х) равен нулю непосредственно, или через один из сумматоров 8, В,..., 8j, если коэффициент при )С в многочлене М(х) отличен от нуля; выход элемента 7 памяти подключен параллельно На вторые входы сумматоров 8 , 8,..., 81 и на -вход элемента ИЛИ 6. , причем выходы элементов ИЛИ 6, 6,..., 6 подключены ко входам соответствующих элементов 7 7..., 7уу,памяти, входами бло1 и 2.являются вторые входы элементов ИЛИ 6 , 6,..., 6, а их выходами - выходы элементов 7 , 7,... 7уу памяти, к управляющим входам которых подключен выход генератора 3 импульсов, IYI выходов блока 1 подключены к соответствующим входам дешифратора k комбинации 10...000, выход которого подключен к первым входам элементов И 5 , 5,... 5(, . вторые входы которых подключены к выходам блока 2, при этом первой группой входов устройства являются входы блока 1, а второй группой входов - входы блока 2, выходами устройства являются выходы элементов И 1, 5| Устройство работает следующим образом. В исходном состоянии элементы 7j , 7,..., памяти блоков 1 и 2 обнулены. С первым шагом работы в блок 1 помещаются коэффициенты полинома-делителя, а в блок 2 - коэффициенты полинома-делимого, причем коэ фициенты при старших степенях X полиномов помещаются в правые элементы 7 памяти блоков 1 и 2. После сэтого начинается сдвиг информации в блоках 1 и 2 под воздействием управляющих импульсов генератора 3 вправо. Т.е. осуществляется умножение на по модулю неприводимого многочлена М(х) полиномов, находящихся в блоках 1 и 2, Процесс сдвига повторяется до тех пор, пока в блоке 1 будет сформи рована комбинаций 10...000. К это му времени в блоке 2 будет сформировано частное от деления многочленов /по модулю неприводимого многочлена Д(Ч). Дешифратор k, обнаружив наличие комбинации 10...000 в блоке 1 сигналом с выхода открывает элементы И 5, $,..., 5„,и результат деления из блока 2 выдается на выход устройства, после чего элементы 7. , 7л ,..., 7уу, памяти блоков 1 и 2 обнуляю тся и устройство готово к выиолнению деления следущих полиномов. Предлагаемое устройство имеет простую логику работы и существенно проще известных, при этом общее коли чество элементов в устройстве сокращается более чем в три раза. Формула изобретения Устройство для деления полиномов над конечными полямиQF (2) по модул неприводимого многочлена, сЬДёржащее VY1 элементов И, генератор импульсов, первый блок умножения на К по модулю неприводимого многочлена Mtit) степен fn, который состоит из элементов ИЛИ, (г элементов памяти и ( сумматоров по модулю два (где1СгсуПААСХ)3-1, - вес многочлена (У)); при этом выход i-го элемента памяти подключен к одному из входов (i-f1}-ro элемента ИЛИ непосредственно, если коэффициент при X в многочлене М(Х равен нулю, или через один из сумматоров по модулю два, если коэффициент при Х в многочлене М(С отличен от нуля ( 4 1,... ,f«-1), выход элемента памяти подключен ко вторым входам сумматоров по модулю два и к первому входу первого элемента ИЛИ, выход J-го элемента ИЛИ подключен к входу соответствующего элемента памяти (j 1,... ,Wi), входы блока умножения на X по модулю неприводимого многочлена M(XJ соединены со вторыми входами элементов ИЛИ соответственно, выходы элементов памяти соединены с выходами первого, блока умножения на X по модулю неприводимого многочлена АЛ (Х , отличающееся тем, , с целью упрощения устрюйства, введен второй блок умножения на X по модулю неприводимого многочлена () и дешифратор, входы которого подключены к выходам первого блока умножения на К по модулю неприводимого многочлена M(Xj, входы которого подключе-, ны к первой группе входов устройства, выход дешифратора подключен к первым входам элементов И, вторые входы которых подключены к выходам второго блока умножения -на X по модулю неприводимого многочлена W(XK входы которого подключены ко второй группе входов устройства, выходы элементов И подключены к выходам устройства. Источники информации, принятые во внимание при экспертизе 1. Мак-Вильяме Ф.Дж. и др. Теория кодов, исправляющих ошибки. Н., Сэязь, 1979, с. 98, .рис. 3.6. 2. Th. С. Bartee et al .Computation with Finite Fields. Inform, and Control, 1963, № 6, p. 85-87, fig. 3, . 3. Блох Э.Л. и др. Обобщенные каскадные коды. М., Связь, 1976, с. 103 (прототип).

Фиг.1