3.3.3. Вычисление преобразования Фурье методом Винограда с помощью полиномиальных преобразований

В подразд. 3.3.1 обсуждался эффективный метод вычисления ДПФ с помощью полиномиальных преобразований. Этот метод редуцированного ДПФ применим главным образом к многомерным ДПФ, когда имеется общий множитель в двух пли более измерениях, и основан на отображении многомерных ДПФ в одномерные и редуцированные ДПФ с помощью полиномиальных преобразований. В этом разделе предлагается другой метод вычисления ДПФ с помощью полиномиальных преобразований [3.1, 3.17]. Покажем, что если ДПФ вычислять с помощью алгоритма Винограда, полиномиальные преобразования можно использовать для отображения ДПФ в одномерные свертки и полиномиальные произведения. По сравнению с алгоритмом Винограда эти полиномиальные преобразования позволяют получить значительную экономию вычислений.

В данном методе ДПФ сначала преобразуется в многомерные корреляции с помощью алгоритма Винограда [3.1, 3.21]. Для -точечного ДПФ такое преобразование выполняется путем вычисления А-точечного ДПФ, в котором каждый скаляр заменяется -точечным ДПФ. Если и А-точечные ДПФ вычисляются как корреляции, в соответствии с алгоритмом Рейдера, эту вычислительную процедуру можно рассматривать как преобразование ДПФ (-точечного ДПФ в одномерные ДПФ и корреляции и двумерные корреляции. Например, для простого случая, соответствующего простым (-точечное ДПФ вычисляется, как следует из (3.102) — (3.104), посредством одного -точечного ДПФ, одной и одной -точечных корреляций. Такой же метод используется для вычисления одномерного -точеч-ного ДПФ, если — взаимно-простые, поскольку это ДПФ можно превратить в двумерное -точечное ДПФ простой переиндексацией с помощью алгоритма Гуда [3.20]. Если имеет более двух множителей, тот же метод можно применить рекурсивно. В этом случае ДПФ превращается в многомерные корреляции.

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

Рис. 3.8. Вычисление -точечного ДПФ с помощью алгоритма Винограда а полиномиальных преобразований

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

Этот метод иллюстрируется на рис. 3.8 для -точечного ДПФ. Так как -точечное ДПФ вычисляется посредством одного умножения и одной -точечной корреляции, то -точечное ДПФ отображается в одно -точечное ДПФ. одну -точечную корреляцию и одну -точечную корреляцию. Поэтому, если используется алгоритм, требующий 8 комплексных умножений для -точечнон корреляции, то -точечио ДПФ вычисляется в соответствии с обычным алгоритмом Винограда за 81 комплексное умножение. Вычисление -точечной

корреляции с помощью полиномиальных преобразований требует только 52 умножения вместо 64 для обычного метода вложения. Поэтому, если метод полиномиального преобразования сочетать с алгоритмом Винограда, число комплексных умножений, требуемых для вычисления -точечного ДПФ, снижается с 81 до 69. Необходимо заметить, однако, что первый метод полиномиального преобразования, который базируется на редуцированных ДПФ, потребовал бы в этом случае только 65 комплексных умножений. Фактически такой результат носит достаточно общий характер, и первый метод полиномиального преобразования, оперирующий с большими полями, где бы он ни использовался, обычно предпочтительнее.

Наиболее интересным применением второго полиномиального преобразования, базирующегося на полях меньшей протяженности, является вычисление ДПФ, для которого первый метод неприменим. Это относится к случаям двумерных ДПФ, когда обе размерности не содержат общих множителей, в то время как при соответствующей двумерной корреляции общие множители для обеих размерностей имеются. Например, -точечное ДПФ нельзя вычислить эффективно первым методом, так как 7 и 9 не имеют общих множителей. При использовании алгоритма Винограда это ДПФ вычисляется методом вложения -точечных ДПФ. При использовании алгоритма Рейдера -точечное ДПФ превращается в одно умножение и одну -точечную корреляцию, а -точечное ДПФ — в 5 умножений и одну -точечную корреляцию. Таким образом, -точечное ДПФ вычисляется посредством пяти -точечных ДПФ, одной 6- и одной -точечных корреляций. Использование полиномиальных преобразований для вычисления -точечной корреляции порождает алгоритм, требующий только 174 действительных умножений вместо 198 для обычного алгоритма Винограда.

Чтобы достичь максимальной эффективности при вычислении больших многомерных ДПФ, целесообразно сочетать оба метода полиномиальных преобразований. Если это сделать, например, при -точечном ДПФ, то ДПФ вычисляется методом вложения и -точечных ДПФ с помощью первого метода полиномиального преобразования, который отображает -точечное ДПФ за одно умножение плюс корреляций, а -точечное ДПФ — за 33 умножения плюс корреляций. Таким образом, -точечное ДПФ вычисляется за 33 умножения, корреляций и 96 -точечных корреляций. Если -точечные корреляции вычисляются с помощью полиномиальных преобразований, -точечное ДПФ вычисляется за 11 344 действительных умножений вместо 13 650 умножений только для первого метода и 19 602 умножений для традиционного алгоритма Винограда. Необходимо заметить, что при совместном применении двух методов полиномиального преобразования число сложений также уменьшается по сравнению с применением только первого метода.

В табл. 3.12 дано число вещественных операций для комплексных двумерных ДПФ, вычисляемых с помощью двух методов полиномиального преобразования. Можно видеть, что даже для преобразований массивов больших размерностей число умножений и сложений может быть очень небольшим [например, -точечное ДПФ вычисляется посредством 3,39 действительных умножений на отсчет или около одного комплексного умножения на отсчет].

На практике экономия вычислений, полученная с помощью двух методов полиномиальною преобразования, может быть весьма значительной, что видно

Таблица 3.12. Число вещественных операций для комплексных двумерных ДПФ, вычисляемых с помощью комбинации двух методов полиномиального преобразования и метода послойного вложения

при сравнении данных табл. 3.11 и 3.12 с данными табл. 3.13. Последние соответствуют двумерным ДПФ, вычисляемым с помощью алгоритма БПФ Рендера—Бреннера и построчно — столбцового метода. При использовании только первого метода полиномиального преобразования число сложений всегда меньше, чем при использовании алгоритма БПФ, а число умножений для ДПФ массивов больших размерностей уменьшается примерно в два раза. При объединении двух методов полиномиального преобразования число сложений остается таким же, как у алгоритма БПФ, а число умножений уменьшается при мерно в четыре раза для ДПФ массивов больших размерностей. Метод полиномиального преобразования также значительно эффективнее, чем алгоритм Винограда преобразования Фурье. Это можно видеть из того, что чечное ДПФ, вычисляемое по этому алгоритму, требует 6,25 умножений и 91,61 сложений на огсчет, тогда как первый метод полиномиального преобразования требует 7,67 умножений и 54,58 сложений на отсчет для -точечного ДПФ, а сочетание двух методов полиномиального преобразования порождает алгоритм только с 3,39 умножениями и 70,33 сложениями на отсчет для (-точечного ДПФ.

Таблица 3.1. Число вещественных операций для комплексных двумерных ДПФ, вычисляемых по алгоритму БПФ Рейдера — Бреннера и построчно-столбцовому методу