[Exeland 0]

Необходимо сделать преобразование Фурье на несколько гармоник. Кто знает как можно это сделать более быстрее. Алгоритмы БПФ здесь не прокатывают потому, что они преобразуют N отсчетов в N гармоник. А мне необходимо получить из N отсчетов K гармоник, где K<<N. У кого какие предложения?

[V_G 8]

Берете формулу классического дискретного преобразования Фурье (не быстрого) и ограничиваетесь нужными базисными функциями. Но это НЕ ГАРМОНИКИ (так же, как и в случае БПФ), это параметры преобразования: постоянная составляющая, один период синуса за время выборки (НЕ первая гармоника), два периода и т.д.

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

[Палыч 6]

У кого какие предложения?

Алгоритм Гертцеля (Goertzel)

[Exeland 0]

Берете формулу классического дискретного преобразования Фурье (не быстрого) и ограничиваетесь нужными базисными функциями. Но это НЕ ГАРМОНИКИ (так же, как и в случае БПФ), это параметры преобразования: постоянная составляющая, один период синуса за время выборки (НЕ первая гармоника), два периода и т.д.

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

:) Так и делаю. Задал синус и косинус таблицей и кручу по отсчетам.

[eugen_pcad_ru 0]

Совместно с Палыч:

Алгоритм Герцеля!

[_Pirra 0]

Доброго времени суток.

 

У меня есть массив данных - амплитуда от перемещения (Ну воттакой вот самописец) мне надо определить волновые числа сигнала по этому массиву. (упрощённо, найти период). Приэтом нельзя использовать библиотеки.

 

Я так поняла, что надо применить к массиву преобразование Фурье, но какое? Ограничения в скорости обработки нет. И мне не доконца понятно, что будет результатом преобразования? Массив ампитуд от чего?

 

Заранее благодарна.

[Xenia 35]

Я так поняла, что надо применить к массиву преобразование Фурье, но какое? Ограничения в скорости обработки нет. И мне не доконца понятно, что будет результатом преобразования? Массив ампитуд от чего?

Это будет массив синусоид и косинусоид, укладывающихся ЦЕЛОЕ число раз на длине вашего массива.

 

Пусть для примера, ваш массив состоит из 16-и последовательных замеров (N=16), а потом вы сделали из него преобразование Фурье F[x].

Тогда в F[0] вы получите постоянную составляющую сигнала (она же средняя арифметическая). В F[1] получите амплитуду гармоники, период которой равен вашим 16-ти точкам. В F[2] - амплитуда гармоники, период которой укаладывается на этом отрезке дважды (период = 8 точек). В F[3] - трижды, и т.д. пока не дойдете до частоты N/2. Это, так называемая, частота Найквиста, выше которой не бывает :). А точнее сказать, более частые гармоники на нашем дискретном участке не представимы. Т.к. сама гармоника F[N/2] будет представлять собой чередующиеся +1 и -1, поскольку ей отпущено всего 2 точки на период.

 

На практике FT-алгоритм даст вам не амплитуду гармоники, а амплитуды sin- и cos-составляющих по отдельности. Амплитуду же гармоники вы может вычислить из них, как гипотенузу sqrt(sin^1+cos^2). Так получится уже спектр мощности, который скорее всего вам и нужен. Если ваша частота близка к одной из базисных частот Фурье-преобразования, то та амплитуда в частотном спектре будет торчать торчком :). А если промежуточная, то будут высокими две стоящие рядом палки.

 

Если вы будете использовать FFT (быстрое Фурье-преобразование) на числе точек, кратном степени числа 2, то там, в зависимости от применяемого алгоритма, могут случиться сложности с поиском того, где ваши частоты будут расположены в масиве после преобразования. Как правило, FFT-алгоритм строит спектр на том же месте, где раньше были данные. А бывает и так, что нужен еще один чистый массив под синусы. Тут уж надо разбираться с тем, какой алгоритм вам достался. Или испытать его на тестовых примерах, чтобы понять, что к чему.

 

Бывает и так, что для более плотной упаковки в F[0] кладется амплитуда частоты Найквиста F[N/2], поскольку она не имеет sin-части (sin-часть у нее всегда нулевая), а постоянную составляющую кладут к ней вместо sin-части. Бывает и противоположный порядок. Тогда можно уложиться на том же масиве в 16 точек, занимая первую половину под cos-, а второю под sin-составляющую:

F[0] - постоянка, F[1]...F[7] - косинусы, F[8] - частота Найквиста, F[9]...F[15] - синусы.

[_Pirra 0]

Может у кого есть простенький пример преобразования фурье?

я пробую использовать воттакой тестовый сигнал для проверки работы. cos(2*pi*i/T1)+cos(2*pi*i/T2); где T1 и T2 периоды.

 

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

 

