Пpеобpазование фypье


Содержание

Основные свойства преобразования Фурье

Между колебанием s(t) и его спектром S(w) существует однозначное соответствие. Для практических приложений важно установить связь между преобразованием колебания и соответствующим ему изменением спектра. Из многочисленных возможных преобразований колебания рассмотрим следующие наиболее важные и часто встречающиеся: сдвиг колебания во времени, изменение масштаба времени, сдвиг спектра колебания по частоте, дифференцирование и интегрирование колебания, сложение, произведение и свертка двух колебаний, а также свойства взаимной обратимости w и t в преобразованиях Фурье.

2.4.1 Сдвиг колебания во времени

Пусть колебание s1(t) произвольной формы существует на интервале времени от t1 до t2 и обладает спектральной плотностью S1(w), т.е. известен закон соответствия s1(t) « S1(w). Рассмотрим такой же сигнал, но возникающий на t секунд позднее. Принимая точку t за новое начало отсчета времени, получим новый смещенный сигнал s2(t) = s1(t — t). Тогда спектральная плотность смещенного колебания после введения новой переменной t = t — t в соответствии с (2.24) определится как:

Из этого соотношения видно, что сдвиг во времени функции s(t) на величину ±t приводит к изменению фазовой характеристики спектра S(w) на величину ±wt. Очевидно и обратное положение: если всем составляющим спектра функции s(t) дать фазовый сдвиг j(w) = ±wt, линейно связанный с частотой w, то функция сдвигается во времени на величину ±t.

Амплитудно-частотная характеристика спектра (т.е. модуль спектральной плотности) от положения колебания на оси времени не зависит, т.к. комплексное число exp(-jwt) при любых t имеет единичный модуль.

2.4.2 Изменение масштаба времени

Предположим, что исходный сигнал s(t) подвергнут преобразованию, связанному с изменением масштаба времени, т.е. роль времени t будет играть новая независимая переменная kt, где k – некоторое вещественное число. Если k > 1, то происходит «сжатие» исходного сигнала во времени; если же 0

Применим преобразование Фурье (2.24) к произведению s(t)cos(wt + j), используя формулы Эйлера:

Первый интеграл в правой части есть не что иное, как спектральная плотность функции s(t) при частоте (w — w), а второй интеграл – при частоте (w + w). Поэтому полученное выше соотношение можно записать в форме:

где S(w) – спектральная плотность исходного колебания s(t).

Из выражения (2.33) вытекает, что расщепление спектра S(w) на две части, смещенные соответственно на +w и -w, эквивалентно умножению функции s(t) на гармоническое колебание cos wt (при j = 0).

2.4.4 Дифференцирование и интегрирование колебания

Пусть сигнал s(t) и его спектральная плотность S(w) заданы. Проанализируем новый сигнал, получаемый из исходного путем дифференцирования, и поставим цель найти его спектр. Оказывается, что справедлива формула:

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

Внеинтегральное слагаемое обращается в нуль, поскольку s®0 при t ® ±¥ (условие интегрируемости сигнала). В результате получаем выражение (2.34).

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

Формула (2.34) обобщается на случай спектра производной n-го порядка. Легко увидеть, что

Итак, дифференцирование сигнала во временной области эквивалентно простой алгебраической операции умножения спектральной плотности на множитель jw. Поэтому принято говорить, что мнимое число jw играет роль оператора дифференцирования, действующего в частотной области.

Во многих радиотехнических устройствах находят применение так называемые интеграторы – физические системы, работающие по следующему принципу: мгновенное значение сигнала на их выходе равно интегралу от функции, описывающей входное воздействие. Если ивх и ивых – соответственно сигналы на входе и выходе идеального интегратора, то

Между спектральной плотностью сигнала s(t) и значением его определенного интеграла с переменным верхним пределом существует связь:

Для доказательства следует заметить, что и воспользоваться формулой (2.34).

Таким образом, множитель 1/(jw) выступает как оператор интегрирования в частотной области.

2.4.5 Сложение и произведение двух колебаний

Так как преобразование Фурье, определяющее спектральную плотность заданной функции времени, является линейным преобразованием, то, очевидно, что при сложении колебаний s1(t), s2(t), . обладающих спектрами S1(w), S2(w), . суммарному колебанию s(t) = s1(t) + s2(t) + . соответствует спектр, являющийся их суммой: S(w) = S1(w) + S2(w) + . .

Однако спектр произведения сигналов не равен произведению спектров, а выражается некоторым специальным интегральным соотношением между спектрами сомножителей.

Пусть v(t), u(t) — два сигнала, для которых установлены соответствия u(t) « U(w), v(t) « V(w). Образуем произведение этих сигналов: s(t) = u(t) v(t) и вычислим его спектральную плотность:

Применив обратное преобразование Фурье, выразим сигнал v(t) через его спектр и подставим результат в (2.37):

Изменив порядок интегрирования, будем иметь:

Заключенный в квадратные скобки интеграл представляет собой спектральную плотность функции u(t) при частоте (w-x), т.е. U(w-x). Следовательно, спектр произведения двух сигналов равен

Интеграл в правой части называется сверткой функций U и V. Операция свертки обозначается как V(w)*U(w). Операция свертки коммутативна, т.е. допускает изменение порядка следования преобразуемых функций: V(w)*U(w) = U(w)*V(w).

Можно показать, что произведению двух спектров U(w)V(w) = S(w) соответствует функция времени s(t), являющаяся сверткой функций u(t) и v(t):

2.4.6 Взаимная заменяемость w и t в преобразованиях Фурье

Обратимся к общему выражению (2.24) и выясним характер функции S(w) для различных функций s(t).

  1. Пусть s(t) есть функция, четная относительно t. Записывая ППФ (2.24) через тригонометрические функции в виде

легко убедиться, что при четности s(t) второй интеграл равен нулю, так как произведение s(t)sinwt является функцией, нечетной относительно t, а пределы интегрирования симметричны. Таким образом, при s(t), четной относительно t, функция S(w), определяемая первым интегралом, есть функция вещественная и четная относительно w.

  1. Если s(t) нечетна относительно t, то в нуль обращается первый интеграл и

В этом случае S(w) – нечетная и чисто мнимая функция w.

3. Если s(t) не является четной или нечетной функцией относительно t, то ее можно разложить на две функции: четную s1(t) и нечетную s2(t). При этом S(w) представляет полную комплексную функцию, причем действительная ее часть четна, а мнимая нечетная относительно w.

Из п. 1 вытекает, что при четной функции s(t) можно произвольно выбирать знак перед t в обратном преобразовании Фурье (2.25); выберем знак минус и запишем формулу (2.25) в виде:

Произведем теперь в последнем интеграле замену переменной интегрирования w на t и параметра t на w. Тогда левая часть должна быть записана в виде функции от w:

Но интеграл в последнем выражении можно рассматривать как спектральную плотность новой функции S(t), полученной путем замены w на t в выражении спектральной плотности колебания s(t). Обозначим эту новую спектральную плотность через S’(w). Тогда S’(w) = 2ps(w).

Этот результат показывает, что переменные w и t в преобразованиях Фурье взаимно заменимы: если колебанию (четному) s(t) соответствует спектр S(w), то колебанию S(t) соответствует спектр 2ps(w).

2.4.7 Свойство инверсии аргумента

В силу того, что действительная часть A(w) функции спектральной плотности является четной функцией частоты, а ее мнимая часть B(w) – нечетной (см. предыдущее свойство), будет справедлива следующая закономерность.

Если сигналу s(t) соответствует его спектральная плотность S(w), то сигналу с инверсным аргументом s(-t) будет соответствовать комплексно-сопряженное значение спектральной плотности S*(w).

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. 9339 — | 7293 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Физический смысл БПФ

Для чего нужно быстрое преобразование Фурье или вообще дискретное преобразование Фурье (ДПФ)? Давайте попробуем разобраться.

Пусть у нас есть функция синуса .

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

Период колебания равен . Если мы хотим увеличить период до , то надо умножить переменную на коэффициент. Это вызовет растяжение графика по горизонтали: .

Частота колебания обратна периоду: . Также говорят о круговой частоте, которая вычисляется по формуле: . Откуда: .

И, наконец, есть фаза, обозначаемая как φ. Она определяет сдвиг графика колебания влево. В результате сочетания всех этих параметров получается гармоническое колебание или просто гармоника:

Очень похоже выглядит и выражение гармоники через косинус:

Большой разницы нет. Достаточно изменить фазу на , чтобы перейти от синуса к косинусу и обратно. Далее будем подразумевать под гармоникой функцию косинуса:

В природе и технике колебания, описываемые подобной функцией чрезвычайно распространены. Например, маятник, струна, водные и звуковые волны и прочее, и прочее.

Преобразуем (18) по формуле косинуса суммы:

Выделим в (19) элементы, независимые от , и обозначим их как и :

По величинам и можно однозначно восстановить амплитуду и фазу исходной гармоники:

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

В результате прямого дискретного преобразования Фурье были получены значений для :

Теперь возьмем обратное преобразование Фурье:


Выполним над этой формулой следующие действия: разложим каждое комплексное на мнимую и действительную составляющие ; разложим экспоненту по формуле Эйлера на синус и косинус действительного аргумента; перемножим; внесем под знак суммы и перегруппируем элементы в две суммы:

Это была цепочка равенств, которая начиналась с действительного числа . В конце получилось две суммы, одна из которых помножена на мнимую единицу . Сами же суммы состоят из действительных слагаемых. Отсюда следует, что вторая сумма должна быть равна нулю. Отбросим ее и получим:

Поскольку при дискретизации мы брали и , то можем выполнить замену: . Следовательно, в синусе и косинусе вместо можно написать . В результате получим:

Сопоставим эту формулу с формулой (20) для гармоники:

Слагаемые суммы (26) аналогичны формуле (20), а формула (20) описывает гармоническое колебание. Значит сумма (26) представляет собой сумму из гармонических колебаний разной частоты, фазы и амплитуды.

Выше объяснялось, каким образом формула вида (20) может быть преобразована в формулу вида (18):

Выполним такое же преобразование для слагаемых суммы (26), преобразуем их из вида (20) в вид (18). Получим:

Далее будем функцию

называть k-й гармоникой.

Для вычисления и надо использовать формулу (21). Теперь выпишем в одном месте все формулы, которые связывают амплитуду, фазу, частоту и период каждой из гармоник с коэффициентами :

Функция — это аргумент комплексного числа. В языке C++ для ее вычиления удобно использовать функцию .

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

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

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

Для защиты релятивизма Поль Дирак ввел афизическое и алогичное понятие отрицательной энергии, а затем и существование «моря» двух компенсирующих друг друга энергий в вакууме — положительной и отрицательной, а также «моря» компенсирующих друг друга частиц — виртуальных (то есть кажущихся) электронов и позитронов в вакууме.

Однако такая постановка является внутренне противоречивой (виртуальные частицы ненаблюдаемы и их по произволу можно считать в одном случае отсутствующими, а в другом — присутствующими) и противоречащей релятивизму (то есть отрицанию эфира, так как при наличии таких частиц в вакууме релятивизм уже просто невозможен). Подробнее читайте в FAQ по эфирной физике.

Пpеобpазование фypье

Еще одно важное свойство устанавливается теоремой Парсеваля для двух функций g(t) и h(t):

Если положить g(t) = h(t), то теорема Парсеваля сводится к теореме для энергии

Выражение (9) — это, в сущности, просто формулировка закона сохранения энергии в двух областях (временной и частотной). В (9) слева стоит полная энергия сигнала, таким образом, функция

описывает распределение энергии по частоте для детерминированного сигнала h(t) и поэтому называется спектральной плотностью энергии (СПЭ). С помощью выражений

можно вычислить амплитудный и фазовый спектры сигнала h( t ).

Операции дискретизации и взвешивания

В следующем разделе мы введем дискретно-временной ряд Фурье (ДВРФ) или иначе дискретное преобразование Фурье (ДПФ) как частный случай непрерывно-временного преобразования Фурье (НВПФ) с использованием двух базовых операций обработки сигналов — взятия отсчетов (дискретизации) и взвешивания с помощью окна. Здесь рассмотрим влияние этих операций на сигнал и его преобразование. В таблице 2 перечислены функции, с помощью которых осуществляется взвешивание и дискретизация .

При равномерных отсчетах с интервалом T секунд частота отсчетов F равна 1 /T Гц. Заметим, что взвешивающая функция и функция отсчетов во временной области обозначаются соответственно TW (time windowing) и TS (time sampling), а в частотной области — FW (frequency windowing) и FS (frequency sampling).

