Login:
Password:
Auth @ DIMS.PRV
Регистрация

Преобразование Фурье

Под класс "Фурье-методы" (или "методы спектрального анализа") попадает большое количество различных вычислительных задач. В одних случаях преобразование Фурье - лишь удобный вычислительный инструмент для получения необходимой информации из экспериментальных данных. В других случаях Фурье-образ (или связанная с ним спектральная функция) - сама по себе представляет определенный интерес.

Какой-либо физический процесс может быть описан либо в области времен (т.е. физическая величина h представляется как функция от времени: h(t)), либо в области частот (при этом процесс описывается амплитудой H(f), а если с учетом фазы, то H - комплексное). В большинстве случаев можно считать h(t) и H(f) различными представлениями одной и той же функции. Взаимосвязь между этими представлениями устанавливается преобразованием Фурье:

H=F{h}, h=invF{H} (2.1)
H(f)=|h(t)*exp(-2pi*i*f*t)*dt (2.2)
h(t)=|H(f)*exp(2pi*i*f*t)*df (2.3)

Если использовать циклическую частоту ω=2πf, то выражения (2.2) и (2.3) будут выглядеть так:

H(w)=|h(t)*exp(-iwt)*dt (2.4)
h(t)=1/2pi|H(w)*exp(iwt)*dw (2.5)

Иногда рассматривают функции, пропорциональные (2.4) и (2.5), выбирая 1/sqrt(2pi) в качестве множителя перед интегралами в обоих выражениях.

Если процесс описывается не во времени, а в пространстве, то h является функцией от координат, а H - функцией от длины волны:

H=F{h}, h=invF{H} (2.6)

В большинстве реальных экспериментов мы имеем дело не с непрерывной функцией, а с выборкой значений, полученных с определенным шагом аргумента - Δ. Т.е нам известны значения функции h(t):

hi=h(iΔ), где i=...,-2,-1,0,1,2,...

Величину, обратную Δ, называют частотой дискретизации. Половину частоты дискретизации называют частотой Найквиста:

fn=1/2D (2.7)

Если непрерывная функция h(t), оцифрованная с интервалом Δ, имеет ограниченный спектр такой, что H(f)=0 при |f|>fN, то функция может быть полностью определена выборкой hi. Это утверждение известно под названием "теорема Шеннона-Котельникова". Если же реальный спектр оцифрованной функции выходит за диапазон, определяемой частотой Найквиста, то полученный спектр внутри диапазона (-fN , fN) будет искажен, а вне этого диапазона будут наблюдаться лишь "копии" спектра с этого участка.

Искажение фурье-образа
(1) - искаженный фурье-образ, (2) - истинный фурье-образ

Очевидно, чтобы уменьшить влияние этого эффекта, для частоты дискретизации следует выбирать частоту как минимум вдвое большую, чем самая высокочастотная составляющая исходного сигнала. С другой стороны, если мы достаточно хорошо оцифровали некоторую функцию, то можно считать, что ее фурье-образ равен нулю при частотах по модулю выше частоты Найквиста и рассматривать только диапазон (-fN , fN). "Качество" оцифровки можно оценить по поведению фурье-образа при приближении к частоте Найквиста: если он стремится к отличному от нуля значению, значит выбранная частота дискретизации мала, а фурье-образ искажен.

Предположим, что мы оцифровали N значений исходной функции:

hn=h(nΔ), где n=0,1,...,N-1

При этом по N точкам исходной функции мы можем получить не больше, чем N независимых значений ее фурье-образа (в граничных точках получаются одинаковые значения):

Диапазон дискретизации фурье-образа

Аппроксимируем интеграл (2.2) суммой:

H(fk)=D*SUMn(hn*exp(-2pi*i*n*k/N)) (2.8)

Сумму в формуле (2.8) называют дискретным преобразованием Фурье (дискретным фурье-образом - Hk). Взаимосвязь между дискретным преобразованием Фурье и выборкой из обычного фурье-образа устанавливается формулой (2.9), а вид обратного дискретного преобразования Фурье - формулой (2.10):

H(fk)=D*Hk (2.9)
hn=1/N/*SUMk(Hk*exp(2pi*i*n*k/N)) (2.10)

Прямой расчет фурье-образа функции по выборке из N значений потребует число операций, сравнимое с N2. С помощью специального алгоритма "быстрое преобразование Фурье" эта задача может быть решена за N log2N операций. Суть этого алгоритма сводится к следующему.

Вычисление фурье-образа в любой точке может быть записано через сумму фурье-образов, вычисленных по половине выборки по четным и нечетным точкам:

Hk=SUMe{N/2}+Wk*SUMo{N/2} (2.11)
Hk=He+Wk*Ho (2.12)

Здесь Hke обозначает k-тоe значение фурье-образа, рассчитанного по половине исходной выборки - по четным точкам, а Hko - по нечетным точкам. Следует заметить, что k пробегает значения от 0 до N-1, а период фурье-образов Hke и Hko - N/2, так что для получения значения исходного фурье-образа приходится брать два периода Hke и Hko.

Рекурсивно воспользовавшись таким преобразованием, мы можем свести проблему вычисления Hke к вычислению фурье-образов по выборке N/4: Hkee и Hkoe. Если N является степенью двойки, то такую рекурсию мы можем продолжать вплоть до разбиения исходной выборки на группы по одному элементу. Фактически, алгоритм быстрого преобразования Фурье применим только, если размер выборки является степенью двойки. Тогда при рекурсивном разбиении выборки на группы мы дойдем до групп размером в 1 элемент, фурье-образ каждой таких групп соответствует некоторому значению исходной функции:

Hkeoee...oee=hn

Очевидно, что это значение не зависит от k и периодично с периодом 1. Чтобы определить, какое значение исходной функции следует брать, примем e=0, а o=1. Тогда перевернутое представление верхнего индекса будет соответствовать двоичному представлению n.

Предположим, что оригинальная выборка hj отсортирована в порядке возрастания перевернутого двоичного представления индексов.

Порядок сортировки для 8 эл.
На рисунке показан порядок сортировки для выборки из 8 элементов.

Каждый элемент уже является значениям фурье-образа по группе из одного элемента. Соседние пары будут образовывать значения фурье-образов по группам из двух элементов. Затем комбинации соседних четверок дадут значения фурье-образов по группам из четырех элементов. Продолжая вычисления, мы дойдем до случая, когда комбинируя первую и вторую половину полученного массива, мы получим значения искомого фурье-образа.

Каждый этап комбинаций требует N операций, всего log2N этапов. Если считать что процесс перестановки исходных данных в требуемом порядке занимает пренебрежимо мало времени, весь алгоритм требует N log2N операций.

Подобный алгоритм применим и для вычисления фурье-образов функций от двух и более переменных. Двухмерное дискретное преобразование Фурье сводится к последовательным одномерным преобразованиям Фурье:

H(k1,k2)=F1{F2{h(j1,j2)}}=F2{F1{h(j1,j2)}} (2.13)