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

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

Иллюстрации

Показать все

Реферат

 

ОПNCan@e

ИЗОБРЕТЕНИЯ «н824202

Союз Советскнк

Соцналистнческнк

Республик

/ ф

МЬ

Ф;..

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (б1) Дойолкительное к авт. свид-ву— (22) Заявлено 270779 (21) 2802836/18-24 (5 )М. КЛ.

С 06 F 7/49 с присоединением заявки йо— (23) Приоритет—

Государственный комитет

СССР

Ilo делам изобретений н открытий

Опубликовано 2 104.81.Бюллетень N9 15

Дата опубликования описания 23.04.81 (53) УДК 681.325.

° 5 (088.8 } (72) Авторы изобретения

Б.Ф. Харчистов и B.È. Финаев

Таганрогский радиотехнический институт им. В.Д. Калмыкова (71) Заявитель (54} УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В КОНЕЧНЫХ

ПОЛЯХ

Изобретение относится к построению кодирующих и декодирующих устройств корректирующих циклических кодов, предназначенных для передачи сообщений с высокой достоверностью в системах доставки и обработки дискретной информации.

Известно устройство для умножения полиномов, содержащее первый, второй и третий сумматоры по модулю два, элемент задержки, регистр, вход которого соединен со входом устройства и с первым входом второго сумматора, выход которого соединен со вторым входом второго сумматора и со входом элемента задержки, выход которого соединен с первым входом третьего сумматора, а выход - является выходом устройства для умножения полиномов j1).

Недостаток этого устройства сос-. тоит в том, что умножение возможно лишь на Фиксированный полином.

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

Недостаток этого устройства состоит в том, что умножение в конечных полях данным устройством производится только лишь на фиксированный полином.

Наиболее близким по технической сущности к предлагаемому является устройство умножения в конечных полях, содержащее ячейки первого, второго и третьего регистра, сумматоры по модулю два первой и второй группы, элементы И, элементы ИЛИ первой и второй групп, блоки умножения, при824202 чем первая группа выходов устройства соединена соответственно с первыми входами элементов ИЛИ первой группы, Выходы которых соединены соответст.венно с первыми входами соответствующих ячеек первого регистра, выходы ячеек нервого регистра, за исключением последней, соединены соответственйо со вторыми входами соответствующих элементов ИЛИ первой группы,. выход последней ячейки первого регистра соединен со вторым входом соответствующего элемента ИЛИ первой группы и с первыми входами элементов

И, выходы которых соединены с первыми входами сумматоров первой группы, выходы которых соединены со входами 15 ячеек третьего регистра соответственно, а вторые входы — с выходами ячеек третьего регистра и с выходами устройства соответственно, вторые входы элементов И, кроме последнего, сое-Щ динены с выходами ячеек второго регистра и с первыми входами вторых сумсумматоров соответственно, второй вход последнего элемента И соединен с выходом последней ячейки второго ре-25 гистра со входом первого элемента ИЛИ второй группы, и со входами блоков умножения, выходы которых соединены соответственно со вторыми входами соответствующих сумматоров второй группы, выходы которых соединены с первыми входами соответствующих элементов ИЛИ второй группы, вторые вхо ды которых соединены со входами уст ройства второй группы, а выходы — со входами ячеек второго регистра (3).

Недостатком является избыточность элементов устройства. Операцию умножению реализуют более простым методом, используя схему для одновременного умножения полиномов сомножителей и де-4Q ления на образующий полином поля. Избыточность элементов устройства снижает надежность в целом.

Цель изобретения — упрощение ycãройства. p$

Указанная цель достигается .тем, что в устройство для умножения в ко. нечных полях, содержащее первый, второй и третий регистры, блоки умножения и группу элементов И, причем пер.— ® вая группа входов устройства соеди. нена с разрядными входами первого регистра, выход последнего разряда которого соединен со входом его пер- . вого разряда и с первыми входами элементов И группы, выход последнего разряда второго регистра соединен со входами блоков умножения, каждый разряд второго регистра содержит сумматор по модулю два и трчггер, первый вход сумматора по модулю два каждого д) разряда второго регистра соединен с выходом соответствующего элемента И группы, второй вход сумматора по мо. дулю .два первого разряда второго регистра соединен с выходом его последнего разряда, а второй вход сумматора по модулю два j-ro разряда второго регистра ()=2, ..., а, где аразрядность регистра) соединен с выходом i-1-го блока умножения, вторая группа входов устройства соединена с входами разрядов третьего регистра, тактовый вход устройства соединен с тактовыми входами первого и второго регистров, выходы разрядов третьего регистра подключены ко вторым входам элементов И группы, выходы триггеров второго регистра, являющиеся выходами соответствующих разрядов второго регистра, подключены к группе выходов устройства, третий вход сумматора по модулю два каждого разряда второго регистра, начиная со второго, соединен с выходом триггера предыдущего разряда второго регистра.

