Устройство для арифметической обработки элементов конечного поля

 

Изобретение относится к вычислительной технике и может быть использовано в устройствах и кодирования и декодирования корректирующих кодов в виде БИС для цифровых проигрывателей. С целью повышения быстродействия устройство для арифметической обработки элементов конечного поля, содержащее блок 1 вычисления обратного элемента, блок 2 суммирования, блок 3 умножения, мультиплексор 4, имеет новые организацию связей и структуру блока умножения, содержащего узел умножения двух многочленов и узел вычисления остатка от деления на порождающий многочлен поля. В блоке 3 умножения реализован более быстрый двухшаговый алгоритм умножения элементов конечного поля. 1 з.п. ф-лы, 3 ил.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (5 ) 4 G 06 F 7/49

ОПИСАЧ»ИЕ ИЗОБРЕТЕНИЯ

И АВТСРСМОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

flG ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

»РИ Г14НТ СССР (21) 432 425/24-24 (22) 10.! 1.87 (46) 15. 2.89. Бюл.,¹ 46 (7, ) Специальное ко» структорско-техно 10» ическое бюро микроэ IpKTpoники (72) Н. Ф. Садыков, М. IO. Балабаев и А. H. Савченко (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 1383338. кл. С» 06 Е 7/49, 1986.

Патент FHB ¹ О! 52702, кл. Н 03 М 13 00, опублик. 1985.

Авторское c âèäåòåëüñòâî СССР

¹ 1363 I 86, »,,i. С» 06 1- 7/38, 1986.

„„SU„„1529213 A 1

2 (54) УСТРОЙСТВО ДЛЯ АРИФМЕТИЧЕС—

КОЙ ОБРАБОТКИ ЭЛЕМЕНТОВ КОНЕ 1НОГО ПОЛЯ (57) Изобретение относится к вычислительной технике и может быть использовано в устройствах кодирования и декодирования корректирующих кодов в виде БИС для цифровых проигрывателей. С целью повышения быстродействия устройство д,»я арифметической обработки элементов конечного поля, содержащее блок 1 вычисления обратного элемента, блок 2 суммирования, блок 3 умножения, мультиплексор

4. имеет новые организацию связей и структуру блока умножения, содержа»цего узел умножения двух многочленов и узел вычисления остатка от деления на порождающий многочлен поля. В блоке 3 iì»»ожения реализован более быстрый двухшаговый алгоритм умножения элементов конечного поля. 1 з.п. ф-лы, 4 ил.

1 ">29213

Изобрете.ние 0THocHl cH K Bht)>HO«ff(T«. fьной технике и может быть использовано в устройствах кодирования и декодирования корректирующих кодов, выполненных, В частности, B виде больп(их интегральных схем, в цифровых звуковых проигр((ватсл5(х системы компакт-диск для обработки элементов поля GI (2 ).

Целью изобретения является (IOBk>iffi«!fit« б ыстроде йств и я уст ро йства.

Гтз фиг. 1 приведена схема устройс. Вз для арифметической обработки элечептоь конечного поля; на фиг. 2 — схема блоки умножения; на фиг. 3 и 4 — пример р(;!.1!!зации блока умножения для случая конечного ноля GF!(2 с порож)dto(EEH» многo членом q ix) =х +х+1.

Устройство (фиг. ) содержит б«(0(е вычисления обратного элемента, блок 2 «уммирования, блок 3 умножения, мультиплексор 4, первый и второй BxO I!>I ) и 6 задания режима устройства, Втîрой и (ервый 2О информационные входы 7 и (3, Выx»ä 9 уcòройства.

Б;!ок 3 )) множения (фиГ. 2) ) содержи Г». 3()«1

3.1 умножения днуx»ногOчленов и узел

3.2 вычисления остатки <>г ле letfHs(tie) no-!

)0iK,cIl0ll1l :If . 1! НОГОчлЕ ll 110!(Я

Б IQK ) x xl 1105KOHия ((())3 . 3) «0(«ржи (С П< РВОГО 110 ШЕСтпи 11(cllhiH ЭЛЕМЕН I Ь и 3.()f 3.16 и с первого I10;(PBHTt>IH эл« х((!«(1(ИСКЛ 10е)Л10(11ББ И, (И 3.17 3.26 л,(13 3.1»()lkt»æcния )Â) х»i 1(ot Оч тенОВ и с ЗГ) ,((< 5(ГО(0 по пятнадцатый элементы ИС,;, 110 (.З, 1011),Б Б И И 3.26 3.31 узл» 3.2

В >! l l l C, 1<. i l H 51 0 C T B T KB OT . ((. Х 1(. Н И Я П З П 0РОЖ (BI() if(i!if i)i I!OI OЧ.!Еl) ПОЛЯ.

Блок 1 Вычисления ооритного эле»щ(т ,:О. »f ii ()(.,)ста вляет собой (I БУ, их)(ющс« (I-рилря.,kt(t5t информационный В.,од, Вхо;1

j) еl л м (l l l c н и я и (! - р а 3 р я ли ы и B I >1 Ол. 1 1 f> H э Г, > . 1, ко(ди нз В.(од разрешс fliIH и< д ill «()», TO Выx0;(б,(окз 1 повторя(1 00«(.ояни<

Ii II (>0(>,(И ЦИОН НО М ВХО («1,0i i На !)X» ) РЕ!.3! «ill«HHH ПОЛЗН УРО(3« llh «(>), I !IИ ИнфОР( м и И ИОН if hl È (> ход 110,(c! Il э, I< . 1! I IT Б, I 0 lfci 13 i>lх0. ц формируется эл«;1(и Г Б =-1, Б, т.«

i)() f) c) 1111>(и,, IЕ»«1lT.

I>, f0 к 2> су:11 )l и p013B и и я (О,, >j) жит (! c м м иТO f)0!3 li 0 Х(0 13) .;)К) El B d, i I(PB hl(. k3XO ihl Ко ГОР I>l x 00 Р и:)х IОТ (1-Р аз Р 51, 1Hhl и ИСРе) hl Й Вхо, 1 блока 2, вторые-0-разрядный !>п OpOH Вход ();10KB 2, RpH BTO!» BhlXÎ fь) (!X >Xf)»c)TOp013 l .0 молу.ll0 образуют (1-разрядный Выход блока 2 т.о., что:31;aHekfHe выхода блока суммирования Вычисляется как подразрядпзя опе

pai!Hя ИСК.(1 ЮЧАЮ1ЦББ ИЛИ обоих входов.

Му;IhTHllë KcOp 4 имеет лва е)-разрядны информационных входа, управляющий Bxoл, и также cf-разрядный вы.(од. В зависимости от логического уровня сигнала Hil 55 управляющем входе мультиплексор 4 пер(,еает на выход устройства значения выхо"„, блока 2 суммирования B случае операции с.>ожеп НЯ ..Iибо В ыхо (3 О. 10кз 3) )м ножен и Я в .tg)f:3«01l(ðdi,èji х множения и деления.

Рзс мо(1)ихi (1(3бОт). )ci )Оис;Вз (фи;

П j)lt i31>li,0. t tlE ilH:4 .)li« .) cl l(HH » НО>КЕ НИ Я., )Е)ЛЕ -!

iH::. H «ЛОЖЕПИЯ НЗД .(«С)(ГГИ»>i KOH()H (0(0

ll0 1Н (>1 (2 ) л!53 itp0i! (3)х(ь(1 )(0 (li О/4 .и!<

I 1(Iр )! :I0г0 1 !(I fl 15

001) и () з тl>! ()и (")1 >>Iе 1! рi> i > <ол ь! I û« э. )е v(и <>!

1 и Б и 0.151 . (.)HK 110 I i)« .С ТЗ В""! В . Ii де

» li0I 0 i,л <. k!OB 5 ((х! и 3 (>. f 0! ..3. (>. ) === а, х, Е )

Ф -4 (3 (я) - - Ь,(се,,)=0

Ы) (i () И» 1! " и!3 if !Л И ; .. (I

»1<ч)т I(0« 5, K0 )(I><)>H f3HC tf i hl a H c!, . В<)!<Ч НЫЕ i «.)З «(>)

;i IИ «1)

КО ->i(>ф и(1ис i ы а (/ — Р;);3РЯ ) if!>i(> l ) 0;Е )(> !I (0("1 1>(! ((1<е)1 и „

Коэффицие((гы ()«з) ль,! Ге! Вы.::;.(и 1!Ия i . И>с;)clitl .) «(e! =-"< >х, .к..:(р),;«Т;3(3.»НО(И

>)=о )

C0(iOH;EBOif )I f) hf(! H<,;)! <<1,i» >f, I H << 1 >) . (Ч)» :-!Взк)тс53 с (> -PdзРH Eflоl О !)ы,<> 51, . Hи,!

11 ((С Т В Г l Я <. >) f 01 и 1> И ((> f) I C Т! l I «. к (> Й > ". p:- i ) f и 11 c I . I, В . Од н Ы» . 1 э, 1 Ы Е I f 1 k i <, i (X i > (. (5. (i!c 1 0 Яниe» ifxîë013:) и 6.

>> (! . («Р а (I И 51 ) ") () () Ж,: 1 И Я

1, ici B X0 ki>i (> П (> 10 i а(Т<5i . РО)"!< h (>

Быхо k блоки: 1)ы (исл«(ия об,".з-по; ).(смептз .(013торяе" сое" 05!НЕ!" 3«0 (B;= 3 fx0;i )1 <..rt f> I ff ll. l«K(1) и Еl 4 .11;>)> ГO f>5)(Т 11(),,< Ь: -! )ci

В!>!),Р;((б.l0>.cl . ), ()" );И(. ГВ.IЯКЯ."1.1 0 ОП(-.(,иilИК)»le)I!0iKe ifk(Я () "Одl!!)Iх >л(1«I!TOB )3 ч)) и Кцif51 i !OKB 3 1»!. :!, "!f > 5l «<,Е"10> : (, f3ь)1fl)(.i HI)il !Iр()из()е (< .IH (. I, (13, ;, и >

Хl О, (),. ПО I!(>POiK, I B V) i (i(I 0 "11! 0« ) i. i(I: З !10«I

<((1; ) Б 1, 3 1 <, 3, 1 i (4; H . . 2 (!> "„ : )«" . 5 1 t i 5:1

1 Р 51 )I 0 1 (> 0 f l 3 (3 (., (C I l H (, (1 !3 Е Л Л 1., 5 .. Г ; ) ) l 3

k3 0, I H I (5l 13 Ь! ) И С, I C i!i . Е :> « I c! I " И 1> 1 1(« 1 <«: .! Н "

If<)1>Ñ>,+;;;d Ю! Цнй»! (0(0

11 1) Я 310« !I ()0 пл В1«, 11. I! i! (I сх, —:.: ). I K

2(9-1> г>) (( х)3 (00) =,," и,.0,)я =-" Sеч,1(«,!«В:"«

>3=0 х;:,) й=0

«0()01й »но!011)ен с(« ic !!и 2 1(-11

К(>эффицИСНТЫ > 1->=..a,О,. c>- — >,—

«з >

IlP«, Сlcll)Л.!К>Г «0()OH . УХ!)(У (:(;<.И <В«,1 и;313

1 ЗКИХ )4, H t), -iT(> (-1 — (<, ci i! ))(f1 i

Fc==- a„b., г =-a lb„— а,b

1 - V > ач !>>« -- +а>-а )1 — . -(«)=-а. — b„.

Выход узла 3.1 прелстивляет собой выход

f)c)3P5f k!f0CThK) 2(j — 1 ()g -1, К)К XK()3cllf0 НЗ фиг. 2), по котором; 2<(1 коэффициентов

F(,. представляю(цих собой двои:ные числа

«О» либо «I», поlBK)T«51 на узел 3.2. 11роff.if3«.((ния е),.(>,. в уллс . 5.1 резлизук>тся при

i l ) 310 ll! il >. (С,)е 1«0!3 И, c". Xf 3()3 f) 013 c! I I H (Ii, )ОИЗВЕД(.fiHЙ ПО МОЛ) .! Ю ДВЗ О« 1 Ill«1."Г!3Л Я

15292

5 ется при помощи элементов ИСКЛЮЧАЮ1ЦЕЕ ИЛИ.

Окончательный результат операции умножения появляется на выходе узла 3.2, в котором вычисляется результат деления прямого произведения F (а) на порождающий многочлен поля. Эта операция необходима для того, чтобы результат операции также представлял собой элемент конечного поля равномерности q.

Для пояснечия работы узла 3.2 пред- 10 ставим прямое произведение на его входе в следующем виде:

У-1 к

Г(а)= F2o. =FI(z) -1- 2!c2), Я-1 где Fl (а) = F.а: ко

e!s-21

F(а) > р «

««

Извест Io, что элементы а" для g)q.) можно представить в виде многочленов сте- 20 пени не более q-1 а"= с4,а где коэффициенты d<, являются двоичными числами «0» или «1», Эти коэффициенты можно считать известными и постоянными для каждого конкретного порождающего многочлена q(x). Подставив это выражение в формулу для Рг(а) имеем:

o -! 2 Я-1г, с (а) =г (а) modq (х) = (F,+> FI d2,а =

i=O «=o е а 2!q- ) 35 где с,=F,+ Fi,d>, есть коэффициенты произведения с.

Операция де Ice!IB.

11а вход 6 подается уровень « I », на в..о .

5 уровень «О». На выходе блока появляется значение В элемента обратного элементу В, поданному на вход 7. Таким образом, операция деления осу1цествляется умножением на обратный элемент. C=A/В=

=Л В

Операция сложения.

g-1 2(s1) 2 (а) =, . (Fkdk« .

20 «=«

F TBK c»pe.IcTBBляются в виде многочлена степени не более чем q-1. Окончательно имеем

13

На вход 5 подаеiñÿ уровень «1», выход мультиплексора 4 повторяет состояние выхода блока 2 суммирования, на BxogII которого с входов 7 и 8 7î аются элемcHты поля В и А. Сумма находится следующим образом.

А-B=x (а,—, -К) а = — C:è где сумма с,=а,--1-6, реализуется поразрядным суммированием по модулю два входных значений.

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

1. Устройство для а рифмстическои обработки элементс в конечного Iloля, содержащес блок вычислсн1.я обратн01.0 э,10мента, блок суммирования, блок умножения и мультиплексор, причем первый информационный вход устрой òâà со,единен с входом первого слагаемого блока суммирования и с входом первого сомножителя блока умножения, выxO,Tû бл0ка суммирования и блока умножения соединены сооТВсТственно с перBым и вторым инф0px!àöèонными входами мультипlcксора, выход которого является выходoxl устройства, первый и второй входы задания режима которого соединены соответственно с управляющим входом мультиплексора и с входом разрешения блока вычнс,1ения обратного элемента, второй информационный вхоl устройства соединен с входом второго слагаемого блока суммирования, отличaюи(eecя тем. что, с целью повышения быстродействия, второй информационный вход устройства соединен с информационным входом блока вычисления обратного элемента, выход которого соединен с входом второго сомножителя блока умножения.

2. Устройство по п. 1, oтличQ!oè(cåc!I тем, что блок умножения содержит узел умножения двух многочленов и узел вычисления остатка от деления на порождающий многочлен поля, причем входы первого и второго сомножителей блока ум1 ожения соединены с cooTBåòcòâx ющнми в одB÷è xзла умножения двуx многоч.1енов, выход которого соединен c вхо 10»1 блока Blil IIIcления остатка от деления на порождаю ций многочлен поля, выход коrop010 является выходом блока умножения.

15292 !) 3 г ) 1 г

4Ч

31, 5

r7

< i

Ф«г 5

< ) — -) < ! 7,"

< (ос. !If lèlñ, H (!С "f()(и

Г(:крс р И 11е; <. <<оррск гор <.) !Сравп<,f

Ги;)а<к Г)6)< 1.опHH< HО

Заказ 7612, 14

Б11ИИ!1И Гос) (арственного ко))итет;) .:<) и<нор«(ннн .:: » êð«тнH; п,»l )<,!! ! ((.!) I !3035, Москва, 2!<, 35, Рг1, с)аи н<)б,;I 4 5!

1ронзво <ственно-изобате IbcKHA кочоинат «!1!:< н< . I, к<ор(п, <(а Гага)и .;:, 1().