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

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

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

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

Устройство содержит первую группу 1 элементов 2 памяти, первый умножитель 3 на примитивный элемент о/ конечного поля GF (2), содержапщй сумматор по модулю два (См2), второй умножитель 5 на примитивный эле- мент конечного поля, вторую группу 6

элементов 2 памяти, группу 7 элемен- 20 своим вторым входам через два тов И 8, вторую группу 9 элементов И 10, группу 11 сумматоров 12 по модулю, группу накапливающих двоичных сумматоров 13 и тактовый 14.

30

последовательно включенных умножителя 3 и 5 на примитивный элемент ос конечного поля,то следующим состоянием элементов памяти 2 группы будет

Алгоритм работы устройства сводит- 25 состо шие,соответствующее .При

число тактов работы устройства, равное f. ni/2J , будет больше двух и состояние элементов памяти 2 группы принимает значения: U/Uc jUsc ,

Uot. ..,.U-o/ Сигналы с выходов элементов 2 группы 1 поступают поразрядно на первые входы элементов И 8 группы 7. Эти же сигналы поступают и на вход умножителя 3 на примитивный элемент 35 и после преобразования в нем (умножения, насч) поступают на первые входы элементов И 0 группы 9 в виде сигналов, соответствующих элементам поля,Uo (в первый такт работы) и

