Есть задача посторить спектр от сигнала (комлексного) оцифрованного с частотой 10 МГц (длинна выборки - 4096-32768 отсчетов). Но от этого спектра нужно только +/- 10 кГц. Но эти 10 кГц нужно иметь с достаточно большим разрешением (нужно хотя-бы 512 дискретов в частотной области).

Эта задача легко решается с помощью неполного DFT, но уж больно долго считается.

Я если честно не очень понимаю алгоритмы БПФ. Скажите пожалуйста можно-ли как-то аналогично БПФ ускорить вычисление вышеизложенной задачи или нет? Может предложите что-то свое?

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

Спасибо.

Гораздо дешевле (во всех отношениях ) будет перенести на нулевую частоту, далее фильтрация - децимация, одним словом DDC (Digital Down Converter ), и после делаете ФФТ.

БПФ в Вашем случае поможет. ДПФ это 512*4096 условных отсчета, в БПФ это будет всего (4096/2)*log2(4096) - разность почти на 2 порядка. При этом на выходе в первом случае будет 512 отсчетов, а во втором - 4096. Никакой магии или потери информации здесь нет. Суть БПФ в том, что ядро преобразования (которая экспонента) циклично и одно его значение умножается на разные отсчеты. Остается лишь грамотно организовать процесс комбинирования.

Почитать о БПФ можно например здесь:
http://www.analog.spb.ru/

Но дело в том, что нужно получить эти 4096 отсчетов на первые 10 кГц. А в случае простого БПФ эти отсчеты получатся на весь сигнал и расстояние между ними будет 10e6/4096 ~ 2.4 кГц. то-есть в интересующий диапазон попадет всего 5-6 отсчетов.

Производить децимацию нежелательно, так как децимационные фильтры приведут к потере части информации, а ее в этом случае и так почти нет.

Делается это все для определения допплеровской частоты в очень плохом принятом сигнале.

Нашел ответ на свой вопрос: БПФ принципиально предназначено для вычисления всех значений в спектре.

Спектральное разрешение не зависит от способа анализа ( ДПФ или БПФ или регрессия или что ещё)

Оно зависит от длины блока данных по принципу неопределённости.

Поэтому всё, что можно сделать в рамках классического анализа - снести полосу в 0 и провести анализ спектра.



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

Например, здесь, но бывают и другие схемы
http://home.comcast.net/~kootsoop/EricJ2/index.htm
Здесь уже хорошо тем, что приведены матлабовские модельки


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

Я возможно не понимаю чего-то. Вот сейчас сделано так: пришедшая выборка (4096-32767 отсчетов) перемножается с синусами частот от -10 до 10 кГц с шагом 50 Гц (в комплексном виде) и результат суммируется. По сути это фильтрация. Получется набор чисел - зависимость амплитуды от частоты.

Вот этот процесс и нужно ускорить. Сейчас перекрытие между окнами - половина длинны окна (иначе долго счтиается). Нужно - как можно меньше.

Если только ускорить - считайте блочный БПФ

Скользящего БПФ не бывает. Усечённый БПФ бывает, но там выигрыш небольшой

Я так понял, что то что я считаю - это не БПФ вообще. Это просто расфильтровка по многим каналам.

Буду думать как это ускорить.

Про потерю информации не беспокойтесь. Если Вам нужно только 10 килогерц - то все частоты выше для Вас не несут никакой информации. Поэтому децимация может сильно помочь. Если её сделать грамотно - то в требуемом Вам диапазоне потери информации не будет.

Дискретное преобразование Фурье - это разложение по ортогональному базису. Его можно также сделать при помощи фильтрации. Но дольше.

Быстрое преобразование Фурье - это один из алгоритмов вычисления Преобразования Фурье, обеспечивающий экономию ресурсов за счет совсместной обработки. Его сложность - O(N*log(N)), для большинства случаев это очень хорошо. Более того, если нужно более чем порядка log(N) отсчетов с точностью до константы порядка 1 - оказывается быстрее вычислить все отсчеты при помощи БПФ, а потом выбрать нужные, чем вычислять частоты по одной. Ускорить можно через децимацию с выкидыванием лишних отсчетов.

Сначала необходимо задаться интересующей нижней (fn) и верхней частотой(fb), затем правильно выбрать частоту дискретизации(fd) она должна быть как минимум в два раза больше fb и правильно
выбрать колличество необходимых отсчетов в окне.
А разрешение по частоте (delF) определяем по формуле delF=1/Тс где Тс=N*delT (N -колличество необходимых отсчетов в окне, delT=1/fd).Это все следует из теоремы Котельникова.
Подобные задачи лучше всего решать при помощи БПФ .

Интересно, почему же будет потеря информации при децимации? Если все правильно сделано никакой потери не должно быть!


А вообще похоже Вас спасет обычный CIC фильтр первого порядка. Памяти только потребует это дополнительно..

Шаг (разрешение) определяется длиной (по времени) вашего окна, по любому БПФ даст Вам все что можно вытянуть из выборки. Нужно лучшее разрешение - делайте более длинную выборку (по времени!), в конечном итоге частоту отсчетов можно существенно снизить, зачем 10М если интересует 10к. Децимация актуальна для устранения шумов - нужна ли она Вам?

Может я неправильно понял вопрос, но ежели нужно увеличенное разрешение в части спектра - можно подумать насчет алгоритмов zoom FFT , либо chirp z-transform (последний вычисляет по точкам не обязательно равномерно расположенным по unity circle).
Реального опыта с ними не имею, только теория. Хотя кажется в целом идея zoom FFT была упомянута выше в ветке (сдвиг нужной части спектра в baseband с последующей десимацией и затем его анализ обычным FFT с необходимым кол-вом точек для нужной резолюции по нужной ширине спектра).
Chirp-Z transform позволяет делать FFT высокой резолюции в заранее определенной части спектра.

Для получения промежуточных отсчетов в спектре при помощи БПФ необходимо сигнал дополнить нулями.

Спасибо всем. Помоделировал - действительно CIC фильтр в сочетании с корректирующим КИХ-фильтром дают хороший результат.

Надеюсь, что Вам поможет http://www.exstrom.com/journal/sigproc/specmag.pdf.
Статья с С кодом: "A C program for spectrum magnification: When an FFT is not enough". Обещают эффективность, гораздо лучшую, чем вставление нулей.