Different-Range FFT Algorithm

lychrel

Member
I'm using Teensy for an application wherein I'll only be analyzing signals of the frequency domain 0 to 1 kHz, and I'd like to have a higher-precision FFT that spans the 512 bins with a smaller frequency-difference between each two. I'm not very good at this sort of thing; could someone point me in the right direction re how to do this?

Thanks!
 
Last edited:
I assume using the audio library? The way you achieve the higher resolution at lower frequencies is to reduce the sample rate Nyquist says 2N for a sample rate where N is the highest frequency of interest. In your case a sample rate of 2khz would give the best resolution. Changing sample rate is not supported with the audio library. I have kludged the library using the ADC input and sampled at 8khz but that was sometime ago and the library is a moving target so might not work now :) Some others (kpc, defragster)? have code that changes the sample rate on the fly but you will have to dig in the forum to find it.

What are you trying to do? It is possible to interpolate values in bins to achieve a much higher resolution.
 
I believe Frank was working on something like this. Maybe he'll chime in?

Something to consider is the FFT's fundamental trade-off between frequency resolution versus update rate. Higher res means fewer updates per second. For example, if you compute a 1024 point FFT (for 512 bins) on 2 kHz sampled data, you're results will span a 500 ms window of time. There's no escaping this fundamental reality of Fourier Transform.

So, assuming you're ok with updates that span lengthy times (good for analyzing steady signals, much too slow for music or speech), you need to get slower sampled data to feed into a FFT. There's 2 ways to do this...

Simply sampling the analog signal slower probably seems like the simplest way, but it actually comes with some really tough problems if the signal is audio. With a slow sample rate, you must filter away content above half the sample rate. As simple as that sounds, it's actually quite difficult to do. In fact, it's so hard that virtually all ADCs designed for audio using massive oversampling and then they digitally filter the data while reducing it to the desired sample rate.

The other way, which involves a lot of numerical processing but avoids tough analog circuit design, is to digitally filter the already sampled 44.1 kHz data. Even though this seem like a lot of work (and indeed it is a lot of work for the CPU), I'd recommend taking this approach. The audio library already has 3 known-good digital filter objects. So if your goal is a 2 kHz sample rate, you can use those filters to get rid of everything above 1 kHz. Filtering is never a perfect "brick wall", so the filtering involves trade-offs, where you'll need to attenuate some frequencies (perhaps 700 to 1 kHz) in order to get everything above 1 kHz sufficiently removed.

Once you're filtered away the too-high frequencies, then all you have to do is keep every Nth sample and discard the rest. For example, you could keep every 22nd sample and throw away the other 21, to end up with 2.0045 Hz sampled data. The simplest way to do this would be to receive data from the audio lib using the record queue object. See File > Examples > Audio > Recorder. Except instead of writing the data to a SD card, you'll just pick several samples from each 128 sample buffer. You'll probably just copy them into your own 1024 sample buffer. Keep repeating until you've filled up all 1024 samples. Then run that through the ARM Math Library arm_cfft_radix4_q15() function. See the audio library's FFT1024 code for an example, where it fills a 1024 sample buffer from the last 8 buffers of 128 samples. You'll do the same, except you'll discard most of the samples and only use 5 or 6 from each 128 (taking care to remember the index between buffers, so you always grab the 22nd sample from the stream). The arm_cfft_radix4_q15() gives you complex pairs of numbers (real and imaginary), so if you only want the magnitude, take the square root of the sum of their squares. Again, refer to the library source for an efficient integer square root. You can probably just copy that code into your program.

The key point is you absolutely must digitally filter the signal before you discard 21 of every 22 samples. The digital filtering is what causes every 22nd sample to properly represent your signal. If you just take every 22nd sample without filter filtering, you'll get absolutely horrible results (assuming your signal is common audio or other content with higher frequencies present).
 
I was looking at this when KPC was doing FFT work and Paul provided a better summary than I could of what I learned and direction - though other forum notes may have useful details. The sound FFT I was considering was secondary to my needs and seeing that higher resolution took longer to sample over a smaller frequency without dropping the cpu burden enough to let run after I needed it. Unfortunately my primary focus went to a ESP8266 based Kickstarter item that skipped my Beta hardware release for improved software - then slipped on shipping due to other outside events.
 
I'm using Teensy for an application wherein I'll only be analyzing signals of the frequency domain 0 to 1 kHz, and I'd like to have a higher-precision FFT that spans the 512 bins with a smaller frequency-difference between each two. I'm not very good at this sort of thing; could someone point me in the right direction re how to do this?

