j := j + k; end;

В данном алгоритме n – размер преобразования; массивы x и y содержат действительные и мнимые компоненты переставляемой последовательности.

Вычисление обратного ДПФ с помощью алгоритма прямого ДПФ

Для вычисления обратного ДПФ можно без каких-либо изменений использовать алгоритм прямого БПФ. Обратное ДПФ N-точечной последовательности X(k), k = 0, 1, …, N-1, определяется следующим образом:

1 N −1

x(n)= N ∑k =0 X (k )W −nk .

Взяв комплексно сопряженное выражение и умножив его на N, получим

N −1

Nx* (n)= ∑X * (k )W nk .

k =0

Правая часть формулы представляет собой ДПФ последовательности X*(k) и может быть вычислена с использованием одного из алгоритмов БПФ. Искомую последовательность x(n) можно получить, взяв комплексно сопряженное с предыдущим выражение и разделив его на N:

1 N −1

Nx* (n)= N ∑k =0 X * (k )W nk .

Таким образом, алгоритм БПФ обеспечивает вычисление и прямого, и обратного ДПФ.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Разработайте функцию, вычисляющую ДПФ от входного вектора длиной N, вызывая функцию Matlab FFT для векторов длиной N/2 с использованием прореживания по времени. Проверьте ее работу.

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

3. Для случая, когда N является степенью 2, модифицируйте функцию из задания 1, заменив вызов FFT рекурсивным вызовом, и предусмотрев останов, когда текущий размер преобразования достигнет 2.

4.Реализуйте функцию двоично-инверсной перестановки данных.

5.Скомбинируйте функции, реализованные в пп. 3 и 4.

6.Модифицируйте функцию из задания 5, заменив рекурсивные вызовы

циклом.

35