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

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

Из зависимости амплитуда(время) получается амплитуда(частота). Полез в Википедию за алгоритмом быстрого преобразования: сделал ctrl+C, ctrl+V первого примера. На выходе получаю следующий файл: 0.000000 0.000000 0.000000 0.500000 0.000000 0.250000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.500000 0.000000 0.250000 Первый столбец — вещественная часть, второй — мнимая, третий — сумма квадратов вещественной и мнимой частей. По коду, на сколько я понял, делается БПФ косинуса с частотой 2*pi/8 что примерно равно 0.785. Назревает глупый вопрос, как этот файл соотносится со спектром косинуса, который должен быть везде нулем, кроме частоты косинуса, в которой он должен быть равен 1?

«Быстрое преобразование Фурье». Дискретное преобразование Фурье (ДПФ).

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

Объясните, пожалуйста, уважаемые сведущие. Может я не тот пример беру? PS в файле убрал минусы перед нулевыми значениями, чтобы он смотрелся ровно:-) • Вопрос задан более трёх лет назад • 12657 просмотров. Фурье как и любое разложение суть нахождение координат (коэффициентов для суммы ) в пространстве ортогональных векторов ( в данном случае косинусов с частотой кратной пи-чего-то-там ). Если ваш исходный вектор ( функция, в данном случае — косинус ) параллелен одному из базисов ( то есть частоты совпадают ), то вы получите нули кроме одного значения. Если же нет, то вы получите разложение на несколько векторов ( частот ), сумма которых с найденными координатами-коэффициентами даст вам исходную функцию ( с заданной точностью ). Музика Падає Снижок.

Быстрое преобразование Фурье - это оптимизация алгоритма дискретного преобразования Фурье, которое в свою очередь - программная реализация классического непрерывного варианта. Оптимизация заключается в том, чтобы не производить некоторые не обязательные вычисления. Алгоритм быстрого преобразования Фурье был создан потому, что вычисление напрямую часто оказывается слишком затратным по времени. В то время как дискретное преобразование требует O(N^2) операций, FFT справляется с задачей за O(N, log, N) операций. При размерах векторов порядка нескольких миллионов это различие может уменьшить время вычисления на несколько порядков.

Пример Рассмотрим работу функции fft(x) пакета matlab на примере распознавания частотной составляющей зашумленного сигнала. Пусть чистый сигнал задаётся комбинацией синусов с частотами 50 и 60 Гц: x(t) = sin(2 pi, 50, t) + sin(2 pi, 60, t) После добавления шума узнать на графике сумму двух синусов становится сложно. Определить частотные составляющие сигнала при таком шуме позволяет преобразование Фурье. Построив график частотного спектра амплитуд исходной функции можно видеть два пика на фоне шума.

Эти пики отвечают тем двум синусам, которые составляют чистый сигнал. В matlab приведённый пример реализуется следующим образом.

Как работает быстрое преобразование Фурье Как работает быстрое преобразование Фурье (перевод с английского) Англоязычный вариант статьи: Быстрое преобразование Фурье (БПФ) - это сложный алгоритм, и его детали, обычно изучают те, кто занимается вопросами цифровой обработки сигналов. Этот раздел описывает общие принципы работы БПФ, основанного на использовании комплексных чисел. Если вы имеете опыт работы в комплексной математике, то легко поймете истинный смысл алгоритма. Не волнуйтесь, если от вас ускользнут некоторые детали: мало ученых и инженеров, которые используют БПФ, могут написать программу с нуля. В частотной и временной области сигнал представлен N комплексными точками.

Каждая из этих точек состоит из двух чисел: действительной и мнимой части. Например, когда мы говорим о комплексном отсчете X [42], речь идет о комбинации ReX [42] и ImX [42]. После умножения двух комплексных переменных, необходимо объединить четыре отдельные компоненты в две. Дальнейшее обсуждение темы «Как работает БПФ» использует специфические термины: сигнал, точка, отсчёт и значение представляют собой сочетание реальной и мнимой частей.

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

В этом примере 16-ти точечный сигнал разлагается на четыре отдельные компоненты. Первый этап заключается в разбиения 16-ти точечного сигнала на два сигнала по 8 точек.

На втором этапе происходит разложение данных сигналов на четыре сигнала по 4 точки. Данная процедура продолжается до тех пор, пока не будет сформировано N сигналов состоящих из одной точки. Черезстрочное разложения используется при разделении выборки сигнала на две выборки.

Сигнал разделяется как при четном, так и при нечетном количестве отсчетов в выбороке. В системе проводится 2 N этапов в разложении, т.е. На 16–ти точечный сигнал ( 2 4) предусматривает 4 этапа, 512 точки ( 2 7) требует 7 этапов, 4096 точки ( 2 12) предусматривает 12 этапов и т.д. Запомним, это значение - оно будет много раз встречаться в этой главе. Рисунок 12.2 - Процедура разбиения сигнала Теперь, когда понятна структура разложения, ее можно значительно упростить. Разложения является не более чем перераспределение отсчетов сигнала.

