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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и 1997039 Сафз Сфветских(б 1) Дополнительное к авт. свид-ву(22) Заявлено 02.06,81 (21) 3295580/18-24с присоединением заявки Йо РМ К з С 06 Г 15/31 Государственный комитет СССР ио делам изобретений и открытий(088. 8)Опубликовано 1502,83, Бюллетень Ио 6 Дата опубликования описания 15.02,83(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИНОМОВ НАД КОНЕЧНЫМИПОЛЯМИ 6 Г(2 ф) ПО МОДУЛЮ НЕПРИВОДИМОГОМНОГОЧЛЕНА Изобретение относится к специализированным циФровым вычислительным устройствам и может использоваться при построении декодирующих устройств двоичных циклических кодов,При декодировании циклических кодов приходится. выполнять операции умножения произвольных элементов ко нечного поля ОГ(2), которые обычно представляются полиномами степени не более в с коэффициентами из поля ОГ(2). В этом случае операции над полиномами производятся по модулю не- приводимого многочлена И(х) степени в, который является образующим поля СР(2 п).Известны устройства для .умножения полиномов по модулю неприводимого многочлена И(х), содержащие параллель но включенные по входу два накопителя на в разрядов каждый, выходы которых подключены к входам третьего накопителя на в разрядов непосредственно или через элементы И и сумматорыпо модулю два. При этом общее количество сумматоров по модулю два и элементов И пропорционально величине в , т.е. квадрату степени расширения 2поля СГ(2) 13. Известно также устройство для умножения полиномов, схема которого содержит регистр, выход которого подключен к входам первого из сумматоров по модулю два, вход устройства подключен к входу регистра и к входу второго сумматора по модулю два, выход которого подключен к одному из входов третьего сумматора по модулю два, элемент задержки, вход которого подключен к выходу первого сумматора по модулю два, а выход подключен к второму входу третьего сумматора по модулю два 21.Однако для получения многочлена над полем СГ(2) необходимо после этого устройства ставить делитель на неприводимый многочлен И(х), .что существенно усложняет устройство,Наиболее близким к предлагаемому является устройство для умножения полиномов над конечными полями СГ(2 дф) по модулю неприводимого многочлена, состоящее из регистра сдвига с обратной связью, содержащего в элементов памяти, в элементов ИЛИ, первые входи которых соединены с выходами соответствующих элементов памяти, вторые входы которых подключены к первой группе входов устройства, выход в-го, 9970 39элемента памяти, являющийся выходом регистра, подключен к первым входам элементов И, вторые входы которых подключены к выходам блока умножения на х по модулю неприводимого много- члена М(х), содержащего е элементов памяти,в элементов ИЛИ и К =4 ф (х)1 - 1 (СЮ(И(х) - вес многочлена М(х) сумматоров по модулю два, причем выход 1-го элемента ИЛИ (1=1щ) подключен к входу 1-го элемента памяти, выход )-го элемента памяти - к входу (1+1)-го элемента ИЛИ непоспедственно, если коэффициент при хв многочлене М(х) равен нулю, или через сумматор по.модулю два, если коэффициент при х в многочлене И(х) отличен от нуля1а), выход щ-го элемента памяти подключен ко входу первого элемента ИЛИ и ко вторым входам сумматоров по модулю два, вторые входы элементов ИЛИ подключены ко второй группе входов устройства, выходы элементов памяти,являющиеся выходами блока умножения на х по модулю неприводимого много- члена М(х), подключены ко вторым входам элементов И, выходы которых подключены к первым входам следующих а сумматоров по модулю два, выходы которых подключены к входам в элементов памяти, выходьг которых подключены ко вторым входам сумматоров по модулю два и к выходам устройства, продвижение информации осуществляется генератором продвигающих импульсов, выход которого подключен к управляющим входам элементов памяти3 1.Однако данное устройство имеет большое количество элементов, что в значительной степени усложняет его. При этом количество элементов пропорционально величине в 1.Целью изобретения является упрощение устройства.Поставленная цель достигается тем, что устройство для умножения полиномов над конечными полями СГ(2 ) по модулю неприводимого многочлена, содержащее генератор импульсов, ю элементов И, блок умножения на х по модулю неприводимого многочлена И(х), который состоит из щ элементов памяти, я элементов ИЛИ и К сумматоров по модулю два (где К=.иф (х)- 1;(ц 11(х) - вес многочлена М(х) , при-. чем выход 1-го элемента ИЛИ подключен к информационному входу 1-го элемента памяти (1 с 1; .,е), выход )-го элемента памяти подключен соответственно к одному из входов (1+1)-го элемента ИЛИ =1,в) непосредственно, если коэффициент при хв многочлене М(х) равен нулю, или через один из сумматоров по модулю два, если коэффициент при х 1 в многочлене М(х) отличеН от нуля, выход в-го элемента памяти подключен к вторым входам сумматоров по модулю два и к первому входу первого элемента ИЛИ, вторые входы элементов ИЛИ подключенык первой группе входов устройства соответственно, содержит дешифратор иблок деления на х по модулю неприводимого многочлена й(х), который состоит из а элементов памяти, е элементов ИЛИ и К сумматоров пО модулюдва, причем информационный вход 1-гоэлемента памяти подключен к выходу1-го элемента ИЛИ, выход -го эле мента памяти подключен к входу (3-1)- го элемента ИЛИ непосредственно,если коэффициент при х 1 в многочлене М(.х) равен нулю, или через одиниз сумматоров по модулю два, если 15 коэффициент при х " в многочленеИ(х) отличен от нуля, выход первогоэлемента памяти подключен ко вторымвходам сумматоров по модулю два ик первому входу е-го элемента ИЛИ, Я вторые входы элементов ИЛИ подключены ко второй группе входов устройства соответственно, к управляющим вхоЭдам элементов памяти блока деленияна х по модулю неприводимого многод члена М(х) и блока умножения на х помодулю неприводимого многочлена М(х).подключен выход генератора импульсов,выходы элементов памяти блока умножения на х по модулю неприводимого многочлена И(х) подключены х первым входам элементов И соответственно, вторыевходы которых подключены к выходамдешифратора, входы которого подключены к выходам элементов памяти блокаделения на х по модулю неприводимогомногочлена И(х), выходы элементов Исоединены с группой выходов устройства соответственно.оНа фиг.1 представлена структурнаясхема устройства для умножения над 4 О конечными полями ОГ(2 ф 1) по модулю неприводимого многочлена; на фиг.2схема блока умножения на х по модулюнеприводимого многочлена М(х); нафиг.3 - схема блока деления на х по 45 модулю неприводимого многочлена и(х).Устройство содержит блок 1 деленияна х по модулю неприводимого многочлена М(х), блок 2 умножения на х по модулю неприводимого многочлена М(х),генератор 3 импульсов, дешифратор 4,элементы И 54,5 5, Блок 2 содержит щ элементов или 6,1,62,бщрв элементов 71,7 7 ламяти,и К сумматоров .по модулю два 8, причем выход элемента ИЛИ б подключенк входу элемента 7 памяти, выходэлемента 7 памяти подключен к одномуиз входов элемента ИЛИ б+ непосредственно, если коэффициент при х вМНОГОЧЛЕНЕ М(х) раВЕН НУЛЮ, ИЛИ ЧЕРЕЗ 60 сумматор по модулю два 8, если коэффициент при х в многочлене И(х) отличен от нуля, выход элемента 7 памяти подключен ко вторым входам сумматоров 8,6, , 8, по модулю два 65 и к одному из входов элемента ИЛИ 6.(,вторые входы элементов ИЛИ б, 66 подключены к входам блока 2, выходы элементов 7 ,7, 7 памятиявляются выходами блока 2,Блок 1 содержит а элементов 9(,9 у, .,ф 9 памяти, в элементов ИЛИ10, 10, , 10 и и К сумматоров 11по модулю два, причем вход элемента9 памяти подключен к выходу элемента ИЛИ 10, выходы элементов 9 памяти) подключен к входам элементовИЛИ,10неподредственно, если коэффициент при х 2 " в многочлене И(х) равен нулю, или через один из суммато-,ров 114, 111, , 11 к, если коэффициент при хф- в миогочлене И(х) отличен от нуля, вьисод элемента 9, памяти подключен ко вторым входам сумматоров 114 у 111., 11 к.по модулю два и ко входу элемента ИЛИ 10вторые входЫ элементов ИЛИ 10,10 д подключены к входам блока 1, выходы элементов 9, 9 , 9 памяти, являющиеся выходами. блока 1, под.ключены к входам дешифратора 4 комбинации ф 10000 ф, .выход которогоподключен к первым входам элементов 15И 54, 5,5 ко вторым входамкоторых подключейы выходы блока 2, куправляющим входам элементов памяти7, 9 блоков 1 и 2 подключен выходгенератора 3 импульсов, выходомустройства являются выходы элементов И 5, 5 у,5 е.устройствн работает следующимобразом.35В исходном состоянии элементы памяти 7, .9 блоков 1 и 2 обнулены. С первым нагом работы в элементы памЯти 9, 9, , 9 ю блока 1 записываются коэффициенты одного полинома сомножителя,а в элементы памяти 7, 7, , 7 п блока 2 - коэффициенты второго полинома-сомножителя, причем как в блоке 1 так и в блоке 2 коффициенты при старших степенях помещаются в правые элементы памяти 7, 9. Со вторым шагом работы устройства под воздействием управляющих импульсов генератора 3 осуществляется сдвиг содержимого блоков 1 и 2, т.е. в блоке 1 осуществляется деление на х по модулю неприводимого полинома И(х), а в блоке 2 - умножение на х по модулю неприводимого многочлена И(х). Второй шаг повторяется до тех пор, пока в блоке 1 не будет сформирован полином нулевой степени, т.е, комбинация ф 10000". К этому моменту в блоке 2 сформировано произведение полиномов по модулю неприводияого многочлена И(х). Дешифратор 4, Я обнаружив наличие комбинации ф 10000" в блоке 1, своим выходным импульсом разрешает выдачу произведения из блока 2 через элементы 5, 5, , 5 щ И на выход устройст- а 5 ва. после чего устройство приводится в исходное состояниемВведение в устройство блока дейения на х по модулю неприводимого многочлена позволяет уменьшить число элементов в устройстве почти в два раза.Формула изобретенияУстройство для умножения политкомов над конечными полями ОГ(Ефф ) по модулю неприводимого многочлена, содержащее генератор импульсов и 1 элементов И, блок умножения на Х по модулю неприводимого многочлена М(Х), которнй состоит из уи элементов памяти, е элементов ИЛИ и К сумматоров по иодулю два ( где К = В М(Х) 1 -1;0) М(Х) 3 - вес мно гочлен а М (Х) причем выход 1-го элемента ИЛИ под-. ключен к информационному входу 4 -го элемента памяти (1= 4 " ю ), выход -го элемента памяти подключен соответственно к одному из входов (.1) - го элемента ИЛИ Ц:(, фИ) непосредственно, если коэффициент при )( в многочлене М(Х) равен нулю, или через один из сумматоров по,модулю два, если коэффициент при ф в много- члене МЬ) отличен от нуля, выход 1 м-го элеиента памяти подключен к вторым входам сумматоров по модулю два и к первому входу первого элемента ИЛИ, вторые входы элементов ИЛИ подключены к первой группе входов устройства соответственно, о т л и ч аю щ е е е с я тем, что, с целью упрощения устройства, оно содержит дешифратор и блок деления на Х по иодулю неприводимого многочлена 3 А, который состоит из уи элементов памяти,И элементов ИЛИ и К сумматоров по иодулю два, причем информационный вход 1-го элемента памяти подключен к выходу 4 -го элемента ИЛИ, выход -го злеиента памяти подключен к входу (-1)-го элемента ИЛИ непосредст вен но, если коэВ)нциент при ) " в многочлене М(Ч) равен нулю, нли через один из сумматоров по модулю два, если коэффициент при Х " в многочлене М(Х) отличен от нуля, выход первого элемента памяти подключен к вторым входам сумматоров по модулю два и к первому входу ОФ-го элемента ИЛИ, вторые входы элементов ИЛИ подключены к второй .группе входов устройства соответственно, к управляющим входам элементов памяти блока деления на Х по иодулю неприводимого многочлена М(Х) и блока умножения на Х по модулю неприводимого многочлена и(х) подключен выход генератора ими;льсов, выходы элементов памяти блока умножения на )( по модулю неприводимого многочлена .(х) подключены к первым входам элементов Я со,997039 и аказ 935/67 Тираж 704 Подписно НИИ Филиал ППП фПатент", г. Ужгород, ул. Проектная,ответственно, вторые входы которыхподключены к выходам дешифратора,входы которого подключены к выходамэлементов памяти блока деления на Хпо модулю неприводимого многочленаМ(х), выходы элементов И соединены сгруппой выходов устройства соответственно.Источники информации,принятые во внимание при экспертизе 1. Вагйее ТЬ.С. ей а 1. СоврцСай 1- оп чФЬ Гпйе Ге 14 в.-"1 ЬГогв. апд Сопйго 1 фф 1963, 9 6, р 85. 2. Авторское свидетельство СССРР 538364, кл. 8 06 Г 7/52, 19753. Блох З.Л. и др. Обобщенные каскадные коды. М., "Связь", 1976, с. 99 (прототип),