| |
 Быстрая свертка! Как?, помогите, пожалуйста, с алгоритмом |
|
|
|
|
 Oct 11 2007, 08:23
|
Местный
Группа: Участник
Сообщений: 214
Регистрация: 19-07-07
Пользователь №: 29 228
|
Цитата И здесь есть очень симпатичная книга по быстрым преобразованиями соответствующие реализации свёртки хоть через Фурье, хоть через Хартлиhttp://www.jjj.de/fxt/fxtpage.html ссылка битая, помоему а если честно, то когда береш 100 000 точек сигнала и сворачиваешь с 8 000 точками коэф. фильтра, то всё равно приходится не мало ждать. Тем более результат после быстрой свертки хуже(может не правильно сворачивал) алгоритм быстрой свертки брал здесь - http://graphics.cs.msu.ru/courses/cg02b/li...y/dspcourse.pdf
--------------------
Нет повести печальнее на свете, чем повесть о хреновом интернете.
|
|
|
|
|
|
|
|
Oct 11 2007, 09:50
|
山伏
Группа: Свой
Сообщений: 1 827
Регистрация: 3-08-06
Из: Kyyiv
Пользователь №: 19 294
|
Цитата(coolibin @ Oct 11 2007, 11:23)  ссылка битая, помоему а если честно, то когда береш 100 000 точек сигнала и сворачиваешь с 8 000 точками коэф. фильтра, то всё равно приходится не мало ждать. Тем более результат после быстрой свертки хуже(может не правильно сворачивал) алгоритм быстрой свертки брал здесь - http://graphics.cs.msu.ru/courses/cg02b/li...y/dspcourse.pdfссылка не битая, просто надо посидеть и разобраЦЦо. А немало ждать на какой машине??? Теоретически результат свертки и быстрой свертки абсолютно идентичны. Интересно, с какими типами данных работаете?
--------------------
Нас помнят пока мы мешаем другим...
//--------------------------------------------------------
Хороший блатной - мертвый...
//--------------------------------------------------------
Нет старик, это те дроиды которых я ищу...
|
|
|
|
|
|
|
|
Oct 11 2007, 10:57
|
Местный
Группа: Участник
Сообщений: 214
Регистрация: 19-07-07
Пользователь №: 29 228
|
Цитата ссылка не битая, просто надо посидеть и разобраЦЦо. А немало ждать на какой машине??? Теоретически результат свертки и быстрой свертки абсолютно идентичны. Интересно, с какими типами данных работаете? по ссылке зашел. машина - pentium 4 2.8. данные - double
--------------------
Нет повести печальнее на свете, чем повесть о хреновом интернете.
|
|
|
|
|
|
|
|
Oct 12 2007, 11:39
|
Местный
Группа: Участник
Сообщений: 214
Регистрация: 19-07-07
Пользователь №: 29 228
|
Что в этой свертке неправильно? Код void fast_conv(const double *pSigA, unsigned int uSizeA, const double *pSigB,unsigned int uSizeB, double *pSigR){
complex<double> *pSigACx, *pSigBCx;
size_t i;
uint uConvSize = get_length(uSizeA + uSizeB - 1);
pSigACx = new complex<double>[uConvSize];
pSigBCx = new complex<double>[uConvSize];
for(i = 0; i != uSizeA; i++){
pSigACx[i] = complex<double>(pSigA[i], 0.0);
}
for(i = uSizeA; i != uConvSize; i++){
pSigACx[i] = complex<double>(0.0, 0.0);
}
fft(pSigACx, uConvSize, false);
for(i = 0; i != uSizeB; i++){
pSigBCx[i] = complex<double>(pSigB[i], 0.0);
}
for(i = uSizeB; i != uConvSize; i++){
pSigBCx[i] = complex<double>(0.0, 0.0);
}
fft(pSigBCx, uConvSize, false);
for(i = 0; i != uConvSize; i++){
pSigACx[i] *= pSigBCx[i];
}
fft(pSigACx, uConvSize, true);
for(i = 0; i != uSizeA; i++){
pSigR[i] = pSigACx[i].real();
}
delete [] pSigACx;
delete [] pSigBCx;
} fft работает правильно!
Сообщение отредактировал coolibin - Oct 12 2007, 11:42
--------------------
Нет повести печальнее на свете, чем повесть о хреновом интернете.
|
|
|
|
|
|
|
|
Oct 12 2007, 12:13
|
Местный
Группа: Свой
Сообщений: 319
Регистрация: 3-09-05
Из: Беларусь, Новополоцк
Пользователь №: 8 188
|
Цитата(coolibin @ Oct 12 2007, 14:39) Что в этой свертке неправильно? Уверены в правильности вычисления прямого и обратного(!) преобразования Фурье? Цитата(coolibin @ Oct 11 2007, 11:23) когда береш 100 000 точек сигнала и сворачиваешь с 8 000 точками коэф. фильтра, то всё равно приходится не мало ждать. Тем более результат после быстрой свертки хуже(может не правильно сворачивал) Вы уверены, что оно Вам надо? Пример: отсчеты сигнала приходят один раз в секунду. Фильтр длиной 8000. Т.е. когда будет получен 8000-й отсчет можно посчитать свертку и выплюнуть результат. Считать можно в лоб (всего то 8000). Если же применять fft в том виде, как это сделали Вы, то придется ждать пока не будет получен весь(!) сигнал и выполнять fft для сигналов длиной 100000(!). Опеределитесь, что Вам нужно! А еще есть алгоритмы разбиения свертки длинного сигнала на несколько более коротких - секционирование называется. Обратите внимание на это.
|
|
|
|
|
|
|
|
Oct 12 2007, 12:44
|
Местный
Группа: Участник
Сообщений: 214
Регистрация: 19-07-07
Пользователь №: 29 228
|
Цитата(shasik @ Oct 12 2007, 15:13) Уверены в правильности вычисления прямого и обратного(!) преобразования Фурье? При пошаговой проверке спектры вычисляются правильно. Могу показать код Цитата(shasik @ Oct 12 2007, 15:13) Вы уверены, что оно Вам надо? Пример: отсчеты сигнала приходят один раз в секунду. Фильтр длиной 8000. Т.е. когда будет получен 8000-й отсчет можно посчитать свертку и выплюнуть результат. Считать можно в лоб (всего то 8000). Если же применять fft в том виде, как это сделали Вы, то придется ждать пока не будет получен весь(!) сигнал и выполнять fft для сигналов длиной 100000(!). Опеределитесь, что Вам нужно!
А еще есть алгоритмы разбиения свертки длинного сигнала на несколько более коротких - секционирование называется. Обратите внимание на это. К тому времени когда запускается моя программа сигнал уже получен. Я работаю с уже с известными данными.
--------------------
Нет повести печальнее на свете, чем повесть о хреновом интернете.
|
|
|
|
|
|
|
|
Oct 12 2007, 14:13
|
Участник
Группа: Участник
Сообщений: 62
Регистрация: 3-10-07
Из: Moscow
Пользователь №: 31 035
|
При вычислении свертки, нужно обязательно учитывать предысторию сигнала.
Длина предыстории определяется порядком фильтра, т.е. если вы берете порядок фильтра 8. Значит 8 семплов сигнала вам нужно брать с предыдущего фрейма.
|
|
|
|
|
|
|
|
Oct 15 2007, 08:10
|
Местный
Группа: Участник
Сообщений: 214
Регистрация: 19-07-07
Пользователь №: 29 228
|
Цитата(Grt @ Oct 12 2007, 17:13) При вычислении свертки, нужно обязательно учитывать предысторию сигнала.
Длина предыстории определяется порядком фильтра, т.е. если вы берете порядок фильтра 8. Значит 8 семплов сигнала вам нужно брать с предыдущего фрейма. С этим проблем нет В статье http://alglib.sources.ru/fft/fastconvolution.php вводятся понятия положительной и отрицательной длинны отклика. В моем случае сворачивается сигнал и коэфф. фильтра, как определить длину положительного/отрицательного отклика. Пополам чтоли?
--------------------
Нет повести печальнее на свете, чем повесть о хреновом интернете.
|
|
|
|
|
|
|
|
Oct 15 2007, 10:08
|
Местный
Группа: Свой
Сообщений: 319
Регистрация: 3-09-05
Из: Беларусь, Новополоцк
Пользователь №: 8 188
|
Почему Код uint uConvSize = get_length(uSizeA + uSizeB - 1); а не просто Код uint uConvSize = uSizeA + uSizeB - 1;
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