Таблица 2. Взвешивание и дискретизирующие функции

Взвешивание во временной области (ширина окна NT сек) Взвешивание в частотной области (ширина окна 1/T Гц) Отсчеты во времени (интервалом T сек) Отсчеты по частоте (с интервалом 1/NT Гц)

Предположим, что берутся отсчеты непрерывного действительного сигнала x(t) c ограниченным спектром, верхняя частота которого равна F0. НВПФ действительного сигнала — это всегда симметричная функция с полной шириной 2F0, см. рис.1.
Отсчеты сигнала x(t) могут быть получены посредством умножения этого сигнала на функцию отсчетов:

Рис.1 — иллюстрация теоремы отсчетов во временной области для действительного сигнала с ограниченным спектром:
а — исходная функция времени и ее преобразование Фурье;
б — функция отсчетов во времени и ее преобразование Фурье;
в — временные отсчеты исходной функции и ее периодически продолженное преобразование Фурье для случая Fo

В соответствии с теоремой о свертке в частотной области, НВПФ сигнала x(t) — это просто свертка спектра сигнала x(t) и преобразования Фурье функции отсчетов по времени ( TS ):

Свертка X(f) c преобразованием Фурье функции отсчетов F =Y1/T( f ) просто периодически продолжает X(f) с частотным интервалом 1/T Гц. Поэтому XS(f) представляет собой периодически продолженный спектр X(f). В общем случае отсчеты в одной области (например, временной) приводят к периодическому продолжению в области преобразования (например, частотной). Если частота отсчетов выбрана достаточно низкой (F

В результате (см. Рис. 1 д ) восстанавливается исходное преобразование Фурье. Используя теоремы о свертке во временной и частотной областях, получаем

Выражение (15) представляет собой математическую запись теоремы отсчетов во временной области ( теоремы Уиттекера, Котельникова, Шеннона — УКШ ), которая утверждает, что с помощью интерполяционной формулы (15) действительный сигнал с ограниченным спектром может быть точно восстановлен по бесконечному числу известных временных отсчетов, взятых с частотой F і 2F0. Дуальной к теореме (15) является теорема отсчетов в частотной области для сигналов с ограниченной длительностью.
Операции во временной области, аналогичные (14), описываются выражением

а соответствующие преобразования — выражениями

Таким образом, НВПФ X(f) некоторого сигнала с ограниченной длительностью может быть однозначно восстановлено по эквидистантным отсчетам спектра такого сигнала, если выбранный интервал отсчетов по частоте удовлетворяет условию F 1/2T Гц, где T — длительность сигнала.

Соотношения между непрерывными и дискретными преобразованиями

Пара преобразований для обычного определения дискретного преобразования Фурье (ДПФ) N-точечной временной последовательности x[n] и соответствующей ей N-точечной последовательности преобразования Фурье X[k] дается выражениями

Чтобы по отсчетам данных получить спектральные оценки в соответствующих единицах измерения энергии или мощности, запишем дискретно-временной ряд Фурье (ДВРФ), который можно рассматривать как некоторую аппроксимацию непрерывно-временного преобразования Фурье (НВПФ), основанную на использовании конечного числа отсчетов данных:

Для того, чтобы показать характер соответствия ДВРФ (дискретные функции и во временной и в частотной областях) и НВПФ (непрерывные функции во временной и в частотной областях), нам потребуется последовательность из четырех линейных коммутативных операций: взвешивания во временной и частотной областях и взятия отсчетов или дискретизации как во временной, так и в частотной областях. Если операция взвешивания выполняется в одной из этих областей, то, согласно теореме свертки, ей будет соответствовать выполнение операции фильтрации (свертки) в другой области с функцией sinc. Точно также, если в одной области выполняется дискретизация, то в другой выполняется операция периодического продолжения. Так как взвешивание и взятие отсчетов являются линейными и коммутативными операциями, то возможны различные способы их упорядочения, дающие одинаковый конечный результат при различных промежуточных результатах. На рис.2 показаны две возможные последовательности выполнения этих четырех операций.

Рис. 2. Две возможные последовательности из двух операций взвешивания и двух операций взятия отсчетов, связывающие НВПФ и ДВРФ: FW — применение окна в частотной области; TW — применение окна во временной области; FS — взятие отсчетов в частотной области; TS — взятие отсчетов во временной области.
1 — преобразование Фурье с непрерывным временем, уравнение (1);
4 — преобразование Фурье с дискретным временем, уравнение (22);
5 — ряд Фурье с непрерывным временем, уравнение (25);
8 — ряд Фурье с дискретным временем, уравнение (27)

В результате выполнения операций взвешивания и взятия отсчетов в узлах 1, 4, 5 и 8 будут иметь место четыре различных типа соотношений Фурье. Узлы, в которых функция в частотной области непрерывна, относятся к преобразованиям Фурье, а узлы, в которых функция в частотной области дискретна относятся к рядам Фурье (подробнее см. в [1]).
Так в узле 4 взвешивание в частотной и дискретизация во временной области порождает дискретно-временное преобразование Фурье (ДВПФ), которое характеризуется периодической функцией спектра в частотной области с периодом 1/T Гц:

Заметим, что выражение (22) определяет некоторую периодическую функцию, совпадающую с заданной в узле 1 исходной преобразованной функцией только на интервале частот от -1/2T до 1/2T Гц. Выражение (22) связано с Z-преобра-зованием дискретной последовательности x[n] соотношением

Таким образом, ДВПФ — это просто Z-преобразование, вычисленное на единичной окружности и умноженное на T.
Если продвигаться от узла 1 к узлу 8 на рис.2 по нижней ветви, в узле 5 операции взвешивания во временной области (ограничения длительности сигнала) и дискретизации в частотной порождают непрерывно-временной ряд Фурье (НВРФ). Используя приведенные в таблицах 1 и 2 свойства и определения функций, получим следующую пару преобразований
(25)
(26)

Заметим, что выражение (26) определяет некоторую периодическую функцию, которая совпадает с исходной (в узле 1) только на интервале времени от 0 до NT.
Независимо от того, какая из двух последовательностей четырех операций выбрана, окончательный результат в узле 8 будет одним и тем же — дискретно-временным рядом Фурье, которому соответствует следующая пара преобразований, полученных с использованием свойств, указанных в таблице 1.

где n=0, . . . ,N-1 ,
Теорема о энергии для этого ДВРФ имеет вид:

и характеризует энергию последовательности из N отсчетов данных. Обе последовательности x[n] и X[k] периодичны по модулю N, поэтому (28) можно записать в форме

где 0 n N. Множитель T в (27) — (30) необходим для того, чтобы (27) и (28) являлись в действительности аппроксимацией интегрального преобразования в области интегрирования

С помощью процесса, называемого дополнением нулями, дискретно-временной ряд Фурье может быть изменен для интерполяции между N значениями исходного преобразования. Пусть имеющиеся отсчеты данных x[0]. x[N-1] дополнены нулевыми значениями x[N]. X[2N-1]. ДВРФ этой дополненной нулями 2N-точечной последовательности данных будет определяться выражением

где верхний предел суммы справа изменен в соответствии с наличием нулевых данных. Пусть k=2m, так что

где m=0,1. N-1, определяет четные значения X[k]. Отсюда видно, что при четных значениях индекса k 2N-точечный дискретно-временной ряд Фурье сводится к N-точечному дискретно-временному ряду. Нечетные значения индекса k соответствуют интерполированным значениям ДВРФ, расположенным между значениями исходного N-точечного ДВРФ. По мере того, как все большее число нулей добавляется в исходную N-то-чечную последовательность, можно получить еще большее число интерполированных данных. В предельном случае бесконечного числа вводимых нулей ДВРФ может рассматриваться как дискретно-временное преобразование Фурье N-то-чечной последовательности данных:

Преобразование (34) соответствует узлу 6 на рис.2.
Бытует неправильное мнение о том, что дополнение нулями улучшает разрешение, поскольку оно увеличивает длину последовательности данных. Однако, как следует из рис.3, дополнение нулями не улучшает разрешающую способность преобразования, полученного по заданной конечной последовательности данных. Дополнение нулями просто позволяет получить интерполированное преобразование более сглаженной формы. Кроме того, оно устраняет неопределенности, обусловленные наличием узкополосных компонент сигнала, частоты которых лежат между N точками, соответствующими оцениваемым частотам исходного ДВРФ. При дополнении нулями повышается также и точность оценивания частоты спектральных пиков. Под термином спектральное разрешение мы будем понимать способность различать спектральные отклики двух гармонических сигналов. Общепринятое эмпирическое правило, часто используемое при спектральном анализе, гласит, что разнесение различаемых синусоид по частоте не может быть меньше эквивалентной ширины полосы окна, через которое наблюдаются сегменты (отрезки) этих синусоид.

Рис.3. Интерполяция за счет дополнения нулями:
а — модуль ДВРФ 16-ти точечной записи данных, содержащих три синусоиды без дополнения нулями (видны неопределенности: нельзя сказать сколько в сигнале синусоид — две, три или четыре);
б — модуль ДВРФ той же последовательности после двукратного увеличения числа ее отсчетов за счет дополнения 16 нулями (неопределенности разрешены, так как различимы все три синусоиды;
в — модуль ДВРФ той же последовательности после четырехкратного увеличения числа ее отсчетов за счет дополнения нулями.

Эквивалентная ширина полосы окна может быть определена как
где W(f) — дискретно-временное преобразование Фурье функции окна, например, прямоугольного (5). Аналогично можно ввести эквивалентную длительность окна

Можно показать, что эквивалентная длительность окна (или любого другого сигнала) и эквивалентная ширина полосы его преобразования являются взаимно обратными величинами: TeBe=1.

Быстрое преобразование Фурье

Быстрое преобразование Фурье (БПФ) — это не еще одна разновидность преобразования Фурье, а название целого ряда эффективных алгоритмов, предназначенных для быстрого вычисления дискретно-временного ряда Фурье. Основная проблема, возникающая при практической реализации ДВРФ, заключена в большом количестве вычислительных операций, пропорциональном N2. Хотя еще задолго до появления компьютеров было предложено несколько эффективных вычислительных схем, позволяющих существенно сократить число вычислительных операций, настоящую революцию произвела публикация в 1965 году статьи Кули (Cooly) и Тьюки (Tukey) c практическим алгоритмом быстрого (число операций Nlog2N) вычисления ДВРФ. После этого было разработано множество вариантов, усовершенствований и дополнений основной идеи, составивших класс алгоритмов, известных под названием быстрого преобразования Фурье. Основная идея БПФ — деление N-точечного ДВРФ на два и более ДВРФ меньшей длины, каждый из которых можно вычислить отдельно, а затем линейно просуммировать с остальными, с тем чтобы получить ДВРФ исходной N-точечной последовательности.
Представим дискретное преобразование Фурье (ДВРФ) в виде

Илон Маск рекомендует:  opendir - Открыть каталог

где величина WN=exp(-j2 /N) носит название поворачивающего множителя (здесь и далее в этом разделе период выборки T=1). Выделим из последовательности x[n] элементы с четными и нечетными номерами

Но так как то
. Следовательно, (36) можно записать в виде

где каждое из слагаемых является преобразованием длины N/2

Заметим, что последовательность (WN/2) nk периодична по k с периодом N/2. Поэтому, хотя номер k в выражении (37) принимает значения от 0 до N-1, каждая из сумм вычисляется для значений k от 0 до N/2-1. Можно оценить число комплексных операций умножения и сложения, необходимых для вычисления преобразования Фурье в соответствии с алгоритмом (37)-(38). Два N/2-точечных преобразования Фурье по формулам (38) предполагают выполнение 2(N/2) 2 умножений и приблизительно столько же сложений. Объединение двух N/2-точечных преобразований по формуле (37) требует еще N умножений и N сложений. Следовательно, для вычисления преобразования Фурье для всех N значений k необходимо произвести по N+N 2 /2 умножений и сложений. В то же время прямое вычисление по формуле (35) требует по N 2 умножений и сложений. Уже при N>2 выполняется неравенство N+N 2 /2 2 , и, таким образом, вычисления по алгоритму (37)-(38) требуют меньшего числа математических операций по сравнению с прямым вычислением преобразования Фурье по формуле (35). Так как вычисление N-точечного преобразования Фурье через два N/2-точечных приводит к экономии вычислительных операций, то каждое из N/2-точечных ДПФ следует вычислять путем сведения их к N/4-точечным преобразованиям:

При этом, вследствие периодичности последовательности W nk N/4 по k с периодом N/4, суммы (40) необходимо вычислять только для значений k от 0 до N/4-1. Поэтому расчет последовательности X[k] по формулам (37), (39) и (40) требует, как нетрудно подсчитать, уже по 2N+N 2 /4 операций умножения и сложения.
Следуя таким путем, объем вычислений X[k] можно все более и более уменьшать. После m=log2N разложений приходим к двухточечным преобразованиям Фурье вида

где «одноточечные преобразования» X1[k,p] представляют собой просто отсчеты сигнала x[n]:

В итоге можно записать алгоритм БПФ, получивший по понятным причинам название алгоритма с прореживанием по времени :

где k=0,1, p=0,1. N/2 -1;

где k=0,1. 2N/M -1, p=0,1. M/2 -1;


На каждом этапе вычислений производится по N комплексных умножений и сложений. А так как число разложений исходной последовательности на подпоследовательности половинной длины равно log2N, то полное число операций умножения-сложения в алгоритме БПФ равно Nlog2N. При больших N имеет место существенная экономия вычислительных операций по сравнению с прямым вычислением ДПФ. Например, при N = 2 10 = 1024 число операций уменьшается в 117 раз.
Рассмотренный нами алгоритм БПФ с прореживанием по времени основан на вычислении преобразования Фурье путем формирования подпоследовательностей входной последовательности x[n]. Однако можно использовать также разложение на подпоследовательности преобразования Фурье X[k]. Алгоритм БПФ, основанный на этой процедуре, носит название алгоритма с прореживанием по частоте. Подробнее о быстром преобразовании Фурье можно прочитать, например, в [2].

Случайные процессы и спектральная плотность мощности

Дискретный случайный процесс x[n,i] можно рассматривать как некоторую совокупность, или ансамбль, действительных или комплексных дискретных временных (или пространственных) последовательностей, каждую из которых можно было бы наблюдать как результат проведения некоторого эксперимента (n — временной индекс, i — номер наблюдения). Последовательность, полученную в результате одного из наблюдений будем обозначать x[n]. Операцию усреднения по ансамблю (т.е. статистического усреднения) будем обозначать посредством оператора <>. Таким образом, — среднее значение случайного процесса x[n] в момент времени n. Автокорреляция случайного процесса в два различных момента времени n1 и n2 определяется выражением rxx[n1,n2]= .

Случайный процесс называется стационарным в широком смысле, если его среднее значение постоянно (не зависит от времени), а автокорреляция зависит только от разности индексов времени m=n1-n2 (временного сдвига или задержки между отсчетами). Таким образом, стационарный в широком смысле дискретный случайный процесс x[n] характеризуется постоянным средним значением = и автокорреляционной последовательностью (АКП)

Отметим следующие свойства АКП:

которые справедливы при всех m.
Спектральная плотность мощности (СПМ) определяется как дискретно-временное преобразование Фурье (ДВПФ) автокорреляционной последовательности

СПМ, ширина которой полагается ограниченной значениями ±1/2T Гц, является периодической функцией частоты с периодом 1/T Гц. Функция СПМ описывает распределение мощности случайного процесса по частоте. Для подтверждения избранного для нее названия рассмотрим обратное ДВПФ

вычисляемое при m=0

Автокорреляция при нулевом сдвиге характеризует среднюю мощность случайного процесса. Согласно (48), площадь под кривой Pxx(f) характеризует среднюю мощность, поэтому Pxx(f) представляет собой функцию плотности (мощность на единицу измерения частоты), которая характеризует распределение мощности по частоте. Пару преобразований (46) и (47) часто называют теоремой Винера-Хинчина для случая дискретного времени. Поскольку rxx[-m]=r*xx[m], то СПМ должна быть строго действительной положительной функцией. Если АКП — строго действительная функция, то rxx[-m]=rxx[m] и СПМ можно записать в форме косинус-преобразования Фурье

что означает также, что Pxx(f) = Pxx(-f), т.е. СПМ — четная функция.
До сих пор мы при определении среднего значения, корреляции и спектральной плотности мощности случайного процесса пользовались статистическим усреднением по ансамблю. Однако на практике обычно не удается получить ансамбль реализаций требуемого процесса, по которому можно было бы вычислить эти статистические характеристики. Желательно оценивать все статистические свойства по одной выборочной реализации x(t), заменяя усреднение по ансамблю усреднением по времени. Свойство, позволяющее такую замену осуществить называется эргодичностью. Говорят, что случайный процесс эргодичен, если с вероятностью, равной единице, все его статистические характеристики можно предсказать по одной реализации из ансамбля с помощью усреднения по времени. Иными словами, средние значения по времени почти всех возможных реализаций процесса с вероятностью единица сходятся к одной и той же постоянной величине — среднему значению по ансамблю

Этот предел, если он существует, сходится к истинному среднему значению тогда и только тогда, когда дисперсия среднего по времени стремится к нулю, что означает выполнение следующего условия:

Здесь cxx[m] — истинное значение ковариации процесса x[n].
Аналогично, наблюдая значение произведения отсчетов процесса x[n] в два момента времени, можно ожидать, что среднее значение будет равно

Допущение об эргодичности позволяет не только ввести через усреднение по времени определения для среднего значения и автокорреляции, но также дать подобное определение и для спектральной плотности мощности

Эта эквивалентная форма СПМ получается посредством статистического усреднения модуля ДВПФ взвешенной совокупности данных, поделенного на длину записи данных, для случая, когда число отсчетов увеличивается до бесконечности. Статистическое усреднение необходимо здесь потому, что ДВПФ само является случайной величиной, изменяющейся для каждой реализации x[n]. Для того, чтобы показать, что (52) эквивалентно теореме Винера-Хинчина, представим квадрат модуля ДВПФ в виде произведения двух рядов и изменим порядок операций суммирования и статистического усреднения:

Используя известное выражение

соотношение (53) можно свести к следующему:

Заметим, что на последнем этапе вывода (55) использовалось допущение о том, что автокорреляционная последовательность «затухает», так что

Взаимосвязь двух определений СПМ (46) и (52) наглядно показывает диаграмма, представленная на рисунке 4.
Если в выражении (52) не учитывать операцию математического ожидания, то получим оценку СПМ

которая называется выборочным спектром.

Рис. 4. Взаимосвязь двух способов оценивания спектральной плотности мощности

Периодограммный метод спектрального оценивания

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

Рис. 5. Основные этапы оценивания СПМ с помощью периодограммного метода

Применение метода начинается со сбора N отсчетов данных, которые берутся с интервалом T секунд на отсчет с последующим (по желанию) этапом устранения тренда. Для того, чтобы получить статистически устойчивую спектральную оценку, имеющиеся данные необходимо разбить на перекрывающиеся (по возможности) сегменты и в последующем усреднить выборочные спектры, полученные по каждому такому сегменту. Параметры этого усреднения изменяются посредством соответствующего выбора числа отсчетов на сегмент (NSAMP) и числа отсчетов, на которое необходимо сдвинуть начало следующего сегмента (NSHIFT), см. рис. 6. Количество сегментов выбирается в зависимости от требуемой степени гладкости (дисперсии) спектральной оценки и требуемого спектрального разрешения. При малом значении параметра NSAMP получается больше сегментов, по которым будет производиться усреднение, а следовательно будут получаться оценки с меньшей дисперсией, но также и меньшим частотным разрешением. Увеличение длины сегмента (параметра NSAMP) повышает разрешение, естественно за счет увеличения дисперсии оценки из-за меньшего числа усреднений. Стрелка возврата на рис.5 указывает на необходимость нескольких повторных проходов по данным при различных длинах и количествах сегментов, что позволяет получить больше информации об исследуемом процессе.

Рис.6. Разбиение данных на сегменты для вычисления периодограммы

Один из важных вопросов, который является общим для всех классических методов спектрального оценивания, связан с взвешиванием данных. Обработка с помощью окна используется для управления эффектами, обусловленными наличием боковых лепестков в спектральных оценках. Заметим, что имеющуюся конечную запись данных удобно рассматривать как некоторую часть соответствующей бесконечной последовательности, видимую через применяемое окно. Так последовательность наблюдаемых данных x[n] из N отсчетов математически можно записать как произведение бесконечной последовательности x[n] и функции прямоугольного окна

x[n]=x[n]·rect[n].
При этом принимается очевидное допущение о том, что все ненаблюдаемые отсчеты равны нулю независимо от того, так ли это на самом деле. Дискретно-временное преобразование Фурье взвешенной последовательности равно свертке преобразований последовательности x[n] и прямоугольного окна rect[n]

Функция DN(f), называемая дискретной функцией sinc, или ядром Дирихле, представляет собой ДВПФ прямоугольной функции. Преобразование наблюдаемой конечной последовательности является искаженной версией преобразования бесконечной последовательности. Влияние прямоугольного окна на дискретно-временную синусоиду с частотой f иллюстрирует рис.7.

Рис.7. Иллюстрация смещения дискретно-временного преобразования Фурье вследствие просачивания из-за взвешивания данных.: а,в — исходная и взвешенная последовательности; б, г — их преобразования Фурье.

Из рисунка видно, что острые спектральные пики ДВПФ бесконечной синусоидальной последовательности расширились за счет свертки с преобразованием окна. Таким образом, минимальная ширина спектральных пиков взвешенной окном последовательности определяется шириной главного лепестка преобразования этого окна и не зависит от данных. Боковые лепестки преобразования окна будут изменять амплитуды соседних спектральных пиков (иногда это явление называют просачиванием). Поскольку ДВПФ — периодическая функция, то наложение боковых лепестков от соседних периодов может привести к дополнительному смещению. Увеличение частоты отсчетов позволяет ослабить эффект наложения боковых лепестков. Аналогичные искажения будут, естественно, наблюдаться и в случае несинусоидальных сигналов. Просачивание приводит не только к появлению амплитудных ошибок в спектрах дискретных сигналов, но может также маскировать присутствие слабых сигналов. Можно предложить ряд других функций окна, применение которых позволяет снизить уровень боковых лепестков по сравнению с тем, который имеется при использовании прямоугольного окна. Снижение уровня боковых лепестков будет уменьшать смещение спектральной оценки, однако это дается ценой расширения главного лепестка спектра окна, что, естественно, приводит к ухудшению разрешения. Следовательно и здесь должен выбираться какой-то компромисс между шириной главного лепестка и уровнем боковых лепестков. Для оценки качества окон используется несколько параметров. Традиционным показателем является ширина полосы главного лепестка на уровне половинной мощности. В качестве второго показателя используется эквивалентная ширина полосы, введенная выше. Два показателя используются и для оценки характеристик боковых лепестков. Первый — их максимальный уровень, второй — скорость спадания, характеризующая быстроту уменьшения боковых лепестков по мере удаления от главного лепестка. В таблице 3 приведены определения некоторых общеупотребительных дискретно-временных функций окна, а в таблице 4 — их характеристики.
Таблица 3. Определения типичных N-точечных дискретно-временных окон

Алгоритмы преобразования Фурье и их применение при анализе звуковой информации

Рубрика: Информационные технологии

Дата публикации: 05.10.2020 2020-10-05

Статья просмотрена: 3042 раза

Библиографическое описание:

Щелбанин А. В., Зинченко Л. А. Алгоритмы преобразования Фурье и их применение при анализе звуковой информации // Молодой ученый. — 2020. — №20. — С. 29-34. — URL https://moluch.ru/archive/124/34105/ (дата обращения: 12.11.2020).

В этой статье представлен вашему вниманию обзор алгоритмов преобразования Фурье и их применение при анализе звуковой информации. В статье представлены несколько конкретных реализаций преобразования Фурье, их анализ, а также накладываемые ограничения. В заключении был сделал вывод о возможности применения этих алгоритмов в различных условиях.

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

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

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

Преобразование Фурье (ℱ) операция, ставящая в соответствие каждой функции действительного переменного f(x) её спектр или Фурье-образ :

Виды преобразования Фурье:

– непериодический непрерывный или дискретный сигнал можно разложить в интеграл Фурье;

– непериодический дискретный сигнал можно разложить в интеграл Фурье;

– периодический непрерывный сигнал можно разложить в бесконечный ряд Фурье;

– периодический дискретный сигнал можно разложить в конечный ряд Фурье.

На практике, обычно, используется последний вид преобразований в связи с тем, что компьютеры способны работать с конечным набором данных.

Дискретное преобразование Фурье

Дискретное преобразование Фурье (ДПФ) (DiscreteFourierTransform, DFT) имеет вид:

ДПФ ставит в соответствие N отсчетам сигнала x(n), где n = 0…N — 1, N отсчетов дискретного спектра X(k), при этом предполагается, что и сигнал, и спектр сигнала являются периодическими и анализируются на одном периоде повторения. В связи с тем, что вычисление ДФП требует умножений полиномов и вычислений синусов, использование данного алгоритма на практике может оказаться очень ресурсоемким.

Псевдокод метода, реализующего ДПФ, представлен ниже:

for k  0 to N/2

for i  0 to N

ReX[k]  ReX[k] + x[i]∙cos(2πik/N)

ImX[k]  ImX[k] – (x[i]∙sin(2πik/N))

returnX[]

Быстрое преобразование Фурье

Когда не хватает ресурсов для вычисления ДФП, переходят к быстрому преобразованию Фурье. В методе БПФ используются коэффициента полинома с четными и нечетными индексами, чтобы определить два новых полинома и с четными и нечетными коэффициентами:

В этом случае содержит все коэффициенты индексами (двоичное представление которых заканчивается цифрой 0), а содержит все коэффициенты с нечетными индексами (двоичное представление которых заканчивается цифрой 1), тогда спектр дискретного сигнала рассчитывается по формуле:

Таким образом, задача вычисления спектра сводится к следующим операциям:

  1. вычислить два полинома и , имеющие степень не выше n/2 d в точках ;
  2. вычислить спектр, объединив результаты, используя формулу (5).

Псевдокод метода, реализующего БПФ, представлен ниже:

if n = 1

then returnx[]

fork 0 to n/2 – 1

returna[]


Каждый вызов recursiveFFT, за исключением рекурсивных вызовов, занимает Θ(n), где n — длина исходного набора дискретных отсчетов. В таком случае, рекуррентное соотношение для временной сложности алгоритма выглядит следующим образом:

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

Помимо «классического» алгоритма БПФ также существует множество его вариаций, основная идея которых также основывается на декомпозиции ДПФ до операций с отдельными точками и последующее объединение полученных результатов:

– БПФ по основанию 2 с прореживанием по времени, БПФ по основанию 2 с прореживание по частоте — в этих алгоритмах используется двоично-инверсная перестановка и умножения результатов укороченного ДПФ на поворотные коэффициенты;

– полифазное БПФ (polyphaseFFT) — алгоритм, позволяющий получить очень высокое разрешение по частоте, по сравнению с другими алгоритмами БПФ;

– алгоритм БПФ Кули-Тьюки (Cooley-TukeyFFTalgorithm) и д. р.

Практическая реализация

В учебных целях был разработан анализатор спектра на микроконтроллере AtmelATmega32–16PU с использованием LCD-дисплея 16х2 на базе контроллера HitachiHD44780 LCD. Было принято решение использовать алгоритм ДПФ для реализации данной задачи в связи со следующими аппаратными и программные ограничениями:

– использование LCD-дисплея 16×2 означает, что имеется возможность визуализировать спектр сигнала с 16 дискретными частотами;

– стек микроконтроллер AtmelATmega32–16PU состоит из двух 8-битных регистров, поэтому, использование алгоритмов БПФ не представляется возможным в связи с возможным переполнением стека из-за рекурсии;

– в качестве лингвистического обеспечения для разработки был выбран язык программирования — C. В связи с этим основным лингвистическим ограничением является невозможность передачи массива в качестве аргумента в функцию, а также возвращать результат вычислений в виде массива в явном виде. В связи с этим ограничением для передачи данных из массива в функцию используются указатели;

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

Ниже представлен фрагмент кода на языке C, реализующий ДПФ на микроконтроллере ATmega32:

void discrete_fourier_transform (int32_t *x, uint32_t *amp, int n)

int32_t re_x, im_x;

Похожие статьи

Исследование процесса цифровой обработки сигнала при работе.

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

Реализация алгоритмов дискретного преобразования Фурье на.

– 336 с. Сайт Wikipedia. Discrete Fourier Transform.

Основные термины (генерируются автоматически): фазовая характеристика, частотный спектр, звуковой сигнал, свойство преобразования, треугольный сигнал, дискретное преобразование, быстрое.

Разработка программного комплекса для обработки НЧ сигналов

Разрабатываемый программный комплекс САЗСМЧ (спектральный анализ звуковых сигналов мозга человека) (рис. 2) оснащен несколькими программными алгоритмами на основе вейвлет-преобразования Добеши (5) [4] и Морле (6) [5, 6].

Преобразование Фурье как основополагающий частотный метод.

частотная область, преобразование, частотная фильтрация, образ, функция, частота, обработка сигналов, меньший размер, линейная фильтрация, дискретное преобразование.

Анализ нестационарных сигналов с помощью. | Молодой ученый

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

Рис. 3. Нестационарный сигнал тока с присутствием разных частот после дискретного преобразования Фурье.

Преобразование Фурье и преобразование Хартли

Сопоставление составляющих спектра Хартли с действительной и мнимой частью спектра Фурье [3]. Свойства преобразования.

Алгоритмы преобразования Фурье и их применение при анализе звуковой информации.

Предварительная обработка речевых сигналов для системы.

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

Моделирование особенностей бинаурального слуха.

Моделирование особенностей бинаурального слуха и исследование спектрального состава звуковых сигналов.

Рис. 4. Блок-диаграмма проведения измерений. Рис. 5. Полученные осциллограммы для тонового сигнала с частотой 100Гц.

Исследование принципов работы программ распознавания.

Важную роль в программах распознавания звука имеет такой параметр, как частота дискретизации, так как изначально аналоговый сигнал нужно преобразовать в цифровой для дальнейшей обработки. Микрофон конвертирует звуковые колебания в аналоговый.

Быстрое преобразование Фурье

Рассмотрим такую распространённую операцию как умножение двух целых чисел. Квадратичный алгоритм — умножения в столбик — все знают со школы. Долгое время предполагалось, что ничего быстрее придумать нельзя.

Первым эту гипотезу опроверг Анатолий Карацуба. Его алгоритм сводит умножение двух \(n\) -значных чисел к трём умножениям \(\frac<2>\) -значных чисел, что даёт оценку времени работы

\[ T(n)=3T\left(\dfrac n 2\right)+O(n)=O\left(n^<\log_2 3>\right)\approx O(n^<1.58>) \]

Чтобы перейти к алгоритму с лучшей оценкой, нам нужно сначала установить несколько фактов о многочленах.

Умножение многочленов

Обратим внимание на то, что любое число можно представить многочленом:

\[ \begin A(x) &= a_0 + a_1\cdot x + a_2 \cdot x^2 + \dots + a_n \cdot x^n \\ &= a_0 + a_1\cdot 2 + a_2 \cdot 2^2 + \dots + a_n \cdot 2^n \end \]

Основание x при этом может быть выбрано произвольно.

Чтобы перемножить два числа, мы можем перемножить соответствующие им многочлены, а затем произвести каррирование: пройтись от нижних разрядов получившегося многочлена и «сдвинуть» переполнившиеся разряды:

Прямая формула для произведения многочленов имеет вид

\[ \left(\sum_^n a_i x^i\right)\cdot\left(\sum_^m b_j x^j\right)=\sum_^x^k\sum_a_i b_j \]

Её подсчёт требует \(O(n^2)\) операций, что нас не устраивает. Подойдём к этой задаче с другой стороны.

Интерполяция

Теорема. Пусть есть набор различных точек \(x_0, x_1, \dots, x_\) . Многочлен степени \(n\) однозначно задаётся своими значениями в этих точках. (Коэффициентов у этого многочлена столько же, сколько и точек — прим. К. О.)

Доказательство будет конструктивным — можно явным образом задать многочлен, который принимает заданные значения \(y_0, y_1, \ldots, y_n\) в этих точках:

Корректность. Проверим, что в точке \(x_i\) значение действительно будет равно \(y\) :

Для \(i\) -го слагаемого внутреннее произведение будет равно единице, если вместо \(x\) подставить \(x_i\) : в этом случае просто перемножается \((n-1)\) единица. Эта единица помножится на \(y_i\) и войдёт в сумму.

Для всех остальных слагаемых произведение занулится: один из множетелей будет равен \((x_i — x_i)\) .

Уникальность. Предположим, есть два подходящих многочлена степени \(n\) — \(A(x)\) и \(B(x)\) . Рассмотрим их разность. В точках \(x_i\) значение получившегося многочлена \(A(x) — B(x)\) будет равняться нулю. Если так, то точки \(x_i\) должны являться его корнями, и тогда разность можно записать так:

\[ A(x) — B(x) = \alpha \prod_^n (x-x_i) \]

для какого-то числа \(\alpha\) . Тут мы получаем противоречие: если раскрыть это произведение, то получится многочлен степени \(n+1\) , который нельзя получить разностью двух многочленов степени \(n\) .

Этот многочлен называется интерполяционным многочленом Лагранжа, а сама задача проведения многочлена через точки — интерполяцией.

Примечание. На практике интерполяцию решают методом Гаусса: её можно свести к решению линейного уравнения \(aX = y\) , где \(X\) это матрица следующего вида:

\[ \begin 1 & x_0 & x_0^2 & \ldots & x_0^n \\ 1 & x_1 & x_1^2 & \ldots & x_1^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \ldots & x_n^n \\ \end \]

Важный факт: многочлен можно однозначно задать не только своими коэффициентами, но также корнями и значениями хотя бы в \((n+1)\) -ой точке.

Умножение через интерполяцию

Что происходит со значениями многочлена-произведения \(A(x) B(x)\) в конкретной точке \(x_i\) ? Оно просто становится равным \(A(x_i) B(x_i)\) .

Основная идея алгоритма: если мы знаем значения в каких-то различных \(n + m\) точках для обоих многочленов \(A\) и \(B\) , то, попарно перемножив их, мы за \(O(n + m)\) операций можем получить значения в тех же точках для многочлена \(A(x) B(x)\) — а с их помощью можно интерполяцией получить исходный многочлен и решить задачу.

Илон Маск рекомендует:  Что такое код pdf_setdash

Если притвориться, что evaluate и interpolate работают за линейное время, то умножение тоже будет работать за линейное время.


К сожалению, непосредственное вычисление значений требует \(O(n^2)\) операций, а интерполяция — как методом Гаусса, так и через символьное вычисление многочлена Лагранжа — и того больше, \(O(n^3)\) .

Но что, если бы мы могли вычислять значения в точках и делать интерполяцию быстрее?

Комплексные числа

Определение. Комплексные числа — это числа вида \(a + bi\) , где \(a\) и \(b\) это обычные вещественные числа, а \(i\) это так называемая мнимая единица: это число, для которого выполняется равенство \(i^2 = -1\) .

Комплексные числа ввели в алгебре, чтобы работать с корнями из отрицательных чисел: \(i\) в каком-то смысле равно \(\sqrt<-1>\) . Так же, как и отрицательные числа, они как бы «не существуют» в реальном мире, а только в сознании математиков.

С комплексными числами можно работать почти так же, как с действительными. Они даже удобнее: все квадратные корни всегда извлекаются, все корни многочленов всегда находятся.

Комплексная плоскость

Комплексные числа удобно изображать на плоскости в виде вектора \((a, b)\) и считать через них всякую геометрию.

Модулем комплексного числа называется действительное число \(r = \sqrt\) . Геометрически, это длина вектора \((a, b)\) .

Аргументом комплексного числа называется действительное число \(\phi \in (-\pi, \pi]\) , для которого выполнено \(\tan \phi = \frac\) . Геометрически, это значение угла между \((a, 0)\) и \((a, b)\) . Для нуля — вектора \((0, 0)\) — аргумент не определён.

Таким образом комплексное число можно представить в полярных координатах:

\[ a+bi = r ( \cos \phi + i \sin \phi ) \]

Подобное представление удобно по следующей причине: чтобы перемножить два комплексных числа, нужно перемножить их модули и сложить аргументы.

Упражнение. Докажите это.

Формула эйлера

Определим число Эйлера \(e\) как число со следующим свойством:

\[ e^ = \cos \phi + i \sin \phi \]

Просто введём такую нотацию для выражения \(\cos \phi + i \sin \phi\) . Не надо думать, почему это так.

Геометрически, все такие точки живут на единичном круге:

Такая нотация удобна, потому что можно обращаться с \(e^\) как с обычной экспонентой. Пусть мы, например, хотим перемножить два числа на единичном круге с аргументами \(a\) и \(b\) . Тогда это можно записать так:

\[ (\cos a + i \sin a) \cdot (\cos b + i \sin b) = e^ \]

Упражнение. Проверьте это: раскройте скобки и проделайте немного алгебры.

Корни из единицы

У комплексных чисел есть много других замечательных свойств, но нам для алгоритма на самом деле потребуется только следующее:

Утверждение. Для любого натурального \(n\) есть ровно \(n\) комплексных «корней из единицы», то есть чисел \(w_k\) , для которых выполнено:

А именно, это будут числа вида:

На комплексной плоскости эти числа располагаются на единичном круге на равном расстоянии друг от друга:

Все 9 комплексных корней степени 9 из единицы

Первый корень \(w_1\) (точнее второй — единицу считаем нулевым корнем) называют образующим корнем степени \(n\) из единицы. Возведение его в нулевую, первую, вторую и так далее степени порождает последовательность нужных корней единицы, при этом на \(n\) -ном элементе последовательность зацикливается:

Будем обозначать \(w_1\) как просто \(w\) .

Упражнение. Докажите, что других корней быть не может.

Дискретное преобразование Фурье

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

Обратным дискретным преобразованием Фурье называется, как можно догадаться, обратная операция — интерполяция коэффициентов \(x_i\) по значениям \(X_i\) .

Почему эта формула верна? При вычислении ПФ мы практически применяем матрицу к вектору:

\[ \begin w^0 & w^0 & w^0 & w^0 & \dots & w^0 \\ w^0 & w^1 & w^2 & w^3 & \dots & w^ <-1>\\ w^0 & w^2 & w^4 & w^6 & \dots & w^ <-2>\\ w^0 & w^3 & w^6 & w^9 & \dots & w^ <-3>\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ w^0 & w^ <-1>& w^ <-2>& w^ <-3>& \dots & w^1 \end\begin a_0 \\ a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_ \end = \begin y_0 \\ y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_ \end \]

То есть преобразование Фурье — это просто линейная операция над вектором: \(W a = y\) . Значит, обратное преобразование можно записать так: \(a = W^<-1>y\) .

Как будет выглядеть эта \(W^<-1>\) ? Автор не будет пытаться изображать логичный способ рассуждений о её получении и сразу её приведёт:

\[ W^ <-1>= \dfrac 1 n\begin w^0 & w^0 & w^0 & w^0 & \dots & w^0 \\ w^0 & w^ <-1>& w^ <-2>& w^ <-3>& \dots & w^ <1>\\ w^0 & w^ <-2>& w^ <-4>& w^ <-6>& \dots & w^ <2>\\ w^0 & w^ <-3>& w^ <-6>& w^ <-9>& \dots & w^ <3>\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ w^0 & w^ <1>& w^ <2>& w^ <3>& \dots & w^ <-1>\end \]

Проверим, что при перемножении \(W\) и \(W^<-1>\) действительно получается единичная матрица:

Значение \(i\) -того диагонального элемента будет равно \(\frac<1> \sum_k w^ w^ <-ki>= \frac<1> n = 1\) .

Значение любого недиагонального ( \(i \neq j\) ) элемента \((i, j)\) будет равно \(\frac<1> \sum_k w^ w^ <-jk>= \frac<1> \sum_k w^k w^ = \frac> \sum_k w^k = 0\) , потому что все комплексные корни суммируются в ноль, то есть \(\sum w^k = 0\) (см. картинку — там всё симметрично).

Внимательный читатель заметит симметричность форм \(W\) и \(W^<-1>\) , а также формул для прямого и обратного преобразования. На самом деле, эта симметрия нам сильно упростит жизнь: для обратного преобразования Фурье можно использовать тот же алгоритм, только вместо \(w^k\) использовать \(w^<-k>\) , а в конце результат поделить на \(n\) .

Зачем это надо?

Напомним, что мы изначально хотели перемножать многочлены следующим алгоритмом:

Посчитаем значения в \(n+m\) каких-нибудь точках обоих многочленов

Перемножим эти значения за \(O(n+m)\) .

Интерполяцией получим многочлен-произведение.

В общем случае быстро посчитать интерполяцию и даже просто посчитать значения в точках нельзя, но для корней единицы — можно. Если научиться быстро считать значения в корнях и интерполировать (прямое и обратное преобразование Фурье), но мы можно решить исходную задачу.

Соответствующий алгоритм называется быстрым преобразованием Фурье (англ. fast Fourier transform). Он использует парадигму «разделяй-и-властвуй» и работает за \(O(n \log n)\) .

Схема Кули-Тьюки

Обычно, алгоритмы «разделяй-и-властвуй» делят задачу на две половины: на первые \(\frac<2>\) элементов и вторые \(\frac<2>\) элементов. Здесь мы поступим по-другому: поделим все элементы на чётные и нечётные.

Представим многочлен в виде \(P(x)=A(x^2)+xB(x^2)\) , где \(A(x)\) состоит из коэффициентов при чётных степенях \(x\) , а \(B(x)\) — из коэффициентов при нечётных.

Пусть \(n = 2k\) . Тогда заметим, что

Зная это, исходную формулу для значения многочлена в точке \(w^t\) можно записать так:

Ключевое замечание: корней вида \(w^<2t>\) в два раза меньше, потому что \(w^n = w^0\) , и можно сказать, что.

У нас по сути в два раза меньше корней (но они так же равномерно распределены на единичной окружности) и в два раза меньше коэффициентов — мы только что успешно уменьшили нашу задачу в два раз.

Сам алгоритм заключается в следующем: рекурсивно посчитаем БПФ для многочленов \(A\) и \(B\) и объединим ответы с помощью формулы выше. При этом в рекурсии нам нужно считать значения на корнях степени не \(n\) , а \(k = \frac<2>\) , то есть на всех «чётных» корнях степени \(n\) (вида \(w^<2t>\) ).

Заметим, что если \(w\) это образующий корень степени \(n = 2k\) из единицы, то \(w^2\) будет образующим корнем степени \(k\) , то есть в рекурсию мы можем просто передать другое значение образующего корня.

Таким образом, мы свели преобразование размера \(n\) к двум преобразованиям размера \(\dfrac n 2\) . Следовательно, общее время вычислений составит

\[ T(n)=2T\left(\dfrac n 2\right)+O(n)=O(n\log n) \]

Заметим, что предположение о делимости \(n\) на \(2\) имело существенную роль. Значит, \(n\) должно быть чётным на каждом уровне, кроме последнего, из чего следует, что \(n\) должно быть степенью двойки.

Реализация

Приведём код, вычисляющий БПФ по схеме Кули-Тьюки:

Как обсуждалось выше, обратное преобразование Фурье удобно выразить через прямое:

Теперь мы умеем перемножать два многочлена за \(O(n \log n)\) :

Примечание. Приведённый выше код, являясь корректным и имея асимптотику \(O(n\log n)\) , едва ли пригоден для использования на реальных контестах. Он имеет большую константу и далеко не так численно устойчивый, чем оптимальные варианты написания быстрого преобразования Фурье. Мы его приводим, потому что он относительно простой.

Читателю рекомендуется самостоятельно задуматься о том, как можно улучшить время работы и точность вычислений. Из наиболее важных недостатков:


внутри преобразования не должно происходить выделений памяти

работать желательно с указателями, а не векторами

корни из единицы должны быть посчитаны наперёд

Следует избавиться от операций взятия остатка по модулю

Вместо вычисления преобразования с \(w^<-1>\) можно вычислить преобразование с \(w\) , а затем развернуть элементы массива со второго по последний.

Здесь приведена одна из условно пригодных реализаций.

Но главная проблема в численной стабильности — мы нарушили первое правило действительных чисел. Однако, от неё можно избавиться.

Number-theoretic transform

Нам от комплексных чисел на самом деле нужно было только одно свойство: что у единицы есть \(n\) «корней». На самом деле, помимо комплексных чисел, есть и другие алгебраические объекты, обладающие таким свойством — например, элементы кольца вычетов по модулю.

Нам нужно просто найти такую пару \(m\) и \(g\) (играющее роль \(w_n^1\) ), такую что \(g\) является образующим элементом, то есть \(g^n \equiv 1 \pmod m\) и при для всех остальных \(k все степени \(g^k\) различны по модулю \(m\) . В качестве \(m\) на практике часто специально берут «удобные» модули, например

\[ m = 998244353 = 7 \cdot 17 \cdot 2^ <23>+ 1 \]

Это число простое, и при этом является ровно на единицу больше числа, делящегося на большую степень двойки. При \(n=2^23\) подходящим \(g\) является число \(31\) . Заметим, что, как и для комплексных чисел, если для некоторого \(n=2^k\) первообразный корень — \(g\) , то для \(n=2^\) первообразным корнем будет \(g^2 (mod m)\) . Таким образом, для \(m=998244353\) и \(n=2^k\) первообразный корень будет равен \(g=31 \cdot 2^ <23-k>(mod m)\) .

Реализация практически не отличается.

С недавнего времени некоторые проблемсеттеры начали использовать именно этот модулю вместо стандартного \(10^9+7\) , чтобы намекнуть (или сбить с толку), что задача на FFT.

Применения

Даны две бинарные строки \(a\) и \(b\) . Нужно найти такой циклический сдвиг строки \(b\) , что количество совпадающих соответствующих символов с \(a\) станет максимально.

Сперва научимся для каждого циклического сдвига \(i\) второй строки считать количество совпадающих единиц \(c_i\) . Это можно сделать за \(O(n^2)\) множеством разных способов, мы рассмотрим следующий: рассмотрим каждую единицу во втором числе, пусть она стоит на \(j\) -й позиции; для каждого \(l\) от \(0\) до \(n-1\) , если \(a_l\) равно 1, то прибавим один к \(c_\) (при этом \(i-j\) берётся по модулю \(n\) ). Такой алгоритм верный, потому что по сути мы перебираем пары единиц, которые могут совпадать, и прибавляем +1 к количеству совпадающих единиц для соответствующего циклического сдвига. И тут мы можем заметить очень важную вещь: если перемножить числа, соответствующие \(a\) и \(b\) , в столбик и не переносить разряды при сложении, то мы получим как раз массив \(c\) (с одним нюансом: его длина может быть больше \(n\) , тогда нам нужно для всех \(i \geq n\) прибавить \(c_i\) к \(c_\) )! А перемножать длинные числа мы уже научились: это легко сделать при помощи БПФ. Таким образом, мы научились искать число совпадающих единиц; заметим, что мы можем инвертировать биты в строках и применить эквивалентный алгоритм, получив в итоге количества совпадающих нулей. Сложим соответствующие элементы в двух массивах и найдём индекс максимального. Также очень часто в задачах на FFT требуется не явно перемножить два полинома, а посчитать свёртку двух векторов. Прямой свёрткой векторов \(a\) длины \(n\) и \(b\) длины \(m\) называется вектор \(s\) длины \(n+m-1\) такой, что \(s_k = \Sigma_^ a_i \cdot b_ (\forall k \in [0;n+m-2])\) (при этом считается, что несуществующие элементы равны нулю). Круговой (циклической) свёрткой векторов \(a\) и \(b\) длины \(n\) называется вектор \(s\) длины \(n\) такой, что \(s_k = \Sigma_^ a_i \cdot b_ (\forall k \in [0; n-1])\) (при этом \(\) берётся по модулю \(n\) ). Оказывается, что линейную свёртку можно считать через круговую: для этого дополним нулями оба вектора до одинаковой длины \(n+m-1\) . Это очень легко доказать: если для некоторого \(k\) \(i \geq k+1\) , то либо \(a_i\) , либо \(b_\) будут равны нулю. Если расписать выражение для прямого преобразования Фурье круговой свёртки и перенести множетили, то можно получить, что круговая свёртка равна вектору произведений многочленов с коэффициентами \(a\) и \(b\) в точках \(0,1,\dots n-1\) . Возможно, когда-нибудь я это распишу.

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

Преобразование Фурье — операция, сопоставляющая функции вещественной переменной другую функцию вещественной переменной. Эта новая функция описывает коэффициенты («амплитуды») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами.

Преобразование Фурье функции $ f $ вещественной переменной является интегральным преобразованием и задается следующей формулой:

Отметим, что разные источники могут давать определения, отличающиеся от приведенного выбором коэффициента перед интегралом, а также знака «−» в показателе экспоненты. Все свойства в этом случае будут аналогичны, хотя вид некоторых формул может измениться.

Кроме этого, существуют разнообразные обобщения этого понятия, которые будут приведены ниже.

Свойства Править

Хотя формула, задающая преобразование Фурье, имеет ясный смысл только для функций класса $ L_1(\R) $ , преобразование Фурье может быть определено и для более широкого класса функций, и даже обобщённых функций. Это возможно благодаря ряду свойств преобразования Фурье:

  • Преобразование Фурье является линейным оператором:

$ \w >

  • Справедливо равенство Парсеваля: если $ f\in L_1(\R)\cap L_2(\R) $ , то преобразование Фурье сохраняет $ L_2 $ -норму:

$ \int\limits_<-\infty>^<\infty>|f(x)|^2\,dx=\int\limits_<-\infty>^<\infty>|<\hat f(w)>|^2\,dw. $

Это свойство позволяет по непрерывности распространить определение преобразования Фурье на всё пространство $ L_2(\R) $ . Равенство Парсеваля будет при этом справедливо для всех $ f\in L_2(\R) $ .

справедлива, если интеграл в правой части имеет смысл. В частности, это верно, если функция $ f $ является достаточно гладкой. Если $ f\in L_2(\R) $ , то формула также верна, поскольку равенство Парсеваля позволяет придать интегралу в правой части смысл с помощью предельного перехода.

Эта формула объясняет физический смысл преобразования Фурье: правая часть — (бесконечная) сумма гармонических колебаний $ e^ $ с частотами $ \omega $ , амплитудами $ \frac<1><\sqrt<2\pi>>|\hat(\omega)| $ и фазовыми сдвигами $ \arg \hat(\omega) $ соответственно.

  • Теорема о свертке: если $ f,\;g\in L_1(\R) $ , тогда

$ \w >, где $ (f\ast g)(t)=\int\limits_<-\infty>^<\infty>f(t-s)g(s)\,ds. $

Эта формула может быть распространена и на случай обобщённых функций.

  • Преобразование Фурье и дифференцирование. Если $ f,\;f’\in L_1(\R) $ , то

$ \w >

Из этой формулы легко выводится формула для $ n $ -й производной:

Формулы верны и в случае обобщённых функций.

  • Преобразование Фурье и сдвиг.

$ \w >

Эта и предыдущая формула являются частными случаями теоремы о свёртке, так как сдвиг по аргументу — это свёртка со сдвинутой дельта-функцией $ \delta(x-x_0) $ , а дифференцирование — свёртка с производной дельта-функции.

  • Преобразование Фурье и растяжение.

$ \w >

  • Преобразование Фурье обобщённых функций. Преобразование Фурье можно определить для широкого класса обобщённых функций. Определим вначале пространство гладких быстро убывающих функций (пространство Шварца):

$ S(\mathbb):=\left\<\varphi\in C^<\infty>(R):\forall n,\;m\in\N\;x^n\varphi^<(m)>(x)\xrightarrow0\right\>. $

Ключевым свойством этого пространства является то, что это инвариантное подпространство по отношению к преобразованию Фурье.

Теперь определим его двойственное пространство $ S^*(\R) $ . Это некоторое подпространство в пространстве всех обобщённых функций — так называемые обобщённые функции медленного роста. Теперь для функции $ f\in S^*(\R) $ её преобразованием Фурье называется обобщённая функция $ \hat\in S^*(\R) $ , действующая на основные функции по правилу

Например, вычислим преобразование Фурье дельта-функции:

Таким образом, преобразованием Фурье дельта-функции является константа $ \frac<1><\sqrt<2\pi>> $ .

Применения преобразования Фурье Править

Преобразование Фурье используется во многих областях науки — в физике, теории чисел, комбинаторике, обработке сигналов, теории вероятностей, статистике, криптографии, акустике, океанологии, оптике, геометрии, и многих других. В обработке сигналов и связанных областях преобразование Фурье обычно рассматривается как декомпозиция сигнала на частоты и амплитуды, то есть, обратимый переход от временно́го пространства (time domain) в частотное пространство (frequency domain). Богатые возможности применения основываются на нескольких полезных свойствах преобразования:

  • Преобразования являются линейными операторами и, с соответствующей нормализацией, также являются унитарными (свойство, известное как теорема Парсеваля или, в более общем случае как теорема Планшереля, или в наиболее общем как дуализм Понтрягина).
  • Преобразования обратимы, причём обратное преобразование имеет практически такую же форму, как и прямое преобразование.
  • Синусоидальные базисные функции (вернее, комплексные экспоненты) являются собственными функциямидифференцирования, что означает, что данное представление превращает линейные дифференциальные уравнения с постоянными коэффициентами в обычные алгебраические. (Например, в линейной стационарной системе частота — консервативная величина, поэтому поведение на каждой частоте может решаться независимо.)
  • По теореме о свёртке, преобразование Фурье превращает сложную операцию свёртки в простое умножение, что означает, что они обеспечивают эффективный способ вычисления основанных на свёртке операций, таких как умножение многочленов и умножение больших чисел.
  • Дискретная версия преобразования Фурье может быть быстро рассчитана на компьютерах с использованием алгоритма быстрого преобразования Фурье (БПФ, англ.FFT ).

Разновидности преобразования Фурье Править

Многомерное преобразование Фурье Править

Преобразование Фурье функций, заданных на пространстве $ \R^n $ , определяется формулой

Здесь $ \omega $ и $ x $ — векторы пространства $ \R^n $ , $ x\cdot\omega $ — их скалярное произведение. Обратное преобразование в этом случае задается формулой

Эта формула может быть интерпретирована как разложение функции $ f $ в линейную комбинацию (суперпозицию) «плоских волн» вида $ e^ $ с амплитудами $ \frac<1><(2\pi)^>|\hat(\omega)| $ , частотами $ \omega $ и фазовыми сдвигами $ \arg\hat(\omega) $ соответственно. Как и прежде, в разных источниках определения многомерного преобразования Фурье могут отличаться выбором константы перед интегралом.

Замечание относительно области задания преобразования Фурье и его основные свойства остаются справедливыми и в многомерном случае, со следующими уточнениями:

  • Взятие частных производных под действием преобразования Фурье превращается в умножение на одноимённую координату:

$ \w >

  • Изменяется константа в теореме о свёртке:

$ \w >

  • Преобразование Фурье и сжатие координат:

$ \w >

  • Более обще, если $ A:\R^n\to\R^n $ — обратимое линейное отображение, то

$ \w >

Ряды Фурье Править

Непрерывное преобразование само фактически является обобщением более ранней идеи рядов Фурье, которые определены для $ 2\pi $ -периодических функций и представляют собой разложение таких функций в (бесконечную) линейную комбинацию гармонических колебаний с целыми частотами:

Разложение в ряд Фурье применимо также к функциям, заданным на ограниченных промежутках, поскольку такие функции могут быть периодически продолжены на всю прямую.

Ряд Фурье является частным случаем преобразования Фурье, если последнее понимать в смысле обобщённых функций. Для любой $ 2\pi $ -периодической функции имеем

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


Дискретное преобразование Фурье Править

Дискретное преобразование Фурье — преобразование конечных последовательностей (комплексных) чисел, которое, как и в непрерывном случае, превращает свёртку в поточечное умножение. Используется в цифровой обработке сигналов и в других ситуациях, где необходимо быстро выполнять свёртку, например, при умножении больших чисел.

Пусть $ x_0,\;x_1,\;\ldots,\;x_ $ — последовательность комплексных чисел. Рассмотрим многочлен $ f(t)=x_0+x_1t+x_2t^2+\ldots+x_t^ $ . Выберем какие-нибудь $ n $ точек на комплексной плоскости $ z_0,\;z_1,\;\ldots,\;z_ $ . Теперь многочлену $ f(t) $ мы можем сопоставить новый набор из $ n $ чисел: $ f_0:=f(z_0),\;f_1:=f(z_1),\;\ldots,\;f_:=f(z_) $ . Заметим, что это преобразование обратимо: для любого набора чисел $ f_0,\;f_1,\;\ldots,\;f_ $ существует единственный многочлен $ f(t) $ степени не выше $ n-1 $ с такими значениями в $ z_0,\;\ldots,\;z_ $ соответственно(см. Интерполяция).

Набор $ \ $ и называется дискретным преобразованием Фурье исходного набора $ \ $ . В качестве точек $ z_k $ обычно выбирают корни $ n $ -й степени из единицы:

Такой выбор продиктован тем, что в этом случае обратное преобразование принимает простую форму, а также тем, что вычисление преобразования Фурье может быть выполнено особенно быстро. Так, в то время как вычисление свёртки двух последовательностей длины $ n $ напрямую требует порядка $ n^2 $ операций, переход к их преобразованию Фурье и обратно по быстрому алгоритму может быть выполнен за $ O(n\log n) $ операций. Для преобразований Фурье свёртке соответствует покомпонентное умножение, которое требует лишь порядка $ n $ операций.

Оконное преобразование Фурье Править

где $ F(t,\;\omega) $ даёт (вообще говоря несколько искажённое) распределение частот части оригинального сигнала $ f(t) $ в окрестности времени $ t $ .

Классическое преобразование Фурье имеет дело со спектром сигнала, взятым во всем диапазоне существования переменной. Нередко интерес представляет только локальное распределение частот, в то время как требуется сохранить изначальную переменную (обычно время). В этом случае используется обобщение преобразования Фурье, так называемое оконное преобразование Фурье. Для начала необходимо выбрать некоторую оконную функцию $ W $ , эта функция должна иметь хорошо локализованный спектр.

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

Некоторые анализаторы спектра используют быстрое (или кратковременное) оконное преобразование. При нём сигнал заданной длительности разбивается на ряд интервалов с помощью скользящего окна того или иного типа. Это позволяет получать, исследовать и строить в виде спектрограмм динамические спектры и анализировать их поведение во времени. Спектрограмма строится в трёх координатах — частота, время и амплитуда. При этом амплитуда задаётся цветом или оттенком цвета каждого прямоугольника спектрограммы. Подобные анализаторы спектра называют анализаторами спектра реального времени. Основным их производителем является корпорация Tektronix (США). Такие анализаторы появились в конце прошлого века и ныне бурно развиваются. Частотный диапазон исследуемых ими сигналов достигает сотен гигагерц.

Указанные методы спектрального анализа реализуются и в системах компьютерной математики, например, Mathcad, Mathematica, Maple и MATLAB.

Другие варианты Править

Дискретное преобразование Фурье является частным случаем (и иногда применяется для аппроксимации) дискретного во времени преобразования Фурье (DTFT), в котором $ x_k $ определены на дискретных, но бесконечных областях, и таким образом спектр является непрерывным и периодическим. Дискретное во времени преобразование Фурье является по существу обратным для рядов Фурье.

Эти разновидности преобразования Фурье могут быть обобщены на преобразования Фурье произвольных локально компактных абелевых топологических групп, которые изучаются в гармоническом анализе; они преобразуют группу в её дуальную группу. Эта трактовка также позволяет сформулировать теорему свёртки, которая устанавливает связь между преобразованиями Фурье и свёртками. См. также дуализм Понтрягина.

Интерпретация в терминах времени и частоты Править

В терминах обработки сигналов, преобразование берёт представление функции сигнала в виде временны́х рядов и отображает его в частотный спектр, где $ \omega $ — угловая частота. То есть оно превращает функцию времени в функцию частоты; это разложение функции на гармонические составляющие на различных частотах.

Когда функция $ f $ является функцией времени и представляет физический сигнал, преобразование имеет стандартную интерпретацию как спектр сигнала. Абсолютная величина получающейся в результате комплексной функции $ F $ представляет амплитуды соответствующих частот ( $ \omega $ ), в то время как фазовые сдвиги получаются как аргумент этой комплексной функции.

Однако важно осознавать, что преобразования Фурье не ограничиваются функциями времени и временными частотами.

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

Илон Маск рекомендует:  IncMonth - Функция Delphi

Таблица важных преобразований Фурье Править

Следующая таблица содержит список важных формул для преобразования Фурье $ F(\omega) $ и $ G(\omega) $ обозначают фурье компоненты функций $ f(t) $ и $ g(t) $ , соответственно. $ f $ и $ g $ должны быть интегрируемыми функциями или обобщёнными функциями.

Соотношения в этой таблице и в особенности множители, такие как $ \sqrt <2\pi>$ , зависят от соглашения, какая форма определения для Фурье преобразования использовалась прежде (хотя в общем виде соотношения, конечно, правильны).

Функция Образ Примечания
1 $ af(t)+bg(t)\, $ $ aF(\omega)+bG(\omega)\, $ Линейность
2 $ f(t-a)\, $ $ e^<-i\omega a>F(\omega)\, $ Запаздывание
3 $ e^f(t)\, $ $ F(\omega-a)\, $ Частотный сдвиг
4 $ f(at)\, $ $ |a|^<-1>F\left(\frac<\omega>\right)\, $ Если $ a $ большое, то $ f(at) $ сосредоточена около 0 и $ |a|^<-1>F\left(\frac<\omega>\right) $ становится плоским
5 $ \frac\, $ $ (i\omega)^n F(\omega)\, $ Свойство преобразования Фурье от $ n $ -й производной
6 $ t^n f(t)\, $ $ i^n\frac\, $ Это обращение правила 5
7 $ (f*g)(t)\, $ $ \sqrt<2\pi>F(\omega)G(\omega)\, $ Запись $ f*g $ означает свёртку $ f $ и $ g $ . Это правило — теорема о свёртке
8 $ f(t)g(t)\, $ $ \frac<(F*G)(\omega)><\sqrt<2\pi>>\, $ Это обращение 7
9 $ \delta(t)\, $ $ \frac<1><\sqrt<2\pi>>\, $ $ \delta(t) $ означает дельта-функцию Дирака
10 $ 1\, $ $ \sqrt<2\pi>\delta(\omega)\, $ Обращение 9.
11 $ t^n\, $ $ i^n\sqrt<2\pi>\delta^<(n)>(\omega)\, $ Здесь, $ n $ — натуральное число, $ \delta^n(\omega) $ — $ n $ -я обобщённая производная дельта-функции Дирака. Следствие правил 6 и 10. Использование его вместе с правилом 1 позволяет делать преобразования любых многочленов
12 $ e^\, $ $ \sqrt<2\pi>\delta(\omega-a)\, $ Следствие 3 и 10
13 $ \cos(at)\, $ $ \sqrt<2\pi>\frac<\delta(\omega-a)+\delta(\omega+a)><2>\, $ Следствие 1 и 12 с использованием формулы Эйлера $ \cos(at)=\frac<1><2>\left(e^+e^<-iat>\right)\, $
14 $ \sin(at)\, $ $ \sqrt<2\pi>\frac<\delta(\omega-a)-\delta(\omega+a)><2i>\, $ Также из 1 и 12
15 $ \exp(-at^2)\, $ $ \frac<1><\sqrt<2a>>\exp\left(\frac<-\omega^2><4a>\right)\, $ Показывает, что функция Гаусса $ \exp(-t^2/2) $ совпадает со своим изображением
16 $ W\sqrt<\frac<2><\pi>>\mathrm(Wt)\, $ $ \mathrm\left(\frac<\omega><2w>\right)\, $ Прямоугольная функция — идеальный фильтр низких частот и функция sinc(x) — её временной эквивалент
17 $ \frac<1>\, $ $ -i\sqrt<\frac<\pi><2>>\sgn(\omega)\, $ Здесь $ \sgn(\omega)\, $ — sign функция. Это правило согласуется с 6 и 10
18 $ \frac<1>\, $ $ -i\sqrt<\frac<\pi><2>>\frac<(-i\omega)^><(n-1)!>\sgn(\omega)\, $ Обобщение 17
19 $ \sgn(t)\, $ $ \sqrt<\frac<2><\pi>>(i\omega)^<-1>\, $ Обращение 17
20 $ \sqrt<2\pi>\mathrm(t)\, $ $ \frac<1>+\pi\delta(\omega)\, $ Здесь $ \mathrm(t)\, $ — функция Хевисайда. Следует из правил 1 и 19

См. также Править

Литература Править

  • Афонский А. А., Дьяконов В. П. Цифровые анализаторы спектра, сигналов и логики / Под ред. проф. В. П. Дьяконова. — М .: СОЛОН-Пресс, 2009. — С. 248. — ISBN 978-5-913-59049-7. (см. ISBN )
  • Дьяконов В. П. MATLAB 6.5 SP1/7.0 + Simulink 5/6. Обработка сигналов и проектирование фильтров. — М .: СОЛОН-Пресс, 2005. — С. 576. — ISBN 5-980-03206-1. (см. ISBN )
  • Сергиенко А. Б. Цифровая обработка сигналов. — 2-е изд. — СПб. : Питер, 2006. — С. 751. — ISBN 5-469-00816-9. (см. ISBN )
  • М. А. Павлейно, В. М. Ромаданов. Спектральные преобразования в MatLab. — СПб. , 2007. — С. 160. — ISBN 978-5-983-40121-1. (см. ISBN )

H Практическое применение преобразования Фурье для обработки сигналов в черновиках Из песочницы

Книги и публикации по цифровой обработке сигналов пишут авторы зачастую не догадывающиеся и не понимающие задач, стоящих перед разработчиками. Особенно это касается систем, работающих в реальном времени. Эти авторы отводят себе скромную роль бога, существующего вне времени и пространства, что вызывает некоторое недоумение у читателей подобной литературы. Данная публикация имеет целью развеять недоумения, возникающие у большинства разработчиков, и помочь им преодолеть «порог вхождения», для этих целей в тексте сознательно используется аналогии и терминология сферы программирования.

Данный опус не претендует на полноту и связность изложения.

Добавлено после прочтения комментариев.
Публикаций о том как делать БПФ немеряно, а о том как сделать БПФ, преобразовать спектр, и собрать сигнал заново, да еще и в реальном времени, явно не хватает. Автор пытается восполнить этот пробел.

Часть первая, обзорная

Существуют два основных способа построения дискретных линейных динамических систем. В литературе, такие системы принято называть цифровыми фильтрами, которые подразделяются на два основных типа: фильтры с конечной импульсной характеристикой (КИХ) и фильтры с бесконечной импульсной характеристикой (БИХ).

Алгоритмическая сущность фильтра с КИХ заключается в дискретном вычислении интеграла свертки:

Где x(t) – входной сигнал
y(t) – выходной сигнал
h(t) – импульсная характеристика фильтра или реакция фильтра на дельта функцию. Импульсная характеристика является обратным преобразованием Фурье комплексной частотной характеристики фильтра K(f).

Для формирования ясной картины у читателя, приведем пример дискретного вычисления интеграла свертки на языке С в реальном времени.

Вызывая данную функцию через определенные интервалы времени T и передавая ей в качестве аргумента входной сигнал, на выходе мы получим выходной сигнал, соответствующий реакции фильтра с импульсной характеристикой вида:

h(t)=1 при 0 >alfa);, но в этом случае происходит потеря alfa значащих разрядов. Рекуррентное выражение фильтра, из примера кода, построено таким образом, чтобы избежать потери значащих разрядов. Именно конечная точность вычислений может испортить всю прелесть цифрового фильтра с бесконечной импульсной характеристикой. Особенно это заметно на фильтрах высоких порядков, отличающихся высокой добротностью. В реальных динамических системах такая проблема не возникает, наша Матрица производит вычисления с невероятной для нас точностью.

Синтезу подобных фильтров посвящена масса литературы, также имеются готовые программные продукты (см. выше).

Часть вторая. Фурье – фильтр

Из вузовских курсов (у вашего покорного слуги это был курс ОТЭЦ) многие собравшие помнят два основных подхода к анализу линейных динамических систем: анализ во временной области и анализ в частотной области. Анализ во временной области — это решение дифференциальных уравнений, интегралы свертки и Дюамеля. Эти методы анализа дискретно воплотились в цифровых фильтрах БИХ и КИХ.

Но существует частотный подход к анализу линейных динамических систем. Иногда его называют операторным. В качестве операторов используются преобразование Фурье, Лапласа и т.п. Далее мы будем говорить только о преобразовании Фурье.

Данный метод анализа не получил широкого распространения при построении цифровых фильтров. Автору не удалось найти вменяемых практических рекомендаций по построению подобных фильтров на русском языке. Единственное краткое упоминание такого фильтра в практической литературе [Рабинер Л., Гоулд Б., Теория и применение цифровой обработки сигналов 1978], но в данной книге рассмотрение подобного фильтра очень поверхностно. В указанной книге данная схема построения фильтра называется: «свертка в реальном времени методом БПФ», что, по моему скромному мнению, совершенно не отражает сути, название должно быть коротким, иначе времени на отдых не останется.

Реакция линейной динамической системы есть обратное преобразование Фурье от произведения изображения по Фурье входного сигнала x(t) на комплексный коэффициент передачи K(f):

В практическом плане, данное аналитическое выражение предполагает следующий порядок действий: берем преобразование Фурье от входного сигнала, умножаем результат на комплексный коэффициент передачи, выполняем обратное преобразование Фурье, результатом которого является выходной сигнал. В реальном дискретном времени такой порядок действий выполнить невозможно. Как брать интеграл по времени от минус до плюс бесконечности?! Его можно взять только находясь вне времени…

В дискретном мире для выполнения преобразования Фурье существует инструмент — алгоритм быстрого преобразования Фурье (БПФ). Именно его мы и будем использовать при реализации нашего Фурье-фильтра. Аргументом функции БПФ является массив временных отсчетов из 2^n элементов, результатом два массива длинной 2^n элементов соответствующие действительной и мнимой части преобразования Фурье. Дискретной особенностью алгоритма БПФ является то, что входной сигнал считается периодичным с интервалом 2^n. Это накладывает некоторые ограничения на алгоритм Фурье-фильтра. Если взять последовательность выборок входного сигнала, провести от них БПФ, умножить результат БПФ на комплексный коэффициент передачи фильтра и выполнить обратное преобразование …ничего получится! Выходной сигнал будет иметь огромные нелинейные искажения в окрестности стыков выборок.

Для решения этой проблемы необходимо применить два приема:

  • 1. Выборки необходимо обрабатывать преобразованием Фурье с перекрытием. То есть, каждая последующая выборка должно содержать часть предыдущей. В идеальном случае выборки должны перекрываться на (2^n-1) отсчетов, но это требует огромных вычислительных затрат. На практике, с лихвой, достаточно трехчетвертного (2^n-2^(n-2)), половинного (2^(n-1)) и даже четвертного перекрытия (2^(n-2)).
  • 2. Результаты обратного преобразования Фурье, для получения выходного сигнала, необходимо, перед наложение друг на друга, умножить на весовую функцию (массив весовых коэффициентов). Весовая функция должна удовлетворять следующим условиям:
  • 2.1 Равна нулю везде, кроме интервала 2^n.
  • 2.2 На краях интервала стремится к нулю.
  • 2.3 И, самое главное, сумма весовых функций Fv(t), сдвинутых на интервал перекрытия k должна быть постоянна:

Такие функции широко применяются в технике цифровой обработки сигналов, и называть их принято — окнами. По скромному мнению автора лучшим, с практической точки зрения, является окно имени Хана:

На рисунке приведены графики иллюстрирующие свойства окна Хана длинной 2^n=256. Экземпляры окна построены с половинным перекрытием k=128. Как видно все оговоренные выше свойства имеются в наличии.

По просьбам трудящихся, на следующем рисунке приведена схема вычислений Фурье-фильтра, при длине выборки 2^n=8, количество выборок 3. На подобных рисунках очень сложно отобразить процесс вычислений, особенно тяжело показать его цикличность, поэтому мы и ограничились количеством выборок равным трем.

Входной сигнал разбивается на блоки длинной 2^n=8 с перекрытием 50%, от каждого блока берется БПФ, результаты БПФ подвергаются нужной трансформации, берется обратное БПФ, результат обратного БПФ скалярно умножается на окно, после умножения блоки складываются с перекрытием.

При выполнение трансформаций спектра, не стоит забывать о главном свойстве массива БПФ действительных сигналов, первая половина массива БПФ комплексно сопряжена со второй половиной, т.е Re[i]=Re[(1 реальное время, БПФ, преобразование фурье, обработка сигналов

Как рассчитать преобразование Фурье функции

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

Критерии сходимости преобразования Фурье (а именно, что функция должна быть абсолютно интегрируемой в вещественной области) довольно строги из-за отсутствия члена с экспоненциальным затуханием, который имеется в преобразовании Лапласа, и это означает, что такие функции, как полиномы, экспоненты и тригонометрические функции, не имеют преобразования Фурье в обычном смысле. Тем не менее с помощью дельта-функции Дирака можно осуществить преобразование Фурье этих функций корректным образом.

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

Пpеобpазование фypье

О преобразовании Фурье, его смысле, свойствах и применении написано много книг, поэтому здесь будут описаны только самые важные его характеристики. Эта статья — своего рода теоретическая выжимка, и для её понимания следует уже обладать базовыми знаниями в этой области. Она не является учебником по преобразованию Фурье (уже существуют такие учебники, написанные профессионалами своего дела). Скорее, эта статья поможет освежить в памяти уже полученные знания в этой области, а также поможет вспомнить полезные формулы, которые у многих людей быстро улетучиваются из головы (к этой группе отношусь и я :) ).

Перед началом изложения хочу выразить благодарность Олегу Красноярову за присланное письмо, в котором были кратко рассмотрены альтернативные алгоритмы БПФ, менее известные, чем широко использующийся вариант. Практически полностью это письмо легло в основу подраздела Быстрое преобразование Фурье.

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


Итак, преобразование Фурье бывает двух видов: дискретное и непрерывное. Непрерывное используется математиками в аналитических исследованиях, дискретное применяется во всех остальных случаях.

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

также существует обратное преобразование, которое позволяет по образу H(f) восстановить исходную функцию h(t):

Очевидно, что образ H(f) является комплексной функцией вещественного аргумента, но также и h(t) может принимать не только вещественные, но и комплексные значения.

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

Свойства непрерывного преобразования Фурье

В таблице ниже описана связь свойств прообраза h и образа H.

Если То
h(t) вещественная H(-f) = H · (f)
h(t) чисто мнимая H(-f) = -H · (f)
h(t) четная H(f) четная
h(t) нечетная H(f) нечетная
h(t) вещественная и четная H(f) вещественная и четная
h(t) вещественная и нечетная H(f) чисто мнимая и нечетная
h(t) чисто мнимая и четная H(f) чисто мнимая и четная
h(t) чисто мнимая и нечетная H(f) вещественная и нечетная

Следующая таблица показывает, как меняется образ при изменении прообраза. Пусть запись обозначает, что H(f) является образом h(t). Тогда имеют место следующие отношения:

Следующий набор свойств относится к операциям свертки и корелляции. Свертка функций g и h определяется, как . Корелляция функций g и h определяется, как . В таком случае имеют место следующие отношения:

Дискретное преобразование Фурье

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

В случае равномерной сетки эта формула упрощается. Также на равномерной сетке обычно избавляются от шага, чтобы получить безразмерную формулу:

Обратное преобразование в таком случае будет иметь вид

При внимательном рассмотрении можно заметить, что индекс при Hn принимает N+1 значение, в то время как при hk — только N значений. Таким образом, как будто бы получается, что функция H содержит в себе больше информации, чем h. На самом деле это не так, поскольку значения H-N/2 и HN/2 совпадают.

Определенное таким образом, дискретное преобразование Фурье сохраняет практически все свойства непрерывного (разумеется, с учетом перехода к дискретному множеству).

Быстрое преобразование Фурье

Сколько операций требуется на проведение дискретного преобразования Фурье? Посчитав по определению ( N раз суммировать N слагаемых), получаем величину порядка N 2 . Тем не менее, можно обойтись существенно меньшим числом операций.

Наиболее популярным из алгоритмов ускоренного вычисления ДПФ является т.н. метод Cooley-Tukey, позволяющий вычислить ДПФ для числа отсчетов N = 2 k за время порядка Nlog2 N (отсюда и название — быстрое преобразование Фурье, БПФ). Этот способ чем-то неуловимо напоминает быструю сортировку. В ходе работы алгоритма также проводится рекурсивное разбиение массива чисел на два подмассива и сведение вычисления ДПФ от целого массива к вычислению ДПФ от подмассивов в отдельности.

Изобретение БПФ привело к потрясающему всплеску популярности преобразования Фурье. Целый ряд важных задач раньше решался за время порядка N 2 , но после проведения преобразования Фурье над исходными данными (за время порядка Nlog2 N) решается практически мгновенно. Преобразование Фурье лежит в основе цифровых корелляторов и методов свертки, активно используется при спектральном анализе (практически в чистом виде), применяется при работе с длинными числами.

Широко распространено ошибочное мнение о том, что метод Cooley-Tukey — единственный существующий метод выполнения БПФ, а само БПФ существует только для случая N = 2 k . На самом деле это не так — существуют алгоритмы БПФ для любого числа отсчетов. В одномерном случае, рассмотренном в этой статье, метод Винограда позволяет решить задачу для простого числа отсчетов N. Этот же алгоритм может быть легко обобщен на случай, когда N является степенью произвольного простого числа (а не только двойки), а также на случай, когда число N является произведением степеней простых чисел — т.е. N является произвольным числом, чье разложение на простые множители нам известно.

В двумерном случае можно использовать метод Нуссбаумера. Существуют и другие алгоритмы, как для одномерного, так и для двумерного случаев, но рассмотрение этих вопросов выходит за рамки статьи (мне рекомендовали следующий источник — Блейхут, «Быстрые алгоритмы цифровой обработки сигналов»).

Как уже говорилось выше, существуют алгоритмы БПФ для произвольного числа отсчетов, но наиболее широкое распространение получил только алгоритм для случая N = 2 k , что является существенным ограничением. Почему же это произошло?

Причина этого в том, что алгоритм, построенный по методу Cooley-Tukey, обладает рядом очень хороших технологических свойств. Структура алгоритма и его базовые операции не зависят от числа отсчетов (меняется только число прогонов базовой операции «бабочка»). Алгоритм легко распараллеливается с использованием базовой операции и конвееризуется, а также легко каскадируется (коэфициенты БПФ для 2N отсчетов могут быть легко получены преобразованием коэфициентов двух БПФ по N отсчетов, полученных «прореживанием» через один исходных 2N отсчетов). Алгоритм прост и компактен, не требует дополнительной оперативной памяти и допускает обработку данных «на месте». Существует целый ряд оптимизированных именно для этого алгоритма DSP-процессоров (это одновременно и причина, и следствие).

Всё это и обусловило популярность в инженерно/программистской среде именно этого алгоритма, и, соответственно, выбора именно 2 k отсчетов при использовании БПФ. Правда, попутно это привело к незаслуженному забвению широкими массами альтернативных алгоритмов, некоторые из которых (что следует отметить) требуют меньше вещественных операций на один отсчет, чем алгоритм Cooley-Tukey. Например, мне доводилось читать описание алгоритма, который по этому показателю на 20-40% (в зависимости от числа отсчетов) превосходил алгоритм Cooley-Tukey.

© Сергей Бочканов, Олег Краснояров

Быстрое преобразование Фурье (стр. 1 из 7)

Быстрое преобразование Фурье (БПФ) — это алгоритм вычисления преобразования Фурье для дискретного случая. В отличие от простейшего алгоритма, который имеет сложность порядка O(N 2 ), БПФ имеет сложность всего лишь O(Nlog2 N). Алгоритм БПФ был впервые опубликован в 1965 году в статье Кули (Cooly) и Тьюки (Tukey).

Данное пособие содержит исходный код работающей программы для вычисления БПФ, подробное объяснение принципа ее работы и теоретическое обоснование. Все это можно найти и на других ресурсах, но трудно найти именно в таком комплекте: и программа, и объяснения, и теория, и на русском языке.

Если у вас нет времени и желания разбираться с теорией, то можете сразу скопировать текст программы на C++. Здесь находится заголовочный файл fft.h и исходник fft.cpp для быстрого преобразования Фурье для числа отсчетов, равного степени двойки. Вызывать надо функцию fft. А здесь находится заголовочный файл и исходник для произвольного (!) числа отсчетов. Он чуть медленнее, но скорость там тоже порядка Nlog2 N. Вызывать надо функцию universal_fft.

Дана конечная последовательность x , x1 , x2 . xN-1 (в общем случае комплексных). Дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности X , X1 , X2 . XN-1 элементы которой вычисляются по формуле:

Дана конечная последовательность X , X1 , X2 . XN-1 (в общем случае комплексных). Обратное дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности x , x1 , x2 . xN-1 элементы которой вычисляются по формуле:

Основным свойством этих преобразований (которое доказывается в соответствующих разделах математики) является тот факт, что из последовательности получается (при прямом преобразовании) последовательность , а если потом применить к обратное преобразование, то снова получится исходная последовательность .

называется поворачивающим множителем .

Рассмотрим ряд свойств поворачивающих множителей, которые нам понадобятся в дальнейшем.

Верхняя цифра в поворачивающем множителе не является индексом, это — степень. Поэтому, когда она равна единице, мы не будем ее писать:

Прямое преобразование Фурье можно выразить через поворачивающие множители. В результате формула (1) примет вид:

Эти коэффициенты действительно оправдывают свое название. Нарисуем на комплексной плоскости любое комплексное число, в виде вектора, исходящего из начала координат. Представим это комплексное число в показательной форме: re jφ , где r — модуль числа, а φ — аргумент. Модуль соответствует длине вектора, а аргумент — углу поворота:

Теперь возьмем какой-нибудь поворачивающий множитель

Если теперь посмотреть на формулу (3), то станет ясен геометрический смысл преобразования Фурье: он состоит в том, чтобы представить N комплексных чисел-векторов из набора , каждое в виде суммы векторов из набора , повернутых на углы, кратные 2π/N.

Если комплексное число представлено в виде e j2πN , где N — целое, то это число e j2πN = 1.

По формуле Эйлера, и ввиду периодичности синуса и косинуса:

e j2 π N = cos(2πN) + j sin(2πN) = cos 0 + j sin 0 = 1 + j0 = 1

Величина -h = -(nl+mk+mlN) — целая, так как все множители целые, и все слагаемые целые. Значит, мы можем применить Теорему 0:

Что и требовалось доказать по (4).

Алгоритм быстрого преобразования Фурье (БПФ) — это оптимизированный по скорости способ вычисления ДПФ. Основная идея заключается в двух пунктах.

  1. Необходимо разделить сумму (1) из N слагаемых на две суммы по N/2 слагаемых, и вычислить их по отдельности. Для вычисления каждой из подсумм, надо их тоже разделить на две и т.д.
  2. Необходимо повторно использовать уже вычисленные слагаемые.

Применяют либо «прореживание по времени» (когда в первую сумму попадают слагаемые с четными номерами, а во вторую — с нечетными), либо «прореживание по частоте» (когда в первую сумму попадают первые N/2 слагаемых, а во вторую — остальные). Оба варианта равноценны. В силу специфики алгоритма приходится применять только N, являющиеся степенями 2. Рассмотрим случай прореживания по времени.

Определим еще две последовательности: [even] > и [odd] > через последовательность следующим образом:

Пусть к этим последовательностям применены ДПФ и получены результаты в виде двух новых последовательностей [even] > и [odd] > по N/2 элементов в каждой.

Утверждается, что элементы последовательности можно выразить через элементы последовательностей [even] > и [odd] > по формуле:

Начинаем от формулы (2), в которую подставляем равенства из (6):

Теперь обратим внимание на то, что:

Подставляя (9) в (8) получаем:

Сравним с формулами для X[even]k и X[odd]k при k = 0,1,…,N/2-1:

Подставляя (11) в (10) получим первую часть формулы (7):

Это будет верно при k = 0,1,…,N/2-1.

Согласно теореме 1:

Подставим (12) в (10), и заменим

Для k = N/2,…,N-1 по формуле (2):

Подставляем (14) в (13):

Эта формула верна для k = N/2,…,N-1 и, соответственно, (k — N/2) = 0,1,…,N/2-1 и представляет собой вторую и последнюю часть утверждения (7), которое надо было доказать.

Формула (7) позволяет сократить число умножений вдвое (не считая умножений при вычислении X[even]k и X [odd]k ), если вычислять Xk не последовательно от 0 до N — 1, а попарно: X и XN/2 , X1 и XN/2+1 . XN/2-1 и XN . Пары образуются по принципу: Xk и XN/2+k .

ДПФ можно вычислить также по формуле:

Согласно второй части формулы (7), получим:

Это доказывает второе равенство в утверждении теоремы, а первое уже доказано в теореме 3.

Также по этой теореме видно, что отпадает необходимость хранить вычисленные X[even]k и X[odd]k после использования при вычислении очередной пары и одно вычисление

На этом шаге будет выполнено N/2 умножений комплексных чисел. Если мы применим ту же схему для вычисления последовательностей [even] > и [odd] >, то каждая из них потребует N/4 умножений, итого еще N/2. Продолжая далее в том же духе log2 N раз, дойдем до сумм, состоящих всего из одного слагаемого, так что общее количество умножений окажется равно (N/2)log2 N, что явно лучше, чем N 2 умножений по формуле (2).

Рассмотрим БПФ для разных N. Для ясности добавим еще один нижний индекс, который будет указывать общее количество элементов последовательности, к которой этот элемент принадлежит. То есть Xk — это k-й элемент последовательности > из R элементов. X[even]k — это k-й элемент последовательности [even] > из R элементов, вычисленный по четным элементам последовательности >. X[odd]k — это k-й элемент последовательности [odd] >, вычисленный по нечетным элементам последовательности >.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL