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

 

Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF(2m). Цель изобретения - повышение быстродействия устройства . Поставленная цель достигается тем, что устройство содержит два блока 1 и 2 умножения полиномов на примитивный элемент поля GF(2m). где m - степень неприводимого многочлена поля, генератор 3 тактовых импульсов, дешифратор 4, элементы И 5i, 625m группы, с первого по четвертый элементы ИЛИ 6-9, первый и второй элементы И 10 и 11, триггер 12, первый и второй элементы ИЛИ-НЕ 13 и 14 и элемент НЕ 15. 1 ил.

СОЮЗ СОВЕТСКИХ социллистических

РЕСПУБЛИК (я)л 6 06 F 15/31

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

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

ПРИ ГКНТ СССР— ...1 . Х Р У

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

27n-.

1

{21) 4712658/24 (22) 29.06.89 (46) 15.06.91. Бюл. 3Ф 22 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И.И.Ковалив и З.Д.Коноплянко (53) 681.325(088,8) (56) Авторское свидетельство СССР

М 997039, кл. G 06 F 15/31, 1983.

Авторское свидетельство СССР

М 989559, кл. G 06 F 15/31, 1980. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ПОЛИНОМОВ НАД КОНЕЧНЫМИ ПОЛЯМИ GF(2 ) (57) Изобретение относится к специализированным цифровым вычислительным

„„. Ы,, 1656551 А1 устройствам и может использоваться в декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF(2 ). Цель изобретения — повышение быстродействия устройства. Поставленная цель достигается тем, что устройство содержит два блока 1 и

2 умножения полиномов на примитивный элемент поля GF(2 ), где m — степень неприводимого многочлена поля, генератор 3 тактовых импульсов, дешифратор 4, элементы

И 51, 52,..., 5 группы, с первого по четвертый элементы ИЛИ 6-9, первый и второй элементы И 10 и 11, триггер 12, первый и второй элементы ИЛИ вЂ” НЕ 13 и 14 и элемент

НЕ 15, 1 ил.

1656551 его функционирования

20

30

Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF(2 ).

Цель изобретения — повышение быстродействия устройства, На чертеже представлена схема устройства для деления полиномов над конечными полями GF(2m).

Устройство для деления полиномов над конечными полями GF(2 ) содержит первый и второй блоки 1 и 2 умножения полиномов на примитивный элемент в поле GF(2 ), ге нератор 3 тактовых импульсов, дешифратор

4, элементы И 5i, 5z,..., Sm группы, с первого по четвертый элементы ИЛИ 6 — 9, первый и второй элементы И 10 и 11, триггер 12, пер, вый и второй элементы ИЛИ-HE 13 и 14, элемент НЕ 15, первый и второй входы 16 и

17 синхронизации, входы делителя и делимого 18 и 19, вход 20 запуска, выходы 21 результата, выход 22 признака запрещения деления, выход 23 признака готовности результатаа устройства.

Устройство для деления полиномов над конечными полями GF(2 ) работает следующим образом.

В исходном состоянии, триггер 12 обнулен. На входы 16 — 20 поданы нулевые потенциалы. На выходе триггера 12 присутствует нулевой потенциал, На выходах элементов

ИЛИ 6 — 8 присутствуют нулевые потенциалы, Поэтому импульсы, поступающие с выхода генератора 3, не установят в единичное состояние триггер 12. Деление полиномов осуществляется за два шага работы устройства.

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

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

17 и 16. Синхронизирующий импульс, подаваемый на вход 17, поступает на второй вход элемента ИЛИ 7, передается на его выход и поступает на вход синхронизации блока 1. Синхрониэирующий импульс, подаваемый на вход 16 устройства, поступает на второй вход элемента ИЛИ 8, передается на его вход синхронизации блока 2. Этим обеспечивается возможность неодновременного поступления на входы 18 и 19 устройства коэффициентов полиномов делителя и делимого. После занесения коэффициентов полиномов делителя и делимого в блоки 1 и 2 устройство готово к выполнению вычисления результата деления.

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

В первом случае полином-делимое равен нулю, полином-делитель не равен нулю.

При этом на все выходы блока 2 умножения поданы нулевые потенциалы и хотя бы на один из выходов блока 1 подан единичный потенциал. В этом случае на выходе элемента ИЛИ вЂ” НЕ 13 формируется нулевой потенциал, а на выходе элемента ИЛИ вЂ” НЕ 14— единичный потенциал, который поступает на первый вход элемента ИЛИ 9 и формирует на его выходе единичный потенциал независимо от потенциала, подаваемого на

его второй вход.

Нулевой потенциал с выхода элемента

ИЛИ вЂ” HE 13 поступает на выход 22 признака запрещения деления, указывая, что деление не запрещено, а также на вход элемента НЕ