Thanks!

could you please explain a little bit more your problem.
you are saying frequency domain 0 to 1 kHz with 512 FFT bins, so the frequency resolution is about 2 Hz.

So what is the problem?
Is it that you use the Paul's audio library that samples at 44.1 kHz?
or do you have any other fixed sampling rate?

In all cases, before doing the FFT you have to (down) sample the data to a sampling rate of about 2kHz for a 1024 point FFT or better to about 4 kHz for a 2048 point FFT.
So if you sample at 44.1 kHz, then decimating by 11 (apply LP filter with 1/11 cutoff filter (similar to matlab) and take every 11th sample), you would end up with 4.01 kHz and a 2048 point FFT gives you a frequency resolution of about 2 Hz.

Unfortunately Paul's audio-library has not implemented both decimation and 2048 point FFT. The implementation of such features would, however, be not difficult.

Also a block size of 128 is somewhat inconvenient for a decimation of 11. Better would be a block-size that is a multiple of the decimation factor. However if you where happy with a resolution of 2.7 Hz, a decimation of 8 would nicely fit into the buffer.
 
lychrel – Audio pitch detection is a key part of my application. My evolving understanding of FFT (and Teensy’s use of it) may help you. I hope others will confirm my understanding (or refute/improve), and help me extend it.

Here’s my train of thought:

FFT is a specialized flavor of a DFT (discrete Fourier transform).
  • A fairly-readable overview can be found at: blogs.mathworks.com/steve/2014/09/23/sinusoids-and-fft-frequency-bins/
  • (I’ve read a dozen such overviews over the last year… I’ve found that my view of “fairly-readible” evolves.)

There are key characteristics (constraints) of FFT and the Teensy Audio Library when being used for audio frequency discovery:
  • Paul S. chose to leverage the sampling rate of 44,100 to be equal to an audio CD’s sample rate. Choosing a single sample rate throughout the audio library allowed simpler design, when compared with a flexible sample rate.
  • When using FFT, the maximum detectible frequency is ½ of the sample rate (someone named Nyquist gets credit for asserting this). This determines the maximum frequency discoverable by Teensy’s Audio Library at 44,100/2 = 22,050 Hz.
  • FFT uses a concept of “bins” to store frequency “hits” as it uses math to estimate one or more sine waves that, if added together, would reproduce the input sound wave.
  • - The number of bins used by FFT is flexible, and the Audio Library offers two options: 256 and 1024 bins. Choosing a number of bins that is a power-of-two allows dramatic math efficiencies – making it the fast Fourier transform (FFT). In these power-of-two cases, many of the calculations can be skipped, since many calculations amount to “multiplying by 1.”
  • The FFT “bin size” is calculable by [Sample Rate]/[Number-of-Bins]. So, on Teensy Audio, using the FFT1024 object, bin size = 44.3 Hz/bin (from 44,100 Hz/1024 bins).
  • [Disclaimer: my chosen terms may not be precise – audio engineers please correct me where it adds value. I hope my high-level picture is correct, despite imprecise terms]
  • With a bin size of 43 Hz, I have been able to detect the pitch of sine waves above about 200Hz, with roughly 1% accuracy. (That is, with an input sine wave of 440 Hz; fed into an FFT1024; plus some additional calculations… I arrive at a frequency between 436 and 444 Hz).
  • Below about 5 times the bin size, frequency determination is more variable or impossible in my hands.
  • Smaller bin size (and presumably, lower detectible pitch) can be achieved by changing one of the two numbers that affect bin size:
  • Increase number of bins – 1024 is maximum easy bin number in Teensy Audio
  • Decrease Sample Rate (paradoxical, but true) – Sample rate on Teensy Audio is fixed at 44,100 in Teensy Audio

So: to do this using FFT1024 in Teensy Audio, Paul suggests that our best choice is to decimate (maybe not the precise word) the samples. Decimating in powers of 2 provides some advantages in tracking the sample batches (use every 2nd sample, every 4th sample, every 8th sample, etc.).
Teensy offers a batch size of 128 samples.

Decimation is not built in to the Audio Library, but could be added (I think). It would require using a pair of “queue” objects – one of output type and one of input type – doing the decimation between the two queue objects.

The following table lists the possible results of decimation on parameters that matter to my solution:
Decimation Table.jpg

Hence the trade-off between low-note-detectability (small bin size), and time-to-acquire-sample.

