Есть ли БПФ, которое использует логарифмическое деление частоты?

Википедия & APOS; sВейвлет статья содержит этот текст:

The discrete wavelet transform is also less computationally complex, taking O(N) time as compared to O(N log N) for the fast Fourier transform. This computational advantage is not inherent to the transform, but reflects the choice of a logarithmic division of frequency, in contrast to the equally spaced frequency divisions of the FFT.

Означает ли это, что также существует алгоритм, подобный FFT, который использует логарифмическое деление частоты вместо линейного? Это тоже O (N)? Это, очевидно, было бы предпочтительным для многих приложений.

 tom1014 июл. 2009 г., 04:47
Это интересная идея. Хотя я не уверен, насколько это полезно: будут ли формы волны с логарифмическими частотами формировать полную основу, и если нет, то для чего они нужны? (Не сказать, что это бесполезно, я действительно имею в виду, что я не уверен.)
 endolith14 окт. 2009 г., 23:42
Теперь, когда я понимаю это лучше, сложное вейвлет-преобразование Морле, вероятно, сделает то, что я представлял, по крайней мере для анализатора спектра.
 tom1012 апр. 2013 г., 18:01
Очень интересно, спасибо. Я также нашел полезной страницу википедии о преобразовании константы-Q:en.wikipedia.org/wiki/Constant_Q_transform
 endolith12 апр. 2013 г., 16:34
 endolith14 июл. 2009 г., 15:54
Я предполагал, что это будет похоже на БПФ, но с ячейками в результате логарифмически разнесены. Анализатор спектра аудио, например, выиграл бы от этого, потому что он имел бы более высокое разрешение на низких частотах и более низкое разрешение на высоких частотах (www-uxsup.csx.cam.ac.uk/pub/doc/suse/suse9.0/userguide-9.0/…), а более высокая скорость вычислений позволит ему обновляться с гораздо большей скоростью или обеспечивает более высокое разрешение в целом.

Ответы на вопрос(3)

РЕДАКТИРОВАТЬ: После прочтения этого, я думаю, что этот алгоритм не очень полезен для этого вопроса, я все равно дам описание для других читателей.

Существует такжеthe Filon's algorithm способ, основанный на квадратуре Филона, который можно найти вNumerical Recipes это [кандидатская диссертация] [1]. Временная шкала логарифмическая, как и результирующая шкала частот.

Этот алгоритм используется для данных / функций, которые упали до 0 в наблюдаемом интервале времени (что, вероятно, не ваш случай), типичным простым примером будет экспоненциальный спад.

Если ваши данные отмечены точками (x_0, y_0), (x_1, y_1) ... (x_i, y_i) и вы хотите вычислить спектр A (f), где f - частота, скажем, f_min = 1 / x_max до f_max = 1 / x_min  журнал разнесен. Действительная часть для каждой частоты f затем рассчитывается по формуле:

A (f) = сумма из i = 0 ... i-1 {(y_i + 1 - y_i) / (x_i + 1 - x_i) * [cos (2 * pi * f * t_i + 1) - cos (2 * pi * f * t_i)] / ((2 * pi * f) ^ 2)}

Мнимая часть это:

A (f) = y_0 / (2 * pi * f) + сумма из i = 0 ... i-1 {(y_i + 1 - y_i) / (x_i + 1 - x_i) * [sin (2 * pi *) f * t_i + 1) - sin (2 * pi * f * t_i)] / ((2 * pi * f) ^ 2)}

[1] Блохович, Томас:Broadband Dielectric Spectroscopy in Neat and Binary Molecular Glass Formers. Университет Байройта, 2003, глава 3.2.3

Чтобы делать то, что вы хотите, вам нужно измерять разное время Windows, что означает, что более низкие частоты обновляются реже (обратно пропорционально степени 2).

Проверьте FPPO здесь: https://www.rationalacoustics.com/files/FFT_Fundamentals.pdf

Это означает, что более высокие частоты будут обновляться чаще, но вы всегда усредняете (скользящее среднее - это хорошо), но вы также можете позволить ему двигаться быстрее. Конечно, если вы планируете использовать обратное БПФ, вам это не нужно. Кроме того, чтобы иметь более высокую точность (меньшую полосу пропускания) на более низких частотах, это означает, что они должны обновляться гораздо медленнее, например, 16k Windows (1/3 м / с).

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

Я думаю, что ссылка, которую я предоставлю, прояснит некоторые ваши варианты ... 7 лет после того, как вы задали вопрос, к сожалению.

Решение Вопроса

Да. Да. Нет.

Это называется логарифмическим преобразованием Фурье. У него есть O (n) время. Однако это полезно для функций, которые медленно распадаются с увеличением области / абсциссы.

Возвращаясь к статье в википедии:

The main difference is that wavelets are localized in both time and frequency whereas the standard Fourier transform is only localized in frequency.

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

Узнайте больше о LFT наhttp://homepages.dias.ie/~ajones/publications/28.pdf

Вот тезисы:

«Мы представляем точное и аналитическое выражение для преобразования Фурье функции, которая была выбрана логарифмически. Процедура значительно более эффективна в вычислительном отношении, чем быстрое преобразование Фурье (БПФ) для преобразования функций или измеренных откликов, которые медленно затухают с увеличением значения абсциссы. Мы иллюстрируем предложенный метод на примере электромагнитной геофизики, где масштабирование часто таково, что следует применять наше логарифмическое преобразование Фурье (LFT). Для выбранного примера мы можем получить результаты, которые согласуются с результатами БПФ, с точностью до 0,5% за время, которое в 1,0е2 раза меньше. Потенциальные приложения нашего LFT в геофизике включают преобразование широкополосных электромагнитных частотных откликов в переходные, ледниковую нагрузку и разгрузку, проблемы подпитки водоносного горизонта, исследования нормального режима и приливов в сейсмологии и импульсное моделирование ударных волн. & quot;

 endolith13 июл. 2009 г., 20:09
Оооо, поэтому сигнал во временной области тоже должен быть логарифмически дискретизирован? (Имеется в виду, что сэмплы не одинаково разнесены во времени?

Ваш ответ на вопрос