Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 51
Педагогическое замечание: если хочется быть ближе к народу, советую сформулировать конкретную задачу, которую вы решаете и лишь потом обобщать. Что это за сигналы и их цифровая обработка? Зачем их сворачивать и что это такое? А то во введении заявлена широкая аудитория, а вы ее сразу интегралом по голове бьете.
Гы, у моего шефа была секретная кандидатская в которой применялись фильтры Фурье. Я еще студентом писал БПФ для него. Литература была на русском, сейчас не вспомню, но талмуд по фильтрам БПФ был листов 400. Помню для ускорения БПФ было что-то из Виноградова. Если не заменили, то оборудование до сих пор стоит на известном изделии, именуемом нынче «Адмирал Кузнецов».
Ну почему же, БПФ достаточно популярная штука, чем быстрее — тем лучше.
Только если использовать наивный подход. Вот подборка альтернатив, вот ещё одна
современные CPU/GPU как раз и построены на таких алгоритмах, поэтому и такая «стоимость» лучшее сказать сложность. без условно очень полезно развивать такие алгоритмы, но как правило они лучшее будут выглядеть в железе, -плис -VHDL — чип — гаджет — или С600, автору респект.
Есть ещё БПХ (Хартли) Fast DHT почти то же самое что и БПФ(Фурье) только для вещественных чисел. Требует в два раза меньше вычислений для частотного анализа сигнала.
Есть специальные версии алгоритмов под общим названием Real FFT, которые вычисляют только половину спектра, избавляясь таким образом от лишних вычислений. Но при наивной реализации БПХ безусловно быстрее — я и сам им пользуюсь.
Пиксельартовые формулы выглядят довольно странно. На LaTeX за недолгое время можно сделать красивые картинки. Косяки с отступами тоже не по-хипстерки.
пример самого простого фильтра низких частот, широко известного как фильтр «фильтр экспоненциального сглаживания»
Всё-таки в профессиональной среде он больше известен как «фильтр 1-го порядка».
Для FIR-фильтрации посредством FFT нет никакой необходимости в перекрытиях с весовым окном. Достаточно просто свёртки, которая через FFT реализуется, например, алгоритмом Overlap–add.
Так это же оно и есть!
это Overlap–add и есть перекрытие с весовым окном!
только можно брать квадратное окно как в Overlap–add, можно брать окно Хана, можно брать любое, лишь бы оно удовлетворяло условиям
2.1 Равна нулю везде, кроме интервала 2^n.
2.2 Не должна иметь точек разрыва, быть гладкой.
2.3 На краях интервала стремится к нулю.
2.4 И, самое главное, сумма весовых функций Fv(t), сдвинутых на интервал перекрытия k должна быть постоянна
вот только с пунктом 2.2 я ошибся, сейчас поправлю
это Overlap–add и есть перекрытие с весовым окном!
только можно брать квадратное окно как в Overlap–add, можно брать окно Хана, можно брать любое, лишь бы оно удовлетворяло условиям
2.1 Равна нулю везде, кроме интервала 2^n.
2.2 Не должна иметь точек разрыва, быть гладкой.
2.3 На краях интервала стремится к нулю.
2.4 И, самое главное, сумма весовых функций Fv(t), сдвинутых на интервал перекрытия k должна быть постоянна
вот только с пунктом 2.2 я ошибся, сейчас поправлю
Только Overlap–add немного калечит спектр, окно применяется до преобразования
Пункт 2.2 меня немножко озадачил… тут не все так однозначно…
Пункт 2.2 меня немножко озадачил… тут не все так однозначно…
Ничего оно не калечит. Свёртка даёт одинаковый результат вне зависимости от реализации (не считая погрешностей от самих операций с плавающей точкой).
Ну а если это не «свертка»?
если мы хотим сделать что нибудь этакое? сдвинуть спектр например (только про гильберта не надо) или добавить эхо, как себя поведет Overlap–add
если мы хотим сделать что нибудь этакое? сдвинуть спектр например (только про гильберта не надо) или добавить эхо, как себя поведет Overlap–add
Если это "'эхо" через импульсный отклик — это и есть свёртка. Ну а если это нелинейные операции, как, например, выделение центра из стерео-каналов — тогда да, нужно 75%-перекрытие с дважды накладываемым косинусоидальным окном.
Ну вот и договорились! только, имхо, 75% это не обязательное требование
А скажите, зачем вообще эхо реализовывать в частотном домене?
По моему скромному мнению, простые линейные операции в частотной области реализовывать не надо, затратно это.
Другое дело какой-нибудь хардкор. Например пропускание спектра через ФНЧ. На звуке дает эффект «гулкой комнаты», многократное эхо. Можно такой же эффект реализовать и во временной области, но сложность будет уже соизмерима.
Или например «пороговый шумоподавитель», вырезаем все гармоники с с уровнем ниже порога.
Другое дело какой-нибудь хардкор. Например пропускание спектра через ФНЧ. На звуке дает эффект «гулкой комнаты», многократное эхо. Можно такой же эффект реализовать и во временной области, но сложность будет уже соизмерима.
Или например «пороговый шумоподавитель», вырезаем все гармоники с с уровнем ниже порога.
Потому что реализация свёртки «в лоб» имеет квадратичную сложность.
Оно оптимальное. Большее перекрытие ничего не даёт.
Уважаемый Refridgerator!
Объясните мне темному, интимологию выражения «свертка через БПФ»
Я встречаю это это повсеместно, даже Рабинер-Гоулд одобряет, может со мной что то не так?
Я с начальной школы усвоил свертка это одно, Фурье другое!
Произведение изображений эквивалентно свертке оригиналов! и наоборот!
Как может быть свертка через преобразование Фурье???!!!
Объясните мне темному, интимологию выражения «свертка через БПФ»
Я встречаю это это повсеместно, даже Рабинер-Гоулд одобряет, может со мной что то не так?
Я с начальной школы усвоил свертка это одно, Фурье другое!
Произведение изображений эквивалентно свертке оригиналов! и наоборот!
Как может быть свертка через преобразование Фурье???!!!
Так же, как и умножение через логарифмы. И я вам даже больше скажу: свёртку можно посчитать не только через умножение спектров, но и через сумму кепстров.
Тут какая-то путаница в терминологии, которую я не могу понять.
Для меня свертка — операция во временной области.
Поэтому для меня «свертка через преобразование Фурье» — оксюморон.
Я пытаюсь понять что со мной не так.
Для меня свертка — операция во временной области.
Поэтому для меня «свертка через преобразование Фурье» — оксюморон.
Я пытаюсь понять что со мной не так.
Свёртка — это не только операция, но и результат операции. Как и у всех остальных мат. функций. Сумму можно посчитать как 2+2+2+2+2, а можно через умножение 2*5 — это будет одна и та же сумма. Синус можно посчитать через ряд, через формулы, из таблицы взять — это будет один и тот синус.
Если точнее, то — линейная свёртка через циклическую используя ДПФ.
Умножение многоразрядных чисел(более миллиона разрядов) — это свертка составляющих их цифр. Для ускорения этой операции используется свертка через преобразование фурье, что неочевидно, зато весьма эффективно.
out_alfa=out_alfa — (out_alfa >>alfa)) + a;
что тут нето со скобками
Первый листинг кода — безобразный. что за переменная kf? а это — i=(i-1)&(L-1);?
Дальше читать не захотелось
Дальше читать не захотелось
Прошу прощения, поправил. Согласовывал код с формулами, пропустил
«а это — i=(i-1)&(L-1);? » — это стандартный прием в нашем колхозе,
городские пишут так i--; if(i<0)i=(L-1);
в нашем колхозе все владеют битовой арифметикой
«а это — i=(i-1)&(L-1);? » — это стандартный прием в нашем колхозе,
городские пишут так i--; if(i<0)i=(L-1);
в нашем колхозе все владеют битовой арифметикой
static int i=0; //текущая позиция
— статик то зачем? Я не пойму для каво статья и о чем? Какое то месиво г… но кода, формул, и собственной теории DSP. То что свертку эффективно вычислять с помощью БПФ — итак все знают. А если нет — без кода и красивее можно изложить… и точно без колхозного стиля программирования.
— статик то зачем? Я не пойму для каво статья и о чем? Какое то месиво г… но кода, формул, и собственной теории DSP. То что свертку эффективно вычислять с помощью БПФ — итак все знают. А если нет — без кода и красивее можно изложить… и точно без колхозного стиля программирования.
Городские пишут так «if (i==0) i=L-1; else --i;»
Я ползовал преобразование Хартли. Два раза быстрее.
Как по мне для такой темы очень не хватает графиков сигналов с подробным описанием: что у нас было, и что хотим получить. Это очень сильно помогает восприятию происходящего.
Меня смущает в таком способе, что если не перекрывать окна — «ничего не получится» (цитата). Если перекрывать, то получится. Неясно, насколько это «получится» будет равно желамому результату, как найти критерии оценки качества фильтрации в зависимости от степени перекрытия и весовой функции? Или все же этот фильтр из разряда «просто поиграться»? Вот в БИХ-фильтрах все понятно, точно знаешь что получишь на выходе, и считаются они не в пример быстрее любых сверток.
Автор говорит о нелинейной фильтрации. БИХ (как и КИХ) — линейные.
Меня тоже волновал, это вопрос! Но боюсь это тема для отдельного исследования…
В моей практической задаче, я обрабатывал звук в телефонном качестве, эксперты не заметили разницы между половинным и трех-четвертным перекрытием, также никакой разницы от при изменении длинны выборки 128-512, разве что спады фильтра круче
В моей практической задаче, я обрабатывал звук в телефонном качестве, эксперты не заметили разницы между половинным и трех-четвертным перекрытием, также никакой разницы от при изменении длинны выборки 128-512, разве что спады фильтра круче
так что же быстрее — realFFT, виноград или cufft?
А имеет ли отношение БПФ к алгоритму голосового «детектора лжи», voice stress analysis (VSA)?
Есть ли где развернутое объяснение алгоритма, теория детектора?
Есть ли где развернутое объяснение алгоритма, теория детектора?
Спасибо!
Вот бы ещё интересно развить тему, для совсем убогих у кого и FPU то нет (но зато 32 бита и ПДП)
Вот бы ещё интересно развить тему, для совсем убогих у кого и FPU то нет (но зато 32 бита и ПДП)
Что-то по-моему, тут решена более сложная задача, чем постулируется.
Во-первых, БПФ не требует отрезка длиной 2^n, это заблуждение. Современный FFT умеет всё сам правильно разбивать и фурьячить.
Во-вторых, избавиться от проблемы с периодичностью в случае ДПФ можно просто выкинув самую правую точку (которая всегда равна самой левой). Тогда магическим образом, сигнал становится периодическим без перекрытий.
Во-первых, БПФ не требует отрезка длиной 2^n, это заблуждение. Современный FFT умеет всё сам правильно разбивать и фурьячить.
Во-вторых, избавиться от проблемы с периодичностью в случае ДПФ можно просто выкинув самую правую точку (которая всегда равна самой левой). Тогда магическим образом, сигнал становится периодическим без перекрытий.
Довольно печально читать маниловские рассуждения без малейшей попытки демонстрации.
А уж это
Стоит отметить, что, скорее всего, данная функция Фурье-фильтра, на практике окажется неработоспособна.
таки вообще глумление.
A
Практическое применение
вообще бесит
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Практическое применение преобразования Фурье для обработки сигналов