15, формируя при этом на его выходе единичный потенциал, Единичные потенциалы с выходов элемента ИЛИ 9 и элемента НЕ 15 поступают на входы элемента И 11, с выхода которого сигнал поступает на вход установки в ноль триггера 12 и на выход 23 устройства. Потенциал, равный логической единице, на входе установки в ноль триггера 12 не изменит его состояния, так как в исходном состоянии триггер 12 обнулен, а на первом шаге работы устройства его состояние не изменялось. Следовательно, как и в исходном состоянии устройства, на выходе триггера 12, элемента И 10 и элементов ИЛИ 6 — 8 нулевые потенциалы и, следовательно, на входы синхронизации блоков 1 и 2 синхроимпульсы не поступают. По нулевым потенциалам на первых входах всех элементов И 5 сформируются нулевые потенциалы. Единичный потенциал, поступающий на выход 23 готовности результата устройства, указывает, что на выходе 21 сформированы потенциалы, соответствующие коэффициентам полиномачастного, все значения которых равны нулю.

Во втором случае полином-делитель равен нулю. При этом на все выходы блока 1 поданы нулевые потенциалы, которые поступают на все входы дешифратора 4 и на все входы элемента ИЛИ вЂ” НЕ 13.

На выходе элемента ИЛИ-Н Е 13 формируется единичный потенциал, который поступает на выход 22 запрещения деления и указывает на то, что возникла запрещенная операция деления на нуль. Кроме того, единичный потенциал поступает на вход эле1656551

40

50 вые потенциалы мента НЕ 15, формирует на его выходе нулевой потенциал, который поступает на вто- рой вход элемента И 11 и в свою очередь формирует на его выходе, а значит, на входе установки в ноль триггера 12 и на выходе 23 готовности результата устройства нулевой потенциал. Этим обеспечивается запрещение функционирования устройства при делении на нуль.

В третьем случае полином-делимое не равен нулю, полином-делитель равен единице.

При этом на первом выходе блока 1 сформирован единичный потенциал, а на остальных выходах блока 1 сформированы нулевые потенциалы. Эти потенциалы подаются на все входы элемента ИЛИ вЂ” НЕ 13 и на все входы дешифратора 4, На выходе элемента ИЛИ вЂ” НЕ 13 формируется нулевой потенциал, который поступает на вход элемента HF 15 и на выход 22 запрещения деления. Этот потенциал формирует на выходе элемента НЕ 15 и на втором входе элемента И 11 единичный потенциал. Единичный потенциал поступает на вторые входы всех элементов И 5, разрешая передачу потенциалов на их выходы, а также поступает на второй вход элемента ИЛИ 9, в результате чего на его выходе и на первом входе элемента И 11 формируется единичный потенциал. Единичный потенциал на выходе

23 готовности результата указывает на то, что на выходах 21 результата деления сформированы потенциалы, соответствующие коэффициентам полинома-частного.

Единичный потенциал на входе установки в ноль триггера 12 не разрешит установку триггера 12 в единицу и, соответственно, прохождение импульсов с выхода генератора 3 через элементы И 10 и ИЛИ 7 и 8 на входы синхронизации блоков 1 и 2.

Поэтому потенциалы на выходах 21 результата не изменяются.

В четвертом случае полинам-делимое не равен нулю, полином-делитель не равен ни нулю, ни единице.

При этом на выходе триггера 12 обоих элементов ИЛИ вЂ” НЕ 13 и 14, а также на выходе дешифратора 4 сформированы нулеНулевой потенциал с выхода элемента

ИЛИ-НЕ 13 поступает на вход элемента НЕ

15 и на выход 22 запрещения деления, указывая, что деление полиномов не запрещено. Этот потенциал формирует на выходе элемента НЕ 15 и на втором входе элемента

И 11 — единичный потенциал. Нулевой потенциал с выхода дешифратора 4 поступает на вторые входы всех элементов И 5 и на второй вход элемента ИЛИ 9. Нулевой по5

25 тенциал с выхода элемента ИЛИ вЂ” НЕ 14 по- :: ступает на первый вход элемента ИЛИ 9.

На выходе элемента ИЛИ 9 формируется нулевой потенциал, который подается на первый вход элемента И 11, на выходе которого тоже формируетися нулевой потенциал, При совпадении потенциалов, равных логическому нулю, на выходах 22 и 23 устройства на вход 20 подается импульс, который поступает на первый вход элемента

ИЛИ 6, на втором входе которого сформирован нулевой потенциал. Этот импульс поступает на информационный вход триггера 12.

