Допустим нужно нам получить спектр сигнала и допустим нужно сделать для этого именно N-точечное БПФ. Однако у нас есть выборка сигнала длинной kN, где k - целое число > 1. Тут имеется три варианта:
1) Взять любые подряд идущие N-точек из выборки и посчитать на них БПФ, но так мы теряем полезный сигнал, который можно было бы использовать.
2) Сделать k раз БПФ и результат усреднить. Вроде бы хорошо, но долго.
3) Каким-то образом усреднить выборку до N-точек и сосчитать один раз БПФ.

Собственно по 3-му пункту мне достался какой-то код, который не до конца понятно что делает. В чем я успел разобраться так это в том, что он умножает всю выборку на окно Кайзера длинной kN, затем ещё на какое-то окно, а затем хитрым образом складывает отсчеты сигнала. А именно так, если s - это исходная выборка умноженная на окна, а a - выборка, которая подается на БПФ, то:
a_0 = s_0 + s_N + s_{2*N} + ... + s_{(k-1)*N}
a_1 = s_1 + s_{N+1} + s_{2*N+} + ... + s_{(k-1)*N+1}
...
a_{N-1} = s_{N-1} + s_{2*N-1} + ... + s_{k*N - 1}

Собственно, кто-нить пояснит что здесь за математика такая? Как это работает и что здесь делается.

Читайте про банки фильтров. а_0...a_{N-1} - это выходы полифазного фильтра. Каждый подканал на выходе БПФ имеет импульсную характеристику s_0...s_{k*N - 1}, таким образом можно получить например АЧХ подканала близкую к прямоугольной с большим подавлением остальных подканалов, а не типа sinx/x как у просто БПФ.

А можно по подробнее???

Up

Над s выполняется БПФ размера kn, находится только каждая k-ая частота. Посмотрите на граф БПФ с прореживанием по частоте. Если выкинуть не нужные вычисления то от бабочек на первых этапах как раз останется написанная вами сумма.

Это называется полифазное БПФ (polyphase FFT). Читай что не ясно спрашивай.

Это не недостаток, если разработчик выбрал такой фильтр что АЧХ соседних поднесущих не перекрываются и соответственно есть гармоники которые ни в один из фильтров не попадают то это недостаток разработчика а не быстрого алгоритма.



При правильном выборе фильтра есть обратное преобразование, и сигнал проходя через прямое-обратное преобразование не претерпевает никаких изменений кроме задержки, это называется perfect reconstruction.

Есть предложение получить суммы (или среднее) для каждой пачки из k последовательных значений (таких сумм получится ровно N), а затем получить их БФП, однократно применяя процедуру FFT. По идее должен получиться усредненный спектр.

Все таки это недостаток, так как алгоритм перестает быть универсальным и заставляет пользователя предварительно исследовать окна на предмет потерь гармоник сигнала. Кроме того из приведенных примеров явно следует, что уменьшается амплитуда гармоники при различных сглаживающих окнах.

Может быть в частных случаях это и возможно, но в общем случае это не реально, как бы вы не выбирали окно. Если было 4096 точек и вы смогли бы представить сигнал безошибочно всего 1024 точками спектра, то почему бы вам не взять 1024 точки спектра используя тот же алгоритм не представить этот спектр скажем 128 точками и т.д. все это было бы можно свернуть в одно число!!! Поэтому при использовании полифазного БПФ можно говорить лишь о приближенном представлении. Разумеется в некоторых частных случаях можно произвести и безошибочное восстановление, я не отрицаю, можно придумать много таких примеров, но я говорю об общем случае, когда нет никакой априорной информации о сигнале, кроме того что известно, что частота дискретизации выбрана по теореме отсчетов.


ТАК НЕЛЬЗЯ: возьмем сигнал 1 1 -1 -1 -1 -1 1 1 поделим на два сумма первых четырех отсчетов равна сумме вторых четырех и равна 0! Если исходный сигнал есть стационарный процесс с нулевым средним то такое усреднение во времени ни к чему хорошему точно не приведет!

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





