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

 

Изобретение относится к вычислительной технике и может быть использовано для построения спецвычислителей произведения в конечых полях. Цель изобретения - расширение облас ти применения за счет возможности умножения элементов поля Галуа GF(P ), представленньк в нормальном базисе. Предложенное устройство содержит п регистров 1, п блоков 2 умножения на примитивный элемент, п блоков 3 формирования частичных произведений, каждый из которых содержит п умножителей 4, и п блоков 5 суммирования с соответствующими связями. Блок 2 умножения на примитивный элемент содержит п групп по п элементов И и п сумматоров по модулю Р с соответствующими связями. Устройство производит умножение элементов поля Галуа GF (Р ), представленных в нормальном базисе. 1 з.п. ф-лы, 2 ил. с В (Л

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

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ д j

OflHCAHHE ИЗОБРЕТЕНИЯ

H А BTGPGHOMV СВИДЕТЕЛЬСТВУ

2 юг.1 (21) 4058748/24-24 (22) 24 ° 04.86 (46) 23.03.88. Бюл. У 11 (71) Институт проблем передачи информации АН СССР и Пензенский политехнический институт (72) В.А.Зиновьев, В.В.Зяблов, Б.А.Савельев,.В.М.Георгиева, С.M,Äîäóíåêoâ, Н.Л.Манев, П.А.Попов и В.Б.Стойнов (53) 681.325(088.8) (56) Авторское свидетельство СССР

Р 824202, кл. G 06 F 7/49, 1981.

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

Ф 900281, кл. G 06 F 7/49, 1982. (54) ПАРАЛЛЕЛЬНОЕ УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В КОНЕЧНЫХ ПОЛЯХ (57) Изобретение относится к вычислительной технике и может быть ис„„SU„„1383338 A 1 пользовано для построения спецвычислителей произведения в конечых полях.

Цель изобретения — расширение области применения за счет возможности умн ножения элементов поля Галуа GF(P ), представленных в нормальном базисе.

Предложенное устройство содержит и регистров 1, и блоков 2 умножения на примитивный элемент, и блоков 3 формирования частичных произведений, каждый из которых содержит и умножителей 4, и и блоков 5 суммирования с соответствующими связями. Блок 2 умножения на примитивный элемент содержит и групп по и элементов И и и сумматоров по модулю Р с соответствующими связями. Устройство производит умножение элементов поля и

Галуа GF (Р ), представленных в нормальном базисе. I s.ï. ф-лы, 2 ил.

l 383338

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

Цель изобретения — расширение области применения за счет возможности умножения элементов поля Галуа

))

GF (P ), представленных в нормальном базисе, 10

На фиг.l представлена структурная схема параллельного устройства для умножения в конечных полях; на фиг.2 структурная схема блока умножения на примитивный элемент. 15

Устройство содержит и регистров 1, и блоков 2 умножения на примитивный элемент, п блоков З.формирования частичных произведений, каждый из которых содержит п умножителей 4, и n . 20 блоков 5 суммирования, причем каждый блок 5 суммирования содержит п входных шин, каждая из которых содержит

P-1 цепей, и входных шин первой группы первого блока 2 умножения .на при- 25 митивный элемент соединены соответственно с первой группой информационных входов устройства, à и входных шин первой группы каждого блока 2 умножения на примитивный элемент, начи- 30 ная с второго, соединены с первой группой информационных входов устройства с циклическим сдвигом на один разряд в сторону старших разрядов, группы с второй по (и+1)-ю входных шин п блоков 2 умножения на примитивный элемент соединены соответственно с п выходами каждого из и регистров

1, каждый информационный вход второй группы устройства соединен с первыми 40 входами и умножителей 4 соответствующего блока 3 формирования частичных произведений, вторые входы которых соединены с выходами соответствующих блоков 2 умножения на прими- 45 тивный элемент, i-й выход j-ro блока

3 формирования частичных произведений соединен с j-м входом k-го блока 5 суммирования (i=i,. ° .,n; j — 1,...,n; k = i+j-1 при i+j (и+1;

k=iwj-n-l, при i+j > n+1), выходные шины блоков 5 суммирования являются выходом параллельного устройства для умножения в конечных полях.

Блок 2 умножения на примитивный элемент содержит и групп по и элементов И 6 и и сумматоров 7 по модулю

Р, причем каждая из входных шин первой группы блока 2 соединена с первыми входами и элементов И 6 соответствующей группы, вторые входы которых являются группами входных шин от второй до (п+1)-й блока 2, выход

ro элемента И 6 j-й группы (i

=l...,,п; ) =1,...,п) соединен с )-м входом k- ãî сумматора 7 по модулю P (k=i+j-1, при i+j и+1; k=i+j-n-l, при i+j c. и+1), выходы сумматора 7 по модулю P являются выходами блока

