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

 

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

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

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

РЕСПУБЛИК (я)5 G 06 Е 7/52

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4741752/24 (22) 26.09.89 (46) 30,01.92. Бюл. М 4 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И.И.Ковалив (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М 1226445, кл. 6 06 F 7/52, 1986.

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

М 1.013950, кл. G 06 F 7/52, 1983. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

ОПЕРАЦИЙ НАД ЭЛЕМЕНТАМИ КОНЕЧНЫХ ПОЛЕЙ (57) Изобретение относится к вычислитель. ной технике и может быть использовано в,, SU(l709302 А1 кодирующих и декодирующих устройствах . двоичных кодов, проверочные матрицы которых содержат элементы конечных полей

GF(2 ). Целью изобретения является расширение функциональных воэможностей за счет выполнения операции деления и достигается она за счет введения в устройство, содержащее два буферных узла 1,2 памяти, первый из которых выполнен в виде регистра, модуль 3 умножения, состоящий из матрицы mxm элементов И, m-1 блоков матричного преобразования и. m многовходовых сумматоров, двух элементов ИЛИ— ..HE 5, 6, элемента НЕ 4, элемента памяти 7 и двух элементов И8, 9, при этом второй буферный узел памяти выполнен в виде счетчика. 2 ил.

1709302

25

35

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

GF(2 ).

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

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

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

НЕ 4, первый 5 и второй 6 элементы ИЛИ—

НЕ, элемент 7 памяти. первый 8 и второй 9 элементы И, выход 10 неопределенности результата устройства, тактовый вход 11 устройства, вход 12 кода операции устройства, выход 13 разрешения занесения полиномз делимого.

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

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

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

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

На вход 11 устройства подается непрерывная серия тактовых импульсов, а на все остальные входы устройства — сигналы "0" соответственно. При этом на выходе элемента 7 памяти, на выходах буферных узлов

1 и 2 памяти формируются сигналы "0". Зна.чит, на входы элементов И 8 и 9, подсоединенные к выходу элемента 7 памяти, на все входы модуля 3 умножения, на всех входы элемента 5 ИЛИ вЂ” НЕ поступают сигналы "0" соответственно. Следовательно, на выходе элемента 5 ИЛИ вЂ” HE, на выходах элементов

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

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

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

Значит, на выходах буферных узлов 1 и

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

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

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

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

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

ИЛИ вЂ” НЕ, а значит, и на выходе элемента 8

И формируется сигнал "1". Для осуществления начала выполнения операции деления необходимо на вход 12 кода операции устройства подать сигнал "1". При этом элемент 7 памяти по очередному тактовому импульсу на его тактовом входе установится в единичное состояние и на его выходе, а значит, и на входе элемента 9 И и на входе элемента 8 И сформируется сигнал "1", Если значения всех коэффициентов полинома-делителя равны нулю, то íà svxo1709302 де элемента 8 И, а значит, и на выходе 10 устройства сформируется сигнал "1", который указывает на то, что осуществляется операция деления на нуль. которая в поле полиномов G F(2 ) не определена, В этом случае операцйя деления устройством не выполняется.

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

"0"

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

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

9 И и по сигналу "1" на его другом входе, соединенном с выходом элемента 7 памяти, проходят на выход элемента 9 И и поступают на второй (счетный) вход буферного узла

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

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

НЕ 4 сформируется сигнал -"1"., à íà m-1 входах. элемента 6 ИЛИ вЂ” НŠ— сигналы "О".

В этом случае на выходе элемента 6-ИЛИ—

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

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

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

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

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

mxm. элементов И (m-разрядность операндов), m — 1 блоков матричного преобразования и m многовходовых сумматоров, причем

20 вход первого и первый вход второго буферных узлов памяти соединены соответственно с первым и вторым информационными входами устройства, j-й выход первого бу-. ферного узла памяти соедйнен с первыми

25 входами m элементов И в каждом )-м столбце матрицы модуля умножения O-1„... m— номер столбца),)-й выход второго буферного узла памяти соединен с J-м входом первого блока матричного преобразования модуля

30 умножения и вторым входом i, 1)-го элемента И матрицы модуля умножения (1=1,..., m— номер строки), i-й выход К-го блока матричного преобразования которого соединен с

1-м входом (К+1)-го блока матричного преоб35 разования и вторым входом (t, К+1)-го элемента И матрицы модуля умножения (К=1...., m — 1), выходы (i, j)-x элементов И матрицы которого соединены с соответствующими входами m многовходовых сумматоров, вы40 ходы которых соединены с выходами результата устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выполнения операции деления, в него введены два элемента

45 ИЛИ-НЕ, элемент НЕ, элемент памяти и два элемента И, а второй буферный узел памяти выполнен в виде счетчика, при этом выходы первого буферного узла памяти соединены с входами первого элемента ИЛИ вЂ” НЕ, вы50 ход которого соединен с первым входом первого элемента И, выход которого соединен с выходом неопределенности результата устройства, выход разрешения занесения полинома делимого которого со55 единен с выходом второго элемента ИЛИНЕ и входом установки в "0" элемента памяти, информационный вход которого соединен с входом кода операции устройства, тактовый вход которого соединен с тактовым входом элемента памяти и первым вхо1709302

Составитель И.Ковалив

Техред М.Моргентал Корректор М.Шароши

Редактор М.Товтин

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

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул,Гагарина. 101 дом второго элемента И, второй вход которого соединен с выходом элемента памяти и вторым.входим первого элемента И, а выход — с вторым входом второго буферного узла памяти, выходы многовходовых сумматоров с второго по m-й соединены с (я+1) входами второго элемента ИЛИ-НЕ, m-й вход которого через элемент Н Е соединен с выходом первого многовходового суммато5 ра.