Аналогично определим

gkix) = Ц gk.k-x, k" = 0, п" - 1,

fe=0

Ck W =l! с,: /е"*, k" = 0, n"--l.

При этом двумерная свертка превращается в одномерную свертку многочленов:

Cl- (X) = i; gnk-k")) W 4- W (mod x«- - 1), /•" = 0,..., n" - 1.

;e"=0

Для каждого г" в этой сумме производится сложение п" произведений многочленов. Всего имеется (п") произведений многочленов. Каждое из произведений многочленов является сверткой и может быть вычислено с помощью подходящего алгоритма. Одним из таких алгоритмов является алгоритм Винограда вычисления свертки.

Для полного вычисления свертки алгоритмом Агарвала- Кули надо применить также алгоритм Винограда вычисления свертки по второму измерению. Но сначала остановимся и оценим сложность этих промежуточных вычислений. Пусть М (1) и А (I) обозначают соответственно число сложений и число умножений, необходимых для вычисления свертки с помощью имеющихся в некоторой доступной библиотеке алгоритмов вычисления циклической свертки. Тогда для вычисления двумерной свертки необходимо (nf М (п) умножений и (n"f А (п} + + (п" - 1) п"п сложений. Эти вычисления можно выполнить даже еще лучше, воспользовавшись алгоритмом Винограда вычисления свертки и вдоль второй оси.

Так как алгоритм Винограда вычисления свертки представляет собой тождество, содержащее сложения и умножения, то можно заменить в нем арифметические элементы многочленами. Следовательно, Сг (х) можно вычислить за А4 {п") умножений многочленов И А (п") сложений многочленов, а для выполнения каждого умножения двух многочленов потребуется М (п) арифметических умножений и А (п} арифметических сложений, так что всего получится М (п ) М (п) арифметических умножений и М (п") А (п) + А (п") М (п) арифметических сложений. Число сложений не является симметричной функцией относительно параметров п и п", чем можно воспользоваться для минимизации числа сложений.

Аналогично если длина п циклической свертки является произведением трех или более взаимно простых множителей.

Рис. 11.5. Характеристики некоторых алгоритмов Агарвала-Кули вычисления циклических сверток. (Используются алгоритмы коротких сверток, приведенные на рис. 11.1.)

то алгоритм Агарвала-Кули позволяет преобразовать эту свертку в трехмерную или многомерную циклическую свертку и вычислять по каждому отдельному измерению циклическую свертку с помощью алгоритма Винограда.

Структуру многомерной циклической свертки можно описать через одномерные циклические свертки также с помощью кроне-керовского произведения (кронекеровское произведение будет описано в § 11 5). На рис. 11.5 приведена таблица мультипликативной сложности некоторых алгоритмов Агарвала-Кули вычисления циклической свертки в полях характеристики 2.

11.5. АЛГОРИТМ ВИНОГРАДА

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Отличный от рассмотренного ранее метод вычисления быстрого преобразования Фурье дается БПФ-алгоритмом Винограда. Этот алгоритм основывается на четырех отдельных идеях: алгоритме Рейдера, описанно.м в § 11.2 алгоритме Винограда вычисления коротких сверток, схеме индексации алгоритма Гуда-Томаса для простых множителей, гнездовом алгоритме Винограда (см.

Такое сведение преобразования Фурье на большой длине к совокупности преобразований Фурье на меньших длинах получило название гнездового алгоритма Винограда. - Прим. перев.

ниже). БПФ-алгоритм Винограда лучше БПФ-алгоритмов Кули- Тьюки и Гуда-Томаса по числу умножений, но сложнее по структуре. За уменьшение числа умножений приходится платить усложнением индексации и использованием операций отображения.

БПФ-алгоритм Винограда подразделяется на малый БПФ-алгоритм Винограда и большой БПФ-алгоритм Винограда. К малому алгоритму относятся преобразования, длина которых равна малому простому числу или степени малого простого числа. Большой БПФ-алгоритм Винограда объединяет малые БПФ-алгоритмы Винограда, чтобы получить преобразование на большой длине

Первым шагом является построение малого БПФ-алгоритма Винограда. Если п - малое простое число, то воспользуемся алгоритмом Рейдера, сводя вычисление преобразования Фурье к вычислению циклической свертки, которую в свою очередь вычислим с помощью алгоритма Винограда вычисления коротких сверток. В общем случае уравнения выписываются непосредственно, так что выбирать слишком большие п непрактично. В алгоритме Рейдера сведения дискретного преобразования Фурье к свертке используется только переиндексация; на этом шаге не требуется никаких сложений и умножений. Структура алгоритма вычисления свертки включает сначала сложения, потом умножения и затем опять сложения. Если п представляет собой степень малого простого числа, то можно использовать ту же самую процедуру, заменив алгоритм Рейдера некоторым более общим алгоритмом, который мы рассматривать не будем.

Построим алгоритм Винограда вычисления пятиточечного БПФ в поле GF (Щ, находящий величины

Vj = И to/Wi, / = О, . . ., 4, (О = аЗ.

Воспользуемся рассмотренным ранее (см. § 9.8) алгоритмом Рейдера, сводящим пятиточечное преобразование Фурье к свертке

b (х) = g (х) а (х) (mod л:* - 1),

g (х) = + а"х2 + а}4 + а", а (х) = VgX + v} + vx + Vt,

b (x) = (I/3 - 1/0) x« + {V, - Vo) x + {V, -Vo)x + (Vx - l/o).