Основные разделы


Основной цикл алгоритма

Напомним основные формулы:

(22)

На рис. 11 проиллюстрирован второй этап вычисления ДПФ. Линиями сверху вниз показано использование элементов для вычисления значений новых элементов. Очень удобно то, что два элемента на определенных позициях в массиве дают два элемента на тех же местах. Только принадлежать они будут уже другим, более длинным массивам, размещенным на месте прежних, более коротких. Это позволяет обойтись одним массивом данных для исходных данных, результата и хранения промежуточных результатов для всех T итераций.

Рис. 11. второй этап вычисления ДПФ

Итак, вот действия, которые нужно выполнить после первичной перестановки элементов.

#define T 4

#define Nmax (2 << T)Q, Temp, j(0, 1);complex x[Nmax];double pi2 = 2 * 3. 1415926535897932384626433832795;N, Nd2, k, mpNd2, m; (N = 2, Nd2 = 1; N <= Nmax; Nd2 = N, N += N)

{ for(k = 0; k < Nd2; k++) { W = exp(-j*pi2*k/N); for(m = k; m < Nmax; m += N) { mpNd2 = m + Nd2; Temp = W * x[mpNd2]; x[mpNd2] = x[m] - Temp; x[m] = x[m] + Temp; } }

}

Переменная Nmax содержит полную длину массива данных и окончательное количество элементов ДПФ. В таблице показано соответствие между выражениями в формуле (22) и переменными в программе.

Внешний цикл - это основные итерации. На каждой из них 2Nmax/N ДПФ (длиной по N/2 элементов каждое) преобразуются в Nmax/N ДПФ (длиной по N элементов каждое).

Следующий цикл по k представляет собой цикл синхронного вычисления элементов с индексами k и k + N/2 во всех результирующих ДПФ.

Самый внутренний цикл перебирает Nmax/N штук ДПФ одно за другим.

Именно так, а не иначе: сначала вычисляются элементы с номерами 0 и N/2, во всех ДПФ в количестве Nmax/N штук, потом с номерами 1 и N/2 + 1 и так далее. На рис. 4 показана последовательность вычислений для N = 8. Такая последовательность обеспечивает однократное вычисление .

Обратите внимание, что x[mpNd2] вычисляется раньше, чем x[k], чтобы значение x[k] не было модифицировано прежде, чем будет использовано.

Алгоритм обратного дискретного преобразования Фурье отличается только тем, что вместо -j надо использовать +j и после всех вычислений поделить каждое x[k] на Nmax.

Для справки: произведение, сумма и экспонента для комплексных чисел вычисляются по формулам:

(x, y)(x', y')=(xx'-yy')(xy'+x'y)

(x, y)+(x', y')=(x+x')(y+y') jv=(cos v, - sinv)

где v - действительное число [7].

Прочитайте еще и эти статьи:

Спутниковая навигация
- что же это такое? Global Positioning System - система глобального позиционирования, т.е. некая система, позволяющая с большой точностью определить координаты любого объекта на поверхности Земли. Благодаря появлению компактных GPS-модулей спутн ...

История создания радио
Радио - технология беспроводной передачи информации посредством электромагнитных волн радиодиапазона . Технические методы и средства, с помощью которых это делается, составляют предмет радиотехники. Научным фундаментом которой является ради ...

© Copyright 2021 | www.techattribute.ru