На чертеже представлена функциональная схема устройства.

Устройство содержит регистры 1, 2 и 3, причем регистры 1 и 2 являются сдвиговыми, тактовый вход 4, блоки 5.(, ° ° °, 5цл умножения, элементы И 6„, ..., 6, входы 7(, ..., 7 и 8((° ° ° ó 8öр выходы 9Л ) ° ° °, 9ц .

Каждая -я ячейка регистра 1 содержит элемент ИЛИ 10 и триггер 11 (i-1, ...,а). Каждая i-я ячейка регистра 2 содержит сумматор 12 по модулю два и триггер 13, причем сумматор 12л по модулю два первой ячейки является двухвходовым, а сумматоры

12, ..., 12СЗ последующих ячеек трехвходовыми, образованных например, последовательным соединением двух двухвходовых сумматоров 14 и 15 по модулю два. Каждая 2-я ячейка регистра 3 содержит триггер 16 (где аразрядность регистров 1, 2 и 3).

Входы 7, ..., 7 устройства соединены соответственно с первыми входами элементов ИЛИ 10, ..., 10 регистра 1, выходы которых соединены соответственно со входами соответствующих триггеров 11, ..., 11 регистра 1, тактовые входы триггеров

11, ..., 11 регистра 1 соединены с тактовым входом 4 устройства и с тактовыми входами триггеров 13, 130 регистра 2, выход триггера 11. регистра 1 соединен со вторым входом элемента ИЛИ 10л, выход триггера 11 регистра 1 соединен со вторым входом элемента .ИЛИ 10 и с первыми входами элементов И бл, б „ вторые. входы которых соединены с выходами триггеров 16, ..., 16О регистра 3, входы которых соединены с входами

84, ..., 8О устройства умножения, выходы элементов б, ..., б,„ соединены со входами сумматоров 12л, 12С, по модулю два, выходы триггеров

13„, ..., 13О perHcTpa 2 соединены соответственно с выходами 9,..., 9 устройства умножения и со вторыми

824202

}}х,>ц;ми соответствующих сумматоров

1,, ..., 12 } регистра 2 соединен со входами блоков 51, ..., 5 },} умножения и со вторым входом сумматора 124 выход .оторого соединен со входом соответствующего триггера 13 регистра, выходы блоков 5}, ..., 5a, ум2

5 ножения соединены соответственно вторыми входами сумматоров 12х, ..., 12С} по модулю два, третьи входы которых соединены с выходами соответствующих триггеров 13, ..., 13 регист ра 2. а-1

При описании работы устройства рассматривают поле GF(2a), опреде ляемое многочленом F(x) степени, а коэффициентами из поля GF(2), т.e. . 15 (х)= + х+ ° -.+F ха

0 } О

F.6GF(a); }=o,...,a-g F =4 1

}" °

Каждый элеме нт F G (2" ) представляют в виде много .-лена над GF(2), степень которого меньше а, т. e. вместо элементов р,g,r 8 GF(2 ) рассматривают многочлены р(х), д(х) и z(x) .соответствующие этим элементам 4-зр(") а-з (") = (g х -с х +... ц . }р(х)+(ь- х" (Ь х х Ь х +- Ь„х Ь)F(x).

=g (I}) Р(Х) +b(i) F (W) I" (I() который появляется на выходах 9}}, 9}} устройства для умножения.

Таким образом сформирован результат умножения двух полиномов.

Эффективность предлагаемого устройства по отношению к известному on }- 1

Р(}х) = Я } .} х", p„6C F(2), } = O, -., =

1=O а-} („)= Х д Х"; g.gCF(g) )=0,. - " ", 1=0

„. х", }-1е,ор(И; i=о,...,а-4

1=О тогда умножение элементов GF (2 ),. т.е. рд=г выполняется по.правилам умножения, представляющих .эти элементы многочленов по модулю F(x), т.е. р(x) д(х)=г(x) mod F(x); r(х)=p(x) °

° g(x)+b(x) ° F(x), где b(x) — полином степени меньшей, чем а-1..

Поскольку Г е. GF(2), i=О, ..., а-1, то блок умножения 11, осуществляющий умножение на F j=1, ..., а-1, 3 реализуется наличием связи, если

F =1, либо отсутствием связи, если 45

F; =0.

Работает устройство умножения в конечных полях следующим образом.

