БПФ с прореживанием по времени

Первый алгоритм называется алгоритмом БПФ с прореживанием по времени.

Пусть задан N-отсчетный дискретный сигнал x (n). Примем, что N равно степени двойки. Если это не так, то всегда можно легко дополнить заданный сигнал нулевыми отсчетами до количества отсчетов, равного ближайшей степени двойки.

Разобьём исходный сигнал x (n) на два N/2-отсчетных сигнала x₁(n) и x₂(n), составленных соответственно из четных и нечетных отсчетов исходного сигнала x (n).

(1.6).

N-точечное ДПФ сигнала x (n) можно записать как.

(1.7).

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

(1.8).

можно записать.

(1.9).

или.

(1.10),.

где X₁(k) и X₂(k) — N/2-отсчетные ДПФ сигналов x₁(n) и x₂(n) соответственно.

Таким образом N-точечное ДПФ X (k) может быть разложено на два N/2-точечных ДПФ, результаты которых объединяются согласно (1.10).

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

Поскольку X (k) определено при, а X₁(k) и X₂(k) определены при, необходимо доопределить формулу (12.10) для. Учитывая, что X₁(k) и X₂(k) — периодические функции с периодомN/2, можно записать.

(1.11),.

поскольку .

Поэтому окончательно для N-точечного ДПФ можно записать.

(1.12).

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

Сначала входной сигнал x (n) разбивается на два сигнала x₁(n) и x₂(n), составленных соответственно из четных и нечетных отсчетов x (n). После этого рассчитывается ДПФ X₁(k) и X₂(k). Затем в соответствии с (1.12) получается X (k).

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

(1.13).

С учетом того, что можно записать.

(1.14).

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

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

(1.15).

Поскольку, то окончательно получим.

(1.16).

На рис. 11.3 представлена порядок операций при последовательном вычислении восьмиточечного ДПФ в соответствии с описанным алгоритмом. Анализ рис. 11.3 показывает, что на каждом этапе БПФ необходимо выполнить N/2 комплексных умножений. Поскольку общее количество этапов равно, то число комплексных умножений, необходимое для нахождения N-точечного ДПФ, приблизительно равно .

Приблизительность оценки означает, что умножения на в действительности сводятся просто к сложениям и вычитаниям комплексных чисел. Так на первом этапе алгоритма, представленного на рис. 11.3, содержатся только сложения и вычитания комплексных чисел поскольку. Даже на втором этапе используются только сложения и вычитания комплексных чисел т.к.. Фактически вместо ожидаемых 12 () достаточно выполнить всего два нетривиальных умножения. Однако для больших значений N фактическое число нетривиальных умножений хорошо аппроксимируется выражением .