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

с(х) = g (х) d (х) (mod л;" - 1)

можно сначала вычислить как линейную, а затем привести по модулю л;" - 1. Следовательно, эффективные способы вычисления линейной свертки дают также эффективные способы вычисления циклической свертки, и, обратно, эффективные способы вычисления циклической свертки можно легко превратить в эффективные способы вычисления линейной свертки. Циклическая свертка может быть записана в виде

гг-1

с,- = S g((, fe))dft, i = О,..., п - 1,

/г=0

где двойные скобки обозначают вычисление индексов по модулю п. Согласно теореме о свертке, в частотной области имеем

и, таким образом, циклическую свертку можно вычислить, последовательно применяя преобразование Фурье, покомпонентное умножение и обратное преобразование Фурье. Если п представляется произведением большого числа сомножителей, то быстрое преобразование Фурье (БПФ), которое будет описано в следующем параграфе, позволяет снизить число вычислений. Преобразование Фурье в поле GF (q") существует только для целых п, делящих *4исло q" - 1, и некоторые из этих п не допускают алгоритмов БПФ. Но в теории обработки дискретных сигналов хорошо известны методы удлинения векторов d, g и с до такой длины п, что компоненты с индексами i = О, п - 1, сохраняют нужные значения, а вектор с связан с векторами d и g соотношением циклической свертки, вычисляемой, однако, на длине п, удобной для применения алгоритмов БПФ.

Возьмем, например, удовлетворяющую условию п 2п длину п, на которой легко вычислить преобразование Фурье, и положим

= 0,...,п- 1,

= «,...,«- 1,

= 0,... п- 1,

= п,... п - п - 1,

= п - п,. .., п - 1,

be =

Щ, О, bi, О,

bi+n-n п-1

£ cikb((c-k)).

где двойные скобки в индексе обозначают вычисление по модулю п. Тогда ci = Ci, i = О, п - 1. Остальные значения с1 не представляют интереса и могут быть отброшены.

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

Предположим, что имеется устройство, вычисляющее циклическую свертку длины п, и что мы хотим воспользоваться этим устройством для умножения многочлена а (х), степень А которого меньше-, на многочлен b (х), степень В которого больше п, чтобы получить произведение с (х) = а (х) b (х). По имеющемуся многочлену b (х) сформируем множество многочленов (х),

Ь<2> (х), (л;)}, степень каждого из которых не превосхо-

дит п - 1, по следующему правилу:

ь? =

где S выбрано достаточно большим для того, чтобы были представлены все коэффициенты многочлена b (х). Отметим, что коэффициенты построенных многочленов перекрываются. Пусть

с<> (х) = а {х) [х) (mod х" - l), / = 1,..., s.

Коэффициенты многочлена с (х), за исключением первых А коэффициентов, содержатся среди коэффициентов многочленов (х), а именно

= А,...,п~ 1,

d = с\\

Ci+(n-A) =

= Л,..., «- 1,

= Л,..., п- 1

Ci+2 (п-А) = Cf\

И т. Д. Л младших коэффициентов многочлена с (х) теряются. Во многих приложениях при вычислении линейной свертки нужны не все коэффициенты выходного многочлена, и тогда описанная

процедура может быть удовлетворительной. Если же нужны все коэффициенты выходного многочлена с (х), то в проделанных выкладках следует просто заменить многочлен b (х) многочленом хЬ (х). Это позволит вычислить все необходимые коэффициенты, но все индексы будут сдвинуты на число А.

Каждая циклическая свертка, за исключением последней, дает п - А коэффициентов линейной свертки и А бесполезных коэффициентов, которые отбрасываются. Так как степень многочлена Ь* (х) может быть меньше, чем п - 1, то последняя свертка может давать больше, чем п - А, значимых коэффициентов.

11.2. БЫСТРЫЕ АЛГОРИТМЫ СВЕРТКИ

Известно много алгоритмов вычисления циклической свертки, и многие из них более эффективны, чем использование быстрого преобразования Фурье и теоремы о свертке. В данном параграфе будет описан быстрый алгоритм Винограда вычисления свертки. Этот метод пригоден для любого поля, но мы интересуемся только конечными полями GF (а). Он сводится к разбиению свертки на легко вычисляемые короткие свертки, которые формируются в соответствии с китайской теоремой об остатках для многочленов. Алгоритм Винограда находит вычет

с (х) = g (х) d (х) (той b (х))

для некоторого фиксированного многочлена b (х) над GF (q). Для построения алгоритма вычисления линейной свертки

с(х) = g (х) d (х)

выберем любое целое число Л, большее степени с (х), и любой многочлен b (х) степени N. Тогда имеем тривиальное утверждение

с (х) = с (х) (mod b (х)),

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

Чтобы разбить вычисление свертки по модулю многочлена на отдельные части, разложим b (х) на взаимно простые множители над некоторым подполем поля GF (q):

b (х) = bi (х) b (х) ... bs (х).

Обычно в качестве поля разложения выбирается простое подполе GF (р), и будем рассматривать этот случай; теория, однако, столь же пригодна и для любого подполя. Процедура минимизирует число умножений в GF (q) и не делает попыток такой минимизации в GF (р). В большинстве практических приложений простое поле является полем GF (2), умножение в котором тривиально.