Быстрая свертка! Как?, помогите, пожалуйста, с алгоритмом Опции

[coolibin]

Нужен алгоритм быстрой свертки(желательно подробный). Если кто то опишет или даст линк, я буду только благодарен

[coolibin]

Что в этой свертке неправильно?

Код

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

[shasik]

Что в этой свертке неправильно?

Уверены в правильности вычисления прямого и обратного(!) преобразования Фурье?

когда береш 100 000 точек сигнала и сворачиваешь с 8 000 точками коэф. фильтра, то всё равно приходится не мало ждать. Тем более результат после быстрой свертки хуже(может не правильно сворачивал)

Вы уверены, что оно Вам надо? Пример: отсчеты сигнала приходят один раз в секунду. Фильтр длиной 8000. Т.е. когда будет получен 8000-й отсчет можно посчитать свертку и выплюнуть результат. Считать можно в лоб (всего то 8000). Если же применять fft в том виде, как это сделали Вы, то придется ждать пока не будет получен весь(!) сигнал и выполнять fft для сигналов длиной 100000(!). Опеределитесь, что Вам нужно!
А еще есть алгоритмы разбиения свертки длинного сигнала на несколько более коротких - секционирование называется. Обратите внимание на это.

[coolibin]

Уверены в правильности вычисления прямого и обратного(!) преобразования Фурье?

При пошаговой проверке спектры вычисляются правильно. Могу показать код

Вы уверены, что оно Вам надо? Пример: отсчеты сигнала приходят один раз в секунду. Фильтр длиной 8000. Т.е. когда будет получен 8000-й отсчет можно посчитать свертку и выплюнуть результат. Считать можно в лоб (всего то 8000). Если же применять fft в том виде, как это сделали Вы, то придется ждать пока не будет получен весь(!) сигнал и выполнять fft для сигналов длиной 100000(!). Опеределитесь, что Вам нужно!
А еще есть алгоритмы разбиения свертки длинного сигнала на несколько более коротких - секционирование называется. Обратите внимание на это.

К тому времени когда запускается моя программа сигнал уже получен. Я работаю с уже с известными данными.

[shasik]

Почему

Код

uint uConvSize = get_length(uSizeA + uSizeB - 1);

а не просто

Код

uint uConvSize = uSizeA + uSizeB - 1;