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

 

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

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

РЕСПУБЛИК (я)5 G 06 F 15/31 7/544

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

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

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСKOMУ СВИДЕТЕЛЬСТВУ (21) 4731705/24 (22) 24,08.89 (46) 23.10.91. Бюл. ¹ 39 (71) Научно-исследовательский институт бы.товой радиоэлектронной аппаратуры (72) И.И.Ковалив (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 1013950, кл. G 06 F 15/31, 1979.

Авторское свидетельство СССР № 1236464, кл. G 06 F 7/52, 1986. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИНОМОВ НАД ПОЛЯМИ GF/2 / (57) Изобретение относится к специализированным устройствам вычислительной техники и может использоваться в декодирующих устройствах. работающих с полиномами над конечными. полями GF/2 /, образованными неприводимыми многочлеИзобретение относится к специализированным устройствам вычислительной техники и может использоваться в декодирующих устройствах, работающих с полиномами над конечными полями

GF/2 /, образованными неприводимыми многочленами вида f(X) =Х + P — 1 Х 1+

+ ..+ P Х + 1, с примитивными элементами, равными Х, где X — фиктивная переменная, используемая для записи полиномов, Р коэффициенты многочлена при степенях фиктивной переменной; j3ЕОР/2 /,! = 1.; 2, ..., m-1, Цель изобретения — повышение быстродействия устройства для умножения полиномов над полями GF/2 /, На фиг. 1 представлена схема устройства для умножения полиномов над полями

„„Я „„1686457 А1 нами вида f(X)=X + j3m-1Х + ... + 1 X+ ", с примитивными элементами, равными Х, где Х вЂ” фиктивная переменная, используемая для записи пол ином оь, /л — коэффи циенты многочлена при степенях фиктивной переменной;,Я66Г/2 /, i =1,2, ..., m-1. ЦелЬ изобретения — повышение быстродействия устройства. Поставленная цель достигается тем, что устройство содержит первую и вторую группы по m триггеров 1 и 2, и умножителей 3 на примитивный элемент поля, и групп по m элементов И 4. где n — число одновременно суммируемых слагаемых произведения полиномов, первый и второй элементы ИЛИ-НЕ 5 и 6, группу из m сумма- ) торов 7 по модулю два, группу накапливающих сумматоров 8 по модулю два и блок 9 управления. 3 ил, GF/2" /; на фиг. 2 — схема блока управления; на фиг. 3 — схема группы из m триггеров.

Устройство содержит первую 1 и.вторую

2 группы по mтриггеров,,и умножителей 3 на примитивный элемент поля, где и — число одновременно суммируемых слагаемых произведения полиномов, и групп по m элементов И 4, первый и второй элементы ИЛИН 5, 6, группу из m сумматоров по модулю два 7, группу из m накапливающих сумматоров по модулю два 8, блок 9 управления, вход 10 признака запуска устройства, тактовый вход 11 устройства, выход 12 признака готовности результата устройства. Блок 9 управления содержит первый и второй элементы ИЛИ 13 и 14, триггер 15 и элемент И

16, Первая и вторая группы триггеров 1 и 2 содержат по m триггеров 17, 1686457

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

В исходном состоянии все триггеры 1 и

2 групп, накапливающие сумматоры 8 по модулю два и триггер 15 блока 9 управления обнулены, На вход 10 устройства и на установочные входы всех триггеров 1 и 2 поданы потенциалы, равные логическому нулю, На первом шаге работы устройства в триггеры 17 по их установочным входам заносятся коэффициенты первого и второго полиномов-сомножителей соответственно, после чего устройство становится готовым к вычислениям, при нулевых потенциалах на его входах первого и второго полиномов— сомножителей.

На втором шаге работы устройства, в зависимости от значений полиномов-сомножителей, возможны две процедуры его функционирования.

Первая процедура выполняется, если хотя бы один из полиномов-сомножителей равен нулю. При этом на выходе хотя бы одного из элементов ИЛИ.-НЕ 5 или 6 сформируется потенциал, равный логической единице, который поступит на вход режима блока 9 управления и сформирует на выходе элемента ИЛИ 13 потенциал, равный логической единице. Этот потенциал поступает на вход установки в ноль триггера 15, не разрешая установку его в единицу по остальным входам, на первый выход блока 9 управления и на выход 12 готовности результата устройства. Потенциал, равный логической единице на выходе 12 устройства, указывает на то, что на выходах накапливающих сумматоров по модулю два 8 сформированы потенциалы, .соответствующие коэффициентам полинома-произведения (результата умножения). Эти потенциалы будут равны нулю, так как все накапливающие сумматоры по модулю два 8 в исходном состоянии были обнулены, а на их тактовые входы не поступил ни один импульс, поскольку на выходетриггера 15сформирован потенциал, равный логическому нулю, который не разрешает прохождение тактовых импульсов на второй выход блока 9 управления.

Следовательно, если хотя бы один из полиномов-сомножителей равен нулю, то полином произведения тоже равен нулю, а результат вычисления формируется сразу же после занесения в устройство коэффициентов полиномов-сомножителей. Вторая процедура выполняется в случае, если ни один из полиномов-сомножителей не равен нулю. При этом на выходах умножителей 3 на примитивный элемент поля формируются потенциалы, соответствующие коэффи15

i 55 нях фиктивной переменной полинома, записанного в триггеры 2, значения которых на единицу меньше порядковых номеров элементов соответственно. На выходах элементов И 4 формируются потенциалы, равные либо потенциалам на одноименных выходах соответствующих умножителей 3 на примитивный элемент поля, если потенциалы на выходах соответвтвующих триггеров 2 равны логической единице, либо нулю, если потенциалы на выходах этих триггеров равны логическому нулю, На выходах сумматоров по модулю два 7 формируются потенциалы, равные результатам поразрядного суммирования помодулюдва потенциалов на выходах одноименных элементов И 4 групп соответственно. На информационных входах триггеров 17,1, 172, ..., 17п, второй группы при и < m/2, либо триггеров 171, 17,2, ..., 17.(m-п) при n > m/2 второй группы формируются потенциалы, равные потенциалам на выходах триггеров 17.(n+1), 17.(n+2), ...17n+n при

n < m/2, либо m-n-триггеров 17.п+1, 17n+2, ..., 17m при n > m/2 соответственно. На выходах элементов ИЛИ-НЕ 5 и 6 формируются потенциалы, равные логическому нулю, так как хотя бы на один из их входов каждого элемента ИЛИ-НЕ 5 и 6 поступает потенциал, равный логической единице. На первый и второй входы режима блока 9 управления поступают потенциалы, равные логическому нулю. Поэтому на выходе элемента ИЛИ

13 и входе установки в "0" триггера 15 и первом выходе блока 9 управления формируется потенциал, равный логическому нулю. Этот потенциал разрешает установку триггера 15 в "1", а также поступает на выход 12 готовности результата устройства, указывая на то, что потенциалы на выходах накапливающих сумматоров по модулю два

8, соответствующие коэффициентам полинома-произведения, еще не сформированы. В этом случае на вход 10 устройства подается импульс, который проходит через первыйвход элемента ИЛИ 14 на информационный вход триггера 15, который по очередному тактоциентам полиномов, равных произведениям примитивного элемента поля на полиномы, коэффициенты которых соответствуют потенциалам на входах умножителей 3 соот5 ветственно. На выходах и-го умножителя Зп на примитивный элемент поля и информационных входах триггеров формируются потенциалы, соответствующие коэффициентам полинома, который равен произведению

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

45

55 вому импульсу на его тактовом входе устанавливается в "1". Потенциал, равный логической единице, с выхода три гера 15 поступает на первый вход элемента И 16 и второй вход элемента ИЛИ 14. Тактовые импульсы, поступающие на тактовый вход блока 9 управления, проходят при потенциале, равном логической единице на его первом входе режима, на выход элемента И 16 и поступают на второй выход блока 9 управления. Потенциал, равный логической еди.нице на втором входе элемента ИЛИ 14, формирует на его выходе и информационном входе триггера 15 потенциал, равный логической единице. В этом случае триггер

15 может изменить свое состояние только при подаче потенциала, равного логической единице, на его вход установки в "0". Тактовые импульсы с второго выхода блока 9 управления поступают на тактовые входы всех триггеров 1, 2 и накапливающих сумматоров 8 по модулю два. Эти импульсы устанавливают триггеры 1 и 2 в состояния, соответствующие потенциалам на их информационных входах, при этом на выходах накапливающих сумматоров по модулю два

8 формируются потенциалы, соответствующие результату поразрядного суммирования по модулю два предыдущих логических состояний выходов накапливающих суматоров по модулю два 8 и логических сумматоров по модулю два 7. Тактовый импульс, поступающий на тактовые входы триггеров

17, устанавливает их в состояния, соответствующие коэффициентам полинома из поля GF/2 /, равного произведению полинома, записанного в эти триггеры до поступления тактового импульса на их так товые входы, íà и-ю степень примитивного элемента поля, Тактовый импульс, поступающий на тактовые входы триггеров 2, сдвигает коэффициенты, записанные в триггеры

17 этой группы, на и разрядов в сторону уменьшения индексов триггеров 17. Тактовый импульс, поступающий на тактовые входы накапливающих сумматоров по модулю два 8, обеспечивает выполнение суммирования по модулю два коэффициентов, записанных в накапливающие сумматоры по модулю два 8 до поступления на их тактовые входы тактового импульса, с коэффициентами, соответствующими потенциалам на одноименных выходах элементов И 4 через сумматоры по модулю 7 соответственно. Тактовые импульсы формируются на втором выходе блока 9 управления до тех пор, пока триггер 15 не установится в свое состояние. При реализации второй процедуры функционирования устройства потенциалы на выходах триггеров 1

35 соответствуют коэффициентам полиномов, не равных нулю, из поля GF/2 /. Поэтому на выходе элемента ИЛИ-НЕ 5 потенциал, равный логической единице, не сформируется. При поступлении на тактовые входы триггеров 2 тактовых импульсов, число которых равно ) m/и L. где п /и 4 — натуральное число, результат от округления m/n до ближайшего большего целого, все триггеры

