Господа! Может кто поможет с решением маленького вопроса?

"Известны быстрые методы вычисления ДПФ с прореживанием по времени и по частоте. Могут ли быть предложены другие методы? Дать аргументированный ответ."

Интересует все! Литература, ссылки в нете, описание.

Буду очень благодарен.

Блейхут Р. — Быстрые алгоритмы цифровой обработки сигналов
Там куча алгоритмов, не только с прореживанием по времени и по частоте.

Хотя, как обсуждали на телесистемах лет пять тому назад, алгоритмы актуальны если предполагать, что операция умножения намного "дороже", чем операция сложения. Сейчас же ситуация другая, так как всюду используются аппаратные умножители.
Было бы интересно узнать мнение специалистов по этому поводу. Насколько продвинулась техника в этом направлении?

Не совсем. Так как при увеличении размера задачи суммарное количество операций зависит сильнее от количества умножений, чем от количества сложений. Но сейчас, действительно, обычно проще в лоб.

В современных библиотеках FFT имеется несколько вариантов кода. Во время выполнения их скорость замеряется и выбирается тот вариант, который быстрее на данной системе. Большое значение имеет не только число умножений и сложений, но и эффективность использования кеш-памяти процессора.

Как вариант стохастическая дискретизация.
Если нужна будет литература по стохастической обработке сигнала обращайтесь.

Хм... может кто-то более подробно объяснит?

Так а что тут объяснять? У вас задача стоит слишком общо. Если вам нужна развертка всего спектра, то, да, здесь только БПФ. Сэкономить вы сможете разве что на пониженной разрядности входных данных (вплоть до 1-битных, как делается в АОНах), смерившись с пониженной точностью оценки спектра. А если вам нужен только участок спектра, или скажем оценка уровня ограниченного числа гармоник, то - методы типа "урезанного БПФ" (например, того же Гёрцеля), или методы "сверхразрешения" (типа АРСС, MUSIC, Монакова и т.д.). Саму операцию перемножения, на самом деле, можно тоже апроксимировать (см. Сколника "Справочник по радиолокации", т.1).

Короче, надо конкретизировать задачу, тогда и более конкретный ответ можно будет дать.

Пардон за оффтоп, Kluwert, не подскажите литературу по этим вопросам.

Извольте: во-первых, "классика жанра" - Марпл С.Л. "Цифровой спектральный анализ и его приложения". Шикарная книга, единственно, немножко уже отставшая от жизни. Ну а как вторую можно порекомендовать Ратынского "Адаптация и сверхразрешение в антенных решетках". Немного сумбурная книжка, но на русском, по-сути, и нету больше ничего толкового. Где-то еще видел неплохую обзорную статью на русском по методам сверхразрешения в журнале "Радиотехника", но напрочь потерял ее координаты.

А по лучшему из современных методов сверхразрешения - "методу моментов", или, он же "метод Монакова", можно прочитать, например, здесь: Монаков А.А., "Оценка алгебраических моментов спектра...", Успехи соврем. радиоэлектрон., №10, 2006.

Доброго времени суток.
У меня небольшой вопрс с трудом укладывающийся в тему...

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

Подскажите какими методами можно проанализировать короткий сигнал? (1-2 периода) Мерить сигнал дольше не могу. У меня рампределение амплитуды не от времени а от перемещения.
С Вейвлетам пока не разобралась.

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

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

Анализирую интерференцию поверхностной волны. О предсказуемости пока ничего сказать не могу.

Можно попробовать увеличить частоту дискретизации, чтобы разрешение поднять.
И побаловаться с разными окнами. Мне лично нравится Hann.

Частота дискретизации никоим образом не поднимет разрешение FFT. И весовые окна тоже.
Пробуйте параметрические методы, пробуйте использовать фазовый спектр для уточнения оценки частоты.

100% так. Если на РС, то лучше не выдумывать, а взять библиотеки Intel MKL или IPP - и получить скорость в 2-8 раз выше, чем при использовании самописного (хоть и на ассемблере) алгоритма. И эти MKL очень хорошо работают на самых разных конфигурациях. И кеш-память - тоже очень важная штука, если данные не влазят в кеш а постоянно подгребаются извне - скорость падает в разы.

Присоединяюсь к "методы "сверхразрешения" (типа АРСС, MUSIC, Монакова и т.д.)"
Действительно, можно понизить частоту дискретизации, взять, скажем, 64 точки из промежутка,
вычислить автокорреляцию
и по формуле, как у Марпла, найти спектр с нужным разрешением.