Устройство для деления многочленов Советский патент 1989 года по МПК G06F17/10 

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

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

На фиг. 1 представлена схема первого варианта устройства; на фиг. 2 - схема второго варианта; на фиг. 3 - пример реализации устройства для случая К N (третий вариант) при L 2, N 4, К - 8, GF(2) О, 1, о/ , «,...,0/0, «/ 1, ш4+ 3+ I О,

многочлен-делитель

х + -к3 + 1.

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

+ауХ

+...+а,х +ав,

коэффициенты ко4ь

00

со

4 О)

торого а.у, 1 0, N, принадлежит полю GF(L), разрядность каждого из регистров равна R log LЈ. со

...+al/4/J+...+a ш+а„ 0.

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

fff

блок 6 деления на и) в поле GF(L ).

314

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

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

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

подключается к третьей группе входов

20

узла сложения в поле GF(L) через узел умножения на W г в поле GF (1/) .

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

Перед началом работы сигналом по установочному входу все регистры 4 устанавливаются в нулевое состояние. На входы 1 подаются коэффициенты многочлена-делителя. Так как коэффициенты многочлена-делимого принадлежат 30 полю GF(L), каждый из них подается на группу из R соответствующих кодов 1. При делении многочленов с коэффициентами из поля GFCl/) используются все NR информационных входов ycl-35

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

Q(t + 1) U/Q(t) + A(t),(1)

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

45

где A(t) - элемент поля GF(L), соответствующий набору коэффициентов многочлена-делимого, подаваемому на входаг 1 в t-м такте; о

Q(t) элементы поля GF(), co- и Q(t+l) - ответствующие содержимому регистров 4 соответственно в моменты времени t и (t+1).55

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

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

у

Q(t+l) W Q(t) +A,(t) +u; A2(t) + + (t) + ... + uJlr- )(t).

где At-(t), i ,Д - элементы поля GF(I/), соответствующие наборам коэффициентов многочлена-делимого, поданным на i-й вход устройства. Например, в первом такте на входы устройства подаются коэффициенты

-(--Ijy м (/ -1)jf-ir M- f многочлена-делимого степени М, на втором - коэффициенты , ,., .. ., м-2ж- у на м коэффициенты

« ) Л/ч-

и т.д. (где о(. - коэффициент при j-й

степени X, j 0, М).

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

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

N - степень многочлена-делителя, причем тактовый вход устройства подключен к синхровходам регистров с первого по N-й, выходы которых подключены соответственно к выходам с первого по N-й устройства, отличающееся тем, что, с целью увеличения быстродействия, в него введены блок умножения наш в поле GF(l/r), где tt - примитивный элемент поля GF(L K), k - степень примитивного элемента поля GF(L), L - основание поля Галуа, блок сложения в поле GF(I/0, при этом информационные входы с первого по N-й устройства подключены соответственно к информационным входам регистров с первого по N-й, выходы которых подключены соответственно к входам блока умножения на W в поле GF(L), выходы которого с первого по N-й подключены соответственно к входам с первого по N-й второй группы блока умножения в поле GF(lf),

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

ные входы с первого по JJ N- i (где k/N) устройства исключены соответственно к входам с первого по блока преобразования, выходы с первого по N-й которого подключены соответственно к эходам с первого по N-й первой группы блока сложения в поле GF(L ), причем блок преобразования

содержит узел сложения в поле GF(L ) и () узлов умножения соответственно на СУ , где i N, 2N,..., V-I)N, в поле GFCL), причем с первого по N-й входы блока преобразования подI°

ключены соответственно к входам с первого по N-й узлы сложения в поле GF(LX), входы с (j N+l)-ro no (j+1) N-rt (где j ,.. .,) блока преоб- разовал ия подключены соответственно к входам с первого по N-й узла умножения на ш t выходы с первого по N-й которого подключены соответственно к входам с (j N-H)-ro no (j + 1) N-й узла сложения в поле GFCL O, выходы с первого по N-й которого подключены соответственно к выходам с первого по N-й блока преобразования.

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

Фм.1

1,

15

и

ь