Устройство для деления многочленов

 

Изобретение относится к вычислительной технике и может быть использовано для ускорения деления многочленов с коэффициентами из поля GF(LN). Цель изобретения - увеличение быстродействия и расширение функциональных возможностей за счет выполнения деления, когда степень примитивного элемента поля GF(LN) больше степени многочлена - делителя. Поставленная цель достигается тем, что устройство содержит по первому варианту блок умножения в поле GF(LN), блок сложения в поле GF(LN) и N регистров, где N - степень многочлена-делителя. Устройство содержит по второму варианту блок сложения в поле GF(LN), блок деления в поле GF(LN) и N регистров, а в случае K*98N, где K - степень примитивного элемента поля GF(LN), устройство (третий вариант) дополнительно содержит блок преобразования. 3 ил.

„„80„„14 461 (51) 4 С 06 F 15/31

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

Н д ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

2 ние быстродействия и расширение функциональных возможностей за счет выполнения деления, когда степень прин митивного элемента поля GF (L ) больше степени многочлена-делителя. Лоставленная цель достигается тем, что устройство содержит по первому варианту блок умножения в поле GF (L ), блок сложения в поле GF (Lå) и N регистров, где N — степень многочлена— делителя. Устройство содержит по второму варианту блок сложения в поле

GF (L+) блок деления в поле GF (L ) и N регистров, а в случае k T N, где степень примитивного элемента поля GF (L ), устройство (третий вариант) дополнительно содержит блок ) преобразования. 3 ил. ф;- . . Г 4й . союз советсних :- " Ф. СО<ИАЛИСТИ ЕСНИ1(®-. РЕСПУБЛИН

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

