1
(21)4810366/24 (22) 04.04.90 (46)15.12.91. Бюл. №46 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72)И.И.Ковалив (53)681.325(088.8) (56) Авторское свидетельство СССР № 997039,кл. G 06 F15/31, 1981.
Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды. Вып. 5. М.: Связь, 1976, с.99, рис.3.30.
(5J) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИНОМОВ НАД КОНЕЧНЫМИ ПОЛЯМИ GF(2m)
(57) Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF (2™). Цель изобретения - уменьшение аппаратурных затрат устройства без снижения его быстродействия. Устройство содержит блок 1 умножения на примитивный элемент поля, сдвиговый регистр 2, элемент И 3 и блок 4 поразрядного суммирования по модулю два. 2 ил.
Ё
С Ю 00 00 00
о
Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF (2m).
Известно устройство умножения полиномов над конечными полями GF (), содержащее два m-разрядных регистра, двухвходовые элементы И и сумматоры по модулю два в количествег пропорциональном т, причем выходы т-разрядных регистров подключены к входам двухвходовых элементов И, выходы которых подключены к вход ам сумматоров по модулю два,, выходы которых являются выходами устройства.
Известно устройство умножения полиномов над конечными полями GF (2™), содержащее два m-разрядных регистра, m -двухзходовых элемента И, m m-входо- вых сумматоров по модулю два и т-1 матричных преобразователей, причем m выходов первого m-разрядного регистра подсоединены к объединенным первым входам m двухвходовых элементов И, образующих m групп по m двухвходовых элементов И соответственно, m выходов второго m-разрядного регистра подсоединены к объединенным одноименным m входам первого матричного преобразователя и вторым входам m двухвходовых элементов И первой группы из m двухвходовых элементов И соответственно, m выходов первых т-2 матричных преобразователей подсоединены к вторым входам m двухвходовых элементов И в группах, порядковые номера которых на единицу больше номеров матричных преобразователей соответственно и к одноимен- ным входам следующих матричных преобразователей за исключением последнего (m-1)-ro матр ичного преобразователя, выходы которого подсоединены только к вторым входам двухвходовых элементов И последней m-й группы двухвходовых элементов И соответственно, при этом выходы одноименных двухвходовых элементов И всех групп подключены к одноименным с группами элементов И входами одноименных с элементами И в каждой группе т-вхо- довых сумматоров по модулю два соответственно, выходы которых являются выходами устройства умножения соответственно.
Известно также устройство умножения полиномов над конечными полями GF (2m), содержащее два блока логарифмирования, один блок суммирования и один блок антилогарифмирования, причем входы блоков логарифмирования являются входами коэффициентов полиномов-сомножителей
соответственно, а выходы - подключены к двум группам входов блока суммирования соответственно, выходы которого подсоединены к входам блока антилогарифмирования соответственно, выходы которого являются выходами результата умножения. Недостатками известных устройств являются значительные аппаратурные затраты.
0 Известно устройства для умножения в конечных полях GF (2m), содержащее первый, второй и третий регистры, т-1 блокоч умножения и т элементов И, причем входы первого и третьего регистра являются вхо5 дами устройства коэффициентов первого и второго полиномов-сомножителей соответственно, а выходы второго регистра являются выходами устройства коэффициентов результирующего полинома, при этом т-й
0 выход первого регистра подсоединен с объединенным входам всех m элементов И, вторые входы которых подсоединены к выходам третьего регистра, а выходы - к первой группе информационных входов
5 второго регистра, m-й выход которого подсоединен к входам всех т-1 блоков умножения и к первому входу второй группы информационных входов второго регистра, причем выходы т-1 блоков умножения под0 соединены к остальным входам второй груп- пы информационных входов второго регистра, а тактовые входы первого и второго регистров объединены и являются тактовым входом устройства.
5 Указанное устройство при низких аппаратурных затратах выполняет операции умножения за т+1 тактов работы, т.е. имеет невысокое быстродействие.
Известно еще устройство для умноже0 ния полиномов над конечными полями GF (2т) по модулю два неприводимого многочлена, содержащее генератор импульсов, дешифратор, m двухвходовых элементов И и по одному блоку деления и умножения на
5 примитивный элемент поля, причем входы блоков деления и умножения на примитивный элемент поля являются входами устройства занесения коэффициентов первого и второго полиномов-сомножителей соответственно,
0 выходы блока деления на примитивный элемент поля подсоединены к входам дешифратора соответственно, выход которого подсоединен к объединенным первым входам m двухвходовых элементов Невыходы
5 которых являются выходами коэффициентов полинома - результата умножения устройства соответственно, а вторые входы подсоединены к выходам блока умножения на примитивный элемент поля соответственно, при этом тактовые входы блоков деления и умножения на примитивный элемент поля объединены и подсоединены к выходу генератора импульсов.
Недостатком такого устройства является низкое быстродействие, если первый полином-сомножитель соответствует степени примитивного элемента поля GF (2), большей, чем т/2, что в ряде случаев не позволяет его использовать, несмотря на его сравнительно низкие аппаратурные затраты.
Наиболее близким к предлагаемому по технической сущности и достигаемому результату при использовании является устройство умножения двух полиномов поля GF (2m), содержащее т-разрядный сдвиговый регистр, блок умножения на примитивный элемент поля, m-разрядный регистр поразрядного суммирования по модулю два (регистр V) и m двухвходовых элементов И, причем первый выход сдвигового регистра подсоединен к объединенным первым входам всех m двухвходовых элементов И, вторые входы которых подсоединены к m выходам блока умножения на примитивный элемент поля соответственно, а выходы - к входам m-разрядного регистра поразрядного суммирования по модулю два соответственно, m выходов которого являются выходами m коэффициентов полинома-произведения соответственно.
Недостатки известного устройства - его большие аппаратурные затраты.
Целью изобретения является уменьшение аппаратурных затрат устройства для умножения полиномов над конечными полями GF (2m) без снижения его быстродействия.
Поставленная цель достигается тем, что в устройстве умножения полиномов над конечными полями GF (2m), содержащем блок умножения на примитивный элемент поля, сдвиговый регистр, элемент И и блок поразрядного суммирования по модулю два. причем информационные входы бло-ка умножения на примитивный элемент поля являются входами коэффициентов первого полинома-сомножителя устройства, а информационные входы сдвигового регистра являются входами коэффициентов второго полинома-сомножителя устройства, выходы блока поразрядного суммирования по модулю два являются выходами коэффициентов результирующего полинома-произведения устройства, тактовые входы сдвигового регистра и блока умножения на примитивный элемент поля объединены и являются тактовым входом устройства, при этом выход сдвигового регистра подсоединен к первому входу элемента И, выходы блока умножения на примитивный элемент поля подсоединены к соответствующим информационным входам блока поразрядного суммирования по модулю два, тактовый
вход которого подсоединен к выходу элемента И, второй вход которого подсоединен к тактовому входу устройства.
Предложенные связи между известными элементами проявляют новое свойство:
уменьшаются аппаратурные затраты устройства для умножения двух полиномов над конечными полями GF (2m) без снижения быстродействия.
На фиг. 1 изображена структурная блоксхема устройства умножения полиномов над конечными полями GF (2m); на фиг. 2 - временные диаграммы работы устройства при m - 3, поле GF (23) образовано неприводимым многочленом f(x) х3 + х + 1, где х фиктивная переменная, используемая для записи полиномов, и устройство умножает первый многочлен, равный х + 1. на второй многочлен, равный х2+1.
Устройство умножения полиномов над
конечными полями GF (2™) содержит блок 1 умножения на примитивный элемент поля, сдвиговый регистр 2, элемент 3 И и блок 4 поразрядного суммирования по модулю два, причем информационные входы блока
1 умножения на примитивный элемент поля являются входами устройства коэффициентов первого полинома-сомножителя, а информационные входы сдвигового регистра 2 являются входами устройства коэффициентов второго полинома-сомножителя, при этом выход сдвигового регистра 2 подсоединен к первому входу элемента 3 И, а выходы блока 4 поразрядного суммирования по модулю два являются выходами устройства коэффициентов результирующего полинома- произведения, причем второй вход элемента 3 И подсоединен с объединенным тактовым входам блока 1 умножения на. примитивный элемент поля и сдвигового регистра 2 и является тактовым входом устройства, а выход элемента 3 И подсоединен к тактовому входу блока 4 поразрядного суммирования по модулю два.
Временные диаграммы работы устройства (фиг, 2) содержит пятнадцать зависимостей изменений уровней сигналов на входах и выходах устройства и его элементов по времени при выполнении устройством операции умножения полиномов х+1 и х +1 над конечным полем GF(23), образованным неприводимым многочленом f(x) х3 + х + 1. i
Буквенные выражения при временных диаграммах соответствуют следующим вхо- дам и выходам устройства и его элементов:
а) - вход первого коэффициента первого полинома устройства;
б)- вход второго коэффициента первого полинома устройства;
в)- вход третьего коэффициента первого полинома устройства;
г)- тактовый вход устройства;
д)- вход первого коэффициента второго полинома устройства;
е)- вход второго коэффициента второго полинома устройства;
ж) - вход третьего коэффициента второго полинома устройства;.
з)- первый выход блока 1 умножения на примитивный элемент поля;
и) - второй выход блока 1 умножения на примитивный элемент поля;
к) - третий выход блока 1 умножения на примитивный элемент поля;
л) - выход сдвигового регистра 2г
м) - тактовый вход блока 4 поразрядного суммирования по модулю два;
н) - выход первого коэффициента результирующего полинома устройства;
о) - выход второго коэффициента результирующего полинома устройства;
п) - выход третьего коэффициента результирующего полинома устройства;
Устройство умножения полиномов над конечными, полями GF () работает следующим образом.
В исходном состоянии устройства блок 1 умножения на примитивный элемент поля, сдвиговый регистр 2 и блок 4 поразрядного суммирования по модулю два установлены в нулевые состояния, а на тактовый вход устройства подается сигнал низкого уровня. При этом на всех выходах устройства сформированы сигналы низких уровней.
На первом шаге работы устройства на информационные входы блока 1 умножения на примитивный элемент поля и сдвигового регистра 2 подаются сигналы, соответствующие коэффициентам первого и второго полиномов-сомножителей соответственно, а затем на тактовый вход устройства подается импульсный сигнал высокого уровня, по переднему фронту которого, как и в прототипе, сигналы на входах устройства запоминаются соответственно в блоке 1 умножения на примитивный элемент поля и в сдвиговом регистре 2. Формирование сигналов на информационных входах блока 1 умножения и сдвигового регистра 2 необходимо произвести раньше переднего фронта тактового импульса для устойчивой работы устройства. При этом на выходах блока Т умножения на примитивный элемент поля, а значит, и на информационных входах блока 4 поразрядного суммирования по модулю
два формируются сигналы, соответствующие коэффициентам полинома-сомножителя, а на первом выходе сдвигового регистра 2, а значит, и на первом входе элемента 3 И
формируется сигнал, соответствующий коэффициенту при нулевой степени фиктивной переменной второго полинома- сомножителя.
Здесь и в-дальнейшем сигнал высокого
0 уровня соответствует коэффициенту полинома, равного единице, а сигнал низкого уровни - нулю.
После занесения коэффициентов полиномов-сомножителей на все входы устрой5 ства коэффициентов полиномов-сомножителей подаются сигналы низких уровней, как и при работе прототипа.
Если во время действия первого по порядку счета импульсного сигнала высокого
0 уровня при занесении коэффициентов полиномов-сомножителей на первом входе элемента 3 И сформируется сигнал высокого уровня, то на выходе элемента 3 И тоже сформируется сигнал высокого уровня (см.
5 фиг. 1, 2), по переднему фронту которого на выходах устройства сформируются сигналы, соответствующие коэффициентам первого полинома-сомножителя, При этом в блоке 1 умножения поля происходит умножение
0 полинома, соответствующего сигналам на выходах блока 1 умножения до подачи очередного тактового импульса на тактовый вход устройства на примитивный элемент поля, в сдвиговом регистре 2 на его выходе
5 формируется сигнал, соответствующий коэффициенту при очередной старшей степени фиктивной переменной второго полинома-сомножителя, а на выходе блока 4 поразрядного суммирования по модулю
0 два - сигналы либо не изменяются, если на выходе сдвигового регистра 2 формируется сигнал низкого уровня, либо сигналы, соответствующие поразрядному сложению коэффициентов полинома, соответствующего
5 сигналам на выходах блока 4 поразрядного суммирования до прихода очередного тактового импульса, и полинома, соответствующего сигналам на выходах блока 1 умножения на примитивный элемент поля
0 после поступления на тактовый вход устройства очередного тактового импульса, если на выходе сдвигового регистра 2 формируется сигнал высокого уровня.
Таким образом., за m тактов работы
5 предлагаемое устройство так же, как и прототип, выполняет операцию
т-1
ai(x); а2(х) - ai(x) (bm-ix 1 1 + bm-ax1™ +
+ ... + bix + bo) - ai(x) bo +
+ ai(x) bi x +... + ai(x) bm-t ai(x) bo + ai(x) a bi + ... +
+ ai(x) bm-1, где ai(x)- первый полином-сомножитель;
Э2(х) - второй полином-сомножитель;
х - фиктивная переменная, использующаяся для записи полиномов-элементов конечного поля GF(2m);
bo, bibm-1 - коэффициенты второго
полинома-сомножителя, причем bo, bi
bm-1 б GF(2);
а- примитивный элемент поля GF(2m), причем а- х.
Рассмотрим работу устройства (см. фиг.1) на следующем примере.
Пусть поле GF(23) образовано неприводимым многочленом f(x) х3 + х + 1 и устройство умножает полиномы; ai(x) х + 1 и Э2(х) х2 + 1.
Элемент поля GF(2 упорядочивается по порядку возрастания степеней примитивного элемента поля следующим образом:
0-х2 + 0-х + 0 0
О х2 + 0-х+1 о°
х + 0 а 1-х2 + 0-х + 0 о2
0 х2 + 1 х + 1 с
1 х2 + 1 х + 0 а4 1 х2 + 1 х + 1 а5- 1 х2 + о х + 1 а6.
При этом а7 а°, а8 а, а9 а2, а10 а3 и т.д., a ai(x) х + 1 0 х2 + 1 х + 1 сЛ| aa(x) х2 + + 0-х+1 а причем Ь0 1, bi 0, 02 1.
Пусть С|(х)- полином, соответствующий сигналам на выходах блока 4 поразрядного суммирования по модулю два, после прохождения 1-го по порядку счета тактового импульсного сигнала высокого уровня на тактовом входе устройства, где 1 Ј I m 3.. с(х) - полином, соответствующий сигналам на выходах блока 1 умножения на примитивный элемент поля после прохождения -го по порядку счета тактового импульсного сигнала высокого уровня на тактовом входе устройства.
Тогда Ci(x) 0 + bo ai(x) - 1 ai(x)- О х2 + 1 х + 1 ;
С2(х) - Ci(x) + bi -ai(x) -a Ci(x) + 0 ai(x) (x);
Сз(х)- Сг(х) + b2 ajfx) a a-Ci(x)+1 ai(x)(xH
+ or or- Ci(x) + or 0 x + 1 x +
+ 1 + 1 x + 1 x+1
-1 x2 + 0 x + 0 o2; (x) - ai(x) cc, (oiM
-ai(x) мз(х) ai(x) ($
Проверка: ai(x) a2(x) or or cc a . Работа устройства на приведенном примере приведена также при помощи временных диаграмм (см. фиг. 2).
Следовательно устройство работает
правильно.
Для выполнения следующей операции умножения устройства, как и прототип, необходимо сначала установить в его исходное состояние, а затем выполнить операцию
умножения в соответствии с временными диаграммами работы устройства (фиг. 2).
Таким образом, устройство при меньших аппаратурных затратах (уменьшение на т-1 элементов И) сохраняет свою работоспособность без снижения быстродействия (так же, как и прототип выполняет операцию умножения за m тактов работы).
Ф о р м у л а и з о б р е т е н и я„
Устройство для умножения полиномов
над конечными полями GF(2m), содержащее блок умножения на примитивный элемент поля, сдвиговый регистр, элемент И и блок поразрядного суммирования по модулю два, причем информационные входы блока
умножения на примитивный элемент поля являются входами коэффициентов первого полинома-сомножителя устройства, а информационные входы сдвигового регистра являются входами коэффициентов второго
полинома-сомножителя устройства, выходы блока поразрядного суммирования по модулю два являются выходами коэффициентов полинома-произведения устройства, тактовые входы сдвигового регистра и блока умножения на примитивный элемент поля объединены и являются тактовым входом устройства, при этом выход сдвигового регистра соединен с первым входом элемента И, отличающееся тем, что, с целью
уменьшения аппаратурных затрат без снижения быстродействия, выходы блока умножения на примитивный элемент поля соединены с соответствующими информационными входами блока поразрядного
суммирования по модулю два, тактовый вход которого соединен с выходом элемента И, второй вход которого соединен с тактовым входом устройства.
5 В
Ж 3
«
и к
л
4
м
4
//
О /7
