Reliable Frequency Detection Using DSP Techniques

Accurate Frequency Detection is important for many projects such as Guitar/Piano Tuners, Vibration Analyzers, Heartrate Monitors, MEMs Sensor Analysis and Laboratory Instruments. There have been many fine examples of projects that try to solve this problem, for example: Arduino Frequency Detection by amandaghassaei  and Arduino Frequency Counter Library. But they all use Time Domain techniques; analyzing the signal for features such as : Zero-Crossings, Peak Detection, Slope Detection etc.. Take a look at the Waveforms shown. One of them is recorded from a Piano playing Middle-C (C4) . The other is from a Synthesizer Playing Middle-C (C4). Clearly any good Time Domain algorithm will work well with the Piano waveform. But the Synthesizer waveform will not be identifiable that way because its very strong harmonic content makes the fundamental frequency undiscernable . It looks impossible to Identify the Frequency of this signal. It is possible. Using the technique I'm going to show you it was measured to be 259.91Hz ... only 0.09Hz away from an Exact Middle C Frequency of 260Hz.

Step 1: You Will Need

I used an Arduino because it will make a great basis for building a Frequency Detector with Analogue Input such as a Guitar Tuner or Heartrate Monitor. But the principles apply to any platform. To demonstrate the principles I'm going to use pre-recorded sound files captured as an array in a .h file. So we won't be needing any circuit for the Arduino this time.

Step 2: Autocorrelation

The trick we use to identify the frequency of a noisy signal is well known in the Mathematical World of Digital Signal Processing (DSP), and is based on some pretty fancy maths. But the technique is not difficult to understand and better still it's super-easy to code. The core of it is just 3 lines of code. What we need to do is to change the original signal into another one that highlights the periodicity of the original signal. So if it is indeed periodic, then that will stand out in the new signal and then we can measure that in the usual way using peak-detect or zero crossing detect. What's the magic algorithm that does that? It's Autocorrelation. Imagine your signal is contained in a window or buffer. Now image you have an exact copy of that window or buffer with a time delay. What Autocorrelation does is to measure the correlation (or similarity) between the signal and its delayed copy each time the copy is delayed by a sample period. See the diagram. When the signal and the copy have no delay they are very similar (i.e. highly correlated) as shown in step 1, and therefore the autocorrelation value for delay = 0 is maximum. Step 2 shows that when the copy is delayed significantly it doesn't look similar to the original in the overlapping area. Therefore the autocorrelation value for this delay is small. Step 3 shows that when the copy is delayed even more the signal in the overlapping area is very similar to the original because the signal is periodic. Therefore the autocorrelation value for this delay shows a peak. We can see that the distance in time between the maximum peak at the beginning and the first peak afterwards must be equal to the fundamental period of the waveform. Now that we've emphasised the periodicity of the signal by Autocorrelation we just need to perform a Peak-Detect to measure the period. Technically the "similarity" or correlation between the signal and its delayed copy is the sum of the product of the two signals. For the technically minded all the details of Autocorrelation can be found here: http://en.wikipedia.org/wiki/Autocorrelation

Step 3: Autocorrleation Code

The core of the Autocorrelation Code is very short:

  
  for(i=0; i < len; i++)
  {
    sum = 0;
    for(k=0; k < len-i; k++) sum += (rawData[k]-128)*(rawData[k+i]-128)/256;
  }

The data is in the rawData[] array. We subtract 128 from each value because it's 8bit unsigned and we require signed values. The sum value is the result of each autocorrelation calculation, i.e. each point of the function. In order to save memory we don't save the output to an array. We're going to work on the individual sum values to find the first peak and therefore calculate the period. Sending the sum values out to be plotted, we get the Autocorrelation function shown. Comparing to the original signal (also shown) it is clear that there is periodicity in the original signal and this has been clearly highlighted by the Autocorrelation function.

Step 4: Peak Detect

