Устройство для вычисления корнеймодулярных алгебраических уравне-ний над конечными полями

Устройство для вычисления корнеймодулярных алгебраических уравне-ний над конечными полями

Иллюстрации

Показать все

Реферат

 

Q П И С А Н И Е (п)811273

ИЗОБРЕТЕН И Я

СОюз ьсеетснйх

Сеииалистичесних

Ресл лин

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 21.02.79 (21) 2727022/18-24 с присоединением заявки ¹ (23) Приоритет (43) Опубликовано 07.03.81. Бюллетень ¹ 9 (45) Дата опубликования описания 07.03.81 (51) М. Кл.а

G 06F 15/32

ГОсур. Зр,теса . и ксм ите

СССР по дела.л иззбретеиий и Отнрытий (53) УДК 681.3 (088.8) (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОРНЕЙ

МОДУЛЯРНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

НАД КОНЕЧНЫМИ ПОЛЯМИ а a "а а а2 " — т з ° . Е (2) Изобретение предназначено для использования в различных радиотехнических системах передачи информации с целью обнаружения и исправления ошибок при декодировании циклических кодов. Необходимость вычисления корней алгебраических модулярных уравнений возникает при декодировании циклических кодов. Данное устройство является одной из составных частей декодоров циклических кодов. Кроме этого, задача вычисления корней модулярных алгебраических уравнений над конечными полями возникает при анализе элементов вычислительных устройств.

Известно устройство, содержащее регистры, генератор и сумматоры (1). Недостатком устройства является конструктивная сл ож н ость.

Наиболее близким к изобретению по технической сущности является устройство, содержащее параллельный регистр, регистры сдвига с логическими обратным связями, генератор тактовых импульсов и сумматоры по модулю два (2). Причем выходы всех регистров поразрядно подключены к соответствующим сумматорам по модулю два. Сущность работы устройства заключается в последовательном переборе элементов коне иного поля GF(2m). и отыскания таких а ", которые являются корнем алгебраического уравнения

i) т

P(Z) =,,2, GF (2 "), (1)

f=o где о; — коэффициенты из поля GF(2 ").

Элементы поля Q, Q, Q, ..., Qf ...,Q ""

10 образуются минимальным примитивным неприводимым многочленом

Q(2) = а,2,mod 2, f =О

15 где а; — коэффициенты из поля GF.

Для осуществления полного перебора элементов поля необходимо иметь l регистров сдвига с логнческими обратными связямп. отличающимися друг от друга нерегуляр ой структурой регистров, что является крупным недостатком известного устройства.

Целью изобретсния является упрощение устройства.

Достигается это тем, что устройство, содержащее генератор тактовых импульсов, параллельный регистр, m выходов которого подключены к первым входам соответствующих суматоров Ilo модулю два, а вход

l0

1О

>!dPdë,!с lbilol u Рсгпс >1)2 5IБ, !5!стсн ипфОР31!1цпоппым входи! устропс!Ба, содержит счетчик, L генераторов 11>l-последо«>ic, . ucii. .!еь спт li, элсмспт р!.!!! — i!13, пр .См ncpJ3blli ВЫХОД ГellcpBTopa Тс!КГОБЫХ 1131>>у.!ЬСОБ сосд шсп с первые!и Входами поры<ого гспср2Т0р2 2!1-послсдоиатслност51, счетч.,ка и элсмспга l 1, выход которого соед! поп с, Б10рым «ходом счетчика, первы.i ыыход «оторо>-о сосдiiilcli с входом генератора тактoиых импульсов, а второп Выход 51Б. гнете» !

>п!рормацпош>ы31 Б!!ходом устропс1иа, вы;>0J bI ГЩ! P2TOP 2 Та!,ТОБЬ1:»>Li !У ЛЬСОБ С !31 Орого llo L-и соединены с первыми ьходами

1 11C13d! О 301 с>1-ПОС. 1СДOI32TC.J»rluCTil С ВТОРОго i.o L-и соотиетстиспно, вторые в соды которых. 5ш.»iiuЗся cuuтветствующими ин-!

РОР ЯЦИОппыхlп J3. 0 23!è У ст130пст!32, Г13У ипа вы; одои каэкдого гсператора 1!1-ПоследоБЯТСЛЬПО Tli COC IiiIICП2 С СООТ13СТСТБУIОЩИМИ

Б..0, 23!!! сумма!opuB по х!оду.i о диа, Выходы которых подк !ю !е ы к соотис J с .B1:10 öпм

l3 ОД23! элем !i la !1>111 — 11> > Выход коlо ро о 1.Одклю !еп к Бгорому и:.ОД1 э,!»eii12 !.

i id ЧертСжС П1ЭСдСТс1!3;>Сна бЛОК-СХСМсl pСТ1303>стБс1.,5 стpÎlicTJ30 содс1зжп1 Гcllcpdт01э так-о ых хшульсои 1, L гсператорои П1-il0слс оыатс.!ьпостpii 2, !!! сумматороы пo моду.ii0 диа 6, эл 3icil ill! I — 11ь. -1, элемент

i!, с Jc!чпк !3) lldpa.l.!Блины» рсгпс!p > .

