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), но только не нулями! Вместо нулей следует в этом месте провести НАКЛОННУЮ ПРЯМУЮ ЛИНИЮ, которая одним свои концом исходит из последней точки исходных данных, а другим концом должна дойти до конца рассширенного массива именно на тот уровнь, соотвествующий первой точке исходных данных. Тогда при склейке в кольцо окажется, что переход получился максимально плавным.
Такой метод практически не дает паразитных вкладов в частотный спектр, возникающих из-за перепада уровней на концах массива данных, а потому и не нуждается ни в каких окнах или дополнительных фильтрах.

[DRUID3]

Попытка не пытка! Тогда уж я еще одно новое слово скажу
В чем, собственно, недостаток FFT в практическом смысле? В прежде всего в его циклическом характере базисных функций и самого способа построения ортонормированного базиса. FFT преобразует массив так, как будто он закольцован, хотя на самом деле этого нет. - не так FFT, как то, что мы делаем всю математику подразумевая sin(t)/cos(t) - а они бесконечные циклические функции.

Т.е. проблему решит не какое-то дополнение нулями - ну же, Xenia, у меня блок где замерян постоянный ток. 11111...111 (V) - как его не дополняй - спектр станет заметно отличным от простой палки на 0-ой частоте... Или вон пример который привел товарищ bahurin - тоже очевиден для мыслеэксперимента.
Проблему решит:
1) Выбор других базисных функций и метода построения базиса.
2) Выбор "иного" математического мира - и так между прочим тоже делают...

Остальное прочел... Здорово. Но это частные случаи.

P.S.: был задан конкретный вопрос и товарищ связист дал на него самый компетентный ответ - смысле на самый первый вопрос(уточнение аФФтАр топика дал просто чумовое ). Дальше понеслось - и дополнение 0-ми, и IIR... Сейчас пойдут теоретико-числовые алгоритмы и кольца Галуа...

P.P.S.: Xenia, перепишите DCT(FCT) для своего mp3 плеера или JPEG просмотрщика - так "грамотно". С "не кольцевой" сверткой. Послушайте(посмотрите) его минут 10. А выводы опубликуйте на форуме...

P.P.P.S.:

Для вычисления фильтрованного значения первой точки свежего блока используются 255 (256-1) точек предыдущего блока.

Мда... Это диагноз... PriBoris, без обид, но Вы жжоте...

Вопрос возник при попытке реализации фильтрации с помощью быстрой линейной свёртки. Длина фильтра почти 256 точек, данные поступают в реальном времени блоками по 512.

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

делайте по 2-а FFT по 256 точек...
или одно по 512 на блок...

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

Кстати блоки по 256 точек, 32-х битная система и тип данных int(если у Вас, PriBoris, так) - это и в самом деле лучше на кольцах Галуа. Зачем нам комплексность и округленные значения sin(t)/cos(t) !?

В чем вопрос?

[Xenia]

P.P.S.: Xenia, перепишите DCT(FCT) для своего mp3 плеера или JPEG просмотрщика - так "грамотно". С "не кольцевой" сверткой. Послушайте(посмотрите) его минут 10. А выводы опубликуйте на форуме...

Ваше требование некорректно . В вашем примере FFT применяется для сжатия сигнала (к более компактной форме представления/хранения), а потому о концевых эффектах там просто нет речи - важно лишь, чтобы обратное FFT воспроизводило исходный сигнал достаточно хорошо.
Здесь мы имеем тот эффект, что последовательное применение FFT и iFFT (если ничего не обрезать в промежуточном частном образе) тождественно воспроизведет (дискретный) оригинал. И это несмотря на любые краевые эффекты.
Но если нам нужно частотное представление само по себе, например, для гармонического анализа анализа или получения свертки, то с "краевыми эффектами" мириться нельзя. Ибо разрыв (ступенька между уровнями) на краях массива порождает при FFT дополнительные частоты, которые на самом деле во входном сигнале отсутствуют. И в этом можно легко убедиться, если использовать обычный метод FT (не Fast).
В принципе можно с определенностью сказать следующее: все три метода (зацикливание, дополнение нулями и дополнение линейным трендом) грешат против истины. В самом деле, при вычислении сверки прямым способом в конце массива создается ситуация, когда в результате относительного сдвига двух сворачиваемых функций приводит к неопределенной ситуации - первая функция "кончилась", выйдя за область, где мы знаем ее значения, а вторая функция еще нет. Если в этой ситуации мы решаем довольствоваться частичной суммой произведений, то это будет эквивалент заполнения недостающей части нулями. А если же решим, что "закончившаяся" функция периодична и решаем скопировать недостающие точки из ее начала - это то, что делает FFT. А мой "трегольник" - это попытка обмануть FFT, подсунув ей данные, на которых принудительная "циклизация", которую делает FFT, приносит наименьший вред (в случаях, когда периодичность исходной функции заведомо отсутствует).
Величина этого вреда может колебаться в широких пределах, в зависимости от того, насколько совпадают все эти три предположения (о дальнейшних значениях функции) с реальностью. В случае, если исходный сигнал - чистая гармоника, да еще и уложившаяся в интервал целым числом периодов, то, конечно же, FFT тут победит, т.к. ее "преположение" о перирдическом характере сигнала полностью оправдалось. Да вот только не бывает на практике таких удачных совпадений. И если вдруг окажется, что за переделами участка сигнал какой-то другой, то преположение о периодичности и цельно-кратности периодов окажется лажей. В этом случае ошибка может быть очень большой. Заполнение нулями - это согласие на среднюю ошибку. Она окажется больше, если в периолд удалось вписаться, или меньше, если вписаться не удалось. Т.е. здесь мы уповаем на нулевое среднее того сигнала, продолжения которого не знаем. Вообще-то это не такое уж плохое предположение.
Ситуация становится из рук вон плохой, когда мы решились на нулевое среднее, но продолжаем использовать метод FFT. Вот тут-то нас и подстерпегают сюрпризы из-за того что FFT-пребразование апроксимирует гармониками те разрывы непрерывности, которые имеют место (в точке перехода крайней точки на нуль и точку перехода нуля на первую точку). И вот именно с этим эффектом борется "метод треугольника", делая этот переход наиболее плавным.