In parallel, here’s what I’ve found for frequencies of some musical inputs:
Trumpet (or soprano voice): Min: 160 Hz Max: 1880 Hz
Trombone (or bass voice): Min: 80 Hz Max: 700 Hz
Tuba 40 Hz? one octave lower?​

So, for my brass instrument work:
  • I’d like to detect pitch correctly down to less than 100 Hz (to use the full range of trumpet or trombone)
  • I want to be able to detect a note change as fast as possible. In the case of a trumpet, faster than 10 times per second would be best. Good trumpet players can run scales at least that fast.
  • So my conclusion: For a trumpet pitch detector, I think want to decimate by 2, resulting in a 100 Hz lowest-detectible-pitch, and a time-to-collect-samples of 46.4 ms.

For this reason, I think it’s worth implementing the queue→decimate→queue concept.

It must be fast – in addition to the time to decimate, code on the Teensy will need to do the following:
- sample-acquisition time (table above),
- FFT calculation (audio library)
- FFT interpretation (my code)
- Other application processing (my code)

Paul and other experts… am I on the right track?

Dave
 
Last edited:
So, for my brass instrument work:

  • I’d like to detect pitch correctly down to less than 100 Hz (to use the full range of trumpet or trombone)
  • I want to be able to detect a note change as fast as possible. In the case of a trumpet, faster than 10 times per second would be best. Good trumpet players can run scales at least that fast.
  • So my conclusion: For a trumpet pitch detector, I think want to decimate by 2, resulting in a 100 Hz lowest-detectible-pitch, and a time-to-collect-samples of 46.4 ms.

hmmm, i wrote library that plugs into the audio library for finding the fundamental frequency down to 29.14 Hz. I use it in my bass and guitar tuner project with good results. It based off the YIN algorithm. Another problem with using FFT for finding musical instrument pitch is the magnitude of the fundamental can be lower than the overtones. Also see Goertzel algorithm even then you have to make some assumptions because I can say for certain that with real instruments I have a hard time deciphering the fundamental frequency from the overtones but its really fast.
 
That's great, duff!
I'll give it a look.
How might I have found your library, short of writing an extended tome as I have here?
I hope it is what I've been looking for!

Is there a similar Goertzel-using Teensy Audio add-on?

Dave
 
Is there a similar Goertzel-using Teensy Audio add-on?
yes the DialTone_Serial example. The Audio Libraries Goertzel implementation has problem at low frequencies but anything above ~440Hz it does a good job. I wanted to look into this but never did, maybe this is something worth looking into since its data processing is so much faster than the Yin. Plus at frequencies > 1000Hz my implementation of the yin does not do a great job, I just "tuned" it for guitar and bass tunning frequencies. Most likely won't look into expanding it beyond that since I don't have a lot of time right now.

This looks great! How fast are you able to detect the fundamental frequency?
~70ms, this is because I needed to detect low frequencies (29.14Hz) so there is no way to get around that. You have to acquire enough of the signal for analysis. You can edit the number blocks to processes to speed up the detection rate here at the cost of not being able detect lower frequencies.

And do you detect more than one frequency? Like a chord?
No, its for single notes but you can use the passband filter then feed that to the tuner object. I haven't tied this yet though. There are probably many preprocessing techniques you could do before feeding it that processed signal but will add additional latency.

If your lowest frequency in the chord is greater than ~440Hz then you could use multiple goertzel but then you would need a lot of them.

Realtime chord detection is probably beyond the processing capabilities of the Teensy 3.1/2, maybe when the Teensy 3++ comes out it will have enough horsepower to make this possibilty? Though I could be wrong maybe the FFT would be able with lots of post processing?

Found this site that seems to be on track: http://www.instructables.com/id/Reliable-Frequency-Detection-Using-DSP-Techniques/
Is this what you are doing
Yes, it use's Auto Correlation with a bunch error correction techniques to get around the false positives of just using the auto correlation. The nice thing with the Yin algorithm is that it is amplitude agnostic in that the natural decay of the signal does not effect the outcome within reasonable limits.
 
Last edited:
Thanks for the answers! Will test this later when I am home...
I am trying to make a octave down effect for bass guitar. Then I would divide the frequency by 2(one octave down) or 4 (2 octaves down). Then the lowest frequency that should be detected is 40Hz or 80Hz. No point to generate frequencies below 20hz anyway.. Then this might speed up to a usable speed! it needs to be around 10ms to avoid a "lagging" feeling when you play the instrument.
With fretted instruments I guess we also can look at the harmonics of the fundamental freq and detect that faster (and accurate) then the actual fundamental frequency and then use FFT to check if there are lower components. If that is faster..?
 
