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

(51)5 О 0 1, 7/544 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ПИСАНИЕ БРЕТЕНИ ВТОР С КОМУ СВИДЕТЕЛЬСТВУ(46) 23.10.91. Бюл. М 39 где Х - фиктивная переменная, используе(71) Научно-исследовательский институт бы- мая для записи полиномоь, ф - коэффици.товой радиоэлектронной аппаратуры енты многочлена при степенях фиктивной(56) Авторское свидетельство СССР устройства. Поставленная цель достигаетсяВ 1013950, кл, О 06 Р 15/31, 1979 тем, что устройство содержит первую и втоАвторское свидетельство СССР рую группы по ги триггеров 1 и 2, и умножиМ 1236464, кл, О 06 Г 7/52, 1986 телей 3 на примитивный элемент поля, и(54)УСТРОЙСТВОДЛЯУМНОЖЕНИЯ ПОЛ- групп по ги элементов И 4. где и - числоИНОМОВ НАД ПОЛЯМИ ОР/2/ одновременно суммируемых слагаемых(57) Изобретение относится к специализи- произведения полиномов, первый и второйрованным устройствам вычислительной тех- элементы ИЛИ-НЕ 5 и 6, группу из ги сумманики и может использоваться в торов 7 помодулюдва,группунакапливаюдекодирующих устройствах, работающих с щих сумматоров 8 по модулю два и блок 9полиномами над конечными полями ОЕ/2/, управления. 3 ил,образованными неприводимыми многочлеИзобретение относится к специализированным устройствам вычислительной техники и может использоваться в.декодирующих устройствах, работающих сполиномами над конечными полямиОГ/2/, образованными неприводимымимногочленами вида 1(Х) = Х+,В - 1 Х 1++ + Я Х + 1, с примитивными элементами,равными Х, где Х - фиктивная переменная,используемая для записи полиномов, 3коэффициенты многочлена при степеняхфиктивной переменной; Р ЕОР/2/, = 1.; 2,, 1 и,Цель изобретения - повышение быстродействия устройства для умножения полиномов над полями ОР/2/,На фиг. 1 представлена схема устройства для умножения полиномов над полями ОЕ/2" /; на фиг. 2 - схема блока управления; на фиг. 3 - схема группы из ги триггеров.Устройство содержит первую 1 и.вторую 2 группы по ги триггеров, и умножителей 3 на примитивный элемент поля, где и - число одновременно суммируемых слагаемых произведения полиномов, и групп по ги элементов И 4, первый и второй элементы ИЛИНЕ 5, 6, группу из ги сумматоров по модулю два 7, группу из ги накапливающих сумматоров по модулю два 8, блок 9 управления, вход 10 признака запуска устройства, тактовый вход 11 устройства, выход 12 признака готовности результата устройства, Блок 9 управления содержит первый и второй элементы ИЛИ 13 и 14, триггер 15 и элемент И 16, Первая и вторая группы триггеров 1 и 2 содержат по ги триггеров 17,1686457 15 20 30 35 40 45 50 55 Устройство работает следующим образом.В исходном состоянии все триггеры 1 и 2 групп, накапливающие сумматоры 8 по модулю два и триггер 15 блока 9 управления обнулены, На вход 10 устройства и на установочные входы всех триггеров 1 и 2 поданы потенциалы, равные логическому нулю,На первом шаге работы устройства в триггеры 17 по их установочным входам заносятся коэффициенты первого и второго полиномов-сомножителей соответственно, после чего устройство становится готовым к вычислениям, при нулевых потенциалах на его входах первого и второго полиномов - сомножителей.На втором шаге работы устройства, в зависимости от значений полиномов-сомножителей, возможны две процедуры его функционирования.Первая процедура выполняется, если хотя бы один из полиномов-сомножителей равен нулю. При этом на выходе хотя бы одного из элементов ИЛИ-НЕ 5 или 6 сформируется потенциал, равный логической единице, который поступит на вход режима блока 9 управления и сформирует на выходе элемента ИЛИ 13 потенциал, равный логической единице, Этот потенциал поступает на вход установки в ноль триггера 15, не разрешая установку его в единицу по остальным входам, на первый выход блока 9 управления и на выход 12 готовности результата устройства. Потенциал, равный логической единице на выходе 12 устройства, указывает на то, что на выходах накапливающих сумматоров по модулю два 8 сформированы потенциалысоответствующие коэффициентам полинома-произведения (результата умножения). Эти потенциалы будут равны нулю, так как все накапливающие сумматоры по модулю два 8 в исходном состоянии были обнулены, а на их тактовые входы не поступил ни один импульс, поскольку на выходетриггера 15 сформирован потенциал, равный логическому нулю, который не разрешает прохождение тактовых импульсов на второй выход блока 9 управления.Следовательно, если хотя бы один из полиномов-сомножителей равен нулю, то полином произведения тоже равен нулю, а результат вычисления формируется сразу же после занесения в устройство коэффициентов полиномов-сомножителей. Вторая процедура выполняется в случае, если ни один из полиномов-сомножителей не равен нулю, При этом на выходах умножителей 3 на примитивный элемент поля формируются потенциалы, соответствующие коэффициентам полиномов, равных произведениям примитивного элемента поля на полиномы, коэффициенты которых соответствуют потенциалам на входах умножителей 3 соот 5 ветственно. На выходах и-го умножителя Зпна примитивный элемент поля и информационных входах триггеров формируются потенциалы, соответствующие коэффициентам полинома, который равен произведению 10 полинома, записанного в триггеры 1, на п-ю степень примитивного элемента поля. На выходах триггеров 2 на первом шаге работы устройства сформированы потенциалы, соответствующие коэффициентам при степенях фиктивной переменной полинома, записанного в триггеры 2, значения которых на единицу меньше порядковых номеров элементов соответственно. На выходах элементов И 4 формируются потенциалы, равные либо потенциалам на одноименных выходах соответствующих умножителей 3 на примитивный элемент поля, если потенциалы на выходах соответвтвующих триггеров 2 равны логической единице, либо нулю, если потенциалы на выходах этих триггеров равны логическому нулю, На выходах сумматоров по модулю два 7 формируются потенциалы, равные результатам поразрядного суммирования помодулюдва потенциалов на выходах одноименных элементов И 4 групп соответственно. На информационных входах триггеров 17,1, 172, ., 17 п, второй группы при ив/2, либо триггеров 17.1, 17,2, , 17.(в-п) при игп/2 второй группы формируются потенциалы, равные потенциалам на выходах триггеров 17.(п+1), 17.(п+2), 17 п+и при и ( щ/2, либо гп-и-триггеров 17.п+1, 17 п+2, ., 17 щ при игп/2 соответственно. На выходах элементов ИЛИ-НЕ 5 и 6 формируются потенциалы, равные логическому нулю, так как хотя бы на один из их входов каждого элементаИЛИ-НЕ 5 и 6 поступает потенциал,равный логической единице, На первый и второй входы режима блока 9 управления поступают потенциалы, равные логическому нулю. Поэтому на выходе элемента ИЛИ 13 и входе установки в "0" триггера 15 и первом выходе блока 9 управления формируется потенциал, равный логическому нулю. Этот потенциал разрешает установку триггера 15 в "1", а также поступает на выход 12 готовности результата устройства,указывая на то, что потенциалы на выходах накапливающих сумматоров по модулю два 8, соответствующие коэффициентам полинома-произведения, еще не сформированы, В этом случае на вход 10 устройства подается импульс, который проходит через первыйвход элемента ИЛИ 14 на информационный вход триггера 15, который по очередному такто 168645740 45 50 55 вому импульсу на его тактовом входе устанавливается в "1", Потенциал, равный логической единице, с выхода тригера 15 поступает на первый вход элемента И 16 и второй вход элемента ИЛИ 14. Тактовые импульсы, поступающие на тактовый вход блока 9 управления, проходят при потенциале, равном логической единице на его первом входе режима, на выход элемента И 16 и поступают на второй выход блока 9 управления. Потенциал, равный логической еди.- нице на втором входе элемента ИЛИ 14, формирует на его выходе и информационном входе триггера 15 потенциал, равный логической единице. В этом случае триггер 15 может изменить свое состояние только при подаче потенциала, равного логической единице, на его вход установки в "0", Тактовые импульсы с второго выхода блока 9 управления поступают на тактовые входы всех триггеров 1, 2 и накапливающих сумматоров 8 по модулю два, Эти импульсы устанавливают триггеры 1 и 2 в состояния, соответствующие потенциалам на их информационных входах, при этом на выходах накапливающих сумматоров по модулю два 8 формируются потенциалы, соответствующие результату поразрядного суммирования по модулю два предыдущих логических состояний выходов накапливающих суматоров по модулю два 8 и логических сумматоров по модулю два 7. Тактовый импульс, поступающий на тактовые входы триггеров 17, устанавливает их в состояния, соответствующие коэффициентам полинома из поля С Е/2/, равного произведению полинома, записанного в эти триггеры до поступления тактового импульса на их так- товые входы, на л-ю степень примитивного элемента поля, Тактовый импульс, поступающий на тактовые входы триггеров 2, сдвигает коэффициенты, записанные в триггеры 17 этой группы, на и разрядов в сторону уменьшения индексов триггеров 17. Тактовый импульс, поступающий на тактовые входы накапливающих сумматоров по модулю два 8, обеспечивает выполнение суммирования по модулю два коэффициентов, записанных в накапливающие сумматоры по модулю два 8 до поступления на их тактовые входы тактового импульса, с коэффициентами, соответствующими потенциалам на одноименных выходах элементов И 4 через сумматоры по модулю 7 соответственно, Тактовые импульсы формируются на втором выходе блока 9 управления до тех пор, пока триггер 15 не установится в свое состояние. При реализации второй процедуры функционирования устройства потенциалы на выходах триггеров 1 5 10 15 20 25 30 35 соответствуют коэффициентам полиномов, не равных нулю, из поля ОЕ/2 /. Поэтому на выходе элемента ИЛИ-НЕ 5 потенциал, равный логической единице, не сформируется. При поступлении на тактовые входы триггеров 2 тактовых импульсов, число которых равно 1 щ/п, где 1 п/п. - натуральное число, результат от округления п/и до ближайшего большего целого, все триггеры 17 этой группы устанавливаются в нулевое состояние, при этом на выходе второго элемента ИЛИ-НЕ 6 формируется потенциал, равный логической единице, который поступает на второй вход режима блока 9 управления и через элемент ИЛИ 13 устанавливает триггер 15 в свое состояние, при этом на втором выходе блока 9 управления перестают формироваться тактовые импульсы, В этом случае устройство переходит к режиму работы, определяемому первой процедурой функционирования устройства. На выходе 12 готовности результата устройства формируется потенциал, равный логической единице, указывающий на то, что на выходах накапливающих сумматоров по модулю два 8 формируются потенциалы, соответствующие коэффициентам результирующего полинома-произведения. Таким образом, сдвиг коэффициентов, записанных в триггеры 2, на и разрядов и преобразование коэффициентов, записанных в триггерах по каждому тактовому импульсу, а также соответствующее их суммирование обеспечивает в этом случае повышение быстродействия устройства для умножения полиномов над полями ОЕ/2 / в гп/Ьщ/ .п 1.раз. Формула изобретения Устройство для умножения полиномов над полями 6 Е/27, содержащее первую и вторую группы из в триггеров в каждой(где а - степень неприводимого многочлена поля), первый и второй умножители на примитивный элемент поля, первую и вторую группы элементов И, группу сумматоров по модулю два и группу накапливающих сумматоров по модулю два, причем входы первого полинома-сомножителя устройства подключены соответственно к установочным входам триггеров первой группы, выходы которых подключены соответственно к входам первого умножителя на примитивный элемент поля и соответственно к первым входам элементов И первой группы, выходы которых подключены соответственно к первым входам сумматоров по модулю два группы, выходы первого умножителя на примитивный элемент поля подключены соответственно к входам второго умножителя на примитивный элемент поля и соответст 1686457венно к первым входам элементов И второй группы, выходы которых подключены соответственно к вторым входам сумматоров по модулю два группы, выходы которых подключены соответственно к информационным входам накапливающих сумматоров по модулю два группы, выходы которых подключены соответственно к выходам произведения полиномов устройства, входы второго полинома-сомножителя которого подключены соответственно к установочным входам триггеров второй группы, выходы первого и второго триггеров второй группы подключены соответственно ко вторым входам И первой и второй групп, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит с третьего по и-й умножители на примитивный элемент поля (где и - число одновременно суммируемых слагаемых произведения полиномов), с третьей по и-ю группы элементов И, первый и второй элементы ИЛИ-НГ и блок управления, причем выходы а-го умножителя на примитивный элемент поля (где а = 2, . , п) подключены соответственно к входам (а+1)- го умножителя на примитивный элемент поля и соответственно к первым входам элементов И (а+1)-й группы, выходы элементов И Ь-й группы(где Ь-.:-.3,., и) подключены соответственно к Ь-м входам сумматоров по модулю два группы, выходы п-.го умножителя на примитивный элемент поля подключены соответственно к информационным входам триггеров первой группы, выходы триггеров первой группы подключены к входам первого элемента ИЛИ-НЕ, выход которого подключен к первому входу режима блока управления, первый выход которого подключен к выходу признака готовности результата устройства, вход признака запуска и тактовый вход которого подключены соответственно к входу запуска и тактовому входу блока управления, второй выход которого подключен к тактовым входам всех на капливающих сумматоров по модулю двагруппы, всех триггеров первой и второй групп, выходы первого и второго триггеров второй группы подключены соответственнок первому и второму входам второго элемен та ИЛИ-НЕ, выход Ь-го триггера второйгруппы подключен ко вторым входам элементов И Ь-й группы и Ь-му входу второго элемента ИЛИ-НЕ, выходы триггеров с (и+1)-го по в-й второй группы триггеров под ключены соответственно к входам с (и+1)-гопо пт-й второго элемента ИЛИ-НЕ и входам установки триггеров с первого по (т-и)-й второй группы, входы установки триггеров с /пз-(и+1)/-го по т-й подключены к входу ну левого потенциала устройства, выход второго элемента ИЛИ-НЕ подключен к второму входу режима блока управления, причем блок управления содержит первый и второй элементы ИЛИ, триггер и элемент И, при 25 этом в блоке управления первый и второйвходы режима и вход запуска блока управления подключены соответственно к первому, второму входам первого элемента ИЛИ и первому входу второго элемента ИЛИ, вы ход которого подключен к информационному входу триггера, выход которого подключен к первому входу элемента И и второму входу второго элемента ИЛИ, выход первого элемента ИЛИподключен к вхо ду установки в "0" триггера и первомувыходу блока управления, тактовый вход которого подключен к тактовому входу триггера и второму входу элемента И, выход которого подключен к второму выходу блока 40 управления.1686457 Составитель А,Смирн Техред М,Моргентал Корректор М.Дем ктор Т,Шаго иэводственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 10 Заказ 3599 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раушская наб 4/5