What's wrong with this Average Magnitude Difference algorithm?

Question

I implemented this Average Magnitude Difference algorithm in Javascript

var abs = Math.abs
var floor = Math.floor
var POSITIVE_INFINITY = Number.POSITIVE_INFINITY
function autocorrelation (data) {
  var length = data.length
  var halfLength = floor(length * 0.5)
  var summation = null
  var smallest = POSITIVE_INFINITY
  var smallestOffset = null
  for (var o = 1; o < halfLength; o++) {
    summation = 0
    for (var i = 0; i < halfLength; i++) {
      summation += abs(data[i] - data[i + o])
    }
    average = summation / halfLength
    if (average < smallest) {
      smallest = average
      smallestOffset = o
    }
  }
  return smallestOffset
}

and I use it this way

analyser.getFloatTimeDomainData(data)
var rms = rootMeanSquare(data)
var offset, frequency
if (rms > RMS_MIN) {
  offset = autocorrelation(data)
  frequency = SAMPLE_RATE / offset
}

to find the frequency of the signal input to the analyser.

Signal input is the output from an oscillator. The oscillator's frequency varies from C0 to B8 and I can't always detect the correct frequency. Can you tell me why, please?

Please, find below two images showing oscillator's frequencies and related detected frequencies

Answer 1

okay, i took a look at your code and at your data.

first of all, the algorithm you are using is not autocorrelation but is the Average Magnitude Difference Function (AMDF). it will give results similar to the autocorrelation but upside-down.

you appear to be implementing the AMDF correctly but you are suffering from the so-called "octave error" problem. you see, a note that is, say, A-440, has a fundamental frequency of 440 Hz. that means the waveform repeats every $\tfrac{1}{440}$-th second. but that same waveform also repeats every $\tfrac{1}{220}$-th second and every $\tfrac{1}{110}$-th second or every $\tfrac{1}{55}$-th second. so, mathematically, it can be construed to be a 220 Hz or 110 Hz or 55 Hz (or even a $\tfrac{3}{440}$-th second period or $\tfrac{440}{3}$ Hz waveform).

so you need to figure out how to turn your AMDF upside down and offset it to get peaks instead of valleys. for the math relating AMDF to ASDF and that to autocorrelation, take a look at this and particularly this. you have multiple pitch candidates and you have to elect the correct candidate. don't do it like the Americans did last November.