gO ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГННТ СССР (21) 4146542/24-24 (22) 13. 11. 86 (46) 30. 05. 89. Бюл. 1(20 (71) Московский инженерно-физический институт (72) М. А. Иванов (53) 681.326.7(088.8) (56) Электроника, 1977, Р 5, с. 2 3-33.

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

1 - 1185338, кл. G 06 F 11/00, 1984. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ИНОГОЧЛЕНОВ (57) Изобретение относится к вычислительной технике и может быть использовано для ускоренного деления м но r o члено в с ко эффицие нт ами иэ поля

GF (L ) . Цель изобретения — увеличеИзобретение относится к вычислительной технике и может иснользоваться в специализированных вычислительных устройствах.

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

GF(L ) больше степени многочленаделителя.

На фиг. 1 представлена схема первого варианта устройства; на фиг. 2 схема второго варианта; на фиг. 3 пример реализации устройства для случая К ) N (третий вариант) при Ь = 2, N = 4, К= 8, GF(2 ) = (О, 1,(и ц) ((- = 1 иг4 . ц З+ многочлен-делитель х + х + 1.

3 +

Устройство для деления многочленов по первому варианту содержит информационные входы 1, блок 2 умножения на йг в поле СГ(1:"), блок 3 сложения в поле GF(? ), регистры 4, выходы 5.

Число регистров равно степени много— члена-делителя (Х) = а х + ... +

+а х +...+а х +ад, коэффициенты коУ у торого а, ? = О, И, принадлежит полю GF(L), разрядность каждого из ре° у-! гистров равна R = 1 1og Lf. и а Ш +...+а 4г+.. ° +а и)+а„ = О. у у ° ° Е у Е ° °

Устройство дпя деления многочленов по второму варианту содержит информационные входы 1, блок 3 сложения в поле GF(L ), регистры 4, выходы 5, к У блок 6 деления на и) в поле GF(L ) ..

1483461 ((г. + 1) = ((Q(t) + A(t), (1) (2) (1(+ 1) = Q(t) + A(t), 45 где A(t) — элемент поля GF (L ) «соответствующий набору коэффициентов многочлена-делимо го, подаваемому н а входы 1 в t-м такте;

Q(t) элементы поля GF(L ) «сои Q (t+1) — ответствующие содержимому регистров 4 соответственно в моменты времени и (t+1).

Уравнение (1) соответстнует устройству на фиг. 1, уравнение (2) нл фиг. 2.

Первые днл нлриантл построения устройства дпя деления многочленон использувтся при К < N.

11ри К > N н состав устройства для деления вводится блок 7 преобразования, который в общем случае содержит узлы умножения в поле ГР(?. ), и узел сложения и поле GF(I. ) .

Пусть, например, К = 3N, тогда 10 блок преобразования 7 имеет 3NR. входов, причем первая группа из NR входов подключается непосредственно к входам первой группы узла сложения в поле GF(L ), вторая группа из NR !5 входов подклвчается ко второй группе входов узла сложения в поле GF(I. ) через узел умножения íà си в поле

GF(L ), третья группа из NR входов подключается к третьей группе входов 20 узла сложения в поле GF(L ) через узел умножения íà 4r в поле GF(L ) .. .Р

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

Перед началом работы сигналом по установочному входу все регистры 4 устанавливаются в нулевое состояние.

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

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

На тактовые входы устройств подаются тактовые импульсы, приход которых нызывавт переклвчения регистров 4 в соответствии с уравнениями 40

Урлнненпе работы третьего варианта устройства для деления имеет вид (при К = g- N, / ) Π— целое)

Q(t+1) = Q(t) + A,(t) + A (t)+

+ш А (t)+...+Þ А .(с) . где A„(t), i = 1, — элементы поля

GF ((), соответствувщие наборам коэффициентов многочлена-делимого, поданным на i-й вход устройства. Например, в первом такте на входы устройства подаются коэффициенты («« - (g (p pá ««((«)у (r ° ° « ««- « "( многочлена-делимого степени М, на втором — коэффициенты,1 ..., с(,„,, „на - -м — коэффициенты

4 „) м- «2. « гч 4+1 и т.д. (где (— коэффициент при 1-й степени Х, j = О, M).

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

1. Устройство для деления многочленов, содержащее N регистров, где

N — степень многочлена-делителя, причем тактовый вход устройства подключен к синхровходам регистров с первого по N-й, выходы которых подключены соответственно к выходам с первого по N — и устройства, о т л и ч а в щ е е с я тем, что, с целью увеличения быстродействия, в него введены блок умножения на си в поле GF(L ), М где (— примитивный элемент поля

GF(L ), k — степень примитивного эле.М мента поля GF(L ), L — основание поля

Галуа, блок сложения в поле GF (L ), при этом информационные входы с первого по N-й устройства подключены соответственно к информационным входам регистров с первого по N-й, выходы которых подклвчены соответственно к входам блока умножения на ю в по.« ле GF(L ), выходы которого с первого по N-й подключены соответственно к входам с первого по N-й второй группы блока умножения в поле GF(I., ) .

2. Устройство по п. I о т . (и— чавщее с я тем, что, с целью расширения функциональных возможностей з а счет выполнения деления, ко гда степень k примитивного элемента поля GF (L ) больше степени N многочлена-делителя, оно содержит блок преобразовлний, причем информлцион—

1483461

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

Редактор О. Спесивых Техред M.дидык Корректор Э. Лончакова

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

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

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

Производственно-издат..льский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 ные входы с первого по -" N-й (где

k/N) устройства подключены соответственно к входам с первого по 3N-й блока преобразования, выходы с перво5 го по N-й которого подключены соответственно к входам с первого по N-й первой группы блока сложения в поле

GF(L ), причем блок преобразования содержит узел сложения в поле GF(L ) и (Ф-1) узлов умножения соответственно на ш, где i = N, 2N...,, V — 1)N, в поле GF(L ), причем с первого по

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

GF(7. ), входы с (j N+I)-ro по (j+I)

N-й (где j = 1,.-... V -1) блока преобразования подключены соответственно к входам с первого по N-й узла умножения на ш, выходы с первого по У

N-й которого подключены соответственно к входам с (j N+I)-го по (j+I) N-й узла сложения в поле GF(L ), выходы .Ф с первого по N-й которого подключены соответственно к выходам с первого по N-й блока преобразования,