Устройство для выполнения операций над элементами конечных полей Советский патент 1992 года по МПК G06F7/52 

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

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

На фиг. 1 изображена схема устройства; на фиг. 2 - схема модуля умножения.

Устройство (фиг. 1) содержит первый 1, выполненный в виде регистра, и второй 2, выполненный в виде счетчика, буферные узлы памяти, модуль 3 умножения, элемент НЕ 4, первый 5 и второй 6 элементы И ЛИНЕ, элемент 7 памяти, первый 8 и второй 9 элементы И, выход 10 неопределенности результата устройства, тактовый вход 11 устройства, вход 12 кода операции устройства, выход 13 разрешения занесения полинома делимого.

Модуль 3 умножения (фиг.2} содержит т элементов И 14, т-1 блоков 15 матричного преобразования и m многовходовых сумматоров 16.

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

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

В исходном состоянии (фиг. 1) буферные узлы 1 и 2 памяти и элемент 7 памяти обнулены.

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

на выходе 13 устройства и на входе установки в О элемента 7 памяти, сформирован сигнал О.

Поскольку на входы элементов И 8 и 9

поступают сигналы О то на их выходах, а следовательно, на выходе 10 устройства и на втором (сч етном) входе буферного узла 2 памяти сформированы сигналы О соответственно. Значит, сигналы на выходах буфер0 ного узла 2 памяти не изменяются.

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

Значит, на выходах буферных узлов 1 и 2 памяти формируются и подаются на входы

0 первой и второй групп,модуля 3 умножения (фиг.1. 2) си-налы, соответствующие коэффициентам первого и второго полиномовсомножителей соответственно.

На выходах модуля 3 умножения, являющихся выходами устройства, формируются потенциалы, соответствующие коэффициентам полинома-произведения. Связь выхода элемента 7 памяти и входа элемента 8 И не разрешает формирование на выходе

0 элемента 8 И, а значит, и на выходе 10 неопределенности результата устройства сигнала 1 при выполнении устройством операции умножения полиномов.

При выполнении устройством операции

5 деления двух полиномов над конечными полями GF() в исходном состоянии на информационные входы буферного узла 1 памят 1 подаются сигналы, соответствующие коэффициентам полинома-делителя.

0 При этом на входы элемента 5 ИЛИ-НЕ и на входы первой группы модуля 3 умножения подаются сигналы, соответствующие коэффициентам полинома-делителя, а на входы второй группы - сигналы О, Значит, на

5 выходах модуля 3 умножения формируются сигналы О, т.е. не изменяются. Если значения всех коэффициентов полинома-делителя равны нулю, то на выходе элемента 5 ИЛИ-НЕ, а значит, и на выходе элемента 8

0 И формируется сигнал Г. Для осуществления начала выполнения операции деления необходимо на вход 12 кода операции устройства подать сигнал 1. При этом элемент 7 памяти по очередному тактовому

5 импульсу на его тактовом входе установится в единичное состояние и на его выходе; а значит, и на входе элемента 9 И и на входе элемента 8 И сформируется сигнал 1.

Если значения всех коэффициентов полинома-делителя равны нулю, то на выходе элемента 8 И, а значит, и на выходе 10 устройства сформируется сигнал 1, который указывает на то, что осуществляется операция деления на нуль, которая в поле полиномов GF(2) не определена. В этом случае операция делейия устройством не выполняется.

Если хотя бы один из коэффициентов поли и ома-делителя равен единице, то на выходе элемента 5 ИЛИ-НЕ, а значит, и на выходе 10 устройства через элемент 8 И сформируется сигнал О. На выходе элемента 6 ИЛИ-НЕ также сформируется сигнал О, так как на. выходах модуля 3 умножения по. сигналам 0 на всех входах его второй группы формируются сигналы О.

Значит, на обнуляющем входе элемента

7памяти и на выходе 13 разрешения занесения полинома-делимого устройства формируются сигналы О и элемент 7 памяти остается в единичном состоянии. При этом тактовые импульсы, поступающие с тактового входа 11 устройства на вход элемента

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

Поступление тактовых импульсов на второй (счетный) вход буферного узла 2 памяти продолжается до тех пор, пока на выхрдах модуля 3 умножения не сформируются сигналы, соответствующие полиномуединице поля GF (), т.е. на входе элемента НЕ 4 сформируется сигнал Г, а на т-1 входах элемента 6 ИЛИ-НЕ - сигналы О.

8этом случае на выходе элемента ФИЛИНЕ сформируется сигнал 1. Значит, на выход 13 разрешения занесения полиномаделимого и на обнуляющий вход элемента 7 памяти подается сигнал 1 и элемент 7 памяти установится в нулевое состояние. При этом по сигналу.О на его выходе, а значит, и на входе элемента 9 И тактовые импульсы через элемент 9 И на вторр (счетный) вход буферного узла 2 не проходят и, следовательно, состояние буферного узла 2 памяти

не изменяется.

По сигналу Гна выходе 13 устройства в буферный узел 1 памяти по его информационным входам заносятся коэффициенты, соответствующие полиному-делимому, а на вход 12 устройства подается сигнал О. При

этом, на выходах модуля 3 умножения формируются сигналы, соответствующие полиному-частному от деления полиномаделимого на полином-делитель над конечным полем GF (2).

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

Формула изобретения Устройство для выполнения операций над элeмeнtaми конечных полей, содержащее два буферных узла памяти, причем первый из них выполнен в виде регистра, и модуль умножения, состоящий из матрицы mxm элементов И (т-разрядность операндов), т-1 блоков матричного преобразования и; m многовходовых сумматоров, причем вход первого и первый вход второго буфернь узлов памяти соединены соответственно с первым и вторым информационными входами устройства, j-й выход первого буферного узла памяти соединен с первыми входами m элементов И в каждом j-м столбце матрицы модуля умножения .- . ff номер столбца),-й выход второго буферного узла памяти соединен с J-M входом первого блока матричного преобразования модуля умножения и вторым входом 1, 1)-го элементаИ матрицы модуля умножения (,.... m номер строки), Ьй выход К-го блока матричного преобразования которого соединен с 1-м входом (К+1)-го блока матричного преобразования и вторым входом (f, К+1)-го элемента И матрицы модуля умножения (...., т-1), выходы (I, j)-x элементов И матрицы которого соединены с соответствующими входами m многовходовых сумматоров, выходы которых соединены с выходами результата устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет выполнения операции деления, в него введены два элемента ИЛИ-НЕ, элемент НЕ, элемент памяти и два элемента И, а второй буферный узел памяти выполнен в виде счетчика, при этом выхо; ы первого буферного узла памяти соединены с входами первого элемента ИЛИ-НЕ, выход которого соединен с первым входом первого элемента И, выход которого соединен с выходом неопределенности результата устройства, выход разрешения занесения ролинома делимого которого соединен с выходом второго элемента ИЛИНЕ и входом установки в О элемента памяти, информационный вход которого соединен с входом кода операции устройства, тактовый вход которого срединен с тактовым входом элемента памяти и первым входом второго элемента И, второй вход которого соединен с выходом элемента памяти и вторым.входом первого элемента И, а выход - с вторым входом второго буферного уэла памяти, выходы многовходовых сумма- 5

Г торов с Йторого по т-й соединены с (т+1) входами второго элемента ИЛИ-НЕ, т-й вход которого через элемент НЕ соединен с выходом первого многовходового сумматора.

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

. V «мим

77/

/5,

J

fS

I РУ-

/5,

ISffj j