New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

much faster mpm auto-correlation #35

Closed
doffen opened this Issue Sep 19, 2018 · 2 comments

Comments

Projects
None yet
2 participants
@doffen

doffen commented Sep 19, 2018

Today I met with a friend, Ron Schafer, co-author of the textbook "Discrete-Time Signal Processing" to get a better understanding of how the mpm auto-correlation works. While reviewing the code he figured out that it is possible to completely eliminate one of the three FFTs in acorr_r() and still get identical results in a much shorter time! Here's the new code, which I have validated. I suggest you try it and if you agree, replace your existing acorr_r code with this improvement.
int N = signal.size();
int N2 = 2 * N;

auto fft_forward = ffts_init_1d(N2, FFTS_FORWARD);
auto fft_backward = ffts_init_1d(N2, FFTS_BACKWARD);

std::vector<std::complex<float>> signalb_ext(N2);

for (int i = 0; i < N; i++)
    signalb_ext[i] = {float(signal[i]), 0.0};

std::vector<std::complex<float>> outb(N2);
std::vector<std::complex<float>> out(N2);
std::vector<std::complex<float>> result(N2);

ffts_execute(fft_forward, signalb_ext.data(), outb.data());

std::complex<float> scale = {1.0f / (float)N2, 0.0};
for (int i = 0; i < N; ++i) 
     out[i] = outb[i] * std::conj(outb[i]) * scale;

ffts_execute(fft_backward, out.data(), result.data());

ffts_free(fft_forward);
ffts_free(fft_backward);

std::vector<double> normalized_result(N, 0.0);
for (int i = 0; i < N; ++i) 
     normalized_result[i] = std::real(result[i]) / std::real(result[0]);
return normalized_result;
@sevagh

This comment has been minimized.

Owner

sevagh commented Sep 19, 2018

My results agree with this so I'll push it. Thanks.

I took my undergrad DSP courses with his textbook, and now several years later he indirectly contributed to my GitHub code - what a cool world.

sevagh added a commit that referenced this issue Sep 19, 2018

Make MPM acorr faster
Removes one FFT operation, making the entire thing a bit faster.

Based on: #35
@sevagh

This comment has been minimized.

Owner

sevagh commented Sep 19, 2018

@sevagh sevagh closed this Sep 19, 2018

sevagh added a commit that referenced this issue Oct 23, 2018

Make MPM acorr faster
Removes one FFT operation, making the entire thing a bit faster.

Based on: #35
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment