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

 

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

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

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

РЕСГ1УБЛИН

„„SU„, 12 464 511 4 G 06 F 7/52

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

К А ВТОРСНОМЪ С8ИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3799364/24-24 (22) 05.10.84

{46) 07.06.86. Бюл. 11 21 (72) Ю.В. Сулимов (53) 681.325(088.8) (56) Авторское свидетельство СССР

В 1013950, кл. G 06 F 7/52, 1983.

Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды. — М.: Связь, 1976, с. 99. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ КОНЕЧНЫХ ПОЛКИ (57) Изобретение относится к вычислительной технике и мо;кет быть использовано при построении специализированных вычислителей для кодирования и декодирования корректирующих ошибки кодов. Цель изобретения — повывышение быстродействия устройства для умножения элементов конечных полей. — достигается за счет введения в устройство группы элементов И, группы сумматоров по модулю 2 н умножителя с соответствующими функциональными связями между ними и известными блоками устройства. Устройство позволяет получить произведения элементов конечных полей с последующим их суммированием и накоплением. 1 ил.

4 12

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

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

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

Устройство содержит первую группу элементфв 2 памяти, первый умножитель 3 на примитивный элемент с( конечного поля GF (2"), содержащий сумматор 4 по модулю два (Си2), второй умножитель 5 на примитивный эле,мент конечного поля, вторую группу 6 элементов 2 памяти, группу 7 элементов И 8, вторую группу 9 элементов

И 1О, группу ll сумматоров !2 по модулю, группу накапливающих двоичных сумматоров 13 и тактовый вход 14.

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

Б> U, U y ° .., U а на выходах первого умножителя на примитивный элемент с конечного поля — элементы конечного поля: U т<

° в о > \б > ° е а в

В результате на выходах группы

Сумматоров по модулю два в каждый такт работы образуются суммы: (V; U+

+Ч U„) (V,,U„ +V„U„ ) (V, U,"+V,Ж) которые суммируются в накапливающих сумматорах, формируя тем самым произведение Z сомножителей U u V

Ь /г)

l> 2 1 -> Х-, (Ч,udñ Ч,, Ud. ) > 1

2 (т/2

<-1

lJ 0 Ч. 0 ПР>< > >> >

I =1

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

Сомножитель U=(U,,. U ) через входы первого сомножителя вводится в двоичные элементы памяти 2 группы

I и в результате этого каждый i-й элемент 2 памяти группы 1 устанавливается в состояние "l" или "О", соответствующее значению соответствую щего разряда U; сомножителя U. Одновременно с этим через входы второго сомножителя в элементы 2 памяти груп36464 2

Ю !

М

35, 40 пы 6 вводятся соответствующие разряды Ч,...,Ч сомножителя Ч. Сигналы

» на входах первого и второго сомножи-. телей устройства соответствуют значениям сомножителей 0 и V только в течение времени, равного одному периоду тактовой частоты работы устройства, а в дальнейшем до момента ввода новых сомножителей входные сигналы на входах сомножителей устройства принимают нулевые значения.

В следующие такты работы устройства элементы 2 памяти группы 1. устанавливаются в состояние, соответствующее сигналаи на выходе умножителя

5 на примитивный элемент < которые поступают на вторые входы этих элементов 2 памяти. Так как выходы . элементов 2 памяти группы подключе-. ны к своим вторым входам через два последовательно включенных умножителя 3 и 5 на примитивный элемент о

I конечного поля>то следующим состоянием элементов памяти 2 группы !будет состояние, соответствующее Бым=Пм .При

С ш>4 число тактов работы устройства, равное f m/2), будет больше двух и состояние элементов памяти 2 группы принимает значения. U>U,,13i., Ц (U р1 ((>nlrb 1)

Сигналы с выходов элементов 2 группы 1 поступают поразрядно на первые входы элементов И 8 группы 7.

Эти же сигналы поступают и на вход умножигеля 3 на примитивный элемент и после преобразования в нем (умножения на .- ) поступают на первые входы элементов И IO группы 9 в ниде сигналов, соответствующих элементам поля,0с >(в первый такт работы) и

> . (U ) =-Uw (во второй такт работы) и далее при m>4 в виде U Uec !! - (i /21 <) lf

В группе 6 элементы ? памяти объединены в два регистра сдвига, причем в первый регистр входят те элементы 2 памяти, первые входы которых являются входами нечетных разрядов V и Ч сомножителя V. Во второй регистр входят элементы 2 памяти, первые входы которых являются входами четных разрядов V u V co2. < множителя V. При этом выход элемента

2 памяти, группы 6, соответствующего

Ч., соединен с вторым входом элемента 2 памяти, соответствующего V< выход которого соединен с объединенными вторыми входами элементов И 8 группы 7. Выход элемента 2 памяти

3 1236 группы 6, соответствующего V» соединен с вторым входом элемента 2 памяти, соответствующего V выход которого соединен с объединенными вторыми входами элементов И 10 группы 9. Таким образом, после ввода в элементы 2 памяти группы 6 сомножителя Ч и при дальнейшей работе. устрой1 ства на вторые входы элементов И 8 группы 7 последовательно поступают 111 сигиалы, соответствующие значениям нечетных разрядов второго сомножителя (V,, V ), а на вторые входы эле.ментов И !О группы 9 — сигналы, соответствующие значениям четных разрядов этого сомножителя (V, V> ).

Благодаря этому разрешается .(при

Ч. =1.) или запрещается (при V =О) прохождение на выходы группы 7 и 9 сигналов, поступивших на первые входы 20 элементов И 8 и И 10 и соответствуюI y щих U,U e - в первом случае, и Um ь

Ф у

11Ы во втором случае, т.е. такое построение схемы реализует выполнение соотношений: V, О, V Ua,Ч 11ос, Ч„асс при V =l 0, i=1.. °,m.

Сигналы вида V 11м, i=),2,...,m

1 с выходов элементов И 8 и И 9 поступают поразрядно в каждый такт работы устройства на первые и вторые входы группы ll сумматоров 12 по модулю два, где и суммируются поразрядно.

При этом, в первом такте образуется сумма V U +Ч Uv, во втором такте сумма V Uw +V„U и так далее, если

m>4.

Сигналы с выходов сумматоров 11, соответствующие указанным суммам, 4О поступают на соответствующие входы накапливающих сумматоров, где и производится получение итоговой суммы за (m/21 тактов работы устройства умножения. (V, U+V, Ucc)+(V Uw +V Uoc )= 45

V. U, равной произведению Е сомножителей U u V.

464 4

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

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

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

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

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

236464

У1

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

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

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

Заказ 3091/5! Тираж 67! Подписное

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

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

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