fft/ifft для последовательности длиной 768 (=512+256) Опции

[PriBoris]

Какой эффективный алгоритм для длин такого типа (2^n+2^(n-1)) выбрать ?
Вопрос возник при попытке реализации фильтрации с помощью быстрой линейной свёртки. Длина фильтра почти 256 точек, данные поступают в реальном времени блоками по 512.

Сообщение отредактировал PriBoris - Jul 27 2010, 08:49

[связист]

Какой эффективный алгоритм для длин такого типа (2^n+2^(n-1)) выбрать ?
Вопрос возник при попытке реализации фильтрации с помощью быстрой линейной свёртки. Длина фильтра почти 256 точек, данные поступают в реальном времени блоками по 512.

Не совсем понятно что Вы делаете?
Насколько я смог понять (а если я понял не правильно, то поправьте меня), Вы пытаетесь отфильтровать сигнал переведя его в частотную область при помощи БПФ и после фильтрации переведя сигнал из частотной области обратно во временную при помощи обратного БПФ. Для этого Вам необходимо сделать БПФ длиной 768 точек.

Про эффективные алгоритмы лучше всего посмотреть книжку Блейхута "Быстрые алгоритмы цифровой обработки сигналов".
Алгоритм Кули-Тьюки наверное подойдёт для Вашей задачи. Получится табличка 3*256 точек. 3-точечные БПФ делаем по плгоритму Винограда, а 256-точечное БПФ делаем бабочками (Кули-Тьюки по основанию 2).
Или алгоритм Гуда-Томаса тоже подойдёт, но его понять сложнее, поэтому разбираться надо дольше. Там тоже получится табличка 3*256 точек.

[PriBoris]

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

Спасибо,с алгоритмом Кули-Тьюки разобрался. В матлабе прокрутил вариант 3*256, всё сходится.

Почти это как? 255.5?

Нет,имелось ввиду,что длина фильтра после различных доработок надфилем получается в районе 210...230.
256 - это я взял с запасом на будущее,округлив до ближайшего красивого (для хранения и использования) числа

делайте по 2-а FFT по 256 точек...
или одно по 512 на блок...
Физический смысл быстрой свертки в том, что у Вашего фильтра есть определенные АЧХ/ФЧХ(которое однозначно связано с его "импульсной"). Мы определяем его и накладываем операцией умножения(свертка-фильтрация над временным рядом соответствует умножению в частотном отображении) на частотный спектр сигнала. Размер блока может быть любым - впринципе, даже меньше длинны фильтра - но тогда его нужно будет пересемплировать с другой частотой Ничего из уже обработанного блока хранить не надо. Это не FIR. А все ускорение за счет того, что переход в частотную область с помощью FFT, посемпловое умножение, и обратный переход уже где-то начиная с 128 точек требует меньше операций чем свертка "в лоб".

Обясните пожалуйста, я не понимаю что я по Вашему мнению планирую делать не так.
Мне нужно реализовать FIR длиной 256, который я собственно реализовал в лоб. Получается затратно по ресурсам.
Я планирую сделать так:
Пришел новый набор данных из 512 точек.
Я создаю буффер их 768 точек, в него в позиции с 1 по 256 я копирую последние 256 точек из предыдущего набора данных, а в позиции с 257 по 768 я копирую свежие 512.
Делаю fft длиной 768.
Домножаю результат на АЧХ/ФЧХ моего фильтра, дополненного нулями до длины 768.
Полученное произведение пропускаю через ifft.
Точки с с 1 по 256 выкидываю, а точки с 257 по 768 считаю результатом фильтрации свежего блока данных.

Лучше делать два таких прохода на блок, но по 512 точек ?
Или один проход, но избыточный, на 1024 точек, чтобы не заморачиваться с Кули-Тьюки (в котором я возможно потреряю много времени на накладных расходах при переиндексации и т.д.)?