I'm thrilled to see this activity around fundamental pitch detection on the forum.
I'd like to see a summary of the best uses for each (FFT1024, FFT256, YIN, Goertzel), and for each:
- time to acquire frequency in freq range X, Y Z, etc.
- most accurate frequency range
- precision to expect
I'll do this for my own use, and will plan to share it as it evolves.

I have a question (for Paul or duff), regarding the available() method (on the FFT1024 and the AudioTuner objects).
Does each call to available() create a snapshot of the acquired data - until the next call to available?
Without that, I could see the reading of the data (in my loop) conflicting/overlapping with filling of data from the interrupts.

Paul or Jeff?
 
well 40Hz needs 25ms to cycle once, how would a FFT be able to process this 10ms after you pluck the string? Remember Nyquist rate thing also! Not sure how to reliably detect the harmonics and relate that to the fundamental? I'm sure its possible but how much processing does it require? That might eat up just as much time than going for the fundamental?

Thats why the bass is so hard to make good digital effects for. I personally have been playing bass for 20 years and don't use any effects because in my opinion they just muddle the sound esp. playing in the low registers. Sometimes I use compressor on certain rigs and I gig once in while using a bass wah for solos with a punk band but we where so loud I could be muddled and not bother with a good clean sound.
 
I have a question (for Paul or duff), regarding the available() method (on the FFT1024 and the AudioTuner objects).
Does each call to available() create a snapshot of the acquired data - until the next call to available?
Without that, I could see the reading of the data (in my loop) conflicting/overlapping with filling of data from the interrupts.
I can't speak for the FFT but for AudioTuner object when "available" is true it has found the fundamental for the last 24 blocks of data it has just processed and then just processes the next 24 blocks. Well, it processes the blocks while collecting the next 24 blocks technically. It dose not use sliding window like the FFT either meaning half of the buffer is from the already processed data, I'm sure there is much more to this than I have a clue about too:)

With my AudioTuner object you don't get access to the raw data since it is only is looking for the largest dip when doing the AutoCorrelation and error correcting techniques. Plus that would require another buffer that eats up precious ram.

As far precision I was getting around 1 cents for real signals.
 
Last edited:
I just did some timing tests...

I can run a loop using fft1024 every 11ms. I do this with a delay(10) in my loop.
As I use delay() shorter than that, I'll get available()=false... More and more as I get shorter.

That's roughly twice as fast as I would expect (see my post above), perhaps because Paul is reusing half of the samples each cycle (is this true?)

Regardless, at this pace, I can detect the fundamental of a trumpet mouthpiece buzz down to 160 Hz... And it seems very reliable. Good for trumpet. Not for trombone.

I'll be looking into the flakier detection below 160, but this is good stuff!

Side note... I spent several hours tracking down rather violent noise in my system... Until I realized I had added one too many Audio library objects, and had not appropriately checked or increased audio memory.

So, out of memory equals, at least, noise.
 
well 40Hz needs 25ms to cycle once, how would a FFT be able to process this 10ms after you pluck the string? Remember Nyquist rate thing also! Not sure how to reliably detect the harmonics and relate that to the fundamental? I'm sure its possible but how much processing does it require? That might eat up just as much time than going for the fundamental?

Thats why the bass is so hard to make good digital effects for. I personally have been playing bass for 20 years and don't use any effects because in my opinion they just muddle the sound esp. playing in the low registers. Sometimes I use compressor on certain rigs and I gig once in while using a bass wah for solos with a punk band but we where so loud I could be muddled and not bother with a good clean sound.

You have some good points!
Are your code detecting the frequency with the highest amplitude?
According to this site: http://www.puremix.net/blog/musical-instruments.html that can lead to some things.. Seems like the 3rd harmonics from a typical bass is higher in amplitude then the fundamental. But we can also see that it is possible to know the fundamental if we know the 2nd and 3rd harmonics. -> common multiple. Or do you filter/remove the harmonics?
Think I read somewhere that if the brain hears the harmonics it "hears" the fundamental even if its not there. Have not tested that=)
 