В исходном состоянии ячейки регистров 1, 2 и 3 находятся в нуле- 5р вом состоянии.

На входы 7, ..., 7 устройства, подаются одновременно в порядке BQ3растания индексов коэффициенты многочлена д(), т.е. на вход 7 - коэфФициент go, на вход 7z, - коэффициент

g на вход 7а - коэффициент g

Причем д„.=1 соответствует единичйый потенциал на входе 71, à g.=0-нулевой потенциал на входе 7 . Аналогичным . образом на входы 84, ..., 8,„ устрой- ЬО стза подаются коэффициенты многочлена р(х) и запоминаются в регистре 3.

Затем на тактовый вход 4 поступают импульсы тактового генератора (на чертеже не показан). На первом .такте коэффициенты многочлена g(x) записываются в регистр 1. При этом на выхо" де триггера 11,„ регистра 1 появляется коэффициент да, KQTQPbIA поступает на первые входы элементов И б „,. бс}, на вторые входы которых пос" тупают коэффициенты полинома p(x) выходоВ регистра 3. В результате на входы триггеров 13А, ..., 13 } поступают через элементы И б -ба и сумматоры 12, ..., 12 коэффицйенты полинома g p(x), На втором такте полином g p(x) .

a-< записывается в триггеры 13.}, ..., 13а} регистра, а на входы сумматоров 12}, 12а по модулю два поступают ко:эффициенты полинома go< р (x) . В результате на выходах сумматоров,14 появляются коэффициенты полинома р хр(х) @ g р(х) =(ц хц „) рЬ) которые. поступают на входы сумматоров 15, на входы которых поступают коэффициенты полинома Ь F(x), где b =1, если,в триггере 13 записана .1, и Ь =О, если записан О.

Таким образом, на входах триггеров

13.}, ..., 13а ноявляются коэффициенты полинома (g x g <)p(x)+b Г(х)

На третьем такте полйном (д „x +

+g )р(х)+Ьа Г(х) записывается в а-а триггере 13.}, ..., 13,„, а на входах соответствующих триггеров формируются коэффициенты полинома

j(g, Х+ц )р(х) Ь F(x) Ix+

-(g„,x+}x х },)Их> ° (Ь, Ь щх1.

Таким образом, на i ì такте (i =

=2, ..., а+1) содержимое регистра 2 умножается на х по модулю F(x) и. суммируется с полиномом g „. „ р(х), т.е. на i-м такте в регистре 2 записан полином

В результате на а+1-м такте в регистре 2 записан полином

I (Хх „х "} д, хх " g„x+}x,)рЫ

824202

Формула изобретения аказ 2112/71

Подписное ределяется следующим образом. Если в известном устройстве требуется 8 элементов, то в данном требуется 7с элементов, т.е. экономится а элементов ИЛИ, что повышает надежность устройства.

Устройство для умножения в конеч. ных полях, содержащее первый, второй и третий регистры, блоки умножении и группу элементов И, цричем первая группа входов устройства соединена .с разрядными входами первого регист« ра, выход последнего разряда которо.го соединен со входом его первого раз ряда и с первыми входами элементов И группы, выход последнего разряда второго регистра соединен со входами блоков умножения, каждый разряд второго регистра содержит сумматор по модулю два и триггер, .первый вход сумматора по модулю два каждого разряда второго регистра соединен с выходом соответствующего элемента И группы, второй вход сумматора по мо- дулю два nepaoro разряда второго регистра соединен- с выходом его последнего разряда, а второй вход сумматорапо модулю два j-го разряда второ- го регистра (j=2, ..., а, где а! разрядность регистра) соединен с выходом j-1-го блока умножения, . o т л и ч а ю at е е с,я тем, что, с це лью упрощения устройства, вторая группа -входов устройства соединена с входами разрядов третьего регистра, тактовый вход устройства соединен с тактовыми входами первого и второго ре о гистров, выходы разрядов третьего регистра подключены ко вторым входам элементов И группы, выходы триггеров второго регистра, являющиеся выходами соответствующих разрядов второго регистра, подключены к группе выхо15 дов устройства, третий вход сумматора по модулю для каждого разряда второго регистра, начиная со второго, соединен с выходом триггера предыдущего разряда второго регистра.

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

1. Авторское, свидетельство СССР

Р 538364, кл. G 06 F 7/39, опублик.

1975.

2. Питерсон У. Коды, исправляющие ошибки, М., "Мир", 1964, с. 133.

3. Блох Э.Л. и др. Обобщенные каскадные коды. М., "Связь"., 1976, с. с. 99 (прототип) Филиал ППП "Патент", г.ужгород, ул.Проектная,4