Устройство для умножения полиномов над конечными полями GF (2 @ ) по модулю неприводимого многочлена Советский патент 1991 года по МПК G06F17/10 G06F7/52 

Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в кодирующих и декодирующих устройст- Sax двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF(2tn), образованных неприводимыми многочленами- вида f(x) х +(5m., ...+J5lX+1, где х - фиктивная переменная, используемая для записи полиномов конечных полей, - коэффициенты при степенях фиктивной переменной, причем В; 6GF(2) / i 1, 2,,,., m-1, а примитивный элемент поля GF(2 ) Об х.

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

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

I

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

m-разрядные регистры 1 и 2 параллельные (фиг. 2) содержат тп элементов 23 памяти.t

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

D неприводимом многочлене, образующем поле подиномов GF(2 ).

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

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

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

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

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

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

0 на выходах элементов И 13 и ИЛИ 15, на всех выходах m-разрядных регистров 1 и 2, а значит и на выходах элементов И 9 группы, являющихся вы- ходами результата операции устройства, сформированы сигналы логического нуля.

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

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

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

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

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

759 .6

ции устройства. Это соответствует тому, что результат операции определен. При этом, поскольку на выходе элемента ИЛИ 14 сформирован сигнал логической единицы, поступающий на вход установки в нуль элемента 17 памяти, последний не установится в единицу по сигналу, подаваемому на его инn Формационный вход, а на выходе 20 устройства формируется сигнал логической единицы, который соответствует тому, что сформирован результат на выходах результата операции уст-

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

5 что соответствует равенству полинома-результата операции полиному-операнду, умножающемуся или делящемуся на единицу поля полиномов.

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

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

Сигнал логического нуля на выходе дешифратора 6 нуля формирует на выходе элемента И 11 и на входе элемендо та НЕ 16 сигнал логического нуля.

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

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

г на входы элементов И 9 группы подаются с выходов га-разрядного регистра 2 сигналы логического нуля. В данном случае результат операции равен нулю, что соответствует равенству нулю ре5

Зультата умножения на нуль, либо результату деления нуля на ненулевой элемент поля GF(2rf) соответственно.

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

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

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

Если на вход 18 кода операции устройства (фиг.1) подан сигнал логической единицы, то сигналы на выходах коммутатора 10, а значит и на

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

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

Q на вход 21 начала вычисления устройства подать.импульс, обеспечивающий его совпадение с началом поступления одного из тактовых импульсов, например, либо длительностью импульса,рав5 ной периоду поступления тактовых импульсов, или импульс, синхронизированный по началу поступления с тактовым импульсом.

Этим обеспечивается возможность

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

При подаче импульса на вход 21 начала вычисления устройства на выходе

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

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

5

0

5

лов, соответствующая единице поля. Сигнал логической единицы на одном из входов элемента И 13 разрешит прохождение тактовых импульсов с его другого входа на его выход, а значит и на тактовые входы т-разрядных регистров t и 2. В дальнейшем до формирования сигнала логической единицы на выходе дешифратора 8 устройство работает как устройство для умножения полиномов над конечными полями GF(2ln) по модулю неприводимого многочлена, если сигнал на входе 18 кода операции устройства равен логическому нулю, или как устройство для де- ления полиномов над конечными полями GF(2nl) по модулю неприводимого многочлена, если потенциал на входе 18 кода операции устройства равен логической единице.

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

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

5

0

5

0

5

0

5

0

5

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

Фие.З

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

ФигМ