Припоступлении из генератора 3 очередного импульса на вход синхронизации триггера 12 при наличии единичного потенциала на его информационном входе триггер 12 устанавливается в единицу. Единичный потенциал поступает на первый вход элемента

И 10 и на второй вход элемента ИЛИ 6.

Потенциал равен логической единице. Единичный потенциал на первом входе элемента И 10 разрешит прохождение íà его выход импульсов, поступающих с выхода генератора 3 на его второй вход. Эти импульсы с выхода элемента И 10 поступают на первые входы элементов ИЛИ 7 и 8. С выходов элементов ИЛИ 7 и 8 сигналы поступают на входы синхронизации блоков 1, 2. По каждому импульсу, поступающему на входы синхронизации блоков 1 и 2, производится умножение их содержимого на примитивный и элемент поля G F(2 ), который равен комбинации сигналов "010.;.0". Этим обеспечивается задание начала функционирования устройства и синхронизация его работы в составе декодирующих устройств при выполнении каждой операции деления.

Единичный потенциал на первом входе элемента ИЛИ 6 формирует на его выходе и на информационном входе триггера 12 сигнал, равный логической единице. Следовательно, импульсы, поступающие на вход синхронизации триггера 12, не изменят его состояния и на входы синхронизации блоков 1 и 2 импульсы с выхода генератора 3 поступают до тех пор, пока на вход установки в ноль триггера 12 не поступит единичный потенциал.

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

В результате последовательного умножения содержимых блоков 1 и 2 умножения на примитивный элемент поля на первом

1656551 элемент поля ОР(2 ), выходы первого блока умножения на примитивный элемент поля ды синхронизации подключены соответственно к вторым входам третьего и второго элементов ИЛИ.

Составитель В. Смирнов

Редактор М.Недолуженко Техред М.Моргентал Корректор. l4.Демчик

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

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 выходе блока 1 сформируется единичный потенциал, а на остальных выходах блока 1 сформируются нулевые потенциалы. В этом случае устройство переходит к режиму работы, соответствующему третьему случаю функционирования устройства, Следовательно, на вход установки в ноль триггера 12 с выхода элемента И 11 поступает единичный потенциал и на выходе элемента И 10 сформируется нулевой потенциал. Поэтому импульсы из выхода генератора 3 не проходят на входы синхронизации блоков 1 и 2 не изменяются. Результатом деления полиномов на выходах

21 устройства будет содержимое блока 2 умножения, так как на вторые входы всех элементов И 5 с выхода дешифратора 4 поступает единичный потенциал.

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

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

Для выполнения следующей операции деления полиномов необходимо привести устройство в исходное состояние и приведенные в описании два шага работы, следующие за исходным состоянием.

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

Устройство для деления полиномов над конечными полями GF(2 ), содержащее первый и второй блоки умножения на примитивный элемент поля GF(2 ), где m — степень неприводимого многочлена поля, дешифратор, генератор тактовых импульсов и группу элементов И, причем входы делителя и делимого устройства подключены соответственно к информационным входам первого и второго блоков умножения на примитивный

GF(2 ) подключены к входам дешифратора, выход которого подключен к первым входам

5 элементов И группы, выходы которых подключены к выходам результата устройства, выходы второго блока умножения на примитивный элемент поля GF(2 ) подключены со*ответственно к вторым входам элементов И

10 группы, отличающееся тем,что,с целью увеличения быстродействия, оно содержит первый и второй элементы ИЛИНЕ, с первого по четвертый элементы ИЛИ, триггер, элемент НЕ, первый и второй эле15 менты И, причем выходы первого блока умножения на примитивный элемент в поле

GF(2 ) подключен к входам первого элемента ИЛИ-НЕ, выход которого подключен к входу элемента НЕ и к выходу признака

20 запрещения деления устройства, вход запуска которого подключен к первому входу первого элемента ИЛИ, выход которого подключен к информационному входу триггера, выход которого подключен к второму входу

25 первого элемента ИЛИ и к первому входу первого элемента И, выход которого подключен к первым входам второго и третьего элементов ИЛИ, выходы которых подключены соответственно к входам синхронизации

30 первого и второго блоков умножения на . примитивный элемент в поле GF(2 ), выходы второго блока умножения на примитивный элемент в поле 6Р(2 ) подключены к входам второго элемента ИЛИ-НЕ, выход

35 которого подключен к первому входу четвертого элемента ИЛИ, выход которого подключен к первому входу второго элемента

И, выход которого подключен к выходу признака готовности результата устрой40 ства и к входу установки в "0" триггера, выход дешифратора подключен к второму входу четвертого элемента ИЛИ, выход элемента НЕ подключен к второму входу второго элемента И, выход генератора тэк45 товых импульсов подключен к входу синхронизации триггера и к второму входу первого элемента И, первый и второй вхо