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

ий институт быпаратуры о СССР1981.бобщенные каязь, 1976, с.99,ОЖЕНИЯ ПОЛМИ ПОЛЯМИ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ УМНИНОМОВ НАД КОНЕЧНЬ6 Р(2 )(57) Изобретение относится к специали рованным цифровым вычислительным у ройствам и может использоваться декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей ОР (2 п). Цель изобретения - уменьшение аппаратурных затрат устройства без снижения его быстродействия. Устройство содержит блок 1 умножения на примитивный элемент поля, сдвиговый регистр 2, элемент И 3 и блок 4 поразрядного суммирования по модулю два, 2 ил.Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей ОР (2),Известно устройство умножения полиномов над конечными полями ОЕ (2"), со, держащее два т-разрядных регистра,двухвходовые элементы И и сумматоры по , модулю два в количестве, пропорциональ ном а, причем выходы т-разрядных регистров подключены к входам. двухвходовых элементов И, выходы которых подключены к входам сумматоров по модулю два, выходы которых являются выходами устройства.Известно устройство умножения полиномое над конечными полями ОР (2 ), содержащее. два п 1-разрядных регистра, гп -двухвходовых элемента И, гп а-входо 2еых сумматоров по модулю два и щматричных преобразователей, причем п 1 выходов первого гп-разрядного регистра подсоединены к объединенным первым входам гп двухвходовых элементов И, образующих гп групп по гп двухеходовых элементов И соответственно, гп выходов второго п-разрядного регистра подсоединены к объединенным одноименным гп входам первого матричного преобразователя и вторым входам в двухеходовых элементов И первой группы из гп двухвходовых элементов И соответственно, гп выходов первых вматричных .преобразователей подсоединены к вторым входам гп двухвходовых элементов И в группах, порядковые номера которых на единицу больше номеров матричных преобразователей соответственно и к одноименн ым входам следующих матричных преобразователей за исключением последнего (п 1-1)-го матричного преобразователя, выходы которого подсоединены только к вторым входам деухеходовых элементов И последней а-й группы двухвходовых элементов И соответственно, при этом выходы одноименных двухвходовых элементов И всех групп подключены к одноименным с группами элементов И входами одноименных с элементами И в каждой группе щ-еходовых сумматоров по модулю два соответственно, выходы которых являются выходами устройства умножения соответственно.Известно также устройство умножения полиномое над конечными полями ОЕ (2 ), содержащее два блока логарифмирования, один блок суммирования и один блокантилогарифмирования, причем входы блоков логарифмирования являются входами коэффициентов полиномов-сомножителей 5 10 15 20 25 30 35 40 45 50 55 соответственно, а выходы. - подключены к двум группам входов блока суммирования соответственно, выходы которого подсоединены к входам блока антилогарифмирования соответственно, выходы которого являются выходами результата умножения,Недостатками известных устройств являются значительные аппаратурные затраты.Известно устройства для умножения в конечных полях ОР.(2), содержащее первый, второй и третий регистры, вблоков умножения и гп элементов И, причем входы первого и третьего регистра являются входами устройства коэффициентов первого и второго полиномов-сомножителей соответственно, а выходы второго регистра являются выходами устройства коэффициентов результирующего полинома, при этом а-й выход первого регистра подсоединен с объединенным входам всех а элементов И, вторые входы которых подсоединены к выходам третьего регистра, а выходы - к первой группе информационных входов второго регистра, а-й выход которого подсоединен к входам всех вблоков умножения и к первому входу второй группы информационных входов второго регистра, причем выхоры вблоков умножения подсоединены к остальным входам второй группы информационных входов второго регистра, а тактовые входы первого и второго регистров объединены и являются тактовым входом устройства.Указанное устройство при низких аппаратурных затратах выполняет операции умножения за в+1 тактов работы, т.е, имеет невысокое быстродействие.,Известно еще устройство для умножения полиномов над конечными полями ОР (2 ) по модулю два неприводимого много- члена, содержащее генератор импульсов, дешифратор, гп двухвходовых элементов И и по одному блоку деления и умножения на примитивный элемент поля, причем входы блоков деления и умножения на примитивный элемент поля являются входами устройства занесения коэффициентов первого и второго полиномов-сомножителей соответственно, выходы блока деления на примитивный элемент поля подсоединены к входам дешифратора соответственно, выход которого подсоединен к объединенным первым входам гп двухеходовых элементов И;выходы которых являются. выходами коэффициентов полинома - результата умножения устройства соответственно, а вторые входы подсоединены к выходам блока умножения на примитивный элемент поля соответственно, при этом тактовые входы блоков де 1698886510 15 20 25 30 35 40 45 50 55 ления и умножения на примитивный элемент поля объединены и подсоединены к выходу генератора импульсов.Недостатком такого устройства является низкое быстродействие, если первый полином-сомножитель соответствует степени примитивного элемента поля ОЕ (2 п), большей, чем е/2, что в ряде случаев не позволяет его использовать, несмотря на его сравнительно низкие аппаратурные затраты.Наиболее близким к предлагаемому по технической сущности и достигаемому результату при использовании является устройство умножения двух полиномов поля ОЕ (2 ), содержащее гп-разрядный сдвиговый регистр,.блок умножения на примитивный элемент поля, в-разрядный регистр поразрядного суммирования по модулю два (регистр /) и гп двухвходовых элементов И, причем первый выход сдвигового регистра подсоединен к объединенным первым входам всех гп двухвходовых элементов И, вторые,входы которых подсоединены к гп выходам блока умножения на примитивный элемент поля соответственно, а выходы - к входам в-разрядного регистра поразрядного суммирования по модулю два соответственно, в выходов которого являются выходами щ коэффициентов полинома-произведения соответственно.Недостатки известного устройства - его большие аппаратурные затраты.Целью изобретения является уменьшение аппаратурных затрат устройства для умножения полиномов над конечными полями ОГ (2 ) без снижения его быстродействия.Поставленная цель достигается тем, что в устройстве умножения полиномов над конечными полями ОР (2 ), содержащем блок умножения на примитивный элемент поля, сдвиговый регистр, элемент И и блок поразрядного суммирования по модулю два, причем информационные входы блока умножения на примитивный элемент поля являются входами коэффициентов первого полинома-сомножителя устройства, а информационные входы сдвигового регистра являются входами коэффициентов второго полинома-сомножителя устройства, выходы блока поразрядного суммирования по модулю два являются выходами коэффициентов результирующего полинома-произведения устройства, тактовые входы сдвигового регистра и блока умножения на примитивный элемент поля объединены и являются тактовым входом устройства, при этом выход сдвигового регистра подсоединен к первому входу элемента И, выходы блока умножения на примитивныйэлемент поля подсоединены к соответствующим информационным входам блока поразрядного суммирования по модулю два, тактовый вход которого подсоединен к выходу элемента И, второй вход которого подсоединен к тактовому входу устройства.Предложенные связи между известными элементами проявляют новое свойство; уменьшаются аппаратурные затраты устройства для умножения двух полиномов над конечными полями ОЕ (2) без снижения быстродействия.На фиг, 1 изображена, структурная блоксхема устройства умножения полиномов над конечными полями ОЕ (2 ); на фиг, 2 - временные диаграммы работы устройства при а -3; поле ОЕ (2 з) образовано неприводимым многочленом (х) - х + х+ 1, где х -зфиктивная переменная, используемая для записи полиномов, и устройство умножает первый многочлен, равный х + 1, на второй многочлен, равный х +1.Устройство умножения полиномов над конечными полями ОЕ (2) содержит блок 1 умножения на примитивный элемент поля, сдвиговый регистр 2, элемент 3 И и блок 4 поразрядного суммирования по модулю два, причем информационные входы блока 1 умножения на примитивный элемент поля являются входами устройства коэффициентов первого полинома-сомножителя, а информационные входы сдвигового регистра 2 являются входами устройства коэффициентов второго полинома-сомножителя; при этом выход сдвигового регистра 2 подсоединен к первому входу элемента 3 И, а выходы блока 4 поразрядного суммирования по модулю два являются выходами устройства коэффициентов результирующего полиномапроизведения, причем второй вход элемента 3 И подсоединен с объединенным тактовым входам блока 1 умножения на, примитивный элемент поля и сдвигового регистра 2 и является тактовым входом устройства, а выход элемента 3 И подсоединен к тактовому входу блока 4 поразрядного суммирования по модулю два,Временные диаграммы работы устройства (фиг, 2) содержит пятнадцать зависимостей изменений уровней сигналов на входах и выходах устройства и его элементов по времени при выполнении устройством операции умножения полиномов х+1 и х +1 над конечным полем ОЕ(2 З), образованным не- приводимым многочленом т(х) = х + х+ 1.Буквенные выражения при временных диаграммах соответствуют следующим входам и выходам устройства и его элементов:5 10 20 30 35 40 45 50 55 а) - вход первого коэффициента первого полинома устройства;б) - вход второго коэффициента первого полинома устройства; .в) - вход третьего коэффициента первого полинома устройства;г) - тактовый вход устройства;д)- вход первого коэффициента второго ,полинома устройства;е)- вход второго коэффициента второго полинома устройства;ж) - вход третьего коэффициента второго полинома устройства;з) - первый выход блока 1 умножения на примитивный элемент поля;и) - второй выход блока 1 умножения на примитивный элемент поля;к) - третий выход блока 1 умножения на примитивный элемент поля,л) - выход сдвигового регистра 2;м) - тактовый вход блока 4 поразрядного суммирования по модулю два;н) - выход первого коэффициента ре,зультирующего полинома устройства;о) - выход второго коэффициента результирующего полинома устройства;и) - выход третьего коэффициента результирующего полинома устройства,Устройство умножения полиномов над конечными полями ОР (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 формируется сигнал высокого уровня,Таким образом, за в тактов работы предлагаемое устройство так же, как и прототип, выполняет операциюа 1(х) а 2(х) - а 1(х)(Ь .1 хп" + Ь .2 х" 2++ а 1(х) а Ьп)-1,где а 1(х) - первый полином-сомножитель;а 2(х) - второй полином-сомножитель;х - фиктивная переменная, использующаяся для записи полиномов-элементов конечного поля ОЦ 2 );Ьо, Ь 1, , Ьп)-1 - . коэффициенты второгополинома-сомножителя, причем Ьо, Ь 1, ,ЬОЦ 2);а - примитивный элемент поля ОГ(2 П),причем а = х.Рассмотрим работу устройства (см.фиг.1) на следующем примере,Пусть поле ОЦ 2 з) образовано неприводимым многочленом 1(х) = х + х+1 и устройство умножает полиномы; а 1(х) = х+ 1 ид 2(х) = х + 1.Злемент поля ОГ(2 ) упорядочиваетсяпо порядку возрастания степеней примитивного элемента поля следующим образом:0 х +О х+0=00 х +О х+1=сРО х +1 х+О=а1 х +О х+О=а 2О х +1 х+1=сР1 х 2+1 х+О=а 41 х +1 х+1=ав1 х+О х+1=а 6.При этом а" =сР, сР =а, сР =сР, а 1 о=сРит.д., а а 1(х)=х+1=0 х +1 х+1=аиа 2(х) = х + 1 - х + 0 х+ 1 = а, причем Ьо - 1,2Ь 1=0, Ь 2=1.Пусть С)(х) - полином, соответетвующийсигналам на выходах блока 4 поразрядногосуммирования по модулю два, после прохождения 1-го по порядку счета тактовогоимпульсного сигнала высокого уровня натактовом входе устройства, где 1( в 3.в;(х) - полином, соответствующий сигналамна выходах блока 1 умножения на примитивный элемент поля после прохождения 1-гопо порядку счета тактового импульсногосигнала высокого уровня на тактовом входеустройства.Тогда С 1(х)-О+ Ьо а 1(х)-1. а 1(х)- -0 х +1 х+1;С 2(х) - С 1(х)+ Ь 1 а 1(х) а- С 1(х)+ 0 а 1(х) а= С 1(х);Схх)-СХ(х)+Ьх ах) а а- СЯх) +а)х) аф С(х +- а 1(Х) аф; йа(х) = а 1(х) а;Проверка: а 1(х) а 2(х) =ад а - а) = а 2. Работа устройства на приведенном примере приведена также при помощи временных диаграмм (см. фиг. 2).Следовательно устройство работает правильно.Для выполнения следующей операции умножения устройства, как и прототип, необходимо сначала установить в его исходное состояние, а затем выполнить операцию умножения в соответствии с временными диаграммами работы устройства (фиг, 2).Таким образом, устройство при меньшихаппаратурныхэатратах(уменьшение на гпэлементов И) сохраняет свою работо- способность без снижения быстродействия (так же, как и прототип выполняет операцию умножения за а тактов работы).Формула изобретения Устройство для умножения полиномов над конечными полями ОР(2 ), содержащее блок умножения на примитивный элемент поля, сдвиговый регистр, элемент И и блок поразрядного суммирования по модулю два, причем информационные входы блока умножения на примитивный элемент поля являются входами коэффициентов первого полинома-сомножителя устройства, а информационные входы сдвигового регистра являются входами коэффициентов второго полинома-сомножителя устройства, выходы блока поразрядного суммирования по модулю два являются выходами коэффициентов полинома-произведения устройства, тактовые входы сдвигового регистра и блока умножения на примитивный элемент поля обьединены и являются тактовым входом устройства, при этом выход сдвигового регистра соединен с первым входом элемента И, отл и ч а ю щ е е с я тем, что, с целью уменьшения аппаратурных затрат беэ снижения быстродействия, выходы блока умножения на примитивный элемент поля соединены с соответствующими информационными входами блока поразрядного суммирования по модулю два, тактовый вход которого соединен с выходом элемента И, второй вход которого соединен с тактовым входом устройства.1698886Составитель И,Ковалив Редактор М.Бандура Техред М,Моргентал Корректор М.Кучерявая каз 4397 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Рауаская наб., 4/5роизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 10