Цитата(PriBoris @ Jul 27 2010, 12:33)
Какой эффективный алгоритм для длин такого типа (2^n+2^(n-1)) выбрать ?
Вопрос возник при попытке реализации фильтрации с помощью быстрой линейной свёртки. Длина фильтра почти 256 точек, данные поступают в реальном времени блоками по 512.
Не совсем понятно что Вы делаете?
Насколько я смог понять (а если я понял не правильно, то поправьте меня), Вы пытаетесь отфильтровать сигнал переведя его в частотную область при помощи БПФ и после фильтрации переведя сигнал из частотной области обратно во временную при помощи обратного БПФ. Для этого Вам необходимо сделать БПФ длиной 768 точек.
Про эффективные алгоритмы лучше всего посмотреть книжку Блейхута "Быстрые алгоритмы цифровой обработки сигналов".
Алгоритм Кули-Тьюки наверное подойдёт для Вашей задачи. Получится табличка 3*256 точек. 3-точечные БПФ делаем по плгоритму Винограда, а 256-точечное БПФ делаем бабочками (Кули-Тьюки по основанию 2).
Или алгоритм Гуда-Томаса тоже подойдёт, но его понять сложнее, поэтому разбираться надо дольше. Там тоже получится табличка 3*256 точек.
fft/ifft для последовательности длиной 768 (=512+256)
Jul 27 2010, 08:33