2 умножения на примитивный элемент.

Устройство работает по следующему алгоритму.

Множимое и множитель обозначаются

)) -1 ))-

А(х)аа а х и В(х)= Ь х (1) -0 ааО где P — характеристика;

n — - степень расширения поля.

Тогда произведение имеет вид

А(х)В(х)= (а;х (B(x)7)

i=0

))-) (г)

Q Ea х (В (х)7 Р

Произведение хВ(х) может быть представлено в виде

1 tl- (, Ь,х (3)

i =--0

В регистрах 1 записаны произведения базисных элементов на примитив1 ный элемент, т.е. элементы ХР" (i=0 1,...,n-l), выходы которых соединены с j-й группой входов блоков 2 умножения, куда подается величина

Р (Х . Содержимое регистров меняется при смене представления элементов поля. Компоненты элементов поля, поступающие на первую группу входов блока 2 умножения, умножаются на элементах И 6 на Х, в результате чего получают члены произведения (3), которые суммируются в сумматорах 7 и в соответствии с (3) на выходе блока 2 формируются произведения, поступающие на вход элемента на элементы Х

На первую группу входов параллель" ного устройства подается множитель

А(х), а на вторую - множитель В(х).

В связи с приведенным сначала по первой группе входов на первый блок 2 подана величина B(x), на второй блок

2 — (В(х)), а на и-й блок 2— (P-()) -))

В(х)), На выходе первого блока

2 формируется Х В (х), на выходе вто1383338 рого блока 2 — Х (В (х))р, на выхо де и-го блока 2 — Х ° (В(х)) " . В блоках 3 формирования частичных произведений полученные величины умно5 жают на соответствующие разряды множителя А(х) . Полученные произведения с выхода схем умножения блоков формирования частичных произведений подаются на блоки 5 суммирования. 1О

Параллельное устройство для умножения в конечных полях по сравнению с известным позволяет производить умножение элементов поля Галуа GF(P ). т представленных в нормальном базисе, 15 что существенно упрощает декодирующее устройство с исправлением ошибок.

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

1. Параллельное устройство для умножения в конечных полях, содержащее и блоков формирования частичньи произведений и и блоков суммирования, причем каждый блок суммирования содержит и входных шин, каждая иэ которых содержит P-l цепей, а выходные шины блоков суммирования являются выходом параллельного устройства дЛя умножения в конечных полях, где P и 30

n — соответственно характеристика и размерность поля Галуа GF(P ), о тл и ч а ю щ е е с я тем, что, с целью расширения области применения за счет возможности умножения элементов поля Галуа GF (P ), представи 35 ленных в нормальном базисе, в него введены и регистров и п блоков умножения на примитивный элемент, причем и входных шин первой группы пер- 40 .вого блока умножения на примитивный элемент соединены соответственно с первой группой информационных входов устройства, а и входных шнн первой группы каждого блока умножения на примитивный элемент, начиная с второго, соединены с первой группой информационных входов устройства с циклическим сдвигом на один разряд в сторону старших разрядов, группы с второй по (и+1)-ную входных шин и блоков умножения на примитивный элемент соединены соответственно с и выходами каждого из и регистров, каждый информационный вход ьторой группы устройства соединен с первыми входами п умножителей соответствующего блока формирования частичных произведений, вторые входы которых соединены с выходами соответствующих блоков умножения на примитивный элемент, i-й выход j-го блока формирования частичных произведений соединен с 1-.м входом k-го блока суммирования (1=1,...,n; j=l,...,n; k=i+j-1 при i+j 6 и+1; k=i+j-n-1 при i+j > и+1).

2. Устройство по и. l, о т л и— чающее с я тем, что блокумножения на примитивный элемент, содержащий и "групп по и элементов И и и сумматоров по модулю Р, причем каждая из входных шин первой группы. блока соединена с первыми входами и элементов И соответствующей группы, вторые входы которых являются группами входных шин от второй до (и+1)-й блока, выход i-го элемента И j-й группы (1=1 è,j=l,...,п) соединен с j-м входом k-го сумматора по модулю P (k=i+j-1 при i+j <п+1; k=

=i+j-п-1 при i+j >и+1), выходы сумматоров по модулю Р являются выходами блока.

1383338

Составитель В.Гусев

Редактор Н.Бобкова Техред Л.Олийнык Корректор М.Демчик

Заказ 1297/47 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035 Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие,г.Ужгород,ул.Проектная,4