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

.СОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 1 6 06 Р 7/52 ГОСУДАРСПО ДЕЛ БРЕТЕНИЯСТВУ ТВЕННЫЙ КОМИТЕТ СССР ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗ ВТОРСНОМУ СВИДЕТ(54)(57) 1. УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ КОНЕЧНЫХ ПОЛЕЙ, содержащее два регистра сомножителей, входы которых являются входами первогои второго сомножителей устройства, многовходовые сумматоры, выходы которых являются выходами результата устройства, группы элементов И, первые входы которых в каждой группе объединены и подключены к соответствующему выходу регистра первого :-омножителя, а выходы регистра второго сомножителя соединены с вторыми входами соответствующих элементов И первой группы, о т л и ч а ю щ е ес я тем, что, с целью упрощении . устройства путем уменьшения количества многовходовых сумматоров, устрой,ЯО 1013950 А ство содержит блоки матричного преобразования, входы йервого из которых соединены с соответствующими выходами регистра второго сомножителя, а выходы 1 -го блока матричного преобразования соединены с вторыми входами соответствующих элементов Й (.+1).й группы и соответствующими входами (,1+1)-го блока матричного преобразования, выходы одноименных элементов И каждой группы подключены к соответствующим входам Одноименного многовходового сумматора.2. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок:матричного преобразования содержит сумматоры по модулю два, причем в разрядах, соответствующих ненулевым значениям коэффициентов многочлена поля, входи блока матричного пре-. образования .подключены к первым входам сумматоров по модулю два, вторые входы которых соединены с входом старшего разряда .и с выходом младшего разряда блока, а в разрядах, соответствующих нулевым значе- аде ниям коэффициентов многочлеиа поля, (" входы блока соединены е его выходами со сдвигом на один разряд в. сторону старших разрядов. ффИзобретение относится к вычислительной технике и может быть применено при, построении специализированных вычислителей для кодирования и декодирования кодов, корректиРующих ошибки.Известно устройство для умножения элементов конечного поля, содержащее кольцевой регистр, регистр с обратными связями, блок элементов И и выходной накопительный ре гистр 11.Недостатком этого устройства является низкое быстродействие.Наиболее близким к предлагаемому является устройство для быстрого умножения элементов конечных палей, содержащее два регистра, многовходовые сумматоры, выходы которых являются выходами устройства, группы двухвходовых элементов И, причем 20 первые входы каждой группы объединены и подключены к соответствующими выходам первого регистра каждый выход второго регистра подключен к соответствующим по порядку объе диненным вторым входам групп элементов И выходы которых подключены через комбинаторную схему ко входаммноговходовых сумматоров 2 1.Недостатком известного устройства З 0 является значительная сложность, определяемая сложностью сумматоров с большим числом входов.Целью изобретения является упрощение устройства за счет уменьшения 35количества многовходовых сумматоров,Для достижении поставленной целиустройство для умножения элементов.конечных полей, содержащее два регистра сомножителей, входы которых являются входами первого и второгосомножителей. устройства, многовходо.вые сумматоры, выходы которых являются выходами результата устройства,группы элементов И, первые входы которых в каждой группе объединеныи подключены к соответствующемувыходу регистра первого сомножителя,а выходы регистра второго сомножителя соединены со вторыми входами соот 50ветствующих элементов И первой группы, содержит блоки матричного преобразования, входы первого .из которых соединены с соответствующимивыходами регистра второго сомножителя, а выходы-го блока матричногопреобразования соединены со вторымивходами соответствующих элементов И+1)-й группы и соответствующимивходами 6+1)-го блока матричногопреобразования, выходы одноименных . 60элементов И каждой группы подключенык соответствующим входам одноименногомноговходового сумматора,Кроме того, блок матричного преобразования содержит сумматоры по мо дулю два, причем в разрядах, соответствующих ненулевым значениям коэфФициентов многочлена поля, входы блока матричного преобразования подключены к первым входам сумматоров па модулю два, вторые входы которых соединены со входом старшего разряда и с выходом младшего разряда блока, а в разрядах, соответствующих нулевым значениям коэффициентов многочлена поля, входы блока соединены с его выходами со сдвигом на один разряд в сторону старших разрядов.На фиг,1 изображена схема устройства на фиг,2 - схема блока матричного преобразования.Устройство содержит регистр 1 первого сомножителя, элементы И 2, объединенные в группы 3, многовходовые сумматоры 4, регистр 5 второго сомножителя, блоки б матричного преобразования, выходы 7 устройства, входы 8 и 9 первого и второго сомножителей сумматоры 10 по модулю два.Устройство работает следующим образом.Сигналы с выхода регистра 5 второго сомножителя поступают на последовательную цепочку блоков б матричного преобразования и на первые входы элементов И 2 первой группы 3, причем первый разряд регистра 5 второго сомножителя соединен со входом первого элемента И 2, второй разряд - со входом второго элемента И и т.д. Для образования сдвигов числа, хра- . нимого в регистре 5, используются блоки, б матричного преобразования, Для получения последующего сдвига используется результат предыдущего преобразования. При этом произведение двух сомножителей 0= О,Од,Я,) иЧ=1 КУ",/и) являющихся элементами конечного поля, определяется каки=а,."2.1 =, ,(а М"-" где суммирование проводится,по модулю два, умножение - как логическое умножение; М - матрица преобразования.Даннаяматрица задается выбранным неприводимым многочленом, определяющим элементы конечного поля. .Преобразование реализуется путем циклического сдвига всех разрядов с суммированием по модулю два старшего разряда с разрядами, определяемыми ненулевыми коэффициентами многочлена поля. При,выборе примн.и тивного многочлена поля вида Р=ХХ 1 для реализации блока б матричного преобразования требуется лишь один двухвходовой сумматор по модулю два. Выходы блоков,б матричного преабразования поразрядно подключаются ко вторым входам элементов И 2,10 соответствующих каждому преобразователю групп 3, Сигналы с выходов регистра 5 и блоков 6 матричногопреобразования проходят на входы многовходовых сумматоров 4 лишь через тегруппы 3 элементов И 2, в которЫхна первые входы элемеитов И подается единичный сигнал с выхода соответствующего разряда регистра 1первого сомножителя. Если же напервые входы элементов И 2. какойлибо группы 3 подается нулевой сигнал с выхода регистра 1, то нулис выхода элементов И 2.данной группы 3 не изменяют результата суммирования. Сигнал на первом выходе устройства является результатом сложения в многовходовом сумматоре 4 всехсигналов с выходов первых элементовИ 2 в группах 3, сигнал на второмвыходе - результатом сигналов с вы Оходов вторых элементов И 2 в группах3 и т.д. Таким образом, с выходовмноговходовых сумматоров 4 получаемрезультат перемножения содержимогорегистров сомножителей. Так же как 25 и известноепредлагаемое устройство выполняет, умножение двух сомножителей за один такт.Такое построение устройства требует для реализации многовходовых сумматоров и блоков матричнбго преобразования наличия максимум (2 ьи +1) двухвходовых сумматоров по модулю два, В то. же время количество двухвходовых сум-". маторов для реализации многовходовых сумматоров в известном устройстве может достичь величины (и-И ) . При определенном выборе многочлена Г (х) эти же величины могут быть. уменьшены до величины и -1) в предлагаемом устройстве идо 1,5 и)в известном.При и=8 и образующем многочлене р(х)=х +Хф+Хх для реализации предлагаемого устройства требуется 157 элементарных Функциональных элементов (77 двухвхздовых сумматоров по модулю . два, 64 двухвходовых схем И и 16 триггеров, для известного - 221 элемент .1141 двухвходовых .сумматоров по модулю два, 64 двухвходовых схем И и 16 ,триггеров,. Составитель Н. Захаревичдактор Н. Егорова Техред К.Мыцьо Корректор С. Шекма сное 4/5 Филиал ПП тент", г. Ужгород, ул. Проектная, 4 Заказ 3006/5ВНИИПИпо д113035,Тира осударственн лам изобрете осква, Ж704 Под го комитета ССС ий и открытий Раушская наб.,