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

 

Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в кодирующих и декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF (2<SP POS="POST">M</SP>), образованных неприводимыми многочленами вида F(X) = X<SP POS="POST">M</SP> + β<SB POS="POST">M-1</SB>X<SP POS="POST">M-1</SP> + ... + β<SB POS="POST">1</SB>X + 1. Цель изобретения - расширение функциональных возможностей за счет реализации операции деления полиномов. Устройство содержит два M-разрядных регистра 1 и 2, блок 3 деления, два блока 4 и 5 умножения, два дешифратора 6 и 7 нуля, дешифратор 8, группу 9 элементов И, коммутатор 10, элементы И 11, 12 и 13, элементы ИЛИ 14, 15, элемент НЕ 16 и элемент 17 памяти. 5 ил.

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

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

РЕСПУБЛИК

С 06 F 7/52, 15/31

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

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

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

ПО ИЗОБРЕТЕНИЯМ И OTHPblTHRM

flPH П(НТ СССР (21) 4744527/24 (22) 24.08.89 (46) 07,07,91. Бюл, В 25 (71) Научно-исследовательский институт бытовой радиоэлектронной аппара-. туры (72) И.И.Ковалив (53) 681.325 (088.8) (56) Авторское свидетельство СССР

В 1013950, кл, С 06 F 7/52, 1982.

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

У 997039, кл. G 06 F 15/31, 1981. (19) (11)

А1

2 (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОЛИНОМОВ НАД КОНЕЧНЫМИ ПОЛЯМИ СР(2" )

ПО МОДУЛЮ НЕПРИВОДИМОГО МНОГОЧЛЕНА (57) Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в кодирующих и декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF(2 ), образованных неприводимыми многочленами вида f (x) = х + „„,х +...+P, х+1.

1661759 тора 6 и 7 нуля, дешифратор 8, группу 9 элементов И, коммутатор 10, элементы И 11, 12 и 13, элементы

ИЛИ 14, 15, элемент HE 16 и элемент

17 памяти. 5 ил.

Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в

Кодирующих и декодирующих устройст- 15

Вах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF(2"), образованных неприводимыми многочленами- вида

f (x) = х +p>, х +...+p, х+1, где х — 20 фиктивная переменная, используемая ля записи полиномов конечных полей, коэффициенты при степенях фиктивной переменной, причем Р; ЕGF",2), 1 2 . . m-1 а примитивный эле- 25 э ° ° ° „ э мент поля GF(2 ) OL= х, Целью изобретения является расширение функциональных возможностей за счет реализации операции деления полиномов. ЗО

На фиг.1 изображена функциональная схема устройства на фиг.2 — схема m-разрядного регистра; на фиг.3,схема блока деления; на фиг.4 — схема блока умножения, на фиг.5 — схема дешифратора, 1

Устройство для умножения полиномов над конечными полями GF(2 ) (фиг. 1) содержит два m-разрядных 0 регистра 1 и 2, блок 3 деления, два блока 4 и 5 умножения, два дешифратора 6 и 7 нуля, дешифратор 8, группу элементов И 9, коммутатор 10, элементы И 11-13, элементы ИЛИ 14 и 15, 45 элемент НЕ 16, элемент 17 памяти, вход 18 кода операции устройства, выходы неопределенности 19 и готов-. ности 20 результата устройства, вход . 21 начала вычисления устройства,тактовый вход 22 устройства, m-разрядные регистры 1 и 2 параллельные (фиг. 2) содержат m элементов 23 памяти. ъ

Блок деления 3 (фиг. 3) содержит

k двухвходовых сумматоров 24 по моду лю два, где k — - число ненулевых коэффициентов при степенях фиктивной переменной не равных ни нулю, ни m

Цель изобретения — расширение функциональных возможностей за счет реализации операции деления полиномов.

Устройство содержит два m-разрядных регистра 1 и 2, блок 3 деления, два блока 4 и 5 умножения, два дешифранеприводимом многочлене, образующем поле поминомов GF(2 ), У)

Блоки умножения 4 и 5 (фиг ° 4) содержат k двухвходовых сумматоров 25 по модулю два. Блоки умножения и деления предназначены соответственно для умножения и деления полиномов на примитивный элемент поля °

Дешифратор 8 (фиг.5) содержит элемент НЕ 26 и дешифратор 27 нуля.

Индексы при номерах элементов, порядковые номера входов и выходов блоков и устройства, изменяющихся от

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

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

GF(2 ) работает следующим образом.

В исходном состоянии (фиг.1 и 2) элемент 17 памяти устройства и все элементы 23 памяти m-разрядных ре гистров 1 и 2 обнулены. На тактовый вход 22 устройства поступает непрерывная серия тактовых импульсов, а на остальные входы устройства поступают сигналы логического нуля. Логический нуль на входе 18 кода операции устройства соответствует операции умножения полиномов. Логическая единица на входе 18 кода операции устройства соответствует операции деления полиномов. При этом на выходе элемента 17 памяти, а значит на выходах элементов И 13 и ИЛИ 15, на всех выходах m-разрядных регистров 1 и 2, а значит и на выходах элементов И 9 группы, являющихся выходами результата операции устройства, сформированы сигналы логического нуля.

Так как на выходах m-разрядных регистров 1 и 2 сформированы сигналы логического нуля, то на выходах де61759 6

5,16 шифраторов 6 и 7 нуля формируются сигналы логической единицы. Следовательно, на выходе элемента ИЛИ 14, .а значит на одном из входов элемента И 12 сформирован сигнал логической единицы. На другом входе элемента И 12 тоже сформирован сигнал логической единицы, поскольку на выходе элемента И 11 сформирован сигнал логического нуля.. Следовательно, на выходе элемента И 12, являющимся выходом 20 готовности результата устройства, сформирован сигнал логической единицы, который указывает на то, что на выходах результата операции устройства сформирован полином-произведение, В исходном состоянии результат операции равен нулю и соответствует результату умножения двух полиномов, равных нулю.

Если же при исходном состоянии устройства на вход 18 кода операции устройства подан сигнал логической единицы, то на выходе элемента И 11, являющимся выходом 19 неопределенности результата устройства, формируется сигнал логической единицы, который указывает на то, что результат деления неопределен, При этом на выходе элемента И 12 формируется сигнал логического нуля, указывая на то, что на выходах элементов И 9 группы результат операции деления не сформирован.

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

Если в m-разрядный регистр 1 зане-. сен полином, равный единице поля

GF(2 ), то на его первом выходе, а значит и на выходе дешифратора 8 формируется сигнал логической единицы.

На выходе первого дешифратора 6 нуля (фиГ. 1), а значит и на выходе элемента И 11 формируется сигнал логического нуля, независимо от сигнала, подаваемого на вход 18 кода операции устройства. Это соответствует тому, что результат операции определен.

При этом, поскольку на выходе элемента ИЛИ 14 сформирован сигнал логической единицы, поступающий на вход установки в нуль элемента 17 памяти, последний не установится в единицу по сигналу, подаваемому на его информационный вход, а на выходе 20 устройства формируется сигнал логической единицы, который соответствует тому, что сформирован результат на выходах результата операции устройства, Этот результат операции соответствует сигналам, сформированным на выходах m-разрядного регистра 2 и переданным через элементы И 9 группы на их выходы по сигналу логичес20 кой единицы, подаваемой с выхода дешифратора 8 на входы элементов И 9 группы, В данном случае результат операции равен полиному-операнду, заносимому в m-разрядный регистр 2, 25 что соответствует равенству полинома-результата операции полиному-операнду, умножающемуся или делящемуся на единицу поля полиномов.

Если в m-разрядные регистры 1и 2

Э0. занесены коэффициенты полиномов-операндов первого вЂ,не равного нулю и, второго — равного нулю соответственно, то на выходах дешифраторов 6 и 7 нуля формируются сигналы логическо35 го нуля и логической единицы соответственно.

Сигнал логического нуля на выходе дешифратора 6 нуля формирует на .выходе элемента И 11 и на входе элемента НЕ 16 сигнал логического нуля, Сигнал логической единицы на выходе дешифратора 7 нуля формирует на выходе элемента ИЛИ 14, а значит на входе установки в нуль элемента 17 памяти и на одном из входов элемента

И 12, на другом входе которого с выхода элемента НЕ 16 сформирован сигнал логической единицы, Следовательно, на выходе 20 устройства формируется сигнал логической единицы, что соответствует наличию сформированного результата операции на выхо-. дах результата операции устройства.

Этот результат равен нулю, так как на входы элементов И 9 группы подаются с выходов m-разрядного регистра 2 сигналы логического нуля, В данном случае результат операции равен нулю, что соответствует равенству нулю ре166175935 зультата умножения на нуль, либо результату деления нуля на ненулевой элемент поля GF(2 ) соответственно.

fA

Если в ш-разрядный регистр 1 за5 несены коэффициенты полинома не равного ни нулю, ни единице поля GF(2 )

1 а в m-разрядный регистр 2 — коэффициенты полинома не равного нулю, ro устройство умножения и деления полиномов над конечными полями

GF(2 ) пер ходит на второй шаг своей работы.

При этом на выходах дешифраторов 6 и 7 нуля и дешифратора 8 сформированы сигналы логического нуля. Значит, на выходе элемента И.11, являющимся выходом 19 неопределенности результата устройства, и выхо1 де элемента ИЛИ 14 формируются сигналы логического нуля, по которому закрывается элемент И 12, а также обеспечивается возможность установки в единицу элемента 17 памяти по его информационному входу. На выхо- 25 дах блока 3 деления (фиг.1, 3) сформированы сигналы, соответствующие результату от деления полинома, записанного в m-разрядный регистр 1, на примитивный элемент поля. На выходах блоков 4 и 5 умножения (фиг,1, 4) сформированы сигналы, соответствующие результату от умножения поли.номов, записанных в m-разрядные ре гистры 1 и 2, на примитивный элемент поля соответственно.

Если на вход 18 кода операции устройства (фиг. 1) подан сигнал логического нуля, то сигналы на выходах коммутатора 10, а значит и на информационных входах m-разрядного регистра 1 будут равны сигналам на одноименных выходах блока 3 деленияна примитивный элемент поля. Следовательно, при поступлении тактовых импульсов на тактовый axon m-разрядного регистра 1 на выходах регистра (фиг. 2) будут формироваться сигналы, соответствующие результатам от деления полиномов записанных В ре» гистр 1 до поступления тактовых импульсов, на примитивный элемент поля.

Этим обеспечивается выполнение устройством операции умножения полино111 ъ мов над конечным полем GF(2 ), Если на вход 18 кода операции устройства (фиг.1) подан сигнал логической единицы, то сигналы на выходах коммутатора 10, а значит и на информационных входах m-разрядного регистра 1 будут соответствовать сигналам на одноименных выходах блока 4 умножения. Следовательно, при поступлении тактовых импульсов на тактовый вход m-разрядного регистра 1 на выходах регистра (фиг. 2) будут формироваться сигналы, соответствующие результатам от деления полиномов, записанных в регистр 1 до поступления тактовых импульсов, на примитивный элемент поля. Этим обеспечивается возможность выполнения устройством операции деления полиномов над конечными полями GF(2®). Для запуска устройства на выполнение операции, заданной сигналом на вход 18 кода операции устройства, необходимо на вход 21 начала вычисления устройства подать импульс, обеспечивающий его совпадение с началом поступления одного из тактовых импульсов, например, либо длительностью импульса,равной периоду поступления тактовых импульсов, или импульс, синхронизированный по началу поступления с тактовым импульсом.

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

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

13 и ИЛИ 15 формируется сигнал логической единицы, который поддерживает этот сигнал на информационном входе, элемента 17 памяти. Следовательно, элемент памяти 17 переведется в нулевое состояние только по сигналу логической единицы на входе. установки в

"0". Это произойдет только тогда, когда на выходе дешифратора 8 сформируется сигнал логической единицы, т.е. когда на выходах m-разрядного регистра 1 появится комбинация сигна1661759

l0 лов, соответствующая единице поля.

Сигнал логической единицы на одном иэ входов элемента И 13 разрешит прохождение тактовых импульсов с его другого входа на его выход, а зна5 чит и на тактовые входы m-разрядных регистров 1 и 2. В дальнейшем до формирования сигнала логической единицы на выходе дешифратора 8 устройство работает как устройство для умножения полиномов над конечными полями

СР(2Ш) по модулю неприводимого многочлена, если сигнал на входе 18 кода операции устройства равен логическому нулю, или как устройство для де- . ления полиномов над конечными полями

GF(2m) по модулю неприводимого многочлена, если потенциал на входе 18 кода операции устройства равен логической единице.

При формировании сигнала логической единицы на выходе дешифратора 8 устройство переходит в состояние, соответствующее занесению единицы поля в m-разрядный регистр 1 на первом шаге работы устройства. При этом элемент 17 памяти по сигналу на его управляющем входе переводится в нулевое состояние, на выходах элементов И 11 и 12 формируются сигналы логического нуля и логической единицы соответственно, а на выходах результата операции устройства — сигналы, соответствующие результату выбранной

35 операции над двумя полиномами поля.

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

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

hl неприводимого многочлена, содержащее

40 два m-разрядных регистра, блок деления, первый блок умножения, дешифратор и группу из m элементов И, первые входы которых объединены и соединены с выходом дешифратора, а выходы — с выходами m коэффициентов результирующего полинома устройства, выходы первого и второго m-разрядного регистра соединены соответственно с одноименными, входами блока деления и первого блока умножения, тактовые входы первого и второго m-разрядных регистров объединены между собой, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей за счет реализации операции деления полиномов, в него вве1 дены второй блок умножения, элемент памяти, два дешифратора нуля, коммутатор, два элемента ИЛИ, элемент НЕ и три элемента И, причем установочные входы первого и второго m-разрядных регистров соединены с входами тп коэффициентов первого и второго полиномов-операндов устройства соответственно, выходы первого m-раэрядного регистра соединены соответственно с одноименными входами второго.блока умножения, первого дешифратора нуля и дешифратора, выход которого соединен с первым входом первого элемента ИЛИ, второй вход которого соединен с выходом первого дешифратора нуля и первым входом первого элемента И, второй вход которого соединен с входом кода операции устройства и управляющим входом коммутатора, информационные входы первой и второй группы которого соединены соответственно с выходами второго блока умножения и блока деления, а выходы — с информационными входами первого m-разрядного первого регистра, тактовый вход которого соединен с выходом второго элемента И, первый вход которого соединен с тактовыми входами устройства и элемента памяти, выход которого соединен с вторым входом второго элемента И и первым входом второго элемента ИЛИ, выход которого соединен с информационным входом элемента памяти, вход установки в "0" которого соединен с первым входом третьего элемента И и выходомпервого элемента ИЛИ, третий вход которого соединен с выходом второго дешифратора нуля, входы которого соединены с вторыми входами соответствующих элементов И группы и выходами второго тп-разрядного регистра, информационные входы которого соединены соответственно с выходами первого блока умножения, выход первого элемента И соединен с выходом неопределенности результата устройства и входом элемента НЕ, выход которого соединен с вторым входом третьего элемента И, выход которого соединен с выходом готовности результата устройства, вход начала вычисления которого соединен с вторым входом второго элемента ИЛИ.

1661759

1661759

Составитель Е.Мурзина

Редактор С.Лыжова Техред H.äää ù

Корректор М. Самборская

Заказ 2124 .Тираж 401 Подписное

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

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

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