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

(51) 4- 06 г 7/49 ОИСАЧИЕ ИЗОБРЕТЕНИЯИ АВТСРСМОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР(7 ) Специальное ко структорско-техноло ическое бюро микроэлектроники (72) Н. Ф. Садыков, М. 10. Балабаев и А. Н. Савчеко(54) УСТРОЙСТВО ДЛЯ АРИФМЕТИЧЕСКОЙ ОБРАБОТКИ ЭЛЕМЕНТОВ КОНЕ 1- НОГО ПОЛЯ(57) Изобретение относится к вычислительной технике и может быть использовано в устройствах кодирования и декодирования корректирующих кодов в виде БИС для цифровых проигрывателей. С целью повышения быстродействия устройство д,я арифметической обработки элементов конечного поля, содержащее блок 1 вычис ления обратного элемента, блок 2 суммирования, блок 3 умножения, мультиплексор 4. имеет новые организацию связей и структуру блока умножения, содержацего узел умножения двух многочленов и узел вычисления остатка от деления на порождаюший многочлен поля. В блоке 3 можения реализован более быстрый двухшаговый алгоритм умножения элементов конечного поля. 1 з.п. ф-лы, 4 ил.3Изобретение относится к вычислительной технике и может быть использовано в устройствах колирования и лекодирования корректирующих кодов, выполненных, В частности, в виде больпих интегральных схем, в цифровых звуковых проигрьВатеях системы компакт-диск лля обработки элементов поля С)Е (2 ф).Це;ьк) изобретения являстся пов)ис нс оыстродействия устройстваНз фиг. 1 привелена схема устройсБЗ )О лля арифметической обработки элемептоь конечного поля; на фиг. 2 - схема блока умножения; на фиг. 3 и 4 - пример рсд,)1.зации блока умножения для случая консчного ноля СзГ(2) с порожлаюшим много членом ц(х) =х+х+1.Устройство (фиг.) содержит блоквычисления обратного элемента, блок 2 суммирования, блок 3 умножения, мультиплскСОр 4, ПЕрВЫй И ВтОрОй ВХОЛЫ 5 И 6;3 с(дания режима устройства, Второй и )ервый 20 информационные входы 7 и ), вьходустройства.Блок 3 умножения (фиг. 2) содержи г лел 3.1 умножения двух многочл(пюв и узел 3 2 вычисления остатка )Г леления нд по- РОК.(с 1011 11 Х 1)ОГОЧЛС 11 1 ОЛЯ25Ьс)ОК 3 умножсни 51 )и . 3) с 0,1 е ржи 1 с ирвого по шеста,п)зт)й элемен)ь и 3, 3.6 и с первого НО левятый элс мс 1 г):ИСК.г(10 с)ЛЮ 111 ЕЕ И 1,"(И 3.17 3.26 ;ЗЛс( 3. УМ)ожспня ДВУХ МНООЧЛЕНОВ И С лс( 51 ГО 0 по пятнадцатый эгемень ИС,1 Ю(Л 1 С)111 Е Е ИИ 3.26 3.31 узлс 3.2 БыцслспЯ ОСтатКа От ЛслсниЯ на по- РОЖЛЗКП(ПП МНООЧЛЕН ЮЛЯ.)10 КБ Ы Ч И СЛ С. Н И и 00 Р с Т НОГО Э 1 Е М С Н Т с 1,0,я представляет собой 11 ВУ, и (Ошсс с)-рс(зрялн(й информ а)ионный Б.,ол, хсл р с 1 з м с и Р с н и я и с) - р 3 3 р 51 л Р ы Й 3 ь х Г) л. 1р и э Г 0 м, КОлд нд Вход разрешсп н подан 1), то Выход б 10 кд 1 НОВТОр 51( 1 с 0;"1 05 НН 1( нс С ОП)ОРс 1 ЦИОН НО М ВХОЛС, 3,0Д НД Б КОЛ Рд 3- СПцн 51 ПОЛЗИ ) РОБ(. П 1, (с ) 11 1 Д И 1,фо, м д НИОН н ь) и Бхол НОлс( и э,)(с 1. Нт В,0 нс 3 131 холс формируется эле;Сп Г = - 1,Б, т.с Обр11 с )л сан)1)30 К ) Су:13 ИрОЕа НИ я (Х)Л(рЖР)Т (1 СХ )сМ д.ТОРО 3 ПО МОДУ 1 К) ЛВД, ПЕРВ Ь Е БХО (Ы КО ГО- рых ОордзуОт (1-рдзр 5 лнь 13 первый Вход блока 2, вторые-разрядный 5;Орой Бхол Олокз 2, прР этом выходы сх ммзторовмолу.ю образуют Олразр 5 дный выход блока 2 т.о., что зпацение выхола блока суммирования Выцисляется как подразрядпзя опс 5 С) рация ИС;КЛ ЮЧА 01 ЦЕ,Е ИЛИ обоих входов.МуБТР(плексор 4 имеет лва (-разрядивк информационны.( входа, управляю)цпй вход, д также с 1-разрядный вы.(од. В зависимости от логического уровня сигнала нд 55 управляюшем входе мультиплексор 4 пер( лает на выход устройства значения выхода блока 2 суммирования в случае операции с,Ож.пня;)иоо Быхо,)сз О.Окз 1м ножен и я в .у час оп(рз),ий у множения и лелсния.ЗС МО;5 И,1 с 3 бОТ( С ГРОИС Ба (фИ: РП ВЫ ПОЛ НСНИ И (Н С",) Д ЦИИ УМ РОсКЕНИ Я.:ЕЛЕНП и (ЛОЖЕни Над Э.)С)Е)ГГс".П КОНЕЧ 010 по.Я С) (2) л,)Я;1 рои 30 льного ш)пож;д 1 1( (НО О, .С 1(д (1 ( Х )сЗСП)(, , 1)15 (фи 1,2)С.б)с ВЕЗТЬ 3 З С"сЬЕ П ро 1 5150)Л ЬНЫЕ ЭЛ(СМС 11 . з и Ь П ОЛ 51,1Ж Н 0) Е;, С Т Д Б " Ь Б . И ЛЕМНОГО Л.НОБ Б)Х) 1 Б(Х) 01Л(х.) == - . а, х,Ф-(Л (х) с -1,р,-( )=-а. -Выход узла 3.1 прелстдвляет собой выходразрядностью 2(; - 1 (2( -1, кзк хкдзз;О нз фиг. 2), по которо)1; 2) 1 коэффициентов Е, представляю(цих собой лвои:ные числа 0 либо 1, полдк)тся на узел 3.2. 11 ро.В(,1(ния с,6, В узс .3. редгиз) к)тся прии )моп:и лсх енгов И, с.ммироание тих пк)изведений по модулю лвд О(", це( гвля15292 5ется при помощи элементов ИСКЛЮЧАЮ.ЦЕЕ ИЛИ.Окончательный результат операции умножения появляется на выходе узла 3.2, в котором вычисляется результат делеция прямого произведения г (а) на порождающий многочлен поля. Эта операция необходима для того, чтобы результат операции также представлял собой элемент конечного поля равномерности д.Для пояснения работы узла 3.2 пред ставим прямое произведение на его входе в следующем виде: 1Г(а)= " Га =Р(а) -1-Б(а), где Е (а) = " Г а:ков-бЕ(а) =г а"15 Известно, что элементы а" для к)д. можно представить ь виде многочленов сте пени не более д а =- Йагде коэффициенты А, являются двоичными числами 0 или 1. Эти коэффициенты можно считать известными и постоянными для каждого конкретного порождающего многочлеца д(х). Подставив это выражение в формулу для Р(а) имеем:=,с,ад,-,) 35 где с,=г,+" Рдесть коэффициенты произведения с. " Операция делснця.11 а вход 6 подается уровень , ца в.,ол 5 уровень О. На выходе блока 1 появляется значение В элемента обратного элементу В, поданному на вход 7. Таким образом, операция деления осугцествляется умножением ца обратный элемент. С=А/В= =А В45Операция сложения.-1 г(М) Е (а) =Х Х (ГА,а. НО а 30 г также представляются в виде многочлена степени не более чем д. Окончательно имеем136На вход 5 полается уровень 1, выход мультиплексора 4 повторяет состояние выхода блока 2 суммирования, на входы которого с входов 7 и 8 подаются элементы поля В и А. Сумма находится слелующим образом.А - В= (а - ,-Ь ) а= сагде сумма с,=а,-4-6, реализуется поразрядным суммированием по модулю лва входных значений.Формули изобретения1. Устройство лля арифметическои обработки элемецтс в конечного поля, содержашес блок вычисления обратцого элемента, блок суммирования, блок умножения и мультиплексор, причем первый информационный вход устройства соединен с входом первого слагаемого блока суммирования и с входом первого сомножителя блока умножения, выходы блока суммирования и блока умножения соединены соответственно с первым и вторым информационными входами мультиплексора, выход которого является выхолом устройства, первый и второй входы задания режима которого соединены соответственно с управляющим входом мультиплексора и с входом разрешения блока вычисления обратного элемента, второй информационный вхол устройства соединен с входом второго слагаемого блока суммирования, отличаюи(ееся тем. что, с целью повышения быстродействия, второй информационный вхол устройства соединен с информационным входом блока вычисления обратного элемента, выход которого соединен с входом второго сомножителя блока умножения.2. Устройство по п. 1, отличаюи(еее тем, что блок умножения солержцт узел умножения двух многочленов и узел вычисления остатка от леления на порождающий многочлен поля, причем входы первого ц второго сомножителей блока умножения соединены с соответствхюцшми в оламц узла умножения лвух многочленов, выход которого соединен с входом блока вычисления остатка от деления ца порождаю ций мцогочлен поля, выход которого является выхолом блока умножения.