Single Tone Detection with the Goertzel Algorithm (2012)
embedded.com
embedded.com
Precisely, you can derive Minsky’s algorithm (modified for frequency detection by adding the input samples into the register you produce the output from) from applying Goertzel’s algorithm to the first backward differences of the input signal.
The derivation is in Dercuano in notes/goertzel-minsky-prefix-sums.html. The latest, and probably the penultimate, version of Dercuano is at http://canonical.org/~kragen/dercuano-20191215.tar.gz.
There are some tricks in there for windowing the computation over different timescales, too.
The problem I'm working on requires something that will work well in the presence of chords and even though I've made really good progress I'm still about 4% away from SOTA, but 100's of times faster. Not quite ready to give up.
edit: found a HN discussion on that: https://news.ycombinator.com/item?id=15266331
The HN discussion has some good information, but it also has some mathematical errors.
Presumably you don't mean the School of the Arts or Summits on the Air (though both involve detecting frequencies), so what is SOTA?
I had a background in signals and controls and was familiar with the DFT. Goertzel was a new variant to me but ran much better on the limited resources.
Good memories.
If you are talking about tuning at 441 etc instead of 440, that was easy enough as it was just an input parameter the user set.
These days it would make more sense to use an algorithm that takes harmonics into account and gives you an estimated fundamental frequency, like Miller Puckette's pitch detection algorithm.
It is possible to estimate where a signal is inside the frequency bin; that's how phase vocoders work.
For sharp/flat indication, I'd be inclined to look at the adjacent-bin magnitudes. But it's been explained to me numerous times that tuning an instrument isn't just a matter of measuring its frequency, and while I can't argue with that, I don't think I'm ever going to truly grok it.
1: https://ccrma.stanford.edu/~jos/sasp/Quadratic_Interpolation...
An amusing thought, which surely JOS has explored: if you use a Karplus–Strong delay line as your resonating element instead of a sinusoid, you can take the overtones into account for free. Maybe that reduces to the ACF, minus some kind of normalization. I'm not sure.
It depends on the instrument. If the instrument has only a few , single physical elements per tone generated and the instrument is frequently tuned then you are correct (say a guitar), there is nothing to be done beyond setting the center frequency correctly depending on how you want to tune.
But tuning a piano or harpsichord is a different matter. First of all, there are many different ways of tuning, for instance there is 'stretch' tuning which deals with inharmonicity (sp?) in the higher regions.
It gets more complex when you have multiple physical resonating elements (such as strings), for instance depending on where you are on the piano keyboard you might have one, two or three strings per note called a 'unison' (sound together).
The strings in a single unison not only need to sound good right after tuning, they need to continue to sound good together afterwards and that means that all of them need to degrade gracefully over time as well and that in turn means that they need to lower in tension in a similar way. Good tuners are able to ensure that the string tension is distributed equally between the 'sounding' part of the string (the middle part) and the non-sounding parts (the ends). The amount of tension on the strings and the friction of the pin block and the pins (stick slip) can make this a lot harder than you might think.
Finally, just turning the pins until the frequency matches is going to result in a piano that de-tunes very quickly, the best approach is to go a bit too high and then to slowly lower the pitch while hitting the keys quite hard so that the tension of the string gets distributed evenly.
Added complexity is that the combined 18,000 KG of tension on the frame will cause the tuning of one section of the strings to affect all the others. If a piano is off very far from being properly tuned you may have to make multiple passes to get the job done.
I can’t remember what we did, but we did provide sharp / flat indication. It definitely worked just like a normal tuner you would find, letting you dial it in quite precisely. Maybe I will crack open the code and look at it...
I know I attempted a Goertzel-based pitch detector once, where I looped over frequencies and picked the one with the largest magnitude. I picked 25Hz and 4200Hz as my limits (from a piano).
Unfortunately for my application it did not give an improvement but I thought it was interesting anyway, and on embedded platforms something like this may be your only option.
I've blogged about it here:
https://jacquesmattheij.com/mp3-to-midi/
That's almost two months ago, a lot has happened since then but it gives you a general idea of what I'm up to.
I will take a look at your software, it definitely sounds interesting, the question at the end of https://github.com/sevagh/transcribe/blob/master/doc/snac.md can be answered in the affirmative, the Onsets and Frames package mentioned elsewhere in this thread does just that and works very well.
By the way, the linked paper is unavailable.
I see indeed the link to the Mcleod pitch method paper is dead. I'll see about hosting it in a git repo.
Has the built in ADC of the AVR at 15 K samples/second which should be enough to process a 5 KHz signal.
Simple example: For a 1.0 second audio sample, if the sign changes from +/- or -/+ 880 times, the frequency is 440Hz.
High amplitude noise will also skew results resulting in a higher frequency output. Low-pass or band-pass filter can work wonders.
Again, zero-cross analysis is suitable for simple use cases where you are directly sampling a signal.
Any suggestions on what might be fruitful avenues?
Also found out that convolution can be calculated much more quickly than N^2 (my original concern) by using the Discrete Fourier Transform. The DFT of convolved series is the same as pointwise multiplying the DFT of each series. So, taking the inverse DFT of the pointwise multiplied series' DFTs will give me the convolution with a cost of N log N instead of N^2, if I use the Fast Fourier Transform.
I'll try this out and report back!
"Dr. Thompson peered inside his perfect offspring to gain insight into its methods, but what he found inside was baffling. The plucky chip was utilizing only thirty-seven of its one hundred logic gates, and most of them were arranged in a curious collection of feedback loops. Five individual logic cells were functionally disconnected from the rest— with no pathways that would allow them to influence the output— yet when the researcher disabled any one of them the chip lost its ability to discriminate the tones. Furthermore, the final program did not work reliably when it was loaded onto other FPGAs of the same type."
Still amazing to re-read, and taking this into account it will be a long long time before we can finally say that we have cracked the DNA code and all its gory little details.
What's the 3dB bandwidth of the bin?
In the Dercuano note I mentioned in my comment above, I go into some detail about alternative ways to window.
Will check out that note.
Also, consider implementation in an FPGA where there are decades worth of validated IP to select from vs. this.
In software there is nothing stopping you from changing your Goertzel coefficient, and thus the frequency detected, on the fly.
Yeah, encrypted "intellectual property" that acts like a black box. Pass.