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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советскнк Сфцналистнческнк Республик(22) Заявлено 270779 (21) 280283 б/18-24с присоединением заявки йо -(51 М К 3 С 06 Г 7/49 Государственный комитет СССР но делам изобретений и открытий(72) Авторы изобретения Б.ф. Харчистов и В.И, Финаев Таганрогский радиотехнический институт им. В.Д. Калмыкова(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В КОНЕЧНЫХ ПОЛЯХИзобретение относится к построению кодирующих и декодирующих устройств корректирующих циклических кодов, предназначенных для передачисообщений с высокой достоверностьюв системах доставки и обработки дискретной информации,Известно устройство для умножения полиномов, содержащее первый,второй и третий сумматоры по модулюдва, элемент задержки, регистр, входкоторого соединен со входом устройства и с первым входом второго сумматора, выход которого соединен совторым входом второго сумматора и ,15со входом элемента задержки, выходкоторого соединен с первым входомтретьего сумматора, а выход - является выходом устройства для умноженияполиномов 1.20Недостаток этого устройства сос-.тоит в том, что умножение возможнолищь на Фиксированный полином.Известно устройство для умноже"ния, содержащее блоки сумматоров помодулю два, ячейки регистра, блоки,умножения первой и второй групп, прйчем вход устройства соединен со вхоцами блоков умножения первой группы,выходы которых соединены с первыми 30 входами блоков сумматоров соответственно, вторые входы которых соединены соответственно с выходами соответствующих блоков умножения второй группы, входы которых, кроме последнего, соединены между собой, а также с выходом устройства и выходом последнего блока умножения второй группы, выход каждого блока сумматора, кроме последнего, соединен со входом соответствующей ячейки регистра, выход каждой ячейки регистра соединен с третьим входом соответствующего блока сумматоров, выход последнего блока сумматоров соединен со входом последнего блока умножения второй группы 2.Недостаток этого устройства состоит в том, что умножение в конечных полях данным устройством производится только лишь на фиксированный полином.Наиболее близким по технической сущности к предлагаемому являетсяустройство умножения в конечных полях, содержащее ячейки первого, второго и третьего регистра, сумматоры по модулю два первой и второй группы, элементы И, элементы ИЛИ первой и второй групп, блоки умножения, причем первая группа выходов устройствасоединена соответственно с первымивходами элементов ИЛИ первой группы,Выходы которых соединены соответст.венно с первыми входами соответствующих ячеек первого регистра, выходыячеек нервого регистра, за исключением последней, соединены соответственйо со вторыми входами соответствующих элементов ИЛИ первой группы,выход последней ячейки первого регистра соединен со вторым входом соответствующего элемента ИЛИ первойгруппы и с первыми входами элементовИ, выходы которых соединены с первымивходами сумматоров первой группы,выходы которых соединены со входами 15ячеек третьего регистра соответственно, а вторые входы - с выходами ячеек третьего регистра и с выходамиустройства соответственно, вторые входы элементов И, кроме последнего, сое-Щдинены с выходами ячеек второго регистра и с первыми входами вторых сумсумматоров соответственно, второйвход последнего элемента И соединенс выходом последней ячейки второго ре гистрасо входом первого элемента ИЛИвторой группы, и со входами блоков умножения, выходы которых соединенысоответственно со вторыми входамисоответствующих сумматоров второйгруппы, выходы которых соединены спервыми входами соответствующих элементов ИЛИ второй группы, вторые входы которых соединены со входами устройства второй группы, а выходы - совходами ячеек второго регистра (3.Недостатком является избыточностьэлементов устройства. Операцию умножению реализуют более простым методом,используя схему для одновременногоумножения полиномов сомножителей и де ления на образующий полином поля. Избыточность элементов устройства снижает надежность в целом.Цель изобретения - упрощение устройства.Указанная цель достигается .тем,что в устройство для умножения в ко. нечных полях, содержащее первый, второЯ и третий регистры, блоки умножения и группу элементов И, причем пер Овая группа входов устройства соединена с разрядными входами первогорегистра, выход последнего разрядакоторого соединен со входом его пер- .вого разряда и с первыми входамиэлементов И группы, выход последнего 55разряда второго регистра соединен совходами блоков умножения, каждый разряд второго регистра содержит сумматор по модулю два и трчггер, первый вход сумматора по модулю два каждого О разряда второго регистра соединен с выходом соответствующего элемента И группы, второй вход сумматора по мо. дулю .два первого разряда второго регистра соединен с выходом его последнего разрдд, а второй вход сумматора по модулю два -го разряда второго регистра =2, , а, где а- разрядность регистра) соединен с выходом 1-1-го блока умножения, вторая группа входов устройства соединена с входами разрядов третьего регистра, тактовый вход устройства соединен с тактовыми входами первого и второго регистров, выходы разрядов третьего регистра подключены ко вторым входам элементов И группы, выходы триггеров второго регистра, являющиеся выходами соответствующих разрядов второго регистра, подключены к группе выходов устройства, третий вход сумматора по модулю два каждого разряда второго регистра, начиная со второгосоединен с выходом триггера предыдущего разряда второго регистра.На чертеже представлена функциональная схема устройства.Устройство содержит регистры 1, 2 и 3, причем регистры 1 и 2 являются сдвиговыми, тактовый вход 4, блоки 5(, , 5 цумножения, элементы И б, , б, входы 7(, , 7 с и 84, , 8выходы 9, , 9 . Каждая -я ячейка регистра 1 содержит элемент ИЛИ 10 и триггер 11 -.1, ,а). Каждая -я ячейка регистра 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, 13 С регистра 2, выход триггера 11. регистра 1 соединен со вторым входом элемента ИЛИ 10, выход триггера 11 регистра 1 соединен со вторым входом элемента .ИЛИ 10,( и с первыми входами элементов И б, 6вторые входы которых соединены с выходами триггеров 16.(, , 16 О регистра 3, входы которых соединены с входами 84, , 8 о устройства умножения, выходы элементов б , , 6, соединены со входами сумматоров 124, 12 С, по модулю два, выходы триггеров 13, , 13 О регистра 2 соединены соответственно с выходами 9 9 устройства умножения и со вторыми824202 я,ц;ми соо 1 ветствующих сумматоров 1 .1, , 12 с регистра 2 соединен со входами блоков 51, , 5 1 1 умножения и со вторым входом сумматора 124 выход 1 оторого соединен со входом соответствующего триггера 13 регистра 2, выходы блоков 51, , 5, 4 ум 5 ножения соединены соответственно вторыми входами сумматоров 12, , 12 С по модулю два, третьи входы которых соединены с выходами соответствующих триггеров 134 .13 регистра 2.ф ф а При описании работы устройства рассматривают поле СГ(2 а), опреде-ляемое многочленом Е(х) степени, а коэффициентами из поля СЕ(2), т.е. . 15 коэффициенты многочлена д(х) записы" ваются в регистр 1. При этом на выхо" де триггера 11, регистра 1 появляется коэффициент да 1 который поступает на первые входы элементов И б ь ба, навторые входы которых пос тупают коэффициенты полинома р(х) выходоВ регистра 3. В результате на входы триггеров 134, , 13поступают через элементй И б -б и сумматоры 124, , 12 с, коэффициенты поли- нома д р(х).На втором такте полином д р(х) .ь-л записывается в триггеры 131, , 13 с регистра, а на входы сумматоров 12,12 с 1 по модулю два поступают коэффициенты полинома дор(х). В результате на выходах сумматоров,14 появляются коэффициенты полинома1. бГ 1 Иг 1=О,а - 11 "20 Каждый элемент ГС(2") представляют в виде много"лена над СГ(2), степень которого меньше а, т.е. вместо элементов р,д,г В СЕ(2 ) рассматривают многочлены р(х), д(х) и г(х), .соответствующие этим элементам р(х) = Е р 1 х р 16 ОЦ 2).1-0- а1:Оа(х) "- 2 дХ; 6 б Г Ф), 1 = Оа 1=0г(Х) = Е г Х", 1 Е,МЮ; 1=аа 1=ОТогда умножение элементов СГ(2), т.е. рд=г выполняется по.правилам умножения, представляющих .эти элементы многочленов по модулю Е(х), т.е. р(х) д(х)Ег(х) вод Г(х); г(х)=р(х)д(х)+Ь(х) Е(х), где Ь(х) - полином степени меньшей, чем а Поскольку Ге СГ(2), 1=0, а, то блок умножения 11 , осуществляющий умножение на Г (=1.а,3реализуется наличием связи, если Г) =1, либо отсутствием связи, если 45 Г; =О.Работает устройство умножения в конечных полях следующим образом.В исходном состоянии ячейки регистров 1, 2 и 3 находятся в нуле О вом состоянии.На входы 74, , 7 устройства:, подаются одновременно в порядке возрастания индексов коэффициенты много- члена д(х), т.е. на вход 7 - коэфФициент д , на вход 7, - коэффициент д на вход 7 ц - коэффициент д Причем д =1 соответствует единичйый потенциал на входе 71, а д =О-нулевой потенциал на входе 7 . Аналогичным . образом на входы 84, , ЗС 1 устрой- ЬО стза подаются коэффициенты многочлена р(х) и запоминаются в регистре 3. Затем на тактовый вход 4 поступают импульсы тактового генератора (на чертеже не показан). На первом .такте хр(х) йрг р(х)-(ц х+ц )рЬ) которые. поступают на входы сумматоров 15, на входы которых поступают коэффициенты полинома Ьс,Г(х), где Ьп =1, если,в триггере 13, запиесли записан Таким образом, на входах триггеров 131, , 13 ц появляются коэффициенты полинома (д1 х+д , )р(х)+Ь Гх) На третьем такте полйном (д х + +до )р(х)+Ьс Г(х) записывается в триггере 131, , 13 а на входах соответствующих триггеров формируются коэффициенты полиномао-эх)а-Г(х) =Таким образом, на -м такте (1= =2, , а+1) содержимое регистра 2 умножается на х по модулю Г(х) и суммируется с полиномом д1 р(х), т.е. на )-м такте в регистре 2 записан полином=ц(х) р(х)+ъх)%(х) фв"ЫЪ который появляется на выходах 9,9 д устройства для умножения, Таким образом сформирован результат умножения двух полиномов.Эффективность предлагаемого устройства по отношению к известному оп824202 формула изобретения аз 2112/71Подписное"Патент",ул.Проектная,4 Филиал П г.ужгоро ределяется следующим образом. Еслив известном устройстве требуется 8элементов, то в данном требуется 7 сэлементов, т.е. экономится а элементов ИЛИ, что повышает надежность устройства. устройство для умножения в конеч" . ных полях, содержащее первый, второй и третий регистры, блоки умножении и группу элементов И, цричем первая группа входов устройства соединена .с разрядными входами первого регист ра, выход последнего разряда которо.го соединен со входом его первого раз ряда и с первыми входами элементов И группы, выход последнего разряда второго регистра соединен со входами блоков умножения, каждый разряд второго регистра содержит сумматор по модулю два и триггер, .первый вход сумматора по модулю два каждого разрядавторого регистра соединен с выходом соответствующего элемента И группы, второй вход сумматора по мо-дулю два первого разряда второго регистра соединен с выходом его последнего разряда, а второй вход сумматора по модулю два -го разряда второ-го регистра (3=2.а, где аразрядность регистра) соединен с выходом )-1-го блока умножения, .о тл и ч а ю щ е е с,я тем, что, с це лью упрощения устройства, вторая группа .входов устройства соединена с входами разрядов третьего регистра, тактовый вход устройства соединен с тактовыми входами первого и второго рео гистров, выходы разрядов третьего регистра подключены ко вторым входамэлементов И группы, выходы триггероввторого регистра, являющиеся выходами соответствующих разрядов второгорегистра, подключены к группе выхо 15 дов устройства, третий вход сумматора по модулю для каждого разряда второго регистра, начиная со второго,соединен с выходом триггера предыду"щего разряда второго регистра,20 Источники информации,принятые во внимание при экспертизе1. Авторское, свидетельство СССРР 538364, кл. 6 06 Г 7/39, опублик.1975.2. Питерсон У. Коды, исправляющие ошибки, М., "Мир", 1964, с. 133.3. Блох Э.Л. и др. Обобщенные каскадные коды. М., "Связь"., 1976, с.с. 99 (прототип)