Устройство для деления полиномов над конечными полями gf(2 ) по модулю неприводимого многочлена
Похожие патенты | МПК / Метки | Текст | Заявка | Код ссылки
Текст
) Заявлено 02. 06, 81 (21) 3295579/18-24 15/31 с присоединением заявки Рй(23) Приоритет 28. 07. 80 кем ктет СССРЕлем кзабретекк и етхрытий публиковано 15. 01.83. Бвллетень РВ 2 53) УДК 681. .3(088,8) 8 01 83 ата опубликования опнса 1ьев Широков и В.А. В изобретения аявнтель СТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ПОЛИНОМОВАД КОНЕЧНЫМИ ПОЛЯМИ 6 Е(2 ")О МОДУЛЮ НЕПРИВОДИМОГО МНОГОЧЛЕНА 1ие относифровымам и можетпостроениидвоичных ц Изобр зированн устройст вано при устройсттен м ц ится к специ вычислительн быть использ декодирующих иклических к ли. хождения рой подклОднако очень сло гарифмиро ния. а, выход котоу устройства 11.йство являетсяаличия схем лологарифмировантилогариф чен к выхо такое устр ным из"за ания и ант в,5 ниягоельно При декодировании циклических кодов, используемых для исправления ошибок, необходимо выполнять операцию деления произвольнЫх элементов поля(2 ), которые обычно представляются полиномами от Х степени не более тттс коэффициентами из поля 5 Г(2). Причем деление полиномов осуществляется по модулю неприводимого многочлена М(Х), образующего поля Я(2 ).Известно устройство для деле полиномов по модулю неприводимо многочлена, состоящее из паралл включенных к входу двух схем логарифмирования, выходы которых соединены с входом разностной схемы, выход которой подключен к входу схемы на-. Известно также уления полиномов надным полем, состоящетельно включенных бобратного многочлен олем и схемы умноженмодулю неприводимого многочлена М(Х) 1,23Наиболее близким к предлагаемомуявляется устройство для деления поли" номов над конечными полями 6 Р(2 тн) по модулю неприводимого многочлена, состоящее из блока вычисления обратного многочлена по модулю неприводимо" го многочлена М(Х), вход которого подключен к первой группе входов устройства, регистра сдвига, вход которого подключен ко второй группе вхо"3 989 дов устройства, блока умножения на Х по модулю неприводимого многочлена фХ), щ входов которого подключены к соответствующим В выходам блока вычисления обратного многочлена, гене. ратора импульсов, выход которого параллельно подключен к управляющим цепям блока вычисления обратного многочлена, регистра сдвига, блока умно. жения на Х по модулю неприводимого многочлена (Ф (К ) и накопителя на Щ элементов поля Я(2),е входов которого подключены к соответствующим выходам 1 элементов И, первые входы которых подключены к выходу регистра сдвига, а вторые - к О выходам блока умножения на Х по модулю неприводимого многочлена3 1.Недостатком этого устройства является его сложность.Цель изобретения - упрощение уст-, ройства.Поставленная цель достигается тем, что в устройство, содержащее Ю элементов И, генератор импульсов, первый блок умножения на М по модулю не- приводимого многочлена М (Х ) степени Щ, который состоит из О элементов ИЛИ И 1 элементов памяти и 1 сумматоров по модулю два (где К: Ю М(ХЦ,ЮМ(Х)3 - вес многочлена ф(Х, при этом выход 4 -го элемента памяти подключен к одному из входов (1+1)-го элемента ИЛИ непосредственно, если коэффициент при У в многочлене МЬ) равен нулю, или через один из сумматоров по модулю два, если коэффициент при )( в многочлене 9(Х) отличен от нуля ( 1 = =1Ит 1), выход и-го элемента памяти подключен ко вторым входам сум- маторов по модулю два и к первому входу первого элемента ИЛИ, выход -го элемента ИЛИ подключен к входу соответствующего 4 -го элемента памяти ( = 1,рИ), входы блока умножения на Х по модулю неприводимого много- членами (Ь ) соединены со вторыми входами элементов ИЛИ соответственно, выходы элементов памяти соединень 1 с выходами первого блока умножения на )( по модулю неприводимого много- члена М(1, введен второй блок. Умножения на Х по модулю неприводимого многочлена М) и дешифратор, входы которого подключены к выходам первого блока умножения на Х по модулю неприводимого многочлена Яф), входы которого подключены к первой группе входов устройства, вцход дешифратора подключен к первым входам элементовИ, вторые входы которых подключенык выходам второго блока умножения на;Х по модулю неприводимого многочленафф), входы которого подключены ковторой группе входов устройства, вы-.ходы элементов И подключены к выходам устройства.На Фиг. 1 представлена структур 1 О ная схема устройства; на Фиг, 2 конструктивное построение блока умножения на Х по модулю неприводимогомногочлена /Ь ,Устройство состоит из двух блоков1 и 2 умножения на Х по модули неприводимого многочленаМ(Х), генератора3 импульсов, деаифратора 4, элементов И 545 , 5 Каждый из блоков умножения содержит в элементовИЛИ , 6.б ,д элементов 7г 1 17 , 7 памяти и Ф. сумматоров84, 8., 81 причем выход элемента 7 памяти подключен к одному извходов элемента ИЛИ б+5, если коэф 25 фициент при у в многочлене М(Х)равен нулю непосредственно, или через один из сумматоров 84,. 88 , если коэФфициент при Х 1 в многочлене Я отличен от нуля; выходэлемента 7 памяти подключен паЬ .раллельно йа вторые входы сумматоров84, 8 .8и на вход элементаИЛИ 6, причем выходы элементовИЛИ 64, 62 6 подключены ко35входам соответствующих элементов7,1 7 . 7, памяти, входами бло. ков 1 и 2,являются вторые входы элементов ИЛЙ б , 6 6 , а их выифходами - выходы элементов 7, 77, памяти, к управляющим входам которых подключен выход генератора 3импульсов, Ж выходов блока 1 подключены к соответствующим входам дешифратора 4 комбинации "10000",45выход которого подключен к первымвходам элементов И 5, 52."Ьрвторые входы которых подключены квыходам блока 2, при этом первойгруппой входов устройства являютсявходы блока 1, а второй группой вхо 50дов - входы блока 2, выходами устройства являются выходы элементовУстройство работает следующим образом.В исходном состоянии элементы74, 2 и памяти блоков 1 и 2обнулены, С первым шагом работы вблок 1 помещаются коэффициенты поли5 .: .,. 9895нома-делителя, а в блок 2 - коэФФициенты полинома-делимого, причем коэфФициенты при старших степенях Х полиномов помещаются в правые элементы7 памяти блоков 1 и 2. После этого значинается сдвиг информации в блоках 1 и 2 йод воздействием управляющих импульсов генератора 3 вправо,т,е. осуществляется умножение напв модулю неприводимого многочлена 16Щх) полиномов, находящихся в блоках1 и 2. Процесс сдвига повторяется дотех пор, пока вблоке 1 будет сформирована комбинация: "10000". К это"му времени в блоке 2 будет сформиро%вано частное от деления многочленов,по модулю неприводимого многочленаК. Дешифратор 4, обнаружив наличие комбинации "10000" в блоке 1,сигналом с выхода открывает элементы 26И 5,1 5 , 5 и результат деленияиз блока 2 выдается на выход устройства, после чего элементы 71,7 памяти блоков 1 и 2 обнууф уГляется и устройство готово к вымол" 2нению деления следуоцих полиномов.Предлагаемое устройство имеетпростую логику работы и .существеннопроще известных, при этом общее количество элементов в устройстве сокра- ЗЕщается более чем в три раза,Формула изобретенияЗЗУстройство для деления полиномов над конечными полямиЯ(2) по модулю неприводимого многочлена, -содержащее р элементов И, генератор импульсов, первый блок умножения на Х по модулю 4 неприводимого многачлена М(Х) степени 1 И; который состоит из Ь элементов ИЛИ, В элементов памяти и М сумматоров по модуле два (гдето(:ЮГМ(Х)3 1 уЩ(Х) - вес многочлена ф(Ъ; при этом выход-го элемента памяти подключен к одному из входов ( +1)-го элемента ИЛИ непосредственно, если 59 6коэффициент при ( в многочлене /Й(Х равен нулю, или через один из сумматоров по модулю два, если коэффициент. при ) в многочдене М(Х) отличен от нуля ( 4 = 118-1), выход рй-го элемента памяти подключен ко вторым входам сумматоров по модулю два и к первому входу первого эле. мента ИЛИ, выход-го элемента ИЛИ подключен к входу соответствующего ,-го элемента памяти= 1и), входы блока умножения на Х по модулю неприводимого многочлена М(Х) соединены со вторыми входами элементов ИЛИ соответственно, выходы элементов памяти соединены с выходами первого, блока умножения на 1 по модулю не- приводимого многочлена 9(Х), о тл и ч а ю щ е е с я тем, что, с целью упрощения устройства, введен второй блок умножения на Х по модулю неприводимого многочлена Яи дешифратор, входы которого подключены к выходам первого блока умножения на К по модулю неприводимого много- члена М(Х), входы которого подключе", ны к первой группе входов устройства, выход дешифратора подключен к первым входам элементов И, вторые входы которых подключены к выходам второго блока умножения на Х по модулю неприводимого многочлена Щ , входы которого подключены ко второй группе входов устройства, выходы элементов И подключены к выходам устройства. Источники информации,принятые во внимание при экспертизе1. Иак-Вильямс Ф.Дж. и др. Теориякодов, исправляющих ошибки. И.,
СмотретьЗаявка
3295579, 02.06.1981
ВОЕННАЯ ОРДЕНА ЛЕНИНА КРАСНОЗНАМЕННАЯ АКАДЕМИЯ СВЯЗИ ИМ. С. М. БУДЕННОГО
ШИРОКОВ АЛЕВТИН ДМИТРИЕВИЧ, ВАСИЛЬЕВ ВИКТОР АФАНАСЬЕВИЧ
МПК / Метки
МПК: G06F 17/10, G06F 7/544
Метки: деления, конечными, многочлена, модулю, неприводимого, полиномов, полями
Опубликовано: 15.01.1983
Код ссылки
<a href="https://patents.su/4-989559-ustrojjstvo-dlya-deleniya-polinomov-nad-konechnymi-polyami-gf2-po-modulyu-neprivodimogo-mnogochlena.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для деления полиномов над конечными полями gf(2 ) по модулю неприводимого многочлена</a>
Предыдущий патент: Устройство для контроля двоичного кода на четность
Следующий патент: Коммутационная система обработки многоканальной статистической информации
Случайный патент: Стенд для ускоренных имитационных испытаний сельскохозяйственных валкоуборочных машин