1.3.3.    Математическая теория БПФ. Алгоритм БПФ с прореживанием по времени

Несмотря на то, что алгоритмы БПФ хорошо известны и широко используются, при первом ознакомлении с ними они по ряду причин достаточно трудны для понимания. К тому же в современной научно-технической литературе встречается несколько различных подходов к описанию алгоритмов БПФ. В данном разделе мы познакомимся с теорией алгоритмов БПФ по основанию 2. Термин «по основанию 2» говорит о том, что число входных отсчетов N кратно степени числа 2, то есть . Среди этих алгоритмов различают два основных типа:

· алгоритм БПФ с прореживанием по времени (decimation-in-time – DIT);

· алгоритм БПФ с прореживанием по частоте (decimation-in-frequency – ьDIF).

Дискретное преобразование Фурье конечной последовательности было определено нами ранее и описывается выражением (1.24). Основная идея БПФ состоит в том, чтобы разбить исходную N-точечную последовательность на две более короткие последовательности, ДПФ которых могут быть скомбинированы таким образом, чтобы получилось ДПФ исходной N-точечной последовательности. Так, например, если N четное, а исходная N-точечная последовательность разбита на две (N/2)-точечные последовательности, то для вычисления искомого N-точечного ДПФ потребуется порядка  комплексных умножений, т.е. вдвое меньше по сравнению с прямым вычислением. Здесь множитель (N/2)² дает число умножений, необходимое для прямого вычисления (N/2)-точечного ДПФ, а множитель 2 соответствует двум ДПФ, которые должны быть вычислены.

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

Проиллюстрируем описанную методику для N-точечной последовательности , считая, что N равно степени 2. Введем две (N/2)-точечные последовательности  и  из четных и нечетных членов  соответственно, т. е.

                                 (1.28)

В этом случае N-точечное ДПФ последовательности  можно записать следующим образом:

     (1.29)

С учетом периодичности и симметричности поворачивающих множителей следует:

.                                              (1.30)

Перепишем выражение (1.29) в следующем виде:

.                                 (1.31)

Полученные суммы представляют собой прямые ДПФ исходных последовательностей  и , тогда выражение (1.31) приводится к виду:

.                                          (1.32)

Из формулы (1.32) следует, что N-точечное ДПФ X(k) может быть разложено на два (N/2)-точечных ДПФ, результаты которых объединяются согласно выражению (1.32). Если бы (N/2)-точечные ДПФ вычислялись обычным способом, то для вычисления N-точечного ДПФ потребовалось бы, очевидно, (N²/2+N) комплексных умножений. При больших ‘>N(когда N²/2>>N) это позволяет сократить время вычисления на 50%.

Поскольку X(k) определено при , а X₁(k) и X₂(k) определены при , необходимо доопределить формулу (1.32) для . Это определение является прямым следствием периодичности ДПФ и симметричности
поворачивающих множителей. Принимая во внимание симметрию поворачивающих множителей

,

получим следующее выражение для доопределения коэффициентов ДПФ:

.                                        (1.33)

На рис. 1.18 с помощью направленного графа представлена последовательность операций при выполнении восьмиточечного ДПФ с использованием двух четырехточечных преобразований.

Входную последовательность  сначала разбивают на две последовательности  и  из четных и нечетных членов , после чего рассчитывают их преобразования  и . Затем в соответствии с формулой (1.33) получают . Незачерченные кружки в правой части (рис. 1.15) обозначают операцию сложения (вычитания), причем верхний выход соответствует сумме, а нижний – разности. Стрелка (®) обозначает операцию умножения входного числа (a) на значение множителя, указанного над стрелкой. В общем случае переменные являются комплексными числами. Заметим, что кружок можно интерпретировать

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

Рассмотренная схема вычислений может быть использована для расчета (N/2)-точечных ДПФ в соответствии с формулой (1.33). Каждая из последовательностей  и  разбивается на две последовательности, состоящие из четных и нечетных членов. Аналогично (N/2)-точечные ДПФ могут быть записаны как комбинации двух (N/4)-точечных ДПФ, т.е.

                                            (1.34)

где ,  и  – (N/4)-точечные ДПФ соответственно четных и нечетных членов .

На рис. 1.16 показан результирующий направленный граф, в котором четырехточечные ДПФ (см. рис. 1.15) рассчитываются согласно формуле (1.34).

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

                                                           (1.35)

или

                                               (1.36)

Здесь  – преобразуемая двухточечная последовательность. Поскольку , для вычислений по формулам (1.36) действительно не нужны операции умножения. Таким образом, восьмиточечное ДПФ (см. рис. 1.15 и 1.16) в итоге сводится к алгоритму, описываемому направленным графом (рис. 1.17).