6.4. АЛГОРИТМЫ БПФ ДЛЯ СОСТАВНОГО ЗНАЧЕНИЯ N

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

общем случае эффективное вычисление дискретного преобразования Фурье связано с представлением в виде произведения сомножителей [1, 7, 9, 10]

Как мы видели в случае, когда является степенью 2 (когда все сомножители равны 2), такое разложение приводит к высокоэффективному вычислительному алгоритму. Кроме того, все необходимые вычисления имеют вид «бабочки», что, по существу, соответствует двухточечному ДПФ. По этой причине -точечные алгоритмы особенно просты для реализации; на практике выгодно всегда иметь дело с последовательностями длины . Это можно сделать во многих случаях, просто дополняя последовательность конечной длины нулями, если это необходимо. Однако в некоторых случаях невозможно выбрать в виде степени 2, что приводит к необходимости рассмотрения более общей ситуации (6.25). Поэтому рассмотрим применение принципа прореживания по времени, когда является произведением сомножителей, не все из которых равны 2. Пусть рърз так что Если является степенью 2, можно выбрать Используя прореживание по времени, можно разложить на две последовательности длины состоящие из четных и нечетных выборок соответственно. Если то можно разделить входную последовательность на последовательностей длины так, что каждая выборка попадает в одну последовательность. Например, если так что то можно разложить на три последовательности длины 4, причем первая последовательность состоит из выборок вторая — из а третья — из . В общем случае можно записать в виде

Внутренние суммы можно представить как -точечные ДПФ:

потому что, как легко проверить,

Таким образом, (6.26) представляет в виде дискретных

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

Следовательно, коэффициент заменяется выражением (6.29), и поэтому общее требуемое число комплексных умножений и сложений станет равным

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

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

Однако имеются примеры (в особенности при или 8), когда получается дополнительная экономия, не вытекающая из (6.31).

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

Внутренняя сумма является шеститочечным ДПФ, соответствующим первой последовательности при второй последовательности при и третьей последовательности при . В этом случае шеститочечные имеют период, кратный шести. Вычисления по (6.32) иллюстрируются рис. 6.24.

Рис. 6.24. Направленный граф первой ступени разложения -точечного ДПФ

Шеститочечные ДПФ, соответствующие внутренней сумме в (6.32), могут быть далее разложены путем разбиения последовательностей на три двухточечные или две трехточечные подпоследовательности. Разбивая каждую шеститочечную подпоследовательность на три двухточечные, заменим внутреннюю сумму на тогда общая формула для вычисления примет вид

Одно из шеститочечных показано подробно на рис. 6.25. Другие имеют аналогичную форму. Если рис.

6.25 и соответствующие графы расположить в соответствующих местах рис. 6.24, то входная последовательность будет расположена в следующем порядке: . Из рис. 6.24 и 6.25 видио, что при таком порядке входов вычисления будут выполняться по алгоритму с замещением. Двухточечные преобразования рис. 6.25 сначала имеют вид «бабочек»; основная операция трехточечного ДПФ имеет более сложный вид, но тем не менее является вычислением с замещением. Вместо двоичной инверсии входы упорядочены более сложным образом. А именно, если обозначить через входной массив, то можно показать, что где .

Рис. 6.25. Направленный граф последующего разложения одного из шеститочечных ДПФ на рис. 6.24

Рис. 6.26. Направленный граф основной операции для коэффициентов, равных 3

Иначе говоря, входы должны запоминаться в обобщенном порядке с разрядной инверсией для того, чтобы проводить вычисления с замещением. Как видно из рис. 6.24, результирующие выходные отсчеты появляются в обычном порядке. Конечный этап вычисления БПФ в соответствии с алгоритмом рис. 6.24 показан на рис. 6.26 для

В случае сомножителей 2 можно уменьшить число умножений в 2 раза, используя симметрию. В случае сомножителей 3 аналогичное преобразование графа рис. 6.26 дает рис. 6.27. Так как то основным комплексным множителем является Следовательно и все степени этого множителя являются комплексными коэффициентами, требующими умножений. Поэтому граф на рис. 6.27 не более эффективен, чем граф на рис. 6.26.

Можно показать, что основное вычисление в ДПФ при коэффициенте 4 (т. е. при ) имеет вид рис. 6.28. В этом случае направленный граф рис. 6.28 может быть перечерчен в виде рис. 6.29 с сопутствующим сокращением девяти комплексных

Рис. 6.27. Другая перегруппировка рис. 6.26.

Рис. 6.28. Направленный граф основной операции для коэффициентов 4

умножений из двенадцати. Аналогичная экономия имеет место для сомножителей 8, 16 и т. д. [11]. Таким образом, даже если иногда выгодно основывать вычисления на сомножителях 4, используя одну ступень, основанную на коэффициенте 2, если нечетно.

В этом параграфе предпринята попытка указать на некоторые преимущества и недостатки использования значений с сомножителями, не равными 2. Основными преимуществами являются большая гибкость и быстродействие в некоторых случаях, основным недостатком — большая сложность вычислительного алгоритма. Хотя мы обсудили только алгоритм с прореживанием по времени, аналогичные рассуждения справедливы также и для прореживания по частоте. Более подробно алгоритмы БПФ с составными общего вида изложены в [9] и [10].

Рис. 6.29. Другая перегруппировка рис. 6.28, дающая экономию числа умножений