Hi folks,

I need to compute the autocorrelation of an input. The "naive" way takes way too long for Pd so I decided to do it via the Wiener-Khinchin Theorem, which solves this problem in N log N time.

In my understanding it's just: Input Stream -> FFT -> a²+b² -> IFFT.
But that doesn't work out. It outputs noise and not the smooth curve to be expected.

In the attachment is a patch where Wiener-Khinchin is applied to a Hann window. I know there are some people around who are into this matter. So, please show up and help me! I'd be grateful.

http://www.pdpatchrepo.info/hurleur/wienerkhinchin.pd

Seems you're experiencing the same surprise as I did a few weeks ago. I had always learned at school 'autocorrelation function can be computed efficiently via the power spectrum', so I never had doubts about it, but when I finally wanted to use it: garbage.

The trick is, you have to zero-pad the input signal, just like with convolution. If you normalise with factor 1./sqrt(fftsize) before [rfft~] and use [sig~ 1] as the input, you'll see a triangle wave, a v-shape, as the autocorrelation result. This is called 'biased autocorrelation'. All other input types also show that contour in the output. To undo the triangle effect, just divide by the triangle (called 'unbiasing'). But this unbiased autocorrelation is still not very beautiful.

By far the best method I've seen is Philip McLeod's Specially Normalized Autocorrelation (SNAC). Read about it in his thesis:

http://miracle.otago.ac.nz/tartini/papers/Philip_McLeod_PhD.pdf

This however can't be applied at signal rate with regular Pd objects, so if you need it at signal rate it must be written in C. I've done a non-signal rate SNAC model (see attached patch), and used SNAC in pitch tracker [helmholtz~], for which you can find the C code:

http://www.katjaas.nl/helmholtz/helmholtz.html

Katja

http://www.pdpatchrepo.info/hurleur/SNAC03.pd

Yop,

Katjav uses this theorem in her recent works on pitch tracking.
I recommend the reading of the topic http://puredata.hurleur.com/sujet-6688-pitch-tracking-time-domain-ippass-function , opening the attached patches. You'll note that at first she uses a "not zero-padded" autocorrelation scheme that she refines in her later posts to suit realtime arbitrary signal analysis.

She also maintains a beautiful homepage: http://www.katjaas.nl/home/home.html .
This could be your next Alibaba's cave

Nau

Dammned ! Katjav herself answered faster than I did

wow, thanks! especially to you, katja.

i don't know why, but i already knew the article about your helmholtz~ patch and somehow dismissed it, because i expected to find more useful information on the remainder of your website (which is great btw.!). although it (that very article) contains all the information i need. :D
and many thanks for the patch. it will certainly help me find inspiration. not too much though, since i am working on a term paper (university) and I am expected to do the work, not you

my plan is to write a pd-patch to measure the jitter (variance of period length) of an incoming signal on-line via comparing the length of individual periods. i hope, pd will be fast enough, otherwise i will have to reactivate my C skills. i'm gonna share my patch here when i'm done and successful, of course.

narfson