Устройство для умножения полиномов над конечными полями gf(2 @ )

 

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

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

РЕСПУБЛИК (я)ю G 06 F 7/49

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

О

ОПИСАНИЕ ИЗОБРЕТЕНИЯ - вЂ”К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4810366/24 (22) 04.04.90 (46) 15.12.91. Бюл. М 46 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И.И.Ковалив (53) 681.325(088.8) (56) Авторское свидетельство СССР

М 997039, кл. G 06 F 15/31, 1981.

Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды. Вып. 5. M. Связь, 1976, с.99, рис.3.30. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИНОМОВ НАД КОНЕЧНЫМИ ПОЛЯМИ

GF(2 ) .. Ж„» 1698886 А1 (57) Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF (2 "). Цель изобретения -- уменьшение аппаратурных затрат устройства без снижения его быстродействия. Устройство содержит блок 1 умножения на примитивный элемент поля, сдвиговый регистр 2, элемент И 3 и блок 4 поразрядного суммирования по модулю два, 2 ил.

1698886

Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF (2 ), Известно устройство умножения полиномов над конечными полями GF (2П ), со1, держащее два m-разрядных регистра, двухвходовые элементы И и сумматоры по, модулю два в количестве, пропорциональ ном m, причем выходы m-разрядных регистров подключены к входам- двухвходовых элементов И, выходы которых подключены к входам сумматоров по модулю два, выходы которых являются выходами устройства.

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

m-разрядного регистра подсоединены к объединенным одноименным m входам первого матричного преобразователя и вторым входам в двухвходовых элементов И первой группы из m двухвходовых элементов И соответственно, m выходов первых m-2 матричных .преобразователей подсоединены к вторым входам m двухвходовых элементов

И в группах, порядковые номера которых на единицу больше номеров матричных преобразователей соответственно и к одноименн ым входам следующих матричных преобразователей за исключением последнего (m-1)-го матричного преобразователя, выходы которого подсоединены только к вторым входам двухвходовых элементов И последней m-й группы двухвходовых элементов И соответственно, при этом выходы одноименных двухвходовых элементов И всех групп подключены к одноименным с группами элементов И входами одноименных с элементами И в каждой группе rn-входовых сумматоров по модулю два соответственно, выходы которых являются выходами устройства умножения соответственно.

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

55 соответственно, а выходы. — подключены к двум группам входов блока суммирования соответственно, выходы которого подсоединены к входам блока антилогарифмирования соответственно, выходы которого являются выходами результата умножения.

Недостатками известных устройств являются значительные аппаратурные затраты.

Известно устройства для умножения в конечных полях GF.(2 ), содержащее первый, второй и третий регистры, m-1 блоков умножения и m элементов И, причем входы первого и третьего регистра являются входами устройства коэффициентов первого и второго полиномов-сомножителей соответственно, а выходы второго регистра являются выходами устройства коэффициентов результирующего полинома, при этом m-й выход первого регистра подсоединен с объединенным входам всех m элементов И, вторые входы которых подсоединены к выходам третьего регистра, а выходы — к первой группе информационных входов второго регистра, rn-й выход которого подсоединен к входам всех m-1 блоков умножения и к первому входу второй группы информационных входов второго регистра, причем выходы в-1 блоков умножения подсоединены к остальным входам второй группы информационных входов второго регистра, а тактовые входы первого и второго регистров объединены и являются тактовым входом устройства.

Указанное устройство при низких аппаратурных затратах выполняет операции умножения за m+1 тактов работы, т.е, имеет невысокое быстродействие..

Известно еще устройство для умножения полиномов над конечными полями GF (2 ) по модулю два неприводимого многочлена, содержащее генератор импульсов, дешифратор, m двухвходовых элементов И и по одному блоку деления и умножения на примитивный элемент поля, причем входы блоков деления и умножения на примитивный элемент поля являются входами устройства занесения коэффициентов первого и второго полиномов-сомножителей соответственно, выходы блока деления на примитивный элемент поля подсоединены к входам дешифратора соответственно, выход которого подсоединен к объединенным первым входам m двухвходовых элементов И;выходы которых являются. выходами коэффициентов полинома — результата умножения устройства соответственно, а вторые входы подсоединены к выходам блока умножения на примитивный элемент поля соответственно, при этом тактовые входы блоков де1698886

10

25

55 ления и умножения на примитивный элемент поля объединены и подсоединены к выходу генератора импульсов.

Недостатком такого устройства является низкое быстродействие, если первый пол ином-сом ножитель соответствует степени примитивного элемента поля GF (2п ), большей, чем m/2, что в ряде случаев не позволяет его использовать, несмотря на его сравнительно низкие аппаратурные затраты.

Наиболее близким к предлагаемому по технической сущности и достигаемому результату при использовании является устройство умножения двух полиномов поля

GF (2 ), содержащее m-разрядный сдвиговый регистр,.блок умножения на примитивный элемент поля, m-разрядный регистр поразрядного суммирования по модулю два (регистр V) и m двухвходовых элементов И, причем первый выход сдвигового регистра подсоединен к объединенным первым входам всех m двухвходовых элементов И, вторые .входы которых подсоединены к гп выходам блока умножения на примитивный элемент поля соответственно, а выходы — к входам m-разрядного регистра поразрядного суммирования по модулю два соответственно, m выходов которого являются выходами m коэффициентов полинома-произведения соответственно.

Недостатки известного устройства — его большие аппаратурные затраты.

Целью изобретения является уменьшение аппаратурных затрат устройства для умножения полиномов над конечными полями GF (2 ) без снижения его быстродействия.

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

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

На фиг, 1 изображена. структурная блоксхема устройства умножения полиномов над конечными полями GE (2 ); на фиг. 2— временные диаграммы работы устройства при m-3; поле GF(2з) образовано неприводимым многочленом f(x) - х + х + 1, где х— з фиктивная переменная, используемая для записи полиномов, и устройство умножает первый многочлен, равный х + 1, на второй многочлен, равный х +1.

Устройство умножения полиномов над конечными полями GF (2 ) содержит блок 1 умножения на примитивный элемент поля, сдвиговый регистр 2, элемент 3 И и блок 4 поразрядного суммирования по модулю два, причем информационные входы блока

1 умножения на примитивный элемент поля являются входами устройства коэффициентов первого полинома-сомножителя, а информационные входы сдвигового регистра

2 являются входами устройства коэффициентов второго полинома-сомножителя; при этом выход сдвигового регистра 2 подсоединен к первому входу элемента 3 И, а выходы блока 4 поразрядного суммирования по модулю два являются выходами устройства коэффициентов результирующего полиномапроизведения, причем второй вход элемента 3 И подсоединен с объединенным тактовым входам блока 1 умножения на. примитивный элемент поля и сдвигового регистра 2 и является тактовым входом устройства, а выход элемента 3 И подсоединен к тактовому входу блока 4 поразрядного суммирования по модулю два, Временные диаграммы работы устройства (фиг, 2) содержит пятнадцать зависимостей изменений уровней сигналов на входах и выходах устройства и его элементов по времени при выполнении устройством операции умножения полиномов х+1 и х +1 над конечным полем GF(2 ), образованным неприводимым многочленом f(x) = х + х+ 1.

Буквенные выражения при временных диаграммах соответствуют следующим входам и выходам устройства и его элементов:

1698886

10

20

35

50

55 а) — вход первого коэффициента первого полинома устройства; б) — вход второго коэффициента первого полинома устройства; . в) — вход третьего коэффициента первого полинома устройства; г) — тактовый вход устройства; д)- вход первого коэффициента второго

