Форум разработчиков электроники ELECTRONIX.ru > Быстрое преобразование Фурье не для степени 2

Alexey Lukin

Oct 21 2011, 16:40

Цитата(GetSmart @ Oct 21 2011, 16:45)

Но тогда комбинация этих двух предложений в цитате с союзом "но" как бы "притянута за уши"

Союз "но" означает, что отношение с/ш в бинах будет лучше при большом размере ДПФ, т.к. увеличение одинаковое, а стартовые условия разные.

GetSmart

Oct 22 2011, 15:49

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

fontp

Oct 24 2011, 08:49

QUOTE (GetSmart @ Oct 22 2011, 19:49)

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

Усечённые алгоритмы БПФ? Есть такие.
Только эффективность оных очень медленно возрастает при увеличении кол-ва нулей.
При кол-ве нулей равном кол-ву выборок эффект вряд ли достигнет 25%. Конечно,
если кол-во нулей в 16 раз больше кол-ва выборок то имеет смысл использовать усечённые алгоритмы.
В принципе принцип этих алгоритмов простой - рисуется граф БПФ и отсекаются заведомо нулевые ветки.
Как алгоритмы, пригодные для программирования описывались , например, в книгах Ярославского по обработке изображений

Alexey Lukin

Oct 27 2011, 06:55

Если алгоритм FFT хорошо оптимизирован, то даже выгоды в 25% не будет. Какая-либо выгода начнётся только тогда, когда число нулей перевалит за 90%.

almost

Oct 27 2011, 11:33

Цитата(GetSmart @ Oct 19 2011, 19:48)

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

А вот с интерполяцией FFT хотелось бы найти где-нить теоретическое обоснование того, что в основных бинах FFT содержится так же информация о дробных частотах, по которым их можно интерполировать. Не какой-то набор статистики результатов. Я пока хочу использовать этот метод, но опасаюсь, что может оказаться, что интерполированные значения не всегда достоверны. И например скачут от начальной фазы этой дробной частоты. С другой стороны, синк-интерполяция означает, что эти промежуточные значения "размазаны" по всему спектру FFT. А не по 2-4 соседним точкам.

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

GetSmart

Oct 27 2011, 21:12

Цитата(almost @ Oct 27 2011, 16:33)

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

Я решил применить для ЧМ демодулятора. Из одного бина ДПФ несколько, я бы так не сказал. ИМХО из какого-то кривого спектра получаются промежуточные бины. Вцелом, спектр дополненный нулями - кривой до безобразия. Но вот пик на спектре как ни странно - достоверный.
И для демодулятора мне нужно разрешение лучше простого ДПФ по кол-ву бинов, то бишь надо видеть много некратных частот. И причём чтобы результат для них не был "ущербным" по отношению к кратным частотам.

По поводу статистического результата (метода?) дополнения нулями, не понял.
Если это о том, что меня устроит статистический результат, то это всё из-за больших шумов. Большие шумы любой метод делают статистическим. А без шумов дополнение нулями даёт всегда результат пика валидный.

almost

Oct 28 2011, 05:39

Цитата(GetSmart @ Oct 28 2011, 01:12)

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

А почему кривой? Ведь, насколько я себе представляю, если дополнить, к примеру, 50 процентов нулей к входной последовательности и сравнить с результатом без нулей то получившей спектр с нулями будет иметь полностью совпадающие 50 процентов спектральных "палок", а остальные "палки" будут располагаться между ними и по значению будут равны среднему от соседних значений. Я нигде не ошибаюсь?
Ещё припоминаю такое понятие как боковые лепестки каждой гармоники. Каждая палка имеет форму sinx/x и чтобы боковые лепестки не заходили на соседние гармоники их разносят при помощи дополнения нулями входной последовательности.
Помогите разгрести кашу в моей голове =)

Цитата(GetSmart @ Oct 28 2011, 01:12)

По поводу статистического результата (метода?) дополнения нулями, не понял.
Если это о том, что меня устроит статистический результат, то это всё из-за больших шумов. Большие шумы любой метод делают статистическим. А без шумов дополнение нулями даёт всегда результат пика валидный.

Неправильно выразился по поводу статистического метода в отношении дополнения нулями.

GetSmart

Oct 28 2011, 06:15

Цитата(almost @ Oct 28 2011, 10:39)

А почему кривой? Ведь, насколько я себе представляю, если дополнить, к примеру, 50 процентов нулей к входной последовательности и сравнить с результатом без нулей то получившей спектр с нулями будет иметь полностью совпадающие 50 процентов спектральных "палок", а остальные "палки" будут располагаться между ними и по значению будут равны среднему от соседних значений. Я нигде не ошибаюсь?

Если бы это было так, то мне бы этот метод вообще не пригодился.
50% "палок" будет совпадать, если их перенормировать. Но промежуточные не будут строго между ними по уровню. Вообще, там ещё фаза есть. Но фазу я не копал.
Справедливости ради, исходный БПФ, недополненный нулями тоже имеет кривой спектр при прямоугольном окне и сигналах некратных периодов. В нём уже энергия мощных некратных синусоид размазывается по всем бинам вокруг основной "палки". И именно это размазывание позволяет точно интерполировать промежуточные значения между бинами.
То есть как я и говорил раньше, спектры слабых сигналов (на фоне сильных) уже будут недостоверные. А достоверный (относительно) будет только самый мощный сигнал, то бишь пик. С окнами с одной стороны картина будет лучше, с другой стороны хуже.

Alexey Lukin

Oct 28 2011, 06:43

Цитата(almost @ Oct 28 2011, 09:39)

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

Правильно, только не среднему, а sinc-интерполированным значениям, т.е. тем самым боковым лепесткам.