i Оператор i IJ.>iåcT L ыыходol3, причем на пс1,ььш J.ciicpa !up ill->!осг!сдоиатель1!Ости 2

liuc у!,ают одш!Очные Мпу.1ьсы сдыига, яв. 5!10>ЦПЕС51 ЗЯДЯ!ОЩПЗIИ с1К ЯХIИ PavOTbi ВССго эстройстыа, па BTupoii генератор М-поc;lc,1ubBTc. 1bllocти 2 посту»aer серия 5!ь1пульсов сдьгil а, состо5!щая из двух импуль0013 и т. д...,, на L-Fi генератор л1-послсдо13с1тес1ы10с1и постУliacT се!3 IЯ ПЗ!ПУльсОВ

Сдип! 2, OC 051111,251 «la L образом, псрВыи l cllepdTÎp 2 ОсущестВл51ст

i;epcuop э. емептоы u, u.-, u*, ..., u, u. " —, Второй гепратор 2 осущсствггяет переоир элсмс1ггов и, и", u ", ...> и", сс--" -- и т. д. L-и генератор 2 осущестылясТ псрсоор элементов и, и, ...,и, и"2" 1. I,оэффицпепты мпогu I;ic 12 (1)

u;, i — = 1, 2, ..., L записываются в соответстБу!Ощпс генераторы 2, а свооодпый член

OQ зспшсывается Б Параллельный регистр 7. . атем генератор l Выдаст сершо импульсов псрвог0 такта, и соответственно, 110 окоп !аш и ccpllli импульсов сдвига в генератора .1>1-Последовательности будут записаны следуloliliic элементы поля о!и, 02а2, ..., i5Lu . Записанные элс3!Снты поля поразРЯДНО СК. 12ДЫисllОТСЯ ПО МОДУЛ!О ДВЯ Б СУ" ЪIматорах 3. Далее пз генератора 1 поступаСГ сср!»! Импульсов второго такта и в соотьстствующих генераторах .!1-последовательности будут записаны элементы поля

4 .С >> г!

IIa j-м такте j-я серия импульсов посту20

2,>

>О од

ЧО

43

ЙО

dd

03 .;T Б I спс132 1013ы .., после Iсl 0 и пих Оудут

Зс. ПИСс!НЫ IIIC"12 01u 02и > 03и"3» ... О!и3 >

O>u.. li, П,!Ко>;СЦ, 1; Пос.ie 1,1.031 ТЯКТЕ, !Эаином и = — " — — i, ы . 0> ераторах 2 вуду r aaiiiiсапы элементы,>1 . Y

-г > -з* » " 1>. >!.сли ио время псрсоора на какоbi-либо