,полинома устройства; е)- вход второго коэффициента второго полинома устройства; ж) — вход третьего коэффициента второго полинома устройства;. з) — первый выход блока 1 умножения на примитивный элемент поля; и) — второй выход блока 1 умножения на . примитивный элемент поля; к) — третий выход блока 1 умножения на примитивный элемент поля; л) — выход сдвигового регистра 2; м) — тактовый вход блока 4 поразрядно го суммирования по модулю два; н) — выход первого коэффициента ре,зультирующего полинома устройства; о) — выход второго коэффициента результирующего полинома устройства; и) — выход третьего коэффициента результирующего полинома устройства;

Устройство умножения полиномов над конечными полями GF (2 ) работает следующим образом.

8 исходном состоянии устройства блок

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

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

2, а значит, и на первом входе элемента 3 И формируется сигнал, соответствующий коэффициенту при нулевой степени фиктивной переменной второго полиномасомножителя, Здесь и в.дэльнейшем сигнал высокого уровня соответствует коэффициенту полинома, равного единице, а сигнал низкого уровня — нулю.

После "занесения" коэффициентов полиномов-сомножителей на все входы устройства коэффициентов полиномов-сомножи" тЕЛЕй ПОДаЮтСЯ ЕИГНаЛЫ НИЗКИХ УРОВнвй, как и при работе прототипа.

Если во время действия первого по порядку счета импульсного сигнала высокого уровня при занесении коэффициентов полиномов-сомножителей нэ первом входе элемента 3 И сформируется сигнал высокого уровня, то на выходе элемента 3 И тоже сформируется сигнал высокого уровня (см. фиг. 1, 2), по переднему фронту которого на выходах устройства сформируются сигналы, соответствующие коэффициентам первого полинома-сомножителя, При этом в блоке 1 умножения поля происходит умножение полинома, соответствующего сигналам на выходах блока 1 умножения до подачи очередного тактового импульса на тактовый вход устройства на примитивный элемент поля, в сдвиговом регистре 2 на его выходе формируется сигнал, соответствующий коэффициенту при очередной "старшей" степени фиктивной переменной второго полинома-сомножителя, а на выходе блока

