По большому счету - нелинейность необратима. Помню Tanya каГ-бЕ намекала нам, когда я сам интересовался этим вопросом. Вернее обратима если точно знать характеристику нелинейного звена и первоначальный входной сигнал. Но Хевисайд уже смотрит на Вас с укоризной...

все это эмпирика, рассуждения. Не первый раз сталкиваюсь с ситуацией когда человек что-то якобы "изобрел" и пытается обосновать. То что вы предлагаете устранить скачок фазы при вычислении fft это понятно. Подобным образом умножение на окно также приводит начало сигнала к его концу. Вы делаете данное приведение интерполяцией полиномом первой степени. Так вот прежде чем говорить о своем достижении, неплохо было бы провести сравнительный анализ своего алгоритма и существующих. Например насколько ваш метод давит боковые лепестки при растекании спектра? Я почему-то думаю, что это будет зависеть от формы сигнала. Для какого-то сигнала будет одно подавление, а для другого - другое. Вот именно в этом и есть нелинейность, когда подавая различные исходные данные вы получаете различный результат. Вот например если у меня так получилось, что частота дискретизации почти кратна частоте синусоиды, то я бы и без вашего метода имел бы отличный спектр, а применив ваш метод я фигню полную получу, потому что вместо синусоиды у меня будет синусоидальный импульс и как следствие - уровень боковых - 13 дБ. В этом и есть нелинейность вашего метода.

а вот вам код матлабовский для построения спектра:


А вот вам спектр синий - ваш метод, красный вообще без ничего как есть



синий это ваш метод. Мало того что лепестки выросли, еще и постоянка появилась из-за вашего изобретательства.

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


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



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

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

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

А почему не 512?


А зачем, простите? Это Вы так перекрытие делаете или что?


???


Тут зависит от задачи - иногда нужно дополнить, а иногда масштабировать...


?????????????????????


Это мегаерундище...

Еще раз - это не FIR. Совсем не FIR. Т.е. о свертке забываем. А значит ничего не храним. Теперь у нас только умножение в частотной области - блочный алгоритм.




Лучше сесть и спокойно разобраться - как же оно - правильно.

Вы все верно спланировали. Это метод перекрытия с накоплением.

Я бы с удовольствием, но реализовав в матлабе описанное, вижу что результат этого метода не отличается от результата встроенной функции filter(b,1,in), которой я скармливаю свой оригинальный фильтр длиной 219.
В иностранной литературе метод называют Overlap-Save. (см.вложение)

Золотые слова, юрийвенедиктович...

Нет, Xenia, Вы ошибаетесь. Т.к. то, что Вы называете зацикливанием при обратной операции восстановит сигнал наиболее достоверно. "Треды" и "нули" нервно курят в стороне. Вот где ухи у "зацикливания" - так это в самой блочности вкупе с бесконечностью базисных функций, именно они - "размывают" в той или иной степени сигнал препятствуя его восстановлению без потерь.


Йа кажеЦЦо понял причину Ваших душевных терзаний . Так вот - сядьте и немного повоображайте. И подумайте когда произойдет выделенное мной если один из сигналов бесконечен. А в случае RT данных это очень удачная идеализация.


Да, но это будет в конце рабочего дня когда оператор выключит приборы.


...ну, мягко говоря, FFT не так работает.


Обманывать - непедагогично!


Это черная магия от ЦОС.


...ну раз в иностранной - тода, да... Я умываю руки, собственно кто йа такой чтобы идти против лавины иностранной науки!!!

Второстепенные вопросы остались. Если кто-то может посоветовать, то буду очень благодарен.

Никаких 512-и быть тут не может, т к результат свертки 2-х последовательностей длин 512 и 256 будет иметь длину 767. Т е размер дпф должен иметь длину минимум 767. Ближайшая внятная размерность 768. Что касается 1024-х точек - уверен, что дпф на 768 точек будет быстрее. Это справедливо, если нет аппаратной поддержки перестановок. (Например, если есть аппаратная поддержка битреверсной адресации, которая используется в алгоритме к-т по основанию 2, то есть выигрыш в числе операций). Так что не парьтесь, Вы на правильном пути.

ps
Можно манипулировать дпф сигнала используя окна без умножения на дпф фильтра, как пытались посоветовать некоторые товарищи. Но это будет совсем другая история, и размер 512 тут далеко не оптимален... Хотя, все зависит от требований к точности.

Под двумя проходами по 512 я имел ввиду :
первый проход : 512 - состоит из второй половины предыдущего блока и из первой половины нового блока данных
второй проход : 512 - состоит из первой и второй половин нового блока данных
то есть на каждый блок данных длиной 512 я прохожусь 2 раза сверткой с длиной 512, и после каждой свертки получаю 256 фильтрованных значений

Сегодня этот вариант реализовал и проверил в процессоре. Выигрыш по сравнению с прамой реализацией FIR составил 6 раз. На данном этапе меня это устраивает. Если в будущем не будет хватать, то буду делать 768-точечное FFT.
Большое спасибо всем откликнувшимся!

Согласно самому определению свертки двух конечных рядов во временном представлении - да. Но товарищу нужно наложить фильтр. Просто фильтр наложить!!! И хрен он его наложит на бесконечный ряд согласно этому определению. Классическая длинна блока, классический алгоритм БПФ, делается в течении дня вместе с тестами... Зачем вся эта ерунда!!!??? Разрабатывать БПФ странной длинны... Добавляется Х.з. сколько операций. В крайнем случае фильтр можно немного "предисказить" для улучшения результата. Хотя - мне за это не платят, так что чего это я ...

А доказательство своей правоты наличием невнятной англоязычной статьи - это супер.

КАроче - школота и дилетанты.

Что он добросовестно и проделал.
КИХ фильтрация и апериодическая дискретная свертка - одно и тоже.
Изобретать тут нечего. Все уже изобретено до нас.

зы:
На счет школоты и дилетантов - эт Вы погорячились...

Сообщение отредактировал thermit - Jul 29 2010, 12:01

Да. Но надо различить 2 случая. 1. имеется массив данных s длины N. Выход ких фильтра с заданной импульсной характеристикой h равен линейной свертке s*h. Но есть еще один случай, когда длина массива s неизвестна. Например данные идут кусками по 512 отсчетов. В этом необходимо чтобы при поступлении следующего куска данных, ячейки памяти ких фильтра хранили информацию о предыдущем куске. И если вы просто в лоб выполните линейную свертку каждого куска и потом их состыкуете, то результат будет отличаться от того, что вы получите если выполните линейную свертку всех кусков сразу. Для того чтобы хранить данные о предыдущем куске делают обработку с перекрытием (overlapped), т.е. каждый раз при поступлении следующего куска захватывают часть предыдущего чтобы заполнить ячейки памяти фильтра.