J-l>I ТсlКТЕ БО БССХ СГЗIМЯ>Ора? 110 310ду,по дыа оудут пул31, то этО озпача T пали iiie корпя ь1!!Огочлспа (i j. (. и! Нал о наличии кор!Гя через элемент Р!.Iil — 1-1тс 4 и элемент

3 поступит па счетчик !э, с Выход2 кОтОрого снимается помер такта, lid котором иы1ислен корень Л=-сц. 1 àêèì ооразом, Ilo

Окончании переОора Оудэ т изВсстны Все корней миoro-!лcliа (l),б г, >,бг . О"- ..., Zt 2гс.

Злеме т р1,3!! — 1-11 i служит для выдачи ипформаци51 о Jla;IFi>>iiil корня, а элемент

1! 0 выдает эту !шформацп о !0.1ько в моме!г! ы поступ lellli51 тактовых пмпульсоы и тем самых! предо BpaiFFaei иозможiibie сбои.

> IЕ1 3ИК КРОЪ!С СЧЕТ2 ЯКТОВ II ВЫДЯЧii Ноi>IЕрои тактов, являющихся показатс.!5!х!п степени корней JLJ, l2> ..., ILL> подасl команду па останов relleparupa 1 !о окончании перебора на такте, p213110:а .1 =2" — i. 1- а этом процедур 2 Бы и ел с II!151 к013 и ей хп!ОГО ч- 1 сна

3 с1 К 2! 1 Ji :J3 2 С 1 С я .

11ci!ользоиапис L î.<:!Накоиысх генераторов .!1-послсд01321с;lьпос1и иыГОдпо Отлич2ет aJlll0c устро >сгыо от прототипа, так как схема сга! овпгся pcl3 2151ðiiuli;10 структуре

li тсхпологи шее в изготоилеш!и. Ь результаi е стоимость па изГОтов.lerllie Оудет пиэке, >!el>i CrOIJ> IOCTb II2 ИЗГOTÎB IClihe УСТРОйСTBdпрототппа.

Формула изобретения

УcTPoiicTI30 Д 15! Вычпслсlпгн 013пеи модул!!рпых алгебраических уравнеш!й над копс шымп полями, содержащее генератор так! овых импульсов, пара.!э!С.1Ы1ый! регистр, П1 Выходов кот0130ГО подк;Iючспы к пе13Вы31 входам соотвстству!ощих сумматоров по модулю два, а вход параллельпого регистра яь 15ICTC51 ш!формационным входом устройства, о Tлпч ающесся тем, что, с цеуп1301цеп1!5! !>CTpuiic r«a, oiio co Tcp31iIIT счетчик, i генераторов Ь1-последовательности, элемент 11, элемент 11.>1!1> — 1-1Е, причем

I1cpBblil Быход Гспср2 ГО!3 2 тактовых из!ну льciJH соединен с перьымп входами первого генератора 1!1-после,1,0вательпости, счетчика и элемента И, вы.,од которого соединен с вторым B. 0.1031 с icrчпка, первьш выход которого соединен с ьходом генератора тактовых импульсов, а второй выход является >пlф013 >12циопllы;,1 БыходО>>! > cTpuiiстВЯ> выходы генератора тактовых импульсов с

2-го по i-й соединены с первыми входами генераторов Л1-»uciic,.FOBaòcdiüíoñòè с 2-го

»o i-й соответствепш3, вторые входы котоСоставитель Н. Палеева

Техред T. Трушкина

Корректор P. Беркович

Редактор Е. Гончар

Заказ 371/9 Изд. ¹ 186 Тираж 749 Подписное

НПО «Поиск» Государственного комитета СССР по делам и с.>рстсиий ll и рьгтии

113035, Москва, Ж-35, Раушская иаб., д. 4 5

Типография, пр. Сапунова, 9

pb1x являются соответствующими информационными входами устройства, группа выходов каждого генератора М-последовательности соединена с соответствующими входами сумматоров по модулю два, выходы которых подключены к соответствующим входам элемента ИЛИ вЂ” НЕ, выход которого подключен к второму входу элемента И.

Источники информации, принятые во внимание нри экспертизе

1. Фарадхкев Р. Г. Линейные последовательностные машины, «Советское радио».—

5 М., 1974.

2. Берлекэмп Э. Алгебраическая теория кодирования. — М., «Мир», 1971, с. 153

1п рототип) .