Устройство для деления полиномов над конечными полями gf(2 @ ) по модулю неприводимого многочлена
ОП ИСАНИЕ
ИЗОбРЕТЕН ИЯ . Н АВТОРСНОМУ СВИДЕТЕЛЬСТВУ
Союз Советских Социалистических Республик {61) Дополнительное к авт. свид-ву (22) Заявлено 02 ° 06 ° 81 (21) 3295579/18-24 с присоединением заявки № (23) Приоритет 28. 07. 80 Опубликовано 15. 01.83. Бюллетень ¹ 2 Дата опубликования описания 18.01.83 (5l)N. Кл. G 06 F 15/31 Гееударстеек»ый кем»тет te лелем »забрете»»» и етхрытий (53) УДК 681.. 3 (088. 8) т Э! А.Д. Широков и В.А. Васильев (72) Авторы изобретения 4 4 1 j (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ПОЛИНОМОВ НАД КОНЕЧНЫМИ ПОЛЯМИ G F (2 ") ПО МОДУЛЮ НЕПРИВОДИМОГО МНОГОЧЛЕНА Изобретение относится к специализированным цифровым вычислительным устройствам и может быть использо:вано при построении декодирующих устройств двоичных циклических кодов. При декодировании циклических кодов, используемых для исправления ошибок, необходимо выполнять операцию деления произвольнЫх элементов поля GF (2 ), которые обычно представляются полиномами от Х степени не более ттт-1 с коэффициентами из поля QF(2). Причем деление полиномов осуществляется по модулю неприводимого многочлена М(у,), образующего поля GF(2 ). Известно устройство для деления полиномов по модулю неприводимого многочлена, состоящее из параллельно включенных к входу двух схем логарифмирования, выходы которых соединены с входом разностной схемы, выход которой подключен к входу схемы на2 хождения антилогарифма, выход которой подключен к выходу устройства 513. Р Однако такое устройство является очень сложным из-за наличия схем логарифмирования и антилогарифмирова5 ния. Известно также устройство для деления полиномов над конечным двоичным полем, состоящее из последовательно включенных блока нахождения обратного многочлена над конечным полем и схемы умножения полиномов по модулю неприводимого многочлена M(X) С2 3. Наиболее близким к предлагаемому 1 .является устройство для деления поли" номов над конечными полями GF(2) по модулю неприводимого многочлена, состоящее из блока вычисления обратного многочлена по модулю неприводимо" ro многочлена М(Х), вход которого подключен к первой группе входов устройства, регистра сдвига, вход котороГо подключен ко второй группе вхо3 989 дов устройства, блока умножения на X по модулю неприводимого многочлена Q(g), щ входов которого подключены к соответствующим и выходам блока вычисления обратного многочлена, генератора импульсов, выход которого параллельно подключен к управляющим цепям блока вычисления обратного многочлена, регистра сдвига, блока умножения íà X по модулю неприводимого многочлена (Ф ($ ) и накопителя íà DT элементов поля QP(2),е входов которого подключены к соответствующим выходам элементов И, первые входы которых подключены к выходу регистра сдвига, а вторые - к N выходам блока умножения на Х по модулю неприводимого многочлена (3). Недостатком этого устройства является его сложность. Цель изобретения — упрощение уст- . ройства. Поставленная цель достигается тем, что в устройство, содержащее Wl элементов И, генератор импульсов, первый блок умножения на М по модулю неприводимого многочлена 9 (X ) степени N, который состоит из тя элементов ИЛИ Ve элементов памяти и К сумматоров по модулю два (где = ou (М(ХД-1,Ю М(Х))— вес многочлена ф(Х)), при этом выход 4 -го элемента памяти подключен к одному из входов (1+1)-го элемента ИЛИ непосредственно, если коэффициент при в многочлене МЬ) равен нулю, или через один из сумматоров по модулю два, если коэффициент при )(в многочлене /А(Х)отличен от нуля (1 = =1, ...,Ит1), выходlet-ro элемента памяти подключен ко вторым входам сум- маторов по модулю два и к первому входу первого элемента ИЛИ, выход ) - го элемента ИЛИ подключен к входу соответствующего 4 -го элемента памяти (g = 1,...,у), входы блока умножения на X по модулю неприводимого многочлена PA() соединены со вторыми входами элементов ИЛИ соответственно, выходы элементов памяти соединены с выходами первого блока умножения на ) по модулю неприводимого многочлена ф(К), введен второй блок. Умножения на Х по модулю неприводимого многочлена М(К) и дешифратор, входы которого подключены к выходам первого блока умножения на )(по модулю неприводимого многочлена ЩХ), входы которого подключены к первой группе входов устройства, выход дешифратора подключен к первым входам элементов И, вторые входы которых подключены к выходам второго блока умножения на ;Х по модулю неприводимого многочлена М(Х), входы которого подключены ко второй группе входов устройства, вы-. ходы элементов И подключены к выходам устройства. На Фиг. 1 представлена структур1g ная схема устройства; на Фиг. 2 — конструктивное построение блока умножения на Х по модулю неприводимого многочлена /Д ()(). Устройство состоит из двух блоков 1 и 2 умножения на X по модули неприводимого многочленаМ(Х), генератора 3 импульсов, деиифратора 4, элементов И 54, 5,..., 5„„. Каждый из блоков умножения содержит и элементов 2О ИЛИ, 6,,..., 6„,, и, элементов 7 (Э 7,..., 7„ памяти и Ф. сумматоров 84, 8,,..., 8, причем выход элемента 7„ памяти подключен к одному из входов элемента ИЛИ 6„+5, если коэф>5 Фициент при у< в многочлене )Ь(Х) равен нулю непосредственно, или через один из сумматоров 8,. 8,..., 8, если коэффициент при )с в многочлене Щ (Х)отличен от нуля; выход элемента 7 памяти подключен па Ь . раллельно йа вторые входы сумматоров 84, 8,..., 8 < и на вход элемента ИЛИ 6„, причем выходы элементов ИЛИ 64, 62,..., 6„„ подключены ко 35 входам соответствующих элементов 7,, 7>, ° ... 7„„ памяти, входами бло- ков 1 и 2,являются вторые входы элементов ИЛЙ 6, 6,..., 6, а их выл ходами - выходы элементов 7, 7,..., 7> памяти, к управляющим входам ко" торых подключен выход генератора 3 импульсов, Ж выходов блока 1 подключены к соответствующим входам дешифратора 4 комбинации "10...000", 45 выход которого подключен к первым входам элементов И 5„,, 5 вторые входы которых подключены к выходам блока 2, при этом первой группой входов устройства являются входы блока 1, а второй группой вхо50 дов — входы блока 2, выходами устройства являются выходы элементов И 51, 5<, ° ° ° 5 Устройство работает следующим образом. В исходном состоянии элементы 74, 72,..., 7 „ памяти блоков 1 и 2 обнулены. С первым шагом работы в блок 1 помещаются коэффициенты поли9895 нома-делителя, а в блок 2 - коэффициенты полинома-делимого, причем коэф. фициенты при старших степенях Х полиномов помещаются в правые элементы 7 памяти блоков 1 и 2. После этого з начинается сдвиг информации в блоках 1 и 2 йод воздействием управляющих импульсов генератора 3 вправо, т.е. осуществляется умножение на пв модулю неприводимого многочлена 16 fA(x) полиномов, находящихся в блоках 1 и 2. Процесс сдвига повторяется до тех пор, пока в блоке 1 будет сформирована комбинация: "10...000". К этому времени в блоке 2 будет сформиро- 1% вано частное от деления многочленов ,по модулю неприводимого многочлена, ф(1 ). Дешифратор 4, обнаружив наличие комбинации "10...000" в блоке 1, сигналом с выхода открывает элементы 26 И 5, 5, ., .,и результат деления из блока 2 выдается на выход устройства, после чего элементы 71, 7,..., 7„ памяти блоков l и 2 обнуу ° ° ° Ь у ляются и устройство готово к вымол" 2$ нению деления следующих полиномов. Предлагаемое устройство имеет простую логику работы и .существенно проще известных, при этом общее коли4ество элементов в устройстве сокра- ЗЕ щается более чем в три раза. Формула изобретения ЗЗ Устройство для деления полиномов над конечными полямиЯ {2 Я) по модулю неприводимого многочлена, -содержащее р элементов И, генератор импульсов, первый блок умножения на Х по модулю 4© неприводимого многачлена М(Х) степени hf, который состоит из 1и элементов ИЛИ, t6 элементов памяти и k сумматоров по модулю два (гдеg=lg М(Х).1-1, QQA(g)) - вес многочлена ф(Ъ)); при этом выход » --го -элемента памяти подключен к одному из входов (» +1)-ro элемента ИЛИ непосредственно, если 59 d коэффициент при )(» a многочлене ф(Х) равен нулю, или через. один из сумматоров по модулю. два, если коэффициент. при }t,» в многочиене М(Х) отличен от нуля { = l.....óé-1), выход уА-го элемента памяти подключен ко вторым входам сумматоров по модулю два и к первому входу первого элемента ИЛИ, выход А -го элемента ИЛИ подключен к входу соответствующего j-го элемента памяти () = 1,...,й»), входы блока умножения на X. no модулю неприводимого многочлена М(Х) соединены со вторыми входами элементов ИЛИ соответственно, выходы элементов памяти соединены с выходами первого. блока умножения íà )t по модулю неприводимого многочлена М(Х), о тл и ч а ю щ е е с я тем, что, с целью упрощения устройства, введен второй блок умножения íà 3 по модулю неприводимого многочлена M (}I> и дешифратор, входы которого подключены к выходам первого блока умножения на К по модулю неприводимого многочлена М(Х), входы которого подключе", ны к первой группе входов устройства, выход дешифратора подключен к первым входам элементов И, вторые входы которых подключены к выходам второго блока умножения .на Х по модулю неприводимого многочлена Я(Х), входы которого подключены ко второй группе входов устройства, выходы элементов И подключены к выходам устройства. Источники информации, принятые во внимание при экспертизе 1. Иак-Вильямс Ф.Дж. и др. Теория кодов, исправляющих ошибки. И., "Связь!, 1979, с. 98, рис. 3,6. 2. Th . С. Bartee et аl.Computat1оп with Finite Fields. "Jnform. and Control", 1963, Н 6, р. 85-87, fig. 3, 4. 3. Блох Э.Л. и др.,Обобщенные каскадные коды. И., "Связь", 1976, с. 103 (прототип). 989559 Тиран< 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Заказ 11131/68 Филиал ППП "Патент", r. Унгород, ул. Проектная, 4 Составитель В. Березкин Редактор M. Петрова ТехредТ.Фанта КорректорГ. Огар