Perfect reconstruction банки фильтров для любых сигналов работают и не надо никакой априорной информации. Гипотетический Perfect reconstruction банк фильтров имеет 1024 FIR фильтра на 1024*4=4096 коэффициентов каждый, на выходе каждого фильтра сигнал прорежен в 1024 раза, входной блок в 4096 отсчётов на выходе будет представлен 4-мя блоками по 1024 отсчёта по которым может идеально точно восстановлен.

Так можно, поскольку в названии темы автор пишет "когда выборка больше, чем требуемое разрешение". Т.е. ему требуется разрешение, меньшее чем то, которое можно получить по полной выборке, а стало быть он сознательно желает урезать и частоту Найквиста, выше которой спектр не просматривается.
В вашем примере "1 1 -1 -1 -1 -1 1 1" вы выбрали k=4 ("сумма первых четырех отсчетов"), а следовательно и "требуемое разрешение" у вас выбрано в 4 раза меньше возможного. А при таком разрешении тонкая структура внутри четверки и не должна выявляться.
Если же требуется максимально возможное разрешение, то надо дополнять последовательность нулями до ближайшей степени двойки, а потом применить к ней FFT. Тогда всё будет видно. Однако такое решение противоречит желанию автора темы иметь разрешение меньшее, чем позволяет выборка.

Абсолютно правильно если есть 4096 отсчетов на входе и 4096 отсчетов на выходе. Полифазное же БПФ берет 4096 отсчетов и делает из них всего 1024 спектральных отсчета (как бы из 4 фильтров берет всего один). В этом случае безошибочного восстановления не получится!



Читайте внимательно статью про полифазное БПФ. Там написано, что имея 4096 отсчетов можно получить спектр используя 1024-точечное БПФ с разрешением ЛУЧШИМ нежили использовать 1024-точечное БПФ для сигнала 1024 отсчетов. Это то что хочет автор, отсчетов сигнала в 4 раза больше чем отсчетов спектра. То что вы предлагаете это неправильно. Если вы возьмете стационарный процесс с нулевым среднем, то при усреденении внутри интервала всегда будет 0 и получите что сигнал после вашей обработки равен 0 и спектр будет равен нулю! Возьмите сигнал одну синусоиду с частотой 0.125 Гц продискретизируйте с частотой 1 Гц и уменьшите количество отсчетов в 8 раз путем усреднения по 8 отсчетам и вы увидите, что при усреденении вы всегда берете один целый период синусоиды и получаете сумму равную нулю! Я не знаю как вам еще это объяснить? Могу пример дать скажем из матлаба.

А причём тут частота Найквиста? Нужно к примеру только из 16384 числа выборок получить 256 частот спектра всех этих выборок. С наименьшими затратами по времени и ресурсам в принципи не столь актуально главное с нулевыми искажениями.

что значит с нулевыми искажениями? Если у вас 16384 отсчета то возьмите БПФ от этого сигнала и получите 16384 отсчета которые и есть БЕЗ ИСКАЖЕНИЙ. По ним вы сможете используя обратное преобразование снова получить 16384 отсчета сигнала. Если вы каким либо способом из 16384 отсчетов спектра возьмете всего 256 отсчетов спектра, то вы НИКОГДА не восстановите 16384 отсчетов сигнала по 256 отсчетам спектра без ошибок. Одним из способов взять из 16384 всего 256 отсчетов это выдернуть каждый 64 отсчет (это и есть полифазное БПФ) только предварительно надо произвести оконное сглаживание чтобы при прореживании не потерять спектральные составляющие.

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

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

под разрешением понимается визуальное представление, расстояние между пинами действительно одно и тоже. Насчет шума согласен. Обычное БПФ в последнем примере не потеряло гармонику. 2 гармоники слились в одну, а полифазное БПФ позволило их различить