Это иллюстрирует рисунок 12.3. Слева представлены номера отсчетов первоначального сигнала, вместе с их двоичными эквивалентами. Справа, измененные номера, а также их двоичные эквиваленты.

Идея состоит в том, что двоичные числа являются инверсией друг друга. Например, отсчёт №3 (0011) можно получить из отсчёта №12 (1100). Отсчёт № 14 (1110) получается из отсчета № 7 (0111), и так далее. Разбиение временной области в БПФ обычно, проводится с использование алгоритма сортировки инвертированных бит.

Это предполагает изменение N временных областей, с подсчетом в двоичном виде и переворачиванием бит слева на право (например, в крайней правой колонке в Рис. Рисунок 12.3 - Процедура перераспределения отсчетов сигнала Следующим шагом алгоритма БПФ является нахождение частоты спектров одноточечного сигналов, определенного во временной области. Это делается элементарно: спектр одноточечного сигнала равен самому себе. Это означает, что на этом шаге ничего не надо. Хотя не стоит забывать, что каждый из одноточечных сигналов теперь представляет собой спектр частот, а не сигнал во временной области Последний шаг в БПФ состоит в том, чтобы объединить N спектров частот в обратном по отношению ко временному разделению порядке. В этом случае алгоритм работает некорректно. К сожалению, обратное быстрое преобразование не применяется, а мы должны вернуться на каком-то этапе ко времени.

На первом этапе, 16 одноточечных частотных спектра объединяются в 8 частотных спектра по 2 точки каждый. На втором этапе 8 частотных спектров синтезируется в 4 спектра, и так далее. На последнем этапе получаем результат БПФ в виде 16 точечного частотного спектра. Рисунок 12.4 показывает, как два частотных спектра, каждый из которых состоял из 4 точек, объединены в единый частотный диапазон на 8 очков. Объединение должно исключить одинаковые разложения во временной области.

Иными словами, операция в частотной области должна соответствовать операции во временной области с исключением пересечений. Рассмотрим два сигналы временной области. 8 точечный временной сигнал формирутеся в два этапа: разбавлением каждого 4-точечного сигнала нулями, для того, чтобы получить 8-ми точечный сигнал, а затем объединять сигналы вместе. Поэтому сигнал 1 превращается в a0b0c0d0, а 2 станет 0e0f0g0h.

Суммирование этих двух сигналов дает 8-точечный сигнал aebfcgdh. Как показано на рис.

12.4, дополнение временной реализации сигнала нулями соответствует дублированию частотного спектра. Таким образом, спектры частот в БПФ, дублируются, а потом прибавляет один к другому. Рисунок 12.4 - Процедура синтеза частотного спектра сигнала Для достижения соответствия, двух сигналов во временной области разбавляются нулями в немного другом виде. В одном сигнала, нечетные отсчеты равны нулю, а в другом сигнале четные отсчеты равны нулю. Иными словами, один из сигналов временной области (0e0f0g0h на рис. 12.4) сдвигается вправо на один отсчет. Этот сдвиг во временной области соответствует умножения на спектр синуса.

Чтобы увидеть это, вспомним, что сдвиг во времененной области эквивалентен свертыванию сигнала со смещенной дельта-функцией. Спектр смещенной дельта функция является синусоидой. Рисунок 12.5 показывает схема совмещения двух 4-х точечных спектра в один 8-ми точечный. Заметим, что рис. 12.5 формируется по базовой схеме рис 12.6 с повторением вновь и вновь.

Рисунок 12.5 - схема совмещения двух 4-х точечных спектра в один 8-ми точечный. Эта простая схема называется «бабочка» в силу своего крылатого вида. «Бабочка» является основным вычислительным элементом БПФ, преобразовывая две комплексные точки в две другие.

Рисунок 12.6 - Cхема «бабочки» Рисунок 12.7 показывает структуру БПФ. Разбиение во временной области выполняется с помощью ранее рассмотренного алгоритма сортировки. Синтез в частотной области требует трех циклов. Внешний цикл проводится Log 2N раз.

Средний цикл движется по каждой отдельной частоте спектра. Внутренний цикл использует бабочку для расчета точек в каждой частоты спектра (т.е.

Циклы через образцы внутри одного окна на рис. Накладных клетки на рис. 12.7 определяют начало и окончания индексов в циклах, а также расчета необходимых синусоиды бабочек. Блок-схема программы, реализующая БПФ приведена на рис. Рисунок 12.7 - Блок-схема программы, реализующая БПФ.

    Search