На рисунке проиллюстрирован второй этап вычисления ДПФ. Линиями сверху вниз показано использование элементов для вычисления значений новых элментов. Очень удобно то, что два элемента на определенных позициях в массиве дают два элемента на тех же местах. Только принадлежать они будут уже другим, более длинным массивам, размещенным на месте прежних, более коротких. Это позволяет обойтись одним массивом данных для исходных данных, результата и хранения промежуточных результатов для всех T итераций.
рис. 4
Применение преобразования Фурье
Пусть у нас есть функция синуса x = sin (t).
Максимальная амплитуда этого колебания равна 1. Если умножить его на некоторый коэффициент A, то получим тот же график, растянутый по вертикали в A раз: x = Asin (t).
Период колебания равен 2π. Если мы хотим увеличить период до T, то надо умножить переменную t на коэффициент. Это вызовет растяжение графика по горизонтали: x = A sin (2πt/T). Частота колебания обратна периоду: ν = 1/T. Также говорят о круговой частоте, которая вычисляется по формуле: ω= 2πν = 2πT. Откуда: x = A sin (ωt).
И, наконец, есть фаза, обозначаемая как φ. Она определяет сдвиг графика колебания влево. В результате сочетания всех этих параметров получается гармоническое колебание или просто гармоника:
Очень похоже выглядит и выражение гармоники через косинус:
Большой разницы нет. Достаточно изменить фазу на π/2, чтобы перейти от синуса к косинусу и обратно. Далее будем подразумевать под гармоникой функцию косинуса:
x = A cos (2πt/T + φ) = A cos (2πνt + φ) = A cos (ωt + φ) (18)
В природе и технике колебания, описываемые подобной функцией чрезвычайно распространены. Например, маятник, струна, водные и звуковые волны и прочее, и прочее. Преобразуем (18) по формуле косинуса суммы:
x = A cos φ cos (2πt/T) — A sin φ sin (2πt/T) (19)
Выделим в (19) элементы, независимые от t, и обозначим их как Re и Im:
x = Re cos (2πt/T) — Im sin (2πt / T) (20)
Re = A cos φ, Im = A sin φ
По величинам Re и Im можно однозначно восстановить амплитуду и фазу исходной гармоники:
и (21) Рассмотрим очень распространенную практическую ситуацию. Пусть у нас есть звуковое или какое-то иное колебание в виде функции x = f (t). Пусть это колебание было записано в виде графика для отрезка времени [0, T]. Для обработки компьютером нужно выполнить дискретизацию. Отрезок делится на N-1 равных частей, границы частей обозначим tn = nT/N. Сохраняются N значений функции на границах частей: xn = f (tn) = { x0, x1, x2,…, xN }. В результате прямого дискретного преобразования Фурье были получены N значений для Xk:
Теперь возьмем обратное преобразование Фурье:
Выполним над этой формулой следующие действия: разложим каждое комплексное Xk на мнимую и действительную составляющие Xk = Rek + i Imk; разложим экспоненту по формуле Эйлера на синус и косинус действительного аргумента; перемножим; внесем 1/N под знак суммы и перегруппируем элементы в две суммы:
(24)
Это была цепочка равенств, которая начиналась с действительного числа xn. В конце получилось две суммы, одна из которых помножена на мнимую единицу j. Сами же суммы состоят из действительных слагаемых. Отсюда следует, что вторая сумма должна быть равна нулю. Отбросим ее и получим:
(25)
Поскольку при дискретизации мы брали tn = nT/N то можем выполнить замену: n = tnN/T. Следовательно, в синусе и косинусе вместо 2πkn/N можно написать 2πktn/T. В результате получим:
(26)
Сопоставим эту формулу с формулой (20) для гармоники:
x = Re cos (2πt/T) — Im sin (2πt / T) (20)
Слагаемые суммы (26) аналогичны формуле (20), а формула (20) описывает гармоническое колебание. Значит сумма (26) представляет собой сумму из N гармонических колебаний разной частоты, фазы и амплитуды. Выше объяснялось, каким образом формула вида (20) может быть преобразована в формулу вида (18):
x = A cos (2πt/T + φ) (18)
Выполним такое же преобразование для слагаемых суммы (26), преобразуем их из вида (20) в вид (18). Получим:
(27)
Далее будем функцию
Gk (t) = Ak cos (2πtk/T + φk) (28)
называть k-й гармоникой.
Для вычисления Ak и φk надо использовать формулу (21). Теперь выпишем в одном месте все формулы, которые связывают амплитуду, фазу, частоту и период каждой из гармоник с коэффициентами Xk:
(29)
Итак. Физический смысл дискретного преобразования Фурье состоит в том, чтобы представить некоторый дискретный сигнал в виде суммы гармоник. Параметры каждой гармоники вычисляются прямым преобразованием, а сумма гармоник — обратным.
Практическая часть Рассмотрим реализацию быстрого преобразования Фурье на примере 8 точек:
x 1+i 1 1+2i -1+2i i -2+i -2+2i 1−2i Разделим множество на четные и не четные:
x_even1 x_odd1 1+i 1 1+2i -1+2i i -2+i -2+2i 1−2i Затем снова, каждое из множеств разобьем на четное и не четное:
x_even2 x_odd2 x_even3 x_odd3 1+i 1+2i 1 -1+2i i -2+2i -2+i 1−2i Теперь можно вычислить преобразованные коэффициенты.
Воспользуемся формулой:
Где номер индекса.
X_even3 X_odd3 X_even2 X_odd2 -1+i 0 1+2i -1+4i 3-i -2+4i 1 3 Для дальнейших расчетов необходимо знать значения функции Продолжая вычисления, получим:
X_even1 X_odd1 6i -1+4i 2,1+2,9 999 999 999 9999i -0,99 999 999 999 999+4i 2−2i -1+4i -2,1−0,9 999 999 999 9999i -3,1
Эти значения рассчитываем по формуле:
Результат будет иметь вид:
X -1+10i 4,12 132 034 355 966+6,5 355 339 059 3272i 6−1,01i 0,12 132 034 355 963+1,1 213 203 435 5967i 1+2i -0,12 132 034 355 964−0,5 355 339 059 3274i -2−2,9 999 999 999 9999i -4,12 132 034 355 965−3,1 213 203 435 5965i
Для реализации комплексной арифметики в среде MS Excel использовались следующие средства:
=КОМПЛЕКС (a;b) — задание комплексного числа a+bi.
=МНИМ.ПРОИЗВЕД (a;b) — произведение двух комплексных чисел.
=МНИМ.РАЗН (a;b) — вычисление разности двух комплексных чисел a-b
=МНИМ.СУММ (a;b) — вычисление суммы комплексных чисел a+b
=МНИМ.EXP (a) — возведение экспоненты в комплексную степень a.
Список литературы
А. П. Господариков, Г. А. Колтон, С. А. Хачатрян. Ряды Фурье. Интеграл Фурье. Операционное исчисление. Учебно-методическое пособие. САНКТ-ПЕТЕРБУРГ, 2005.
Э. Ч. Титчмарш.
Введение
в теорию интегралов Фурье: — Санкт-Петербург, Ком
Книга, 2007 г.- 480 с.
А. Е. Полищук: Абелевы многообразия, тэта-функции и преобразование Фурье: — Москва, МЦНМО, 2010 г.- 312 с.
Г. Нуссбаумер. Быстрое преобразование Фурье и алгоритмы вычисления сверток. Перевод с английского Ю. Ф. Касимова и И. П. Пчелинцева под редакцией чл.-кор. АН Каз
ССР В. М. Амербаева и Т. Э. Кренкеля/ МОСКВА:
РАДИО И СВЯЗЬ — 1985
И. Снеддон. Преобразование Фурье. Издательство: ИНОСТРАННОЙ ИТЕРАТУРЫ — 1955
Залманзон Л. А. Преобразование Фурье, Уолша, Хаара и их применение в управлении, связи и других областях Наука: 1989
