Устойчивость БПФ/ОБПФ на "длинных" сигналах

Ivan Karamazov
Сообщения: 89
Зарегистрирован: 28 окт 2010, 22:31
Откуда: Москва

Устойчивость БПФ/ОБПФ на "длинных" сигналах

Сообщение Ivan Karamazov »

Здравствуйте,
У меня по прежнему остается вопрос по поводу устойчивости пары преобразований ДПФ / ОДПФ к ошибкам округления на длинном сигнале.
Более конкретно – я выполняю преобразование Гильберта широкополосного (аудио) сигнала, изначально представленного в виде последовательности 16-разрядных отсчетов. Все вычисления выполняются строго с double (мантисса – 53 бита). Для расчетов используется FFTW 3.2.2 (http://www.fftw.org). На всякий случай приведу статистику по близкому для моих потребностей к предельному по длине сигналу:
Число отсчетов – 173 445 888; FFTW при этом требует 7 459 271 745 сложений, 5 377 550 278 умножений и 1 418 328 812 операций «умножить и сложить» при прямом и, соответственно, (+)14 835 433 984, (*)10 740 649 784 и (*+)2 793 296 128 при обратном преобразовании.
В этой связи «лобовой» вопрос – на сколько значащих цифр в результате можно рассчитывать?

Примечание 1. Я, разумеется, проверял полученный комплексный сигнал повторным ДПФ, оно показывает подавление всех отрицательных частот (по крайней мере, на «реальном» звуке) порядка -200 дБ. Но по мере того, как я (каждый вечер в течении недели) придумывал разные специальные сигналы, у меня стало складываться впечатление, что точность вычислений мало зависит от числа отсчетов, а больше от характера сигнала. Т.е. (из того, что я сотворил) больше всего ДПФ / ОДПФ не любит «радиоимпульсов» (особенно – задний фронт), особенно – если это ЛЧМ-импульсы. В реальных сигналах некоторая неустойчивость (вроде бы) появляется только когда сигнал имеет участки, подвергшиеся ограничению; по крайней мере я заметил, что сигнал с 5-ю подряд обрезанными отсчетами дает в результате последовательности преобразований ОДИН «гнилой» отсчет, который очень сильно меняется в зависимости от сборки FFTW (msvc/gcc x86/AMD64). Причем «гнилой отчет» живет на совсем другой позиции, чем ограничение. Если ограничение сгладить, результаты становятся стабильными.

Примечание 2. Я предвижу один из возможных ответов типа — «существует подход, называемый блочно-оконным БПФ (или как-то близко), который дает возможность работать с сигналом неограниченной длинны при ограниченных ресурсах системы и даже почти в реальном времени». Заранее могу сказать, что этот подход не нахожу приемлемым для звука, исходя из анализа качества значительного количества коммерчески – доступных программных и даже аппаратных решений -- от БПФ-шумоподавителей до просто фильтров или фазовращателей. Я не думаю, что смогу построить реализацию такого преобразования лучше, чем это было сделано до сего дня. Вообще, это типовой момент, когда алгоритмы определенного класса не пригодны для задач класса определенного. Этот тезис готов подтвердить картинкой, каковую пока оставляю в рукаве :) .
Заранее благодарен.
Иван.
Если ваши решения вам нравятся -- это хорошие решения. И наоборот.

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: Устойчивость БПФ/ОБПФ на "длинных" сигналах

Сообщение Бахурин Сергей »

по поводу примечания 1. Трудно что-то определенное сказать, это надо смотреть. Предлагаю перейти в матлаб или в gnuoctave для экспериментов в этой области. Надо смотреть что пошагового происходит.

по поводу примчания 2. Обработка с перекрытием дает тотже результат, что и фильтр Гильберта. По сути это и есть фильтр Гильберта только полученный умножением спектров. Поэтому для бесконечного сигнала можно использовать обработку с перекрытием и обеспечить заданный уровень подавления в области отр. частот.

Ivan Karamazov
Сообщения: 89
Зарегистрирован: 28 окт 2010, 22:31
Откуда: Москва

Re: Устойчивость БПФ/ОБПФ на "длинных" сигналах

Сообщение Ivan Karamazov »

