Преобразование Фурье действительной или комплекснозначной функции x(t), заданной на бесконечном интервале, представляет собой комплексную величину
Если область интегрирования не ограничена, то, как уже отмечалось ранее, преобразование X(¦) не существует, если реализация x(t) обладает всеми свойствами стационарного случайного процесса. Ограничив интервал задания функции х(t), скажем, приняв его равным [0, Т], можно построить конечное преобразование Фурье
(7)
Предположим теперь, что функция x(t) представлена N эквидистантными наблюдениями с интервалом дискретности h, который выбран таким образом, что частота среза достаточно высока. Поскольку t0= О, моменты tn = nh (в данном случае удобно начать с п = 0). Уравнение (6) запишется в виде:
Дискретная аппроксимация выражения (7) при произвольном значении f есть:
(7a)
Для расчета функции X(f, T) обычно выбираются дискретные значения частоты:
Преобразованная последовательность дает на этих частотах составляющие Фурье:
(8)
причем интервал дискретности h внесен в значение X(fk, T), чтобы перед знаком суммы не было множителя. Заметим, что преобразование однозначно только до значений k=N/2, поскольку этой точке соответствует частота Найквиста. Быстрое преобразование Фурье применяется для вычисления последовательности Xk,но может быть также использовано для нахождения коэффициентов Фурье Aqи Bqиз соответствующих формул. Упростим обозначения, положив:
Заметим, что W(N) = 1 и при всех и и v справедливо равенство
Положим также:
Формула (8) примет теперь вид:
(9)
Следует внимательно рассмотреть уравнения (8) и (9), представляющие собой не что иное, как преобразование Фурье последовательности х(п), содержащей конечное число N членов. Для расчета всех значений X(k) по этим формулам необходимо выполнить примерно N2операций умножения и сложения комплексных чисел (одна такая комплексная операция эквивалентна четырем операциям умножения и сложения действительных чисел).
Идея быстрого преобразования Фурье. Быстрое преобразование Фурье основывается на представлении величины N в виде ряда (отличных от единицы) сомножителей и в выполнении обычного преобразования Фурье для более коротких последовательностей, число членов в которых определяется соответствующими сомножителями. Если N может быть представлено в виде произведения р целых и больших единицы чисел
то, как доказано ниже, входящая в уравнение (9) последовательность X(k) может быть найдена итеративно путем расчета суммы р слагаемых:
(N/r1) преобразований Фурье, каждое из которых требует 4r12операций с действительными числами;
(N/r2) преобразований Фурье, каждое из которых требует 4r22операций с действительными числами;
………………………………………….
(N/rp) преобразований Фурье, каждое из которых требует 4rp2операций с действительными числами.
Таким образом, общее число операций:
В результате при использовании БПФ, а не стандартного метода получаем коэффициент ускорения вычислений (к.у.в.):
Пример 9.3. Коэффициент ускорения вычислений для 2р, где р - целое число.
В этом случае, согласно формуле для к.у.в.:
Однако скорость вычислений можно увеличить еще вдвое, используя следующее свойство: при N = 2р все значения W(kn) равны либо +1, либо -1. Таким образом:
(10)
Но иэтот результат представляет собой лишь консервативную оценку; в действительности можно добиться нового двукратного увеличения скорости, разделив исходную реализацию пополам и производя расчет. В частности, при N = 213 = 8192 из формулы (10) получаем, что к.у.в.=(8192/52) « 158.
Оценка спектральной плотности. Полученные результаты показывают, что первичная оценка спек тральной плотности для отдельной реализации x(t) на частоте f, имеет вид:
(11)
Так как Т = Nh, то, согласно обозначению (7а),
На стандартных дискретных значениях частоты:
которые получают при использовании метода БПФ, коэффициенты ряда Фурье определяются формулой (8):
(12)
Таким образом, как вытекает из соотношений (11) и (12), оценка спектральной плотности принимает вид
