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:

Arduino Frequency Detection

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.

Step 1: The Algorithm


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.

Other Algorithms:

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

<p>Amazing Word! i'm going to be inspired by your work! Have you done it in the end with the Due?</p><p>What about the Zero board, since is more powerful, could get to better performance?</p>
I haven't tried on due or zero yet. I worked with a teensy 3.2 and realized the full 32 bit advantage along with 96mhz processor.<br><br>I stopped optimizing it when I fully ported over to the teensy 3.2 for my purposes which I noticed has a pitch detection method built into the audio library ( which utilizes the YIN algorithm.)<br><br>Thanks for the kind words though! I hope to see an instructable of yours to inspire me as well.
I will try to implement it on the Zero (l12bit ADC, lot of memory, 48MHz clock) . The only thing is that i'll work on an higher level of programming, meaning that for getting the samples from A0 i will use the method &quot;analogRead&quot; that for some mysterious reason it samples at ~2.3kHz (i measured that with micros()).<br><br>It shoudn't be a problem since i wold like to catch the picth of human voice ~(100-1100Hz) so for Nyquist i think that may be enough... (At least the upper limit). Or will i find some problems? maybe the algorithm work best with lots of samples..<br><br><br>Another thing, do you think it's possible to modify your code in order to get the pitch from 4 different Analog input (4 mic) at the same time?<br>The ~assembly language in setting up the data gathering confuses me a little bit.<br><br>Thaks for your reply :) :)<br>All the best.

About This Instructable



Bio: Electrical Engineering student at Clarkson University in Potsdam, NY
More by daviddein:Arduino Pitch Detection Algorithm (using AMDF) Ramps 1.4 DIY SMD Pick and Place 
Add instructable to: