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

[PriBoris]

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

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

[bahurin]

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

если надо поставить фильтр, например ФНЧ, то быстрее всего это БИХ - фильтр рассчитать и использовать. В этом случае выши 256 точек сведутся к БИХ фильтру порядка не больше 10.

Если же очень хочется ких фильтр, то тогда 512 точек сигнала переводите в спектр и потом уже спектр умножаете на частотную характеристику фильтра, и переводите через ifft. Как-то я не нашел в вашем вопросе 738 точек, поскольку:

данные поступают в реальном времени блоками по 512.

Сообщение отредактировал bahurin - Jul 27 2010, 10:07

[Xenia]

Кажется Вы пытаетесь сказать новое слово в цифровой обработке сигналов...

Попытка не пытка! Тогда уж я еще одно новое слово скажу
В чем, собственно, недостаток FFT в практическом смысле? В прежде всего в его циклическом характере. FFT преобразует массив так, как будто он закольцован, хотя на самом деле этого нет.
Вот практический тому пример. Положим, мы преобразуем массив данных, полученных от АЦП. Причем измеренный сигнал имеет некий линейный тренд, выражающийся в том, что уровень сигнала в первой точке массива не совпадает с уровнем в конечной (например, база сигнала постоянно повышается со временем). Такое поведение входного сигнала довольно обычно и называется дрейфом.
Однако FFT-алгоритм нам на зло станет рассматривать этот массив, как свернутый в кольцо, а потому усмотрит в нем чудовичный разрыв непрерывности в том месте, где происходит склейка в кольцо. Из этого "уступа" в частотном образе сигнала появятся большие вклады не только высокочастностных составляющих, но и низкочастотных. И все лишь для того, чтобы этот уступ воспроизвести. Можно, конечно, окнами с ними бороться - это традиционный путь. А вот я "изобрела" совсем простой путь, но исключительно эффективнный. Он состоит в том, что надо дополнить массив (примерно в два раза до следующего размера, кратного степени числа 2), но только не нулями! Вместо нулей следует в этом месте провести НАКЛОННУЮ ПРЯМУЮ ЛИНИЮ, которая одним свои концом исходит из последней точки исходных данных, а другим концом должна дойти до конца рассширенного массива именно на тот уровнь, соотвествующий первой точке исходных данных. Тогда при склейке в кольцо окажется, что переход получился максимально плавным.
Такой метод практически не дает паразитных вкладов в частотный спектр, возникающих из-за перепада уровней на концах массива данных, а потому и не нуждается ни в каких окнах или дополнительных фильтрах.