Last Update: January 16, 2016 (Recently added an improved matlab code (step7) with samples and lots of notes)
Foreword: This Instructable is written in a style to show how I analyzed, tested, implemented, and optimized an algorithm. Also, In the process, I learned how much work goes into doing each step and I've garnered more respect for those who have built other algorithms for my naive mindset.
Additionally, any critiques are very welcome!
Motivation: I needed to retrieve frequency data from a violin pickup. The work I did with another project creating a color organ had an FHT and I thought it would be easy enough to adapt it to my use. Trying to use it proved difficult since a violin creates what is called "quasi-harmonic" tones. Basically, the periodic frequency of the waveform was never the dominant one and I could only pick up higher harmonics of a single tone. Frustrating! So I had to build my own PDA because of the lack of search results for Arduino based PDA's. I ended up implementing the AMDF (autocorrelation magnitude difference algorithm).
Thanks: To Amanda Ghassaei for providing a general framework for how to build and test your own algorithm. I tried using her work on another Instructable:
But the core of the work she did didn't help me as much as it I wanted it to. So from there I looked for pitch detection algorithms and it got me too do all of this work. She has some pretty neat projects! Check out her website which is linked in the Instructable above.
I am not sure who invented the algorithm but from what google tells me a British statistician by the name of George Udny Yule had published a paper in the late 1800's in reference to partial autocorrelation algorithm. Additionally there a bunch of papers published by the IEEE starting in the early 1900's citing improvements to the method for use in electronics.
AMDF - Here's the skinny:
AMDF (N) = 1/N * Sum (i = 0 -> N) of ( | x(i) - x(i+N) | )
AMDF (autocorrelation magnitude difference function) is basically tracing overlapping lines on a given window of samples. Here is what basically happens:
1.) Gather data to form a window of N*2 samples wide.
2.) Cut the window in half.
3.) Overlay the first half over the top of the second half.
4.) Take the absolute value of the difference in the area between the two waveforms and sum it up.
5.) Divide the sum by the number of samples.
6.) Repeat steps 2 through 6 for a full sweep of all delays N that you expect to occur or be present in a waveform.
7.) If a quasi-harmonic tone is present, the AMDF will output a low number at or close to 0 at some delay N.
8.) Divide the sample frequency by your delay N, and you've got the most probable frequency of the quasi-harmonic tone.
A big note however! The AMDF does not work on more than one tone at a time. You won't be able to differentiate between double stops, multiple strummed notes, etc.
As far as my research has taken me, there are a couple of other pitch detection algorithms out there. Obviously more, but I didn't search too extensively. I won't cover them but I will mention them hear for your further research if you so choose.
Of course, the original autocorrelation method is out there which is the basis of AMDF. The advantage of AMDF over basic autocorrelation is that the AMDF has a bunch of subtractions and additions with one division (which can be coded into a multiplication). For the Arduino Uno which is native 8bit architecture and doesn't have hardware division or multiplication, this is an absolute plus.
Another pitch detection algorithm is the Yin algorithm. This algorithm boasts a very low percentage error rate with each step of the algorithm detailing its effectiveness so that you can implement as much or as little as you'd like. From testimonials I've read it is not very computationally intensive which is great! So yeah... Why I didn't got there is because the Yin algorithm apparently has a patent on its use. Additionally, if you search around, someone has already compiled the source code for you in C so that you can play around with it. There is a published paper on the Yin algorithm as well, very interesting stuff.
Here is the Yin Source Code, if you want to take a look!: http://mroy.chez-alice.fr/yin/index.html
Here is the published paper on the algorithm: http://recherche.ircam.fr/equipes/pcm/cheveign/pss/2002_JASA_YIN.pdf