Цитата(nadie @ Mar 1 2006, 18:03)

Я абсолютно не собираюсь выяснять здесь отношения.
To st256
Цитата
Т.е. Вы предлагаете, оставлять фразы типа "свертка требует меньше перемножений, чем БПФ" без последствий? А если их кто прочтет и решит, что это истинно? Подумайте, ради Бога, о будущих поколениях разработчиков!
Если вы не можете математически обосновать ложность утверждения "свертка требует меньше перемножений, чем БПФ при условии, что длина фильтра существенно меньше чем длина массива данных", то имейте хотя бы мужество признать, что вы не правы и извиниться.
Девушка, просто никогда не надо маскировать пробелы в знаниях, иностранными словами. Это раз.
А на счет "два", я Вам так же просто объясню, почему сверка проигрывает БПФ.
1. Что делает FIR фильтр N-ого порядка? Он берет массив выборок длинной N, перемножает со своими коэффициентами (коих количество тоже N) и полученные произведения складывает:
y1 = x1*h1 + x2*h2 + ... + xN*hN
полученное значение является выходным отчсетом. Кстати, если загляните в матанализ, то увидите, что точно таким же образом вычисляют коэффициент корреляции между двумя массивами длинны N.
Т.е. имеем: выходной отсчет FIR-фильтра это всего лишь коэффициент корреляции импульсной характеристики фильтра и входного массива выборок. Это понятно?
2. Из всего вышесказанного, вытекает следующее: количество перемножений на один выходной отсчет пропорционально порядку фильтра.
В принципе оно может быть при некоторых условиях и меньше (полифазная обработка и т.п.), но реализация фильтра обычно требует количества умножений в пределах N - N/2 в зависимости от системы команд.
3. А что делает БПФ? Да тоже самое: вычисление корреляции входного массива длинной N с набором неких коэффициентов. Длинна же каждого "набора коэффициентов" тоже равна N. При этом количество перемножений на один выходной отсчет БПФ составляет всего Log2(N)/2. Разницу ощущаете? Log2(N)/2 и N/2 ?
При этом, БПФ можно истолковать как гребенку фильтров с АЧХ вида sin(x)/x. Иначе говоря, БПФ измеряет мниную и вещественную часть некой синусоиды наилучшим образом, так как использует т.н. согласованную фильтрацию. Иначе говоря, измерить синусоиду лучше невозможно НИКАКОЙ другой схемой.
Теперь о фильтрации непрерывного сигнала (Ваше N >> n). В "фундаментальной" литературе описан следующий метод: берется сигнал, делается БПФ, домножается на хар-ку Вашего фильтра в спектральной области, потом обратное БПФ.
Называется все это сверка при помощи БПФ. Выйгрыш очень серьезный по быстродействию. Еще при помощи БПФ перемножают матрицы (та же свертка, при определенных условиях), решаются системы уравнений. Должен заметить, что приемущество БПФ перед сверткой описанно во многих учебниках по ЦОС. Короче учите букварь и не говорите больше глупостей.
За сим прощаюсь навечно, ибо я должен еще послать модератора, который вступился за Ваше попранное достоинство.