1
(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/2m/
(57)Изобретение относится к специализированным устройствам вычислительной тех- ники и может использоваться в декодирующих устройствах, работающих с полиномами над конечными полями GF/2m/, образованными неприводимыми многочленами вида f(X) Xm + + ... +/7i X + 1. с примитивными элементами, равными X, где X - фиктивная переменная, используемая для записи полиномов-, коэффициенты многочлена при степенях фиктивной
переменной;/3|еСР/2т/, 1 1,2т-1. Цель
изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что устройство содержит первую и вторую группы по m триггеров 1 и 2, п умножителей 3 на примитивный элемент поля, п групп по m элементов И 4, где п - число одновременно суммируемых слагаемых произведения полиномов, первый и второй элементы ИЛИ-НЕ 5 и 6, группу из m сумматоров 7 по модулю два, группу накапливающих сумматоров 8 по модулю два и блок 9 управления.3 ил.
(Л
С
Изобретение относится к специализированным устройствам вычислительной тех- ники и может использоваться в декодирующих устройствах, работающих с полиномами над конечными полями GF/2m/. образованными неприводимыми
многочленами вида f(X) + - 1 Xm 1 + + ..+ /$ X + 1, с примитивными элементами, равными X, где X - фиктивная переменная, используемая для записи полиномов, ($ - коэффициенты многочлена при степенях фиктивной переменной; / ifGF/2m/, 1 1,2, ..., m-1,
Цель изобретения - повышение быстродействия устройства для умножения полиномов над полями GF/2m/.
На фиг. 1 представлена схема устройства для умножения полиномов над полями
GF/2m/: на фиг. 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 содержат no m триггеров 17.
О 00
с
ел
vj
Устройство работает следующим образом.
В исходном состоянии все триггеры 1 и 2 групп, накапливающие сумматоры 8 по модулю два и триггер 15 блока 9 управления обнулены. На вход 10 устройства и на установочные входы всех триггеров 1 и 2 поданы потенциалы, равные логическому нулю.
На первом шаге работы устройства в триггеры 17 по их установочным входам за- носятся коэффициенты первого и второго полиномов-сомножителей соответственно, после чего устройство становится готовым к вычислениям, при нулевых потенциалах на его входах первого и второго полиномов - сомножителей.
На втором шаге работы устройства, в зависимости от значений полиномов-сомножителей, возможны две процедуры его функционирования.
Первая процедура выполняется, если хотя бы один из полиномов-сомножителей равен нулю. При этом на выходе хотя бы одного из элементов ИЛИ-НЕ 5 или 6 сформируется потенциал, равный логической единице, который поступит на вход режима блока 9 управления и сформирует на выходе элемента ИЛИ 13 потенциал, равный логической единице. Этот потенциал поступает на вход установки в ноль триггера 15, не разрешая установку его в единицу по остальным входам, на первый выход блока 9 управления и на выход 12 готовности результата устройства. Потенциал, равный логической единице на выходе 12 устройства, указывает на то, что на выходах накапливающих сумматоров по модулю два 8 сформированы потенциалы, .соответствующие коэффициентам полинома-произведения (результата умножения), Эти потенциалы будут равны нулю, так как все накапливающие сумматоры по модулю два 8 в исходном состоянии были обнулены, а на их тактовые входы не поступил ни один импульс, поскольку на выходе триггера 15 сформирован потенциал, равный логическому нулю, который не разрешает прохождение тактовых импульсов на второй выход блока 9 управления.
Следовательно, если хотя бы один из полиномов-сомножителей равен нулю, то полином произведения тоже равен нулю, а результат вычисления формируется сразу же после занесения в устройство коэффициентов полиномов-сомножителей. Вторая процедура выполняется в случае, если ни один из полиномов-сомножителей не равен нулю. При этом на выходах умножителей 3 на примитивный элемент поля формируются потенциалы, соответствующие коэффициентам полиномов, равных произведениям примитивного элемента поля на полиномы, коэффициенты которых соответствуют потенциалам на входах умножителей 3 соответственно. На выходах n-го умножителя З.п на примитивный элемент поля и информационных входах триггеров формируются потенциалы, соответствующие коэффициентам полинома , который равен произведению полинома, записанного в триггеры 1, на п-ю степень примитивного элемента поля. На выходах триггеров 2 на первом шаге работы устройства сформированы потенциалы, соответствующие коэффициентам при степенях фиктивной переменной полинома, записанного в триггеры 2,значения которых на единицу меньше порядковых номеров элементов соответственно. На выходах элементов И 4 формируются потенциалы, равные либо потенциалам на одноименных выходах соответствующих умножителей 3 на примитивный элемент поля, если потенциалы на выходах соответствующих триггеров 2 равны логической единице, либо нулю, если потенциалы на выходах этих триггеров равны логическому нулю. На выходах сумматоров по модулю два 7 формируются потенциалы, равные результатам поразрядного суммирования по модулю два потенциалов на выходах одноименных элементов И 4 групп соответственно. На информационных входах
триггеров 17.1. 17.2 17п. второй группы
при п т/2, либо триггеров 17.1. 17.2
п т/2. либо m-n-триггеров 17.П+1,17ги-2
17т при п т/2 соответственно. На выходах элементов ИЛИ-НЕ 5 и 6 формируются потенциалы, равные логическому нулю, так как хотя бы на один из их входов каждого элемента ИЛИ-НЕ 5 и 6 поступает потенциал, равный логической единице. На первый и второй входы режима блока 9 управления поступают потенциалы, равные логическому нулю. Поэтому на выходе элемента ИЛИ 13 и входе установки в О триггера 15 и первом выходе блока 9 управления формируется потенциал, равный логическому нулю. Этот потенциал разрешает установку триггера 15 в Г, а также поступает на выход 12 готовности результата устройства, указывая на то, что потенциалы на выходах накапливающих сумматоров по модулю два 8, соответствующие коэффициентам полинома-произведения, еще не сформированы. В этом случае на вход 10 устройства подается импульс, который проходит через первыйвход элемента ИЛИ 14 на информационный вход триггера 15, который по очередному тактовому импульсу на его тактовом входе устанавливается в 1. Потенциал, равный логической единице, с выхода триггера 15 поступает на первый вход элемента И 16 и второй вход элемента ИЛИ 14. Тактовые импульсы, поступающие на тактовый вход блока 9 управления, проходят при потенциале, равном логической единице на его первом входе режима, на выход элемента И 16 и поступают на второй выход блока 9 управления. Потенциал, равный логической единице на втором входе элемента ИЛИ 14, формирует на его выходе и информационном входе триггера 15 потенциал, равный логической единице. В этом случае триггер 15 может изменить свое состояние только при подаче потенциала, равного логической единице, на его вход установки в О. Тактовые импульсы с второго выхода блока 9 управления поступают на тактовые входы всех триггеров 1, 2 и накапливающих сумматоров 8 по модулю два. Эти импульсы устанав- ливают триггеры 1 и 2 в состояния, соответствующие потенциалам на их информационных входах, при этом на выходах накапливающих сумматоров по модулю два 8 формируются потенциалы, соответствующие результату поразрядного суммирования по модулю два предыдущих логических состояний выходов накапливающих сумато- ров по модулю два 8 и логических сумматоров по модулю два 7. Тактовый импульс, поступающий на тактовые входы триггеров 17, устанавливает их в состояния, соответствующие коэффициентам полинома из поля GF/2m/, равного произведению полинома, записанного в эти триггеры до поступления тактового импульса на их тактовые входы, на n-ю степень примитивного элемента поля. Тактовый импульс, поступающий на тактовые входы триггеров 2, сдвигает коэффициенты, записанные в триггеры 17 этой группы, на п разрядов в сторону уменьшения индексов триггеров 17. Тактовый импульс, поступающий на тактовые входы накапливающих сумматоров по модулю два 8, обеспечивает выполнение суммирования по модулю два коэффициентов, записанных в накапливающие сумматоры по модулю два 8 до поступления на их тактовые входы тактового импульса, с коэффициентами, соответствующими потенциалам на одноименных выходах элементов И 4 через сумматоры по модулю 7 соответственно. Тактовые импульсы формируются на втором выходе блока 9 управления до тех пор, пока триггер 15 не установится в свое состояние. При реализации второй процедуры функционирования устройства потенциалы на выходах триггеров 1
соответствуют коэффициентам полиномов, не равных нулю, из поля GF/2m/. Поэтому на выходе элемента ИЛИ-НЕ 5 потенциал, равный логической единице, не сформиру- 5 ется. При поступлении на тактовые входы триггеров 2 тактовых импульсов, число которых равно Jm/nL. где Jm/nt,- натуральное число, результат от округления m/n до ближайшего большего целого, все триггеры
0 17 этой группы устанавливаются в нулевое состояние, при этом на выходе второго элемента ИЛИ-НЕ 6 формируется потенциал, равный логической единице, который поступает на второй вход режима блока 9 управ5 ления и через элемент ИЛИ 13 устанавливает триггер 15 в свое состояние, при этом на втором выходе блока 9 управления перестают формироваться тактовые импульсы. В этом случае устройство переходит
0 к режиму работы, определяемому первой процедурой функционирования устройства. На выходе 12 готовности результата устройства формируется потенциал, равный логической единице, указывающий на то, что на
5 выходах накапливающих сумматоров по модулю два 8 формируются потенциалы, соответствующие коэффициентам результирующего полинома-произведения. Таким образом, сдвиг коэффициентов, записанных в триггеры
0 2, на п разрядов и преобразование коэффициентов, записанных в триггерах по каждому тактовому импульсу, а также соответствующее их суммирование обеспечивает в этом случае повышение быстродей5 ствия устройства для умножения полиномов над полями GF/2m/ в m/ im/ п1.раз.
Формула изобретения Устройство для умножения полиномов
0 над полями-GF/2m/. содержащее первую и вторую группы из m триггеров в каждой (где m - степень неприводимого многочлена поля), первый и второй умножители на примитивный элемент поля, первую и вторую
5 группы элементов И, группу сумматоров по модулю два и группу накапливающих сумматоров по модулю два, причем входы первого полинома-сомножителя устройства подключены соответственно к установоч0 ным входам триггеров первой группы, выходы которых подключены соответственно к входам первого умножителя на примитивный элемент поля и соответственно к первым входам элементов И первой группы,
5 выходы которых подключены соответственно к первым входам сумматоров по модулю два группы, выходы первого умножителя на примитивный элемент поля подключены соответственно к входам второго умножителя на примитивный элемент поля и соответстпенно к первым входам элементов И второй группы, выходы которых подключены соответственно к вторым входам сумматоров по модулю два группы, выходы которых подключены соответственно к информационным входам накапливающих сумматоров по модулю два группы, выходы которых подключены соответственно к выходам произведения полиномов устройства, входы второго полинома-сомножителя которого подключены соответственно к установочным входам триггеров второй группы, выходы первого и второго триггеров второй группы подключены соответственно ко вторым входам И первой и второй групп, отличающееся тем, что, с целью повышения быстродействия, оно содержит с третьего по n-й умножители на примитивный элемент поля (где п число одновременно суммируемых слагаемых произведения полиномов), с третьей по n-ю группы элементов И, первый и второй элементы ИЛИ-НЕ и блок управления, причем выходы а-го умножителя на
примитивный элемент поля (где а 2п-1)
подключены соответственно к входам (а+1)- го умножителя на примитивный элемент поля и соответственно к первым входам элементов И (а+1)-й группы, выходы элементов И b-й группы (где b 3п) подключены
соответственно к b-м входам сумматоров по модулю два группы, выходы п-го умножителя на примитивный элемент поля подключены соответственно к информационным входам триггеров первой группы, выходы триггеров первой группы подключены к входам первого элемента ИЛИ-НЕ. выход которого подключен к первому входу режима блока управления, первый выход которого подключен к выходу признака готовности результата устройства, вход признака запуска и тактовый вход которого подключены соответственно к входу запуска и тактовому входу блока управления, второй выход которого подключен к тактовым входам всех накапливающих сумматоров по модулю два
группы, всех триггеров первой и второй
групп, выходы первого и второго триггеров
второй группы подключены соответственно
к первому и второму входам второго элемента ИЛИ-НЕ, выход Ь-го триггера второй группы подключен ко вторым входам элементов И b-й группы и b-му входу второго элемента ИЛИ-НЕ, выходы триггеров с (п+1)-го по m-й второй группы триггеров подключены соответственно к входам с (п+1)-го по m-й второго элемента ИЛИ-НЕ и входам установки триггеров с первого по (т-п)-й второй группы, входы установки триггеров с /m-{n+1)/-ro по m-й подключены к входу нулевого потенциала устройства, выход второго элемента ИЛИ-НЕ подключен к второму входу режима блока управления, причем блок управления содержит первый и второй элементы ИЛИ, триггер и элемент И, при
этом в блоке управления первый и второй входы режима и вход запуска блока управления подключены соответственно к первому, второму входам первого элемента ИЛИ и первому входу второго элемента ИЛИ, выход которого подключен к информационному входу триггера, выход которого подключен к первому входу элемента И и второму входу второго элемента ИЛИ, выход первого элемента ИЛИ подключен к входу установки в О триггера и первому выходу блока управления, тактовый вход которого подключен к тактовому входу триггера и второму входу элемента И. выход которого подключен к второму выходу блока
управления.
77
Фиг Л
Фиг. 2
о4о х /7,
ФиеЗ