4 поразрядного суммирования по модулю два — сигналы либо не изменяются, если на выходе сдвигового регистра 2 формируется сигнал низкого уровня, либо сигналы, соответствующие поразрядному сложению коэффициентов полинома, соответствующего сигналам на выходах блока 4 поразрядного суммирования до прихода очередного тактового импульса, и полинома, соответствующего сигналам на выходах блока 1 умножения на примитивный элемент поля после поступления на тактовый входустройства очередного тактового импульса, если на выходе сдвигового регистра 2 формируется сигнал высокого уровня, Таким образом, за rn тактов работы предлагаемое устройство так же, как и прототип, выполняет операцию а1(х) а (х) а1(х) (bm-1х + Ь - х +

+ ... + box+ Ьо) - а1(х) Ьо+

+ а1(х) b> х+. ° . +а (х) b -t х 11698886

= а1(х) Ьо+ а1(х) а b1+ ... +

+ a1(x) а() Ь„, 1, где а1(х) — первый полином-сомножитель; аг(х) — второй полином-сомножитель; х — фиктивная переменная, использующаяся для записи полиномов-элементов конечного поля GF(2 );

bp, Ь1, ..., bm-1 —. коэффициенты второго полинома-сомножителя, причем Ьо, b1, ..., bm-16 G F(2); а — примитивный элемент поля GF(2 ), причем а = х.

Рассмотрим работу устройства (см. фиг.1) на следующем примере, Пусть поле GF(2 ) образовано неприводимым многочленом f(x) = х + х+1 и устройство умножает полиномы; а1(х) = х + 1 и

32(x) = х + 1.

Злемент поля GF(2) упорядочивается по порядку возрастания степеней примитивного элемента поля следующим образом:

О х +О x+0=0

О х +О х+1=сР

O хг+1 х+О =а1

1 х +O x+0=a

О х +1 x+1=a

2+1, +О 4

1 х +1 х+1=сР х +0 x+1=a .

При этом aà = aÐ, (Р = а, сР = сР, а = сР и т.д., а а1(х) = х + 1 = О x2+ 1 x + 1 = a 14 аг(х) = х + 1 - х + О х+ 1 = а, причем bp - 1, г

b1=0, b2=1.

Пусть C((x) — полином, соответетвующий сигналам на выходах блока 4 поразрядного суммирования по модулю два, после прохождения i-ro по порядку счета тактового импульсного сигнала высокого уровня на тактовом входе устройства, где 1 < I < m 3. в;(х) — полином, соответствующий сигналам на выходах блока 1 умножения на примитивный элемент поля после прохождения 1-го по порядку счета тактового импульсного сигнала высокого уровня на тактовом входе устройства.

Тогда С1(х)-О+ bp а1(х)-1. а1(х)-О х +1 х.+1;

Сг(х) - С1(х) + b1 а1(х) а- С1(х) + О . а 1(х) а = С1(х);

Ca(x) - Ca(x) + ba а1(х) а а- C)(x) t 1 at(x) ах С1(х +

+а" а Ct(x)+tP-О х +1 х+

+1+1 х +1 х+1= х + 0 х + 0 =аР; с01 (х) - а1(х) ° a; пах) = а1(х) а2; са(х) = а1(х) г9;

Проверка: а1(х) аг(х) =а а - сР = a .

Работа устройства на приведенном примере приведена также при помощи временных диаграмм (см. фиг. 2).

Следовательно устройство работает правильно.

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

Таким образом, устройство при меньших аппаратурных затратах (уменьшение на

m-1 элементов И) сохраняет свою работо способность без снижения быстродействия (так же, как и прототип выполняет операцию умножения за m тактов работы).

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

Устройство для умножения полиноMÎB над конечными полями G F(2 ), содержащее блок умножения на примитивный элемент поля, сдвиговый регистр, элемент И и блок поразрядного суммирования по модулю два, причем информационные входы блока умножения на примитивный элемент поля являются входами коэффициентов первого полинома-сомножителя устройства, а информационные входы сдвигового регистра являются входами коэффициентов второго полинома-сомножителя устройства, выходы блока поразрядного суммирования по модулю два являются выходами коэффициентов полинома-произведения устройства, тактовые входы сдвигового регистра и блока умножения на примитивный элемент поля обьединены и являются тактовым входом устройства, при этом выход сдвигового регистра соединен с первым входом элемента °

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

И, второй вход которого соединен с тактовым входом устройства.

1698886

Составитель И.Ковалив

Техред M,Moðãåíòàë Корректор M.Kó÷åðÿâàÿ

Редактор M.Áàíäóðà

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 4397 Тираж Подписное

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

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