Девятиточечная циклическ,йя свертка, 19 умножений

Семиточечиая циклическая свертка, 13 умножений

для полей характеристики 2.

необходимо 15 умножений. Однако поскольку данный частный многочлен g (х) имеет только два отличных от единицы значения коэффициентов, то тривиально просто так организовать вычисление, что понадобится только шесть умножений. Быстрый алгоритм, который будет приведен ниже, превосходит алгоритмы как с 15, так н с шестью умножениями. Заметим также, что молено воспол1,зоБаться приведенным на рис. 11.1 алгоритмом

10 110 0 0 0 1 10 1010 0 10 11010 0 10 0 110 0 110 0 0

10 0 0 1 о 1 fl 10 10

loot

110 0 1 1 Г1

1 111 1 1 1.1 1111

do d, d2

Рис. 11.2. Алгоритм Винограда для вычисления четырехточечиой свертки.

семиточечной свертки, который, однако, содержит 13 умножений. •

Согласно изложенной выше теории, можно выбрать любой многочлен b (х), степень которого не меньше 7. Выберем b (х) - = а: -f 1; тогда

(х +1) = (х+1)(х + х+ 1) (х + х+1) = = by (х) Ь (х) bs (х).

Можно было бы выбрать также многочлен

b (X) = х{х+ 1)2 (х + х+ 1),

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

Прежде всего найдем все необходимые для алгоритма фиксированные многочлены:

g<i) (х) = Rb, (.) Ig (х) 1 - а, gi2) = R,,,i lg(x)] = l, g(3) (д;) = i, [g х)] == + ах+ I.

Выполняемое в таком виде вычисление свертки с (х) требует четырех умножений и 35 сложений в поле GF (8). Несомненно,

Согласно китайской теореме об остатках для многочленов, flC) (х) = xf" + + х + х + х + х + 1, а(2> (х) = х + х + х + I, а(З) х) = а:« + + x« + 1.

Теперь нам надо вычислить три короткие свертки: с(1) (х) = g(i> (х) d(i> {х) = adC) (х),

с(3) (х) = g(3) (х) (х) = (аЗх2 + аЧ f 1) (х).

По заданному многочлену d (х) вычисляем вычеты

dC) (х) = + di + 4.

сГ(2> (х) = dax + dix + c?o.

d(3) (д;) = dx + c?ix + do-

Таким образом, для вычисления (х) требуется одно умножение, для вычисления с<> (х) умножений делать не надо, а для вычисления с> (х) требуется три умножения. Собирая вместе все эти вычисления, получаем следующее выражение для свертки:

с (X) = (Ах + A2 + A + A,+As)x + (Ах + As + A, + А,) г + + (Ах + А2 + А + А, + As) X* + (Ах + А2+ As + + А + А, + Ае) х +

+ (Ах + А2 + As + А + А, + А, + А,) х +

+ (Ах + As + А + А, + А., + As)x + (Ах + А, +

+ А, + As),