Бахурин Сергей писал(а):Обработка с перекрытием дает тотже результат, что и фильтр Гильберта. По сути это и есть фильтр Гильберта только полученный умножением спектров. Поэтому для бесконечного сигнала можно использовать обработку с перекрытием и обеспечить заданный уровень подавления в области отр. частот.
Предположим, что я живу в мифе. С этим надо разобраться. Я прикладываю грубую картинку фрагмента спектра +90-градусного преобразования 4-х синусоид, выполненного ДПФ с перекрытием (программа Adobe Audition, 1.0-3.0). Фиолетовым показан начальный фрагмент полученного спектра, выполненный в соответствии с пресетом "+90 град.", ДПФ с перекрытием и, очевидно, тщательно подобранными параметрами. (Всех настроек не помню, но размер окна -- 16384). Тонкой зеленой линией показан ранее запомненный спектр мнимой части того же исходного сигнала, полученный "полным" ДПФ / КИХ-фильтром (разрешения не хватает, чтобы увидеть разницу между последними). Тонкие полоски ниже -96 дБ -- шумы квантования 16-разрядного сигнала. "Боковики" у основных частот -- плоды Блэкменна-Харриса. На опущенной ВЧ-части спектра -- та же дрянь. Во временной области видна очень низкочастотная АМ, при нелинейной обработке превращается в щелчки.
Допустим, изначальный автор этой программы некто Дэвид Джонсон был не прав и просто плохо реализовал свой "FFT Engine", во всяком случае, визуально разница между блочным и полным ДПФ налицо. И честное слово, остальные проги, равно как и процессоры эффектов, по крайней мере на слух не лучше Adobe Audition (как правило -- еще хуже), когда они пытаются использовать ДПФ с перекрытием.
Господь с ними.
Я, грешным делом, за всю свою жизнь так и не сподоболся точно узнать. а как оно делается на самом деле :oops: :oops: -- это самое блочно-оконное ДПФ с перекрытием. Я, конечно, все найду, но сэкономлю кучу времени, если мне подскажут адекватный первоисточник, желательно ссылку, а не книгу. Заранее благодарен, Иван.

ps: А Вы уверены, что хорошее подавление отрицательной части спектра является
абсолютным критерием качества преобразования Гильберта? В этом несовершенном мире каждое "оптимальное преобразование" оптимально "в каком-то смысле", особенно физически нереализуемое :?:
pps: Я бы не задавал глупых вопросов, если бы лет этак 18+ назад не покинул тему, по крайней мере в части реализации алгоритмов ЦОС. За последние года 2 я сильно восстановился, но с учетом крайне негативного "потребительского" опыта работы с готовыми решениями с ДПФ с перекрытием я склонен глупые вопросы себе прощать. Т.е. я реально боюсь ДПФ :oops: :oops:, даже "полного", хотя с ним, вроде бы все нормально, на самом деле.
Вложения
sp-fft.png
sp-fft.png (16.56 КБ) 13003 просмотра
Если ваши решения вам нравятся -- это хорошие решения. И наоборот.

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: Устойчивость БПФ/ОБПФ на "длинных" сигналах

Сообщение Бахурин Сергей »

1. по поводу обработки с перектрытием нужно погуглить overlapped processing .Вот например как Tektronix делает.
А Вы уверены, что хорошее подавление отрицательной части спектра является
абсолютным критерием качества преобразования Гильберта? В этом несовершенном мире каждое "оптимальное преобразование" оптимально "в каком-то смысле", особенно физически нереализуемое :?:
Ну это скорее философия. А так по сути все стремятся убрать отрицательную область если хотят получить аналитический сигнал. Это обусловлено прежде всего тем, что требуется обеспечить минимум внеполосных излучений при модуляции.

Ivan Karamazov
Сообщения: 89
Зарегистрирован: 28 окт 2010, 22:31
Откуда: Москва

Re: Устойчивость БПФ/ОБПФ на "длинных" сигналах

Сообщение Ivan Karamazov »

ну да, философия. В общем, спасибо громадное, отдельное спасибо за сайт (надеюсь, этот форум с ближайшем времени реально оживет, а если и нет -- уверен, что материалы сайта не пропадут); с моей стороны мой проект "Гильберт/CWAVE" в настоящее время более всего требует принятия решения "что с ним делать" (в стол/раздать друзьям/опубликовать в интернете -- я планировал последнее (еще 3 недели назад, на основе КИХ-фильтра)), но Ваш сайт как бы отмазал меня от жизненной необходимости таковой публикации. С ДПФ с перекрытием почти обещаю поиграть подробно, это существенный пробел в моем инженерном репертуаре/образовании.
УДАЧИ!!!
Если ваши решения вам нравятся -- это хорошие решения. И наоборот.

