что такое преобразование фурье простыми словами
Практическое применение преобразования Фурье для обработки сигналов
Книги и публикации по цифровой обработке сигналов пишут авторы зачастую не догадывающиеся и не понимающие задач, стоящих перед разработчиками. Особенно это касается систем, работающих в реальном времени. Эти авторы отводят себе скромную роль бога, существующего вне времени и пространства, что вызывает некоторое недоумение у читателей подобной литературы. Данная публикация имеет целью развеять недоумения, возникающие у большинства разработчиков, и помочь им преодолеть «порог вхождения», для этих целей в тексте сознательно используется аналогии и терминология сферы программирования.
Данный опус не претендует на полноту и связность изложения.
Добавлено после прочтения комментариев.
Публикаций о том как делать БПФ немеряно, а о том как сделать БПФ, преобразовать спектр, и собрать сигнал заново, да еще и в реальном времени, явно не хватает. Автор пытается восполнить этот пробел.
Часть первая, обзорная
Существуют два основных способа построения дискретных линейных динамических систем. В литературе, такие системы принято называть цифровыми фильтрами, которые подразделяются на два основных типа: фильтры с конечной импульсной характеристикой (КИХ) и фильтры с бесконечной импульсной характеристикой (БИХ).
Алгоритмическая сущность фильтра с КИХ заключается в дискретном вычислении интеграла свертки:
Где 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. Это накладывает некоторые ограничения на алгоритм Фурье-фильтра. Если взять последовательность выборок входного сигнала, провести от них БПФ, умножить результат БПФ на комплексный коэффициент передачи фильтра и выполнить обратное преобразование …ничего получится! Выходной сигнал будет иметь огромные нелинейные искажения в окрестности стыков выборок.
Для решения этой проблемы необходимо применить два приема:
Такие функции широко применяются в технике цифровой обработки сигналов, и называть их принято — окнами. По скромному мнению автора лучшим, с практической точки зрения, является окно имени Хана:
На рисунке приведены графики иллюстрирующие свойства окна Хана длинной 2^n=256. Экземпляры окна построены с половинным перекрытием k=128. Как видно все оговоренные выше свойства имеются в наличии.
По просьбам трудящихся, на следующем рисунке приведена схема вычислений Фурье-фильтра, при длине выборки 2^n=8, количество выборок 3. На подобных рисунках очень сложно отобразить процесс вычислений, особенно тяжело показать его цикличность, поэтому мы и ограничились количеством выборок равным трем.
Входной сигнал разбивается на блоки длинной 2^n=8 с перекрытием 50%, от каждого блока берется БПФ, результаты БПФ подвергаются нужной трансформации, берется обратное БПФ, результат обратного БПФ скалярно умножается на окно, после умножения блоки складываются с перекрытием.
При выполнение трансформаций спектра, не стоит забывать о главном свойстве массива БПФ действительных сигналов, первая половина массива БПФ комплексно сопряжена со второй половиной, т.е Re[i]=Re[(1
Понимание алгоритма БПФ
Здравствуйте, друзья. Уже завтра стартует курс «Алгоритмы для разработчиков», а у нас остался один неопубликованный перевод. Собственно исправляемся и делимся с вами материалом. Поехали.
Быстрое преобразование Фурье (БПФ — англ. FFT) является одним из важнейших алгоритмов обработки сигналов и анализа данных. Я пользовался им годами, не имея формальных знаний в области компьютерных наук. Но на этой неделе мне пришло в голову, что я никогда не задавался вопросом, как БПФ так быстро вычисляет дискретное преобразование Фурье. Я стряхнул пыль со старой книги по алгоритмам, открыл ее, и с удовольствием прочитал об обманчиво простой вычислительной уловке, которую Дж. В. Кули и Джон Тьюки описали в своей классической работе 1965 года, посвященной этой теме.
Цель этого поста — окунуться в алгоритм БПФ Кули-Тьюки, объясняя симметрии, которые к нему приводят, и показать несколько простых реализаций на Python, применяющих теорию на практике. Я надеюсь, что это исследование даст специалистам по анализу данных, таким как я, более полную картину того, что происходит под капотом используемых нами алгоритмов.
Дискретное преобразование Фурье
БПФ — это быстрый алгоритм для вычисления дискретного преобразования Фурье (ДПФ), которое напрямую вычисляется за . ДПФ, как и более знакомая непрерывная версия преобразования Фурье, имеет прямую и обратную форму, которые определяются следующим образом:
Прямое дискретное преобразование Фурье (ДПФ):
Обратное дискретное преобразование Фурье (ОДПФ):
Преобразование из xn → Xk является переводом из конфигурационного пространства в пространство частотное и может быть очень полезным как для исследования спектра мощности сигнала, так и для преобразования определенных задач для более эффективного вычисления. Некоторые примеры этого в действии вы можете найти в главе 10 нашей будущей книги по астрономии и статистике, где также можно найти изображения и исходный код на Python. Пример использования БПФ для упрощения интегрирования сложных в противном случае дифференциальных уравнений смотрите в моем посте «Решение уравнения Шредингера в Python».
Из-за важности БПФ (далее может быть использовано равносильное FFT — Fast Fourier Transform) во многих областях Python содержит множество стандартных инструментов и оболочек для его вычисления. И NumPy, и SciPy имеют оболочки из чрезвычайно хорошо протестированной библиотеки FFTPACK, которые находятся в подмодулях numpy.fft и scipy.fftpack соответственно. Самый быстрый БПФ, о котором я знаю, находится в пакете FFTW, который также доступен в Python через пакет PyFFTW.
На данный момент, однако, давайте оставим эти реализации в стороне и зададимся вопросом, как мы можем вычислить БПФ в Python с нуля.
Вычисление дискретного преобразования Фурье
Для простоты мы будем касаться только прямого преобразования, поскольку обратное преобразование может быть реализовано очень похожим образом. Взглянув на приведенное выше выражение ДПФ (DFT), мы видим, что это не более чем прямолинейная линейная операция: умножение матрицы на вектор
с матрицей М, заданной
Имея это в виду, мы можем вычислить ДПФ с использованием простого умножения матрицы следующим образом:
Мы можем перепроверить результат, сравнив его со встроенной в numpy БПФ-функцией:
Просто чтобы подтвердить медлительность нашего алгоритма, мы можем сравнить время выполнения этих двух подходов:
Мы более чем в 1000 раз медленнее, что и следовало ожидать для такой упрощенной реализации. Но это не самое худшее. Для входного вектора длины N алгоритм БПФ масштабируется как , в то время как наш медленный алгоритм масштабируется как . Это означает, что для элементов мы ожидаем, что БПФ завершится за где-то около 50 мс, в то время как наш медленный алгоритм займет около 20 часов!
Так как же БПФ добивается такого ускорения? Ответ заключается в использовании симметрии.
Симметрии в дискретном преобразовании Фурье
Одним из наиболее важных инструментов в построении алгоритмов является использование симметрий задачи. Если вы можете аналитически показать, что одна часть проблемы просто связана с другой, вы можете вычислить подрезультат только один раз и сэкономить эти вычислительные затраты. Кули и Тьюки использовали именно этот подход при получении БПФ.
Мы начнем с вопроса о значении . Из нашего выражения выше:
где мы использовали тождество exp [2π i n] = 1, которое выполняется для любого целого числа n.
Последняя строка хорошо показывает свойство симметрии ДПФ:
для любого целого числа i. Как мы увидим ниже, эту симметрию можно использовать для гораздо более быстрого вычисления ДПФ.
ДПФ в БПФ: использование симметрии
Кули и Тьюки показали, что можно разделить вычисления БПФ на две меньшие части. Из определения ДПФ имеем:
Мы разделили одно дискретное преобразование Фурье на два слагаемых, которые сами по себе очень похожи на меньшие дискретные преобразования Фурье, одно на значения с нечетным номером и одно на значения с четным номером. Однако до сих пор мы не сохранили никаких вычислительных циклов. Каждый член состоит из (N / 2) ∗ N вычислений, всего .
Хитрость заключается в использовании симметрии в каждом из этих условий. Поскольку диапазон k равен 0≤k True
Сопоставим этот алгоритм с нашей медленной версией:
-In [6]:
Наш расчет быстрее чем прямая версия на порядок! Более того, наш рекурсивный алгоритм асимптотически : мы реализовали быстрое преобразование Фурье.
Обратите внимание, что мы все еще не приблизились к скорости встроенного алгоритма FFT в numpy, и этого следовало ожидать. Алгоритм FFTPACK, стоящий за fft numpy, — это реализация на Фортране, которая получила годы доработок и оптимизаций. Кроме того, наше решение NumPy включает в себя как рекурсию стека Python, так и выделение множества временных массивов, что увеличивает время вычислений.
Хорошая стратегия для ускорения кода при работе с Python / NumPy — по возможности векторизовать повторяющиеся вычисления. Это мы можем сделать — в процессе удалять наши рекурсивные вызовы функций, что сделает наш Python FFT еще более эффективным.
Обратите внимание, что в вышеупомянутой рекурсивной реализации FFT на самом низком уровне рекурсии мы выполняем N / 32 идентичных матрично-векторных произведений. Эффективность нашего алгоритма выиграет, если одновременно вычислить эти матрично-векторные произведения как единое матрично-матричное произведение. На каждом последующем уровне рекурсии мы также выполняем повторяющиеся операции, которые можно векторизовать. NumPy отлично справляется с такой операцией, и мы можем использовать этот факт для создания этой векторизованной версии быстрого преобразования Фурье:
Хотя алгоритм немного более непрозрачен, это просто перестановка операций, используемых в рекурсивной версии, с одним исключением: мы используем симметрию в вычислении коэффициентов и строим только половину массива. Опять же, мы подтверждаем, что наша функция дает правильный результат:
Поскольку наши алгоритмы становятся намного более эффективными, мы можем использовать больший массив для сравнения времени, оставляя DFT_slow :
In [9]:
Мы улучшили нашу реализацию еще на порядок! Сейчас мы находимся на расстоянии примерно в 10 раз от эталона FFTPACK, используя всего пару десятков строк чистого Python + NumPy. Хотя это все еще не соответствует в вычислительном отношении, с точки зрения читаемости версия Python намного превосходит исходный код FFTPACK, который вы можете просмотреть здесь.
Итак, как FFTPACK достигает этого последнего ускорения? Ну, в основном, это просто вопрос детальной бухгалтерии. FFTPACK тратит много времени на повторное использование любых промежуточных вычислений, которые можно использовать повторно. Наша клочковатая версия все еще включает в себя избыток выделения памяти и копирования; на низкоуровневом языке, таком как Fortran, легче контролировать и минимизировать использование памяти. Кроме того, алгоритм Кули-Тьюки можно расширить, чтобы использовать разбиения размером, отличным от 2 (то, что мы здесь реализовали, известно как БПФ Кули-Тьюки радикса по основе 2). Также могут быть использованы другие более сложные алгоритмы БПФ, в том числе принципиально отличные подходы, основанные на сверточных данных (см., Например, алгоритм Блюштейна и алгоритм Рейдера). Комбинация вышеупомянутых расширений и методов может привести к очень быстрым БПФ даже на массивах, размер которых не является степенью двойки.
Хотя функции на чистом Python, вероятно, бесполезны на практике, я надеюсь, что они преподнесли некоторую интуицию в том, что происходит на фоне анализа данных на основе FFT. Как специалисты по данным, мы можем справиться с реализацией «черного ящика» фундаментальных инструментов, созданных нашими более алгоритмически настроенными коллегами, но я твердо убежден, что чем больше у нас понимания о алгоритмах низкого уровня, которые мы применяем к нашим данным, тем лучшими практиками мы будем.
Этот пост был полностью написан в блокноте IPython. Полный блокнот можно скачать здесь или посмотреть статически здесь.
Многие могут заметить, что материал далеко не новый, но, как нам кажется, вполне актуальный. В общем пишите была ли статья полезной. Ждём ваши комментарии.
Простыми словами о преобразовании Фурье
Я полагаю что все в общих чертах знают о существовании такого замечательного математического инструмента как преобразование Фурье. Однако в ВУЗах его почему-то преподают настолько плохо, что понимают как это преобразование работает и как им правильно следует пользоваться сравнительно немного людей. Между тем математика данного преобразования на удивление красива, проста и изящна. Я предлагаю всем желающим узнать немного больше о преобразовании Фурье и близкой ему теме того как аналоговые сигналы удается эффективно превращать для вычислительной обработки в цифровые.
(с) xkcd
Я буду исходить из предположения что читатель понимает что такое интеграл, комплексное число (а так же его модуль и аргумент), свертка функций, плюс хотя бы “на пальцах” представляет себе что такое дельта-функция Дирака. Не знаете — не беда, прочитайте вышеприведенные ссылки. Под “произведением функций” в данном тексте я везде буду понимать “поточечное умножение”
Начать надо, наверное, с того что обычное преобразование Фурье — это некая такая штука которая, как можно догадаться из названия, преобразует одни функции в другие, то есть ставит в соответствие каждой функции действительного переменного x(t) её спектр или фурье-образ y(w):
Если приводить аналогии, то примером аналогичного по смыслу преобразования может послужить например дифференцирование, превращающее функцию в её производную. То есть преобразование Фурье — такая же, по сути, операция как и взятие производной, и её часто обозначают схожим образом, рисуя треугольную “шапочку” над функцией. Только в отличие от дифференцирования которое можно определить и для действительных чисел, преобразование Фурье всегда “работает” с более общими комплексными числами. Из-за этого постоянно возникают проблемы с отображением результатов этого преобразования, поскольку комплексные числа определяются не одной, а двумя координатами на оперирующем действительными числами графике. Удобнее всего, как правило, оказывается представить комплексные числа в виде модуля и аргумента и нарисовать их по раздельности как два отдельных графика:
График аргумента комплексного значения часто называют в данном случае “фазовым спектром”, а график модуля — “амплитудным спектром”. Амплитудный спектр как правило представляет намного больший интерес, а потому “фазовую” часть спектра нередко пропускают. В этой статье мы тоже сосредоточимся на “амплитудных” вещах, но забывать про существование пропущенной фазовой части графика не следует. Кроме того, вместо обычного модуля комплексного значения часто рисуют его десятичный логарифм умноженный на 10. В результате получается логарифмический график, значения на котором отображаются в децибелах (дБ).
Обратите внимание что не очень сильно отрицательным числам логарифмического графика (-20 дБ и менее) при этом соответствуют практически нулевые числа на графике “обычном”. Поэтому длинные и широкие “хвосты” разнообразных спектров на таких графиках при отображении в “обычные” координаты как правило практически исчезают. Удобство подобного странного на первый взгляд представления возникает из того что фурье-образы различных функций часто необходимо перемножать между собой. При подобном поточечном умножении комплекснозначных фурье-образов их фазовые спектры складываются, а амплитудные — перемножаются. Первое выполняется легко, а второе — сравнительно сложно. Однако логарифмы амплитуды при перемножении амплитуд складываются, поэтому логарифмические графики амплитуды можно, как и графики фаз, просто поточечно складывать. Кроме того, в практических задачах часто удобнее оперировать не «амплитудой» сигнала, а его «мощностью» (квадратом амплитуды). На логарифмической шкале оба графика (и амплитуды и мощности) выглядят идентично и отличаются только коэффициентом — все значения на графике мощности ровно вдвое больше чем на шкале амплитуд. Соответственно для построения графика распределения мощности по частоте (в децибелах) можно не возводить ничего в квадрат, а посчитать десятичный логарифм и умножить его на 20.
Заскучали? Погодите, еще немного, с занудной частью статьи, объясняющей как интерпретировать графики, мы скоро покончим :). Но перед этим следует понять одну крайне важную вещь: хотя все вышеприведенные графики спектров были нарисованы для некоторых ограниченных диапазонов значений (в частности, положительных чисел), все эти графики на самом деле продолжаются в плюс и минус бесконечность. На графиках просто изображается некоторая “наиболее содержательная” часть графика, которая обычно зеркально отражается для отрицательных значений параметра и зачастую периодически повторяется с некоторым шагом, если рассматривать её в более крупном масштабе.
Определившись с тем, что же рисуется на графиках, давайте вернемся собственно к преобразованию Фурье и его свойствам. Существует несколько разных способов как определить это преобразование, отличающихся небольшими деталями (разными нормировками). Например в наших ВУЗах почему-то часто используют нормировку преобразования Фурье определяющую спектр в терминах угловой частоты (радианов в секунду). Я буду использовать более удобную западную формулировку, определяющую спектр в терминах обычной частоты (герцах). Прямое и обратное преобразование Фурье в этом случае определяются формулами слева, а некоторые свойства этого преобразования которые нам понадобятся — списком из семи пунктов справа:
Если взять функцию, состоящую из суммы множества синусоид с разными частотами, то согласно свойству линейности, фурье-образ этой функции будет состоять из соответствующего набора дельта-функций. Это позволяет дать наивную, но наглядную интерпретацию спектра по принципу “если в спектре функции частоте f соответствует амплитуда a, то исходную функцию можно представить как сумму синусоид, одной из которых будет синусоида с частотой f и амплитудой 2a”. Строго говоря, эта интерпретация неверна, поскольку дельта-функция и точка на графике — это совершенно разные вещи, но как мы увидим дальше, для дискретных преобразований Фурье она будет не так уж и далека от истины.
Второе свойство преобразования Фурье — это независимость амплитудного спектра от сдвига сигнала по времени. Если мы подвинем функцию влево или вправо по оси x, то поменяется лишь её фазовый спектр.
Третье свойство — растяжение (сжатие) исходной функции по оси времени (x) пропорционально сжимает (растягивает) её фурье-образ по шкале частот (w). В частности, спектр сигнала конечной длительности всегда бесконечно широк и наоборот, спектр конечной ширины всегда соответствует сигналу неограниченной длительности.
Четвертое и пятое свойства самые, пожалуй, полезные из всех. Они позволяют свести свертку функций к поточечному перемножению их фурье-образов и наоборот — поточечное перемножение функций к свертке их фурье-образов. Чуть дальше я покажу насколько это удобно.
Наконец последнее, седьмое свойство, говорит о том, что преобразование Фурье сохраняет “энергию” сигнала. Оно осмысленно только для сигналов конечной продолжительности, энергия которых конечна, и говорит о том, что спектр подобных сигналов на бесконечности быстро приближается к нулю. Именно в силу этого свойства на графиках спектров как правило изображают только “основную” часть сигнала, несущую в себе львиную долю энергии — остальная часть графика просто стремится к нулю (но, опять же, нулем не является).
Вооружившись этими 7 свойствами, давайте посмотрим на математику “оцифровки” сигнала, позволяющую перевести непрерывный сигнал в последовательность цифр. Для этого нам понадобится взять функцию, известную как “гребенка Дирака”:
Гребенка Дирака — это просто периодическая последовательность дельта-функций с единичным коэффициентом, начинающаяся в нуле и идущая с шагом T. Для оцифровки сигналов, T выбирают по возможности малым числом, T