(Uct) -Uo (во второй такт работы) и далее при в виде ,, Uoi , . . . , .. (f b3-ii- f

СЯ к тому, что на выходах элементов памяти первой группы с каждым тактом работы (по входу 14) образовываются следующие элементы конечного поля: U, и, и,. .., Uj - ,,,., а на выходах первого умножителя на примитивный элемент о конечного поля - элементы конечного поля: U, Uof, U,. . .

и

у ot , . . . .

в результате на выходах группы сумматоров по модулю два в каждый такт работы образуются суммы: (V, U+

.) (,u), (V,,uL),

. .. j которые суммируются в накапливающих сумматорах, формируя тем самым произведение Z сомножителейU и V m/7l.

(V , Uot

I-. 1 т/г

40

г, -1

(. V V. 0 n

i

В группе . 6 элементы 2 памяти 5 объединены- в два регистра сдвига, причем в первый регистр входят те элементы 2 памяти, первые входы которых являются входами нечетных раз-рядов V и V, сомножителя V. Во вто- jg рой регистр входят элементы 2 памяти, первые входы которых являются входами четных разрядов V и V, сомножителя V. При этом выход элемента 2 памяти, группы 6, соответствующего Vj , соединен с вторым входом элемента 2 памяти, соответствующего V, ., выход которого соединен с объединенными вторыми входами элементов И 8 группы 7. Выход элемента 2 памяти

1--1

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

Сомножитель U(U,,..,,U) через входы первого сомножителя вводится 3 двоичные элементы памяти 2 группы 1 и в результате этого каждый i-й элемент 2 памяти группы 1 устанавливается в состояние 1 или О, соответствующее значению соответствую- iaero разряда Uj сомножителя U. Одновременно с этим через входы второго сомножителя в элементы 2 памяти груп

364642

пы 6 вводятся соответствующие разряды V| ,...,V сомножителя V. Сигналы на входах первого и второго сомножителей устройства соответствуют значениям сомножителей U и V только в течение времени, равного одному периоду тактовой частоты работы устройства, а в дальнейшем до момента ввода новых сомножителей входные сигналы на J0 входах сомножителей устройства принимают нулевые значения.

В следующие такты работы устройства элементы 2 памяти группы 1- устанавливаются в состояние, соответст- ,5 вующее сигналам на выходе умножителя 5 на примитивньй элемент с которые поступают на вторые входы этих элементов 2 памяти. Так как вь1ходы . элементов 2 памяти группы I подключеВ группе . 6 элементы 2 памяти 5 объединены- в два регистра сдвига, причем в первый регистр входят те элементы 2 памяти, первые входы которых являются входами нечетных раз-рядов V и V, сомножителя V. Во вто- jg рой регистр входят элементы 2 памяти, первые входы которых являются входами четных разрядов V и V, сомножителя V. При этом выход элемента 2 памяти, группы 6, соответствующего Vj , соединен с вторым входом элемента 2 памяти, соответствующего V, ., выход которого соединен с объединенными вторыми входами элементов И 8 группы 7. Выход элемента 2 памяти

35

3

группы 6, соответствующего V, , соединен с вторым входом элемента 2 памяти, соответствующего V, выход которого соединен с объединенными вторыми входами элементов И 10 группы 9. Таким образом, после ввода в элементы 2 памяти группы 6 сомножите ля V и при дальнейшей работе устройства на вторые входы элементов И 8 группы 7 последовательно поступают сигналы, соответствующие значениям нечетных разрядов второго сомножителя (V, Vj), а на вторые входа элементов И 10 группы 9 - сигналы, соответствующие значениям четных разрядов этого сомножителя (Vj , V, ).

Благодаря этому разрешается (при Vj Г) или запрещается (при ) про хождение на выходы группы 7 и 9 сигналов , поступивших на первые входы элементов И 8 и И 10 и соответствующих UjUoL -- в первом случае, и , втором случае, т.е. такое построение схемы реализует выполнение соотношений: V U , VjUot ,V,Uoc, при V, ,0, ,. ..,m.

Сигналы вида V. Uot ,2,...,m с выходов элементов И 8 и И 9 гюсту- пают поразрядно в каждый такт работы устройства на первые и вторые входы ГРУППЫ П сумматоров 12 по модулю два, где и суммируются поразрядно. При этом, в первом такте образуется сумма V, и , во втором такте - сумма V.JUcyL +V Uot и так далее, если .

Сигналы с выходов сумматоров 11, соответствующие указанным суммам, поступают-на соответствующие входы накапливающих сумматоров, где и производится получение итоговой суммы за га/21 тактов работы устройства умножения: (V, U+V, U«)+(.+V Uoc)

m

-TL V. , равной произведению Z

i 1

сомножителей U и V,

364644

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

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

5 конечного поля, первую группу из m элементов И, первую и вторую Группы из m элементов памяти, входы начальной записи которых являются соответственно входами первого и второго

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

j«l подключен к i-му входу первого умножителя на примитивный элемент конечного поля и к первому входу i-ro элемента И первой группы, второй вход которого подключен к выходу пер20 вого элемента памяти второй группы,, тактовый вход устройства подключен к синхронизирующим входам элементов памяти первой и второй групп и m накапливающих сумматоров группы, о т5 личающееся тем, что, с целью повьппения быстродействия устройства, в него введены .вторая группа из га элементов И, группа из m сумматоров по модулю два, второй умножитель на примитивный элемент конечного поля, i-й вход которого подключен

. к i-му выходу первого умножителя на примитивный элеме.нт конечного поля, а i-й выход подключен к информационному входу i-ro элемента памяти пер0

5

0

5

вой группы, 1-й выход первого умножителя на примитивный элемент конечного поля подключен к первому входу 1-го элемента . И второй группы, второй вход которого подключен к выходу второго элемента памяти второй группы, а выход - к первому входу 1-го сумматора по модулю два группы, второй вход которого подключен к выходу i-ro элемента И первой группы, а выход - к входу i-ro накапливающего сумматора группы, при этом второй вход j-ro (,2,.,.,m-2) элемента памяти второй группы подключенк выходу (j+2)-ro элемента памяти второйгруппы.

11

W

12

4r ч/

rj

/4

Ф 4 V i- Z Zi Zj Z.

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислителей для кодирования и декодирования корректирующих ошибки кодов. Цель изобретения - повы- вьйпение быстродействия устройства для умножения элементов конечных полей.- достигается за счет введения в устройство группы элементов И, группы сумматоров по модулю 2 и умножителя с соответствующими функциональными связями между ними и известными блоками устройства. Устройство позволяет получить произведения элементов конечных полей с последующим их суммированием и накоплением. I ил. с Э to со О5 4 О5 4

Редактор H. Гулько

Составитель В, Смирнов

Техред М.Ходанич Корректор В.. Бутяга

Заказ 3091/51 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам.изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная,4.