To detect the location of the first peak after the maximum we use a simple peak detector coded as a State Machine as follows:

    // Peak Detect State Machine
    if (pd_state == 2 && (sum-sum_old) <=0) 
    {
      period = i;
      pd_state = 3;
    }
    if (pd_state == 1 && (sum > thresh) && (sum-sum_old) > 0) pd_state = 2;
    if (!i && pd_state == 0) {
      thresh = sum * 0.5;
      pd_state = 1;
    } 

The state machine moves from one state to the next when an event occurs as follows: STATE0 : Set thresh the threshold under which value we'll ignore the data : NEW STATE = 1 STATE1 : look for the signal being above the threshold AND the slope of the signal is positive : NEW STATE = 2 STATE2 : look for the slope of the signal is negative or zero. If so we've found the PEAK! : NEW STATE = 3

Step 5: Here's all of the Code

#include "C4.h"

// Sample Frequency in Hz
const float sample_freq = 22050;

int len = sizeof(rawData);
int i,k;
long sum, sum_old;
int thresh = 0;
float freq_per = 0;
byte pd_state = 0;
  
void setup() {
  Serial.begin(115200);

  sum = 0;
  pd_state = 0;
  int period = 0;
  // Autocorrelation
  for(i=0; i < len; i++)
  {
    sum_old = sum;
    sum = 0;
    for(k=0; k < len-i; k++) sum += (rawData[k]-128)*(rawData[k+i]-128)/256;
    
    // Peak Detect State Machine
    if (pd_state == 2 && (sum-sum_old) <=0) 
    {
      period = i;
      pd_state = 3;
    }
    if (pd_state == 1 && (sum > thresh) && (sum-sum_old) > 0) pd_state = 2;
    if (!i) {
      thresh = sum * 0.5;
      pd_state = 1;
    }
  }
  // Frequency identified in Hz
  freq_per = sample_freq/period;
  Serial.println(freq_per);
  }

void loop() {
  // put your main code here, to run repeatedly: 
  
} 

Step 6: C4.h File

The C4.h File contains the buffer we're analysing. You can fill that by reading a Block of Data from the ADC in the Arduino. Or you can generate the data from A program such as Audacity. Here's an example file of the Synthesiser Waveform:

