SU1709302A1 - Устройство дл выполнени операций над элементами конечных полей - Google Patents

Abstract

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

Description

Изобретение относитс  к вычислительной технике и может быть использовано в кодирующих и декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей 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).

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

Claims (1)

1. Формула изобретени  Устройство дл  выполнени  операций над эл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) входами второго элемента ИЛИ-НЕ, т-й вход которого через элемент НЕ соединен с выходом первого многовходового сумматора .

   . V «мим

   77/

   /5,

   J

   fS

   I РУ-

   /5,

   ISffj j