17 этой группы устанавливаются в нулевое состояние, при этом на выходе второго элемента ИЛИ-НЕ 6 формируется потенциал, равный логической единице, который поступает на второй вход режима блока 9 управления и через элемент ИЛИ 13 устанавливает триггер 15 в свое состояние, при этом на втором выходе блока 9 управления перестают формироваться тактовые импульсы. В этом случае устройство переходит к режиму работы, определяемому первой процедурой функционирования устройства.

На выходе 12 готовности результата устройства формируется потенциал, равный логической единице, указывающий на то, что на выходах накапливающих сумматоров по модулю два 8 формируются потенциалы, соответствующие коэффициентам результирующего полинома-произведения. Таким образом, сдвиг коэффициентов, записанных в триггеры

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

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

Устройство для умножения полиномов над полями GF/2 /, содержащее первую и вторую группы из m триггеров в каждой(где

m — степень неприводимого многочлена поля), первый и второй умножители на примитивный элемент поля, первую и вторую группы элементов И, группу сумматоров по модулю два и группу накапливающих сумматоров по модулю два, причем входы первого полинома-сомножителя устройства подключены соответственно к установочным входам триггеров первой группы, выходы которых подключены соответственно к входам первого умножителя на примитивный элемент поля и соответственно к первым входам элементов И первой группы, выходы которых подключены соответственно к первым входам сумматоров по модулю два группы, выходы первого умножителя на примитивный элемент поля подключены соответственно к входам второго умножителя на примитивный элемент поля и соответст1686457 венно к первым входам элементов И второй группы, выходы которых подключены соответственно к вторым входам сумматоров по модулю два группы, выходы которых подключены соответственно к информационным входам накапливающих сумматоров по модулю два группы, выходы которых подключены соответственно к выходам произведения полиномов устройства, входы второго полинома-сомножителя которого подключены соответственно к установочным входам триггеров второй группы, выходы первого и второго триггеров второй группы подключены соответственно ко вторым входам И первой и второй групп, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит с третьего по и-й умножители на примитивный элемент поля (где и — число одновременно суммируемых слагаемых произведения полиномов), с третьей по и-ю группы элементов И, первый и второй элементы ИЛИ/I-НE и блок управления, причем выходы а-го умножителя на примитивный элемент поля(гдеа=2, ..., п-1) подключены соответственно к входам (а+1)го умножителя на примитивный элемент поля и соответственно к первым входам элементов И (а+1)-й группы, выходы элементов И Ь-й группы(где Ь-:-3,.„, п)подключены соответственно к b-м входам сумматоров по модулю два группы, выходы n-.ro умножителя на примитивный элемент поля подключены соответственно к информационным входам триггеров первой группы, выходы триггеров первой группы подключены к Вхо дам первого элемента ИЛИ-НЕ, выход которого подключен к первому входу режима блока управления, первый выход которого подключен к выходу признака готовности результата устройства, вход признака запуска и тактовый вход которого подключены соответственно к входу запуска и тактовому входу блока управления, второй выход которого подключен к тактовым входам всех на5 капливающих сумматоров по модулю два группы, всех триггеров первой и второй групп, выходы первого и второго триггеров второй группы подключены соответственно к первому и второму входам второго элемен10 та ИЛИ-НЕ, выход b-ro триггера второй группы подключен ко вторым входам элементов И 0-й группы и b-му входу второго элемента ИЛИ-НЕ, выходы триггеров с (и+1)-го по m-й второй группы триггеров под15 ключены соответственно к входам с (и+1)-ro по m-й второго элемента ИЛИ-НЕ и входам установки триггеров с первого по (m-и)-й второй группы, входы установки триггеров с

/m-(и+1)/-го по m-й подключены к входу ну20 левого потенциала устройства, выход второго элемента ИЛИ-НЕ подключен к второму входу режима блока управления, причем блок управления содержит первый и второй элементы ИЛИ, триггер и элемент И, при

25 этом в блоке управления первый и второй входы режима и вход запуска блока управления подключены соответственно к первому, второму входам первого элемента ИЛИ и первому входу второго элемента ИЛИ, вы30 ход которого подключен к информационному входу триггера, выход которого подключен к первому входу элемента И и второму входу второго элемента ИЛИ, выход первого элемента ИЛИ подключен к вхо35 ду установки в "0" триггера и первому выходу блока управления, тактовый вход которого подключен к тактовому входу триггера и второму входу элемента И, выход которого подключен к второму выходу блока

40 управления.

1686457

1686457

Составитель А,Смирнов

Техред М,Моргентал Корректор М.Демчик

Редактор T.Øàãîâà

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

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

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

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