| |
 Быстрая свертка! Как?, помогите, пожалуйста, с алгоритмом |
|
|
|
 |
Ответов
|
|
  Dec 4 2010, 18:54
|
Группа: Новичок
Сообщений: 5
Регистрация: 2-12-10
Пользователь №: 61 351
|
Ну ладно…
Пусть мы имеем отсчеты квадратурного (комплексного) сигнала, поступающие непрерывно на коррелятор, имеющий линию задержки длинной k с комплексными эталонными коэффициентами. Один такт вычислений в этом случае даст 4 операции умножения и 3 суммирования на 1 ячейку линии задержки (комплексное умножение). Так как этих ячеек k, то общее количество операций k*(4умн+3сум). Кроме того, необходио суммирование результата умножения по всем ячейкам. Итого количество операций Ot для корреляция во времени:
Ot= k*(4умн+3сум)+kсум;
Для частотной области только перемножаем спектры сигналов и получаем количество опеаций k*(4умн+3сум). Суммировать здесь действительно не надо. Но для выполнения БПФ необходимо k*log2(k) операций. Итого для вычисления свертки в частотной области необходимо Of операций:
Of= k*(4умн+3сум)+2*k*log2(k).
Так при k=2048 для вычисления свертки во времени необходимо 16384 операций умножения и суммирования, а для частоной 59392. Чудовищный проигрыш…
|
|
|
|
|
|
Сообщений в этой теме
 coolibin Быстрая свертка! Как? Oct 10 2007, 06:42 DRUID3 Цитата(coolibin @ Oct 10 2007, 09:42) Нуж... Oct 10 2007, 09:12 fontp Цитата(DRUID3 @ Oct 10 2007, 13:12) Сверт... Oct 10 2007, 12:20 rloc Цитата(coolibin @ Oct 10 2007, 10:42) Нуж... Oct 15 2007, 11:55 shasik В Matlab'e приведенный выше пример полностью п... Oct 15 2007, 13:58 coolibin ЦитатаИ здесь есть очень симпатичная книга по быст... Oct 11 2007, 08:23 fontp Цитата(coolibin @ Oct 11 2007, 12:23) ссы... Oct 11 2007, 09:42 DRUID3 Цитата(coolibin @ Oct 11 2007, 11:23) ссы... Oct 11 2007, 09:50 Oldring Цитата(coolibin @ Oct 10 2007, 10:42) Нуж... Oct 11 2007, 10:00 coolibin Цитатассылка не битая, просто надо посидеть и разо... Oct 11 2007, 10:57 coolibin Что в этой свертке неправильно?
Кодvoid fast_conv... Oct 12 2007, 11:39 shasik Цитата(coolibin @ Oct 12 2007, 14:39) Что... Oct 12 2007, 12:13 coolibin Цитата(shasik @ Oct 12 2007, 15:13) Увере... Oct 12 2007, 12:44 Grt При вычислении свертки, нужно обязательно учитыват... Oct 12 2007, 14:13 coolibin Цитата(Grt @ Oct 12 2007, 17:13) При вычи... Oct 15 2007, 08:10 shasik Почему
Кодuint uConvSize = get_length(uSizeA +... Oct 15 2007, 10:08 coolibin Цитата(shasik @ Oct 15 2007, 13:08) Почем... Oct 15 2007, 13:36 shasik Цитата(coolibin @ Oct 12 2007, 14:39) Что... Oct 18 2007, 08:05 coolibin Цитата(shasik @ Oct 18 2007, 11:05) Ну, т... Oct 18 2007, 08:21 coolibin Алгоритм описаный здесь http://alglib.sources.ru/f... Oct 16 2007, 06:36 shasik Цитата(coolibin @ Oct 16 2007, 09:36) Алг... Oct 22 2007, 10:00 coolibin А никто не скажет, когда применять быструю свертку... Oct 23 2007, 07:03 shasik Цитата(coolibin @ Oct 23 2007, 10:03) А н... Oct 23 2007, 07:26 coolibin Цитата(shasik @ Oct 23 2007, 10:26) ЗЫ: Е... Oct 23 2007, 08:00 fontp Цитата(coolibin @ Oct 23 2007, 12:00) А ч... Oct 23 2007, 08:19 shasik Цитата(coolibin @ Oct 23 2007, 11:00) А ч... Oct 23 2007, 11:43 Ole2 Подскажите пожалуйста, откуда берется выигрыш при ... Dec 3 2010, 15:54 fontp QUOTE (Ole2 @ Dec 3 2010, 18:54) Подскажи... Dec 3 2010, 20:43 fontp QUOTE (Ole2 @ Dec 4 2010, 21:54) Ну ладно... Dec 4 2010, 19:41 :-) http://www.williamspublishing.com/PDF/5-8459-0710-... Dec 4 2010, 20:22 Ole2 Если делать БПФ поблочно, то конечно, выигрыш буде... Dec 5 2010, 10:33
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