Last edited:
Are your code detecting the frequency with the highest amplitude?
No, but if harmonics amplitude are much greater than fundamental there would be problems, I find that this not an issue with the instruments i've tested thats why it works good for my guitar tuning project which is on hold now cause I got cute little baby to look after:). Mom works 14 hours a day for her fellowship so i'm Mr. Mom now.

According to this site: http://www.puremix.net/blog/musical-instruments.html that can lead to some things. Seems like the 3rd harmonics from a typical bass is higher in amplitude then the fundamental.
cool site, thanks for sharing, theory is not my strong point I'm trying to learn though, i used to work at a engineering department so lots of brilliant profs and students to bounce ideas off, but not anymore since i moved:(.

But we can also see that it is possible to know the fundamental if we know the 2nd and 3rd harmonics. -> common multiple. Or do you filter/remove the harmonics?
No, there is no filter, but i do use filter objects (low pass & band pass) before feeding it to the AudioTuner object for my tuner project which helps with aliasing and such. I haven't come across any project that use the harmonics to find the fundamental in a realtime system but if you do please share! My next project is to interface the teensy with 1Wamp for electric guitars which will be awesome i think since it has a mp3-aux input. I have that problem of not finishing one project before starting another!

here are some links i used for code and analog:
http://sound.eti.pg.gda.pl/student/eim/synteza/leszczyna/index_ang.htm
http://www.musicdsp.org/index.php
http://cnx.org/contents/i5AAkZCP@2/Pitch-Detection-Algorithms
http://www.phy.mtu.edu/~suits/NoteFreqCalcs.html

http://www.radio-electronics.com/info/circuits/opamp_band_pass_filter/op_amp_bandpassfilter.php
http://sim.okawa-denshi.jp/en/Fkeisan.htm
 
No, but if harmonics amplitude are much greater than fundamental there would be problems, I find that this not an issue with the instruments i've tested thats why it works good for my guitar tuning project which is on hold now cause I got cute little baby to look after:). Mom works 14 hours a day for her fellowship so i'm Mr. Mom now.
Enjoy! Its a good time (to do guitar boxes...) and everything else that needs to be done!

No, there is no filter, but i do use filter objects (low pass & band pass) before feeding it to the AudioTuner object for my tuner project which helps with aliasing and such. I haven't come across any project that use the harmonics to find the fundamental in a realtime system but if you do please share! My next project is to interface the teensy with 1Wamp for electric guitars which will be awesome i think since it has a mp3-aux input. I have that problem of not finishing one project before starting another!

here are some links i used for code and analog:
http://sound.eti.pg.gda.pl/student/eim/synteza/leszczyna/index_ang.htm
http://www.musicdsp.org/index.php
http://cnx.org/contents/i5AAkZCP@2/Pitch-Detection-Algorithms
http://www.phy.mtu.edu/~suits/NoteFreqCalcs.html

http://www.radio-electronics.com/info/circuits/opamp_band_pass_filter/op_amp_bandpassfilter.php
http://sim.okawa-denshi.jp/en/Fkeisan.htm

Good links you have there! Will dive into that.. And the 1Wamp seems like a nice fellow. Maybe not for concerts but more for the living room?
Regarding fast detection of the fundamental I think I will try to make several bandpass filters and then run the tuner on them to get several peaks. Not sure if that will be faster though when I have to use multiple tuners..? will see!
 
sure! I hope people find it useful.

I've merged this into the audio library. I took some small liberties, mainly to renaming the fit the library and Arduino naming conventions.

One quick question: internally the library has a "periodicity" variable. Maybe that was meant to be "probability"?
 
I've merged this into the audio library. I took some small liberties, mainly to renaming the fit the library and Arduino naming conventions.

One quick question: internally the library has a "periodicity" variable. Maybe that was meant to be "probability"?
yes, this confusing but I look at it as the probability of the periodicity of the signal not just a strict mathematical definition of probability. So for example if the signal is somewhat or vary aperiodic such as the frequency is changing with time or noisey, this would exhibit low or no periodicity which should looked at with skepticism of algorithms found frequency. So I think just using probability would be fine for the name of that variable.

I admit that my math is not so strong to define this correctly but from my reading, it should be fairly correct, hope that makes sense.


I made a first attempt at documentation. Here it is:

http://www.pjrc.com/teensy/gui/?info=AudioAnalyzeGuitarTuner

Hopefully I didn't butcher it too badly? Let me know if anything should be corrected or if you'd like to add anything?
Wow I haven't looked at the gui tool in a while, very nice! The description looks good, I don't think any changes needed, thanks for adding this.
 
Back
Top