Заранее благодарна.

[subver 0]

Зачем определять период преобразованием Фурье? Что мешает использовать автокорелляционную функцию, с помощью которой период определяется достаточно просто и точно?

[Xenia 35]

Может у кого есть простенький пример преобразования фурье?

я пробую использовать воттакой тестовый сигнал для проверки работы. cos(2*pi*i/T1)+cos(2*pi*i/T2); где T1 и T2 периоды.

Ладно, давайте разберем ваш случай. Использую язык MatLab, где уже есть встроенная функция fft() для быстрого преобразования Фурье.

 

Подготовим исходные данные:

T1 = 3;

T2 = 5; // выбираем конкретные периоды

N = 16; // выбираем длину числового массива

 

for i = 1:N // цикл по всем точкам массива

M(i) = cos(6.28*i/T1) + cos(6.28*i/T2); // заполняем массив по вашей формуле

end

 

Получаем в массиве вот это:

-0.1895 -1.3101 0.1899 -0.1897 0.4954 1.3126 -1.2999 -1.3193 1.3035 0.5092 -0.1944 0.1954 -1.3019 -0.2123 1.9998 -0.1665

 

Вычисляем частоты:

F1 = N/T1 = 16/3 = 5.3333

F2 = N/T2 = 16/5 = 3.2000

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

 

Сам расчет:

absfftM = abs( fft(M) ); // весь расчет в одной строке - сначала делаем fft(), а из него потом находим амплитуду гармоник, как абсолютную величину комплексного числа (корень квадратный из суммы его косинусной и синусной частей).

 

Получим такой результат:

0.1778 0.4203 1.1033 7.5016 1.8213 5.6483 4.3394 2.4653 2.1837 2.4653 4.3394 5.6483 1.8213 7.5016 1.1033 0.4203

 

Первое число соответствует F0 (постоянной составляющей), следующие за ней - амплитудам соответствующих гармоник F1 ... F8, а дальше зеркальное отражение, которое нам неинтересно. Т.е расшифровка будет такая:

0.1778 - постоянная составляющая (в идеале должна быть равна нулю, но остались дробные "хвостики", т.к. наши периоды оказались не кратны N)

0.4203 - амплитуда частоты 1

1.1033 - амплитуда частоты 2

7.5016 - амплитуда частоты 3 (высокая, в идеале должна иметь высоту 8)

1.8213 - амплитуда частоты 4

5.6483 - амплитуда частоты 5 (высокая, в идеале должна иметь высоту 8)

4.3394 - амплитуда частоты 6

2.4653 - амплитуда частоты 7

2.1837 - амплитуда частоты 8 (это частота Найквиста, дальше нее не смотрим)

 

Смотрим, какие частоты в нашем спектры превалируют. Таких частот две:

7.5016 - амплитуда частоты 3

5.6483 - амплитуда частоты 5

- они самые большие.

 

Убеждаемся, что наш алгорим "угадал" частоты

F2 = N/T2 = 16/5 = 3.2000

F1 = N/T1 = 16/3 = 5.3333

с той точностью, которую ему позволила дискретизиция. Если бы точек было не 16, а 128 или 256, то было бы на порядок точнее.

Из-за этих дробных частей соседняя амплитуда

4.3394 - амплитуда частоты 6

оказалась тоже высока, за счет того, что частота 5 оказалась чуть ниже нормы. Это только из-за того, что наши периоды не уложилсь нацело в массив длиной 16 (число 16 не делится без остатка на 3 и 5), но если бы поделилось нацело, но этого бы не случилось.

 

Так понятно?

[Alexashka 0]

Может у кого есть простенький пример преобразования фурье?

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

[TigerSHARC 0]

Если величина выборка небольшая, то можно и фурье влоб посчитать.

ПРосто быстрый алгоритм может быть избыточен в силу вычисления всего спектра целиком.

[Alexashka 0]

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

Тем более что при малом числе коэффициентов фурье дает очень плохое разрешение на низких частотах.

Да. еще тут не упоминалось о наложении окон, без нормального окна Вы не получите "верные" коэффициенты (мощности)

 

ЗЫ. Еще до кучи- можно почитать про банки цифровых фильтров и про ДПФ с расширенным весовым окном :)

Статейка

[_Pirra 0]

Всем большое спасибо. С БПФ разобралась.

 

А что за "автокорелляционная функция"? и как её применять для поиска периода?

[lisstret 0]

Всем большое спасибо. С БПФ разобралась.

 

А что за "автокорелляционная функция"? и как её применять для поиска периода?

 

То же что и корелляционная, только свертка сигнала со своей копией.