6.2. Введение в алгоритмы БПФ с основанием 2

Несмотря на то, что алгоритмы БПФ хорошо известны и широко используются, при первом ознакомлении с ними они по ряду причин достаточно трудны для понимания. Прежде всего, читателю нужно усвоить много новых терминов. К тому же в литературе встречается несколько различных подходов к описанию алгоритмов БПФ, которых появилось очень много. Наконец, ввиду сложности операции перестановки данных ее проще всего понять на конкретных примерах.

ДПФ конечной последовательности , , было определено в гл, 2 как

                            (6.1)

или в более удобной форме как

,             (6.2)

где . Легко показать, что  является периодической последовательностью с периодом , т. е.

, .                     (6.3)

Ниже будет показано, что периодичность  является одним из ключевых моментов БПФ. Часто периодичность  подчеркивают тем, что вместо  записывают .

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

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

                   (6.4)

-точечное ДПФ последовательности  можно записать как

С учетом того, что

,                   (6.7)

перепишем выражение (6.6) в виде

                            (6.8)

                     (6.9)

где  и  равны -точечным ДПФ последовательностей  и . Из формулы (6,9) следует, что -точечное ДПФ  может быть разложено на два -точечных ДПФ, результаты которых объединяются согласно (6.9). Если бы -точечные ДПФ вычислялись обычным способом, то для вычисления -точечного ДПФ потребовалось бы, очевидно,  комплексных умножений. При больших  (когда ) это позволяет сократить время вычисления на 50%.

Поскольку  определено при , а  в  определены при - необходимо доопределить формулу (6.9) для . Это определение достаточно очевидно и может быть записано следующим образом:

                          (6.10)

На фиг. 6.1 с помощью направленного графа представлена последовательность операций при выполнении восьмиточечного ДПФ с использованием двух четырех точечных преобразований. Входная последовательность  сначала разбивается на две последовательности  и  из четных и нечетных членов  после чего рассчитываются их преобразования  и . Затем в соответствии с формулой (6.10) получают .

Фиг. 6.1. Вычисление восьми точечно го ДПФ через два четырехточечных ДПФ.

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

                       (6.11)

или

                       (6.12)

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

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

Фиг. 6.2. Вычисление восьмиточечного ДПФ через два четырехточечных ДПФ, которые в свою очередь вычисляются через четыре двухточечных ДПФ.

Фиг. 6.3. Восьмиточечное ДПФ, полученное последовательны прореживанием в 2 раза.

Двухточечное ДПФ , , может быть рассчитано без использования умножений по формулам

                           (6.13)

Здесь ,  - преобразуемая двухточечная последовательность. Поскольку  и , для вычислений по формулам (6.13) действительно не нужны операции умножения. Таким образом, восьмиточечное ДПФ (фиг. 6.1 и 6.2) в итоге сводится к алгоритму, описываемому направленным графом, представленным на фиг. 6.3.