Ivan Karamazov
Сообщения: 89
Зарегистрирован: 28 окт 2010, 22:31
Откуда: Москва

Re: Устойчивость БПФ/ОБПФ на "длинных" сигналах

Сообщение Ivan Karamazov »

Мне не удалось с 2-х попыток получить удовлетворительное (хотя бы не устапающее ранее похороненному КИХ-фильтру сверхвысокого порядка с окном) решение для Фурье-с-перекрытием. Я не сдамся чуть позже, пока не наиграюсь с результатами преобразования Гильберта :)
Речь, на самом деле вот о чем. Ранее говорилось, что КИХ фильтр для Гильберта, имеючи порядок в 2+ раза больше, чем число отсчетов в исходном *конечном* сигнале, дает абсолютно точное (с точностью до ошибок округления) мнимую часть, и это вполне очевидно.
Под впечатлением этого тезиса у меня (довольно навязчиво) сложилось мнение, что должно существовать что-то вроде "теоремы о конечных сигналах", определяющей условия точного (для конечного во времени / по числу остчетов сигнала) для формально нереализуемых преобразований типа Гильберта, идеального прямоугольного фильтра и т.п.
Т.е. поверхностный просмотр сайта и google ничего конкретного не дал. Я прав или нет? и если такая теорема ("теорема"??) существует, она могла бы стать украшением сайта.
--
Я пока намертво застрял в реализации сочетания комплексной алгебры со всей своей тригонометрией и навороченного графического интерфейса, но будет здорово, если кто-либо ответит.
Если ваши решения вам нравятся -- это хорошие решения. И наоборот.

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: Устойчивость БПФ/ОБПФ на "длинных" сигналах

Сообщение Бахурин Сергей »

ну в общем-то это и есть правило. Если импульсная характеристика фильтра в 2 раза длиннее выборки сигнала, то вы получаете идеальные характеристики. Например если у вас длина выборки сигнала N отсчетов, то если взять фильтр sinx/x длиной 2N то получите идеальный прямоугольный ФНЧ.

mks
Сообщения: 16
Зарегистрирован: 18 окт 2010, 11:04

Re: Устойчивость БПФ/ОБПФ на "длинных" сигналах

Сообщение mks »

Вот это очень интересно, как можно на конечном числе отсчётов ИХ получить идеальную прямоугольную АЧХ. Можно немного поподробнее и если не сложно с примерами в Matlab.

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: Устойчивость БПФ/ОБПФ на "длинных" сигналах

Сообщение Бахурин Сергей »

Я не совсем верно выразил свою мысль, а Вы не совсем верно поняли. Речь вот о чем: если импульсная характеристика в 2 раза длинее сигнала, то при свертке ее хватает чтобы накрыть сигнал как справа так и слева и в этом смысле фильтр с КИХ ведет себя как идеальный фильтр, поскольку устраняются ошибки усечения. Но если вы посмотрите отклик на конечном интервале времени, то разумеется прямоугольной АЧХ не увидите, но не из-за того, что импульсная характеристика усечена, а из-за того что исходный сигнал усечен.

Аватара пользователя
Santik
Сообщения: 609
Зарегистрирован: 28 дек 2010, 08:04
Откуда: Мирный (Якутия)
Контактная информация:

Re: Устойчивость БПФ/ОБПФ на "длинных" сигналах

Сообщение Santik »

Но по мере того, как я (каждый вечер в течении недели) придумывал разные специальные сигналы, у меня стало складываться впечатление, что точность вычислений мало зависит от числа отсчетов, а больше от характера сигнала.
http://www.twirpx.com/file/240664/
Цитата из книги: "Возможно,что перед выполнением БПФ мнимую часть последнего члена (w=N/2) придется приравнять нулю, так как в противном случае в результате обратного преобразования выходной вектор может оказаться не вещественным. Такое случается при при обработке синтетических сейсмограмм. Нужно быть достаточно внимательным, чтобы обеспечивать правильную симметрию выходного вектора и требуемую симметрию коэффициента с w=N/2."

Другими словами - надо фильтровать входной сигнал, лучше с F= F Найквиста/2 (или увеличивать частоту дискретизации) чтобы гарантировать устойчивость БПФ/ОБПФ.

Ответить