Быстрое преобразование Фурье не для степени 2, как довести число отсчетов до стпени двойки Опции

[Sergey Makarov]

Добрый день!
Стоит задача осуществить быстрое преобразовние Фурье для 500 отсчетов. Аппаратно DSP поддерживает быстрое преобразование по модулю 2. Вопрос, как довести кол-во точек до 512? Достаточно ли заполнить недостающие значения нулями? Сильно ли исказится результат преобразования после такого допущения? Если можно ссылкой на математическое обоснование поделитесь плз. Или все таки придется до 512 точек дополнять интерполировав существующие значения? Кто чем может помогите плз.

[Alexey Lukin]

Ничего не искажается! Наоборот, становится видно больше правильных деталей. А спектры некоторых сигналов (например, ядер фильтров) без дополнения их нулями перед ДПФ вообще некорректно рассматривать.

[GetSmart]

Ничего не искажается! Наоборот, становится видно больше правильных деталей. А спектры некоторых сигналов (например, ядер фильтров) без дополнения их нулями перед ДПФ вообще некорректно рассматривать.

Оставим в покое ядра фильтров.
Но по поводу "становится видно больше правильных деталей" очень любопытно.

ДПФ/БПФ всего лишь свёртка с синусом aka интеграл. Ну а если мы зануляем часть функции, то с чего бы это результат интеграла функции не изменится? В ДПФ/БПФ в конце идёт нормировка результата и она расчитана на 2^n, допустим 512 точек. Синус исходника был на интервале 500 точек. Значит ошибка нормировки 500/512 = 0,97656. Иногда это неважно, иногда очень важно. А уж если кто-то пожелает в разы увеличивать блок нулями в своих корыстных целях, то вообще мама не горюй.

Но это вообще-то пока ещё мелкий недостаток, который легко перенормируется. Гораздо серьёзней, когда блоки дополняются нулями и из них выцепляются низшие гармоники. Тут уже идут значительные фазовые искажения в дополнение к амплитудным. На 1-2-3 гармониках блока, хотя в зависимости от желаемой точности и на 10-20 (грубо говоря).

Оконные функции само собой сильно улучшают ситуацию тем, что они львиную долю информации берут из центра блока, а нули дополняются по краю/краям.

Для сингулярных спектров типа синусов (ширина спектра меньше бина) ДПФ в чистом виде (без спектральных окон) не является вообще адекватным инструментом анализа. Результат будет полностью зависить от того куда палка легла по отношению к бину ДПФ (не даст соврать гурукилер)

Гурукиллер Вас всегда поправит
А вообще, что за дискриминация спектров? Все спектры имеют право встречаться в жизненных ситуациях.
Вот пример глюков "Что такое эффект размазывания"
http://psi-logic.narod.ru/fft/fft9.htm

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

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

Upd.
Хотя есть ещё третий вариант непрерывного спектра "в жизненных ситуациях". Когда разные сигналы накладываются друг на друга. Даже если один из них является идеальным с прерывным спектром, то другие могут быть с непрерывным. В данном случае переоцифровка (в пределе) сигнала ситуацию не разрулит, т.к. предел ограничен "вредным" сигналом. Эта ситуация вообще чаще всего бывает. Идеальный ЦОС-овик понимая все нюансы всех этапов прохождения своего сигнала будет просто приближаться к мат.пределу точности при правильном использовании инструментов. Правильно понимая достоверность результата при этом.

Upd2
Я бы с удовольствием замутил разговор страниц на 50 на эту тему. Только съезжу в отпуск на Бора-Бора

Сообщение отредактировал GetSmart - Sep 16 2011, 23:16

[Alexey Lukin]

ДПФ/БПФ всего лишь свёртка с синусом aka интеграл.

ДПФ это не свёртка. ДПФ это умножение сигнала на матрицу, которая свёрткой не является.

Ну а если мы зануляем часть функции, то с чего бы это результат интеграла функции не изменится?

Дополнение сигнала нулями — это отнюдь не зануление части сигнала. Представьте, что у вас есть сигнал длины 512 точек и его копия, дополненная нулями до 1024 точек. ДПФ от второго сигнала будет совпадать с ДПФ от первого на сетке частот первого ДПФ. В этом смысле спектр не искажается. Но у второго ДПФ будет информация о сигнале на промежуточных частотах — результаты скалярных произведений с промежуточными частотами. Именно это я и называю полезными деталями. В случае, например, синусоидального сигнала эти промежуточные частотные отсчёты позволят вам более точно узнать частоту сигнала. А в случае фильтра — получить его АЧХ (которая, как известно, является непрерывной функцией частоты) в промежуточных точках по частоте, найти нули АЧХ и т.п.

В ДПФ/БПФ в конце идёт нормировка результата и она расчитана на 2^n, допустим 512 точек. Синус исходника был на интервале 500 точек.

Если дополнение нулями не кратное, то полученный спектр будет дискретной выборкой из непрерывного спектра исследуемого отрезка сигнала. Это может быть плохо или хорошо, в зависимости от задач. Чаще всего это хорошо, по тем же причинам, которые описаны выше: частотное разрешение анализа получается выше.

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

Что-то не понял мысли...

ИМХО, непрерывный спектр существует только у частотно-модулированных сигналов или недооцифрованных.

И этой тоже...

[GetSmart]

ДПФ это не свёртка. ДПФ это умножение сигнала на матрицу, которая свёрткой не является.

ДПФ это свёртка с синусом и косинусом. И интеграл само собой.

Дополнение сигнала нулями — это отнюдь не зануление части сигнала. Представьте...

Я не писал зануление части сигнала. Не надо меня искажать. Если функция ФФТ юзает 512 точек, из которых 500 присутствуют, остальные нулевые, то это есть зануление части функции. Равноценно тому, что было получено 512 действительных точек, а потом 12 было занулено. Эквивалентно потери части информации в функции 512 точек. Однако львиная доля информации ещё осталось. Результат, относительно случая с полным набором точек будет искажён. Насколько велики искажения - (0.01%...ХХ%) зависит от многих нюансов. Часть я описал.

Если что-то непоняли, бывает. Это неудивительно, т.к. в книжках многое не пишут чтобы не перегружать читателя и/или не вызывать у читателя какие-то сомнения. Но если понимаете "физику процесса", то сразу понимаете море подводных камней, причём там, где никто никаких сомнений в книжках не высказывал.

Сообщение отредактировал GetSmart - Sep 17 2011, 08:55