unsigned char rawData[970] = {
	0x73, 0x7E, 0x3E, 0x39, 0xB0, 0x4D, 0x16, 0x48, 0x7C, 0xAB, 0x95, 0x9F,
	0xA6, 0x47, 0x5E, 0x52, 0x28, 0x92, 0x9C, 0x9A, 0xDC, 0x90, 0x12, 0x7F,
	0xE5, 0x94, 0x81, 0x79, 0x90, 0x5D, 0x48, 0x9B, 0xA9, 0xB5, 0x68, 0x56,
	0x82, 0xA7, 0x5F, 0x74, 0xEB, 0x86, 0x4D, 0xB4, 0xAA, 0xAF, 0x74, 0x46,
	0x99, 0xAD, 0x7D, 0x32, 0xCA, 0x8B, 0x63, 0xBF, 0x4D, 0x76, 0x78, 0x9A,
	0xC9, 0x4D, 0xBB, 0xD9, 0x2E, 0x6E, 0x7B, 0x9B, 0xC4, 0x57, 0x79, 0x7F,
	0x0D, 0x8B, 0xC8, 0x4F, 0xB2, 0x3F, 0x6F, 0xE1, 0x2A, 0x7E, 0xA6, 0x9E,
	0x78, 0x6B, 0x64, 0x24, 0x99, 0x74, 0x1C, 0x3B, 0x6C, 0xA1, 0x9E, 0x96,
	0xAB, 0x63, 0x4F, 0x62, 0x2C, 0x72, 0xA3, 0x92, 0xCA, 0xB2, 0x2E, 0x51,
	0xD5, 0xAD, 0x81, 0x7C, 0x87, 0x75, 0x43, 0x86, 0xA5, 0xB4, 0x82, 0x54,
	0x74, 0xA0, 0x7A, 0x5E, 0xCF, 0xAF, 0x4D, 0x96, 0xB3, 0xA8, 0x8F, 0x47,
	0x82, 0xA9, 0x93, 0x3D, 0x97, 0xB4, 0x57, 0xB1, 0x70, 0x60, 0x82, 0x83,
	0xC9, 0x6F, 0x88, 0xE9, 0x59, 0x51, 0x82, 0x86, 0xC3, 0x77, 0x63, 0x8C,
	0x2B, 0x55, 0xCE, 0x68, 0x91, 0x72, 0x42, 0xDA, 0x5C, 0x56, 0xA7, 0x9C,
	0x8A, 0x66, 0x71, 0x2F, 0x73, 0x90, 0x2E, 0x31, 0x5E, 0x93, 0xA2, 0x94,
	0xA7, 0x7D, 0x4C, 0x64, 0x3B, 0x56, 0x9E, 0x94, 0xB5, 0xC3, 0x54, 0x37,
	0xB5, 0xC1, 0x87, 0x7E, 0x81, 0x82, 0x4C, 0x6F, 0xA0, 0xAF, 0x96, 0x5C,
	0x69, 0x94, 0x8C, 0x5C, 0xAC, 0xC7, 0x61, 0x7A, 0xB3, 0xA6, 0x9D, 0x57,
	0x6B, 0xA2, 0x9E, 0x55, 0x6E, 0xBF, 0x67, 0x95, 0x8F, 0x57, 0x80, 0x7C,
	0xB8, 0x92, 0x6D, 0xD9, 0x89, 0x43, 0x7D, 0x7F, 0xB4, 0x95, 0x5D, 0x88,
	0x4D, 0x37, 0xB8, 0x8B, 0x77, 0x8F, 0x3C, 0xB4, 0x8F, 0x43, 0x99, 0x9D,
	0x93, 0x6B, 0x72, 0x44, 0x55, 0x97, 0x49, 0x2B, 0x52, 0x84, 0xA1, 0x96,
	0xA0, 0x90, 0x54, 0x5F, 0x4C, 0x45, 0x8E, 0x98, 0xA5, 0xC6, 0x79, 0x32,
	0x8E, 0xC9, 0x94, 0x80, 0x7E, 0x85, 0x5C, 0x5E, 0x96, 0xA9, 0xA2, 0x6A,
	0x61, 0x88, 0x95, 0x66, 0x8C, 0xCB, 0x7E, 0x67, 0xA8, 0xA8, 0xA2, 0x6C,
	0x5D, 0x96, 0xA3, 0x6E, 0x59, 0xB3, 0x82, 0x7C, 0x9E, 0x5F, 0x75, 0x7C,
	0xA2, 0xA8, 0x6A, 0xBB, 0xAF, 0x49, 0x6E, 0x7F, 0xA2, 0xA7, 0x65, 0x7B,
	0x68, 0x31, 0x93, 0xA5, 0x6E, 0x94, 0x4E, 0x89, 0xAE, 0x4A, 0x81, 0xA0,
	0x96, 0x76, 0x6F, 0x57, 0x45, 0x8C, 0x66, 0x2E, 0x47, 0x75, 0x9C, 0x99,
	0x9A, 0x9A, 0x64, 0x59, 0x58, 0x41, 0x79, 0x9A, 0x9C, 0xBF, 0x97, 0x3F,
	0x6C, 0xC1, 0xA3, 0x82, 0x7E, 0x84, 0x6C, 0x56, 0x87, 0xA4, 0xA7, 0x7B,
	0x5F, 0x7C, 0x96, 0x74, 0x77, 0xC0, 0x99, 0x63, 0x96, 0xAB, 0xA3, 0x80,
	0x5A, 0x86, 0xA2, 0x82, 0x55, 0x99, 0x9A, 0x72, 0x9C, 0x70, 0x6A, 0x7E,
	0x92, 0xAF, 0x77, 0x9B, 0xC1, 0x60, 0x5F, 0x7E, 0x93, 0xAD, 0x76, 0x70,
	0x77, 0x3B, 0x70, 0xAE, 0x76, 0x8B, 0x67, 0x69, 0xB3, 0x63, 0x6A, 0x9D,
	0x98, 0x81, 0x6E, 0x64, 0x44, 0x78, 0x7A, 0x39, 0x3E, 0x68, 0x92, 0x9C,
	0x97, 0x9C, 0x75, 0x58, 0x5D, 0x46, 0x66, 0x95, 0x98, 0xB4, 0xAA, 0x55,
	0x55, 0xAE, 0xB0, 0x88, 0x7E, 0x82, 0x77, 0x58, 0x77, 0x9E, 0xA7, 0x8A,
	0x63, 0x72, 0x91, 0x81, 0x6F, 0xAB, 0xAD, 0x6C, 0x84, 0xA9, 0xA3, 0x8D,
	0x60, 0x76, 0x9D, 0x8F, 0x5E, 0x80, 0xA4, 0x76, 0x91, 0x82, 0x66, 0x7B,
	0x88, 0xAB, 0x88, 0x86, 0xC0, 0x7E, 0x57, 0x79, 0x89, 0xA9, 0x89, 0x6B,
	0x7B, 0x4D, 0x57, 0xA5, 0x87, 0x80, 0x7A, 0x5C, 0xA5, 0x7F, 0x5D, 0x93,
	0x9A, 0x8A, 0x71, 0x6A, 0x4C, 0x65, 0x83, 0x4C, 0x3A, 0x5C, 0x87, 0x9B,
	0x96, 0x9B, 0x84, 0x5D, 0x5E, 0x4E, 0x58, 0x8B, 0x97, 0xA9, 0xB2, 0x6F,
	0x4C, 0x95, 0xB6, 0x91, 0x80, 0x81, 0x7D, 0x60, 0x6B, 0x94, 0xA5, 0x96,
	0x6C, 0x6B, 0x89, 0x8A, 0x70, 0x96, 0xB4, 0x7C, 0x76, 0xA1, 0xA5, 0x96,
	0x6C, 0x6B, 0x94, 0x97, 0x6C, 0x6F, 0xA2, 0x82, 0x85, 0x8D, 0x69, 0x76,
	0x83, 0xA1, 0x97, 0x7D, 0xB2, 0x98, 0x5A, 0x70, 0x84, 0xA0, 0x97, 0x6F,
	0x78, 0x5F, 0x4B, 0x92, 0x95, 0x7B, 0x82, 0x5F, 0x8F, 0x94, 0x5E, 0x83,
	0x9A, 0x8F, 0x77, 0x6D, 0x56, 0x59, 0x81, 0x5F, 0x3B, 0x52, 0x7B, 0x97,
	0x97, 0x99, 0x8E, 0x66, 0x5D, 0x56, 0x51, 0x7D, 0x96, 0xA0, 0xB2, 0x86,
	0x4F, 0x7C, 0xB3, 0x9C, 0x83, 0x80, 0x80, 0x69, 0x64, 0x89, 0xA1, 0x9C,
	0x78, 0x68, 0x80, 0x8D, 0x76, 0x86, 0xB1, 0x8E, 0x71, 0x96, 0xA5, 0x9B,
	0x79, 0x66, 0x88, 0x99, 0x7A, 0x67, 0x95, 0x8F, 0x7E, 0x90, 0x72, 0x70,
	0x7F, 0x96, 0x9F, 0x80, 0xA0, 0xA7, 0x67, 0x67, 0x7F, 0x96, 0x9E, 0x78,
	0x74, 0x6C, 0x4C, 0x7C, 0x9C, 0x7E, 0x83, 0x68, 0x7B, 0x9C, 0x6A, 0x75,
	0x97, 0x93, 0x7E, 0x6F, 0x60, 0x54, 0x78, 0x6F, 0x43, 0x4A, 0x70, 0x91,
	0x98, 0x97, 0x93, 0x72, 0x5E, 0x5B, 0x51, 0x6F, 0x91, 0x9B, 0xAE, 0x97,
	0x5B, 0x69, 0xA7, 0xA5, 0x88, 0x7F, 0x81, 0x72, 0x62, 0x7D, 0x9B, 0x9F,
	0x83, 0x6A, 0x78, 0x8C, 0x7D, 0x7C, 0xA6, 0x9D, 0x74, 0x89, 0xA3, 0x9E,
	0x85, 0x68, 0x7D, 0x97, 0x85, 0x68, 0x87, 0x96, 0x7E, 0x8C, 0x7C, 0x6E,
	0x7C, 0x8E, 0xA0, 0x87, 0x91, 0xAC, 0x79, 0x62, 0x7A, 0x8E, 0x9F, 0x84,
	0x72, 0x72, 0x53, 0x69, 0x99, 0x86, 0x81, 0x73, 0x6F, 0x98, 0x7A, 0x6B,
	0x90, 0x96, 0x85, 0x73, 0x66, 0x55, 0x6D, 0x78, 0x4F, 0x46, 0x65, 0x88,
	0x97, 0x96, 0x95, 0x7D, 0x62, 0x5E, 0x54, 0x64, 0x8A, 0x98, 0xA7, 0xA2,
	0x6C, 0x5E, 0x96, 0xAA, 0x8F, 0x80, 0x80, 0x78, 0x65, 0x73, 0x94, 0x9F,
	0x8D, 0x6F, 0x72, 0x87, 0x84, 0x78, 0x99, 0xA4, 0x7D, 0x7F, 0x9D, 0xA0,
	0x8D, 0x6F, 0x74, 0x91, 0x8D, 0x6E, 0x7A, 0x96, 0x84, 0x87, 0x84, 0x6F,
	0x78, 0x87, 0x9C, 0x90, 0x89, 0xA8, 0x8B, 0x64, 0x73, 0x88, 0x9B, 0x8E,
	0x74, 0x74, 0x5E, 0x5D, 0x8E, 0x8E, 0x7F, 0x7A, 0x6C, 0x8E, 0x87, 0x6A,
	0x85, 0x96, 0x8A, 0x77, 0x6B, 0x5A, 0x64, 0x79, 0x5C, 0x46, 0x5C, 0x7F,
	0x94, 0x95, 0x95, 0x86, 0x69, 0x5F, 0x58, 0x5D, 0x80, 0x94, 0xA1, 0xA6,
	0x7D, 0x5D, 0x84, 0xA8, 0x96, 0x83, 0x80, 0x7C, 0x6A, 0x6D, 0x8B, 0x9D,
	0x94, 0x77, 0x6F, 0x81, 0x87, 0x7A, 0x8D, 0xA5, 0x89, 0x7A, 0x95, 0xA0,
	0x94, 0x77, 0x6F, 0x89, 0x91, 0x77, 0x73, 0x91, 0x8A, 0x83, 0x88, 0x74,
	0x74, 0x82, 0x96, 0x96, 0x87, 0x9F, 0x98, 0x6C, 0x6D, 0x82, 0x96, 0x94,
	0x7A, 0x74, 0x67, 0x59, 0x80, 0x92, 0x81, 0x7D, 0x6E, 0x82, 0x8F, 0x6F,
	0x7B, 0x93, 0x8E, 0x7D, 0x6F, 0x60, 0x5F, 0x76, 0x68, 0x4B, 0x54, 0x75,
	0x8F, 0x95, 0x95, 0x8C, 0x71, 0x62, 0x5C, 0x5A, 0x76, 0x90, 0x9C, 0xA6,
	0x8B, 0x62, 0x75, 0xA1, 0x9D, 0x87, 0x80, 0x7E, 0x70, 0x6A, 0x82, 0x99,
	0x98, 0x7F, 0x6F, 0x7B, 0x87, 0x7D, 0x84, 0xA1, 0x92, 0x7C
}; 

Step 7: Files

Here's a link to the Files including several .h files containing Audio samples you can try out. The samples were taken from the extensive collection captured by the University of Iowa Electronic Music Studios.