3.3. Вычисление двумерных ДПФ с помощью полиномиальных преобразований

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

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

3.3.1. Алгоритм редуцированного ДПФ

Рассмотрим двумерное -точечное ДПФ

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

Чтобы вычислить с помощью полиномиальных преобразований, необходимо сначала представить ДПФ в терминах алгебры полиномов. Это осуществляется заменой (3.72) на

В получено заменой Z на в (3.74). Таким образом, эквивалентны (3.72). Заметим, что на этом шаге нет необходимости задавать по модулю хотя такое задание справедливо, поскольку

Предположим теперь, что -простое. Тогда разлагается в произведение двух циклотомических полиномов:

При что соответствует представляет собой простое -точечное ДПФ

При всегда является корнем полинома

Поскольку — множитель — множитель можно определить по модулю вместо сводятся к

Если простое и то перестановка по модулю отображает все значения Таким образом, порядок следования индексов можно изменить посредством умножения их на что приведет к

Поскольку определен по модулю Подстановка Z вместо в (3.83) дает

где правая часть равенства не зависит от — полиномиальное преобразование последовательности длиной которое вычисляется без умножений с помощью только операций сложения. При этих условиях единственными умножениями, требуемыми для вычисления (-точечного ДПФ, являются те, которые соответствуют (3.84) и заданному (3.78) -точечному ДПФ.

Покажем теперь, что вычисление (3.84) эквивалентно вычислению дискретных преобразований Фурье последовательности длиной в которой последний входной отсчет равен 0, а первый выходной отсчет не вычисляется. Это можно видеть из того, что выходные отсчеты полиномиального преобразования (3.85) представляют собой полиномов по членов. Полагая, что эти полиномы заданы выражением

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

и подставляя их в (3.84), получим

Таким образом, для простого -точечное ДПФ отображается с помощью полиномиальных преобразований в -точечных ДПФ вместо -точечных ДПФ для построчно-столбцового метода вычислений. Схема вычислений по этому методу полиномиального преобразования показана на рис. 3.6. Воспользовавшись тем, что в N ДПФ, определенных (3.87), последний входной член равен нулю, а первый выходной член не вычисляется, можно получить небольшое дополнительное сокращение числа умножений. Это можно реализовать, если заметить, что, поскольку при и простом (3.87) можно переписать как

где

Тогда редуцированные ДПФ (3.88) можно вычислить как -точечные корреляции, используя алгоритм Рейдера [3.19]. Действительно, если примитивный корень по модулю то

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

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

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

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

Аналогичный метод полиномиального преобразования для вычисления ДПФ можно так же просто определить и для составного Условия выполнения полиномиального преобразования без умножений устанавливаются с помощью метода, очень похожего на тот, который использовался в подразд. 3.2.1 для двумерных сверток (табл. 3.9). Особенно интересен случай -точечного ДПФ при Эти ДПФ вычисляются, как показано на рис. 3.7, посредством одного -точечного полиномиального преобразования по модулю одного -точечного полиномиального преобразования по модулю -точечных редуцированных ДПФ, половина входных и выходных членов которых равна нулю, и одного -точечного ДПФ, которое, в свою очередь, можно вычислить аналогичным образом. Для случая наиболее интересно то, что полиномиальные преобразования вычисляются с помощью алгоритма типа БПФ, так что все вычисления организуются способом, очень похожим на традиционное вычисление БПФ.

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

В этом редуцированном ДПФ умножения на обычно являются комплексными. Однако, используя алгоритм Рейдера — Бреннера [3.15] или один из его производных, эти умножения можно преобразовать в умножения чисто вещественных

(кликните для просмотра скана)

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

или чисто мнимых чисел. Это осуществляется заменой входной последовательности последовательностью определяемой как

Тогда -точечное от вычисляется при

Поскольку вычисляются посредством простых сложений: четное; — нечетное, (3,96) где

Таблица 3.10. Число вещественных операций для коротких и редуцированных ДПФ (см. скан)

При использовании этого метода редуцированное ДПФ, определенное в (3.93), вычисляется за вещественных умножений и вещественных сложений, где — число умножений и число сложений, требуемых для вычисления -точечных ДПФ.

В разд. 3.6 приведены различные алгоритмы коротких редуцированных ДПФ, а в табл. 3.10 собраны данные о числе вещественных операций для наиболее часто употребляемых алгоритмов. На основании этих данных и алгоритмов коротких ДПФ, предназначенных для использования в алгоритмах Винограда преобразования Фурье [3.1, 3.2] и Рейдера — Бреннера, в табл. 3.11 показано число вещественных операций для различных двумерных ДПФ.

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

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