[Simon Inns] just rolled out his latest project, a PIC based spectrum analyzer. He’s using a Fast Fourier Transform routine crafted in C to run as efficiently as possible on the 8-bit chip. The video after the break shows that the results are quite pleasing, with just a bit of noticeable lag between the sound and the waveform representation on the graphic LCD. We found his notes about using an audio amplifier chip to be interesting. He utilizes the properties of an LM386 to move the input signals from a range of -0.5V to +0.5V into a very ADC friendly range of 0-5V.

It never seems to end, Fourier’s failed attempts to predict the weather have so many functions in real-world applications. They are useful for voice recognition engine management even in models used to predict the weather! I guess he actually did eventually help predict the weather after all.

I picked up two books on the subject recently A translation from Russian that was almost incomprehensible until I read (Fourier For dummies)

If you can find the dummies book grab it. If you already have a math degree go for the russian translation.(sorry I don’t have the author name handy, but how many Russian/English translations of dead French mathematicians could there be at Barnes and Nobel?

Well i was thinking about beat detection for uCs some days ago.

Maybe i can get some more speed out of it with another uC and some sacrifices ;)

Thanks for sharing this!

Hello Nippey,

I am Rene from Germany. I am also looking for a good beatdetection with a mikrocontroller. We are developing small LED lighting effects. Maybe we can share things.

Thank u in advance

Rene

@ Trollicus: You mean this book http://search.barnesandnoble.com/Fourier-Series/Georgi-P-Tolstov/e/9780486633176/?itm=3&USRI=fourier#TABS ?

Why on earth isnt he using a DS series pic.

DS = Digital Signal.

Instead of using a subroutine to do this, he could be outsourcing it to a specific module on the pic !

They have a built in FFT Module.

you are wrong my friend none of the micro pics DS or not have a built in FFT modules

OMG YES!

@Alex,

Yes, he could have use dedicated hardware. But where is the challenge? He did a nice job with just software!

Aggreed :)

But, Come on, have you seen how thick a book on FFT Algorithms are!.

Then to implement that on a PIC18 !

I am Agreeing, that it is a neat feat.

Good job!

It just needs a faster screen with at least 32 shades/colors so it can be a scrolling spectrogram (aka “voice-print”). They’re much cooler.

Amos, the screen is not the cause of the ‘lag’. The reason is the calculation and interpretation of the FFT (+ driving and drawing on the LCD).

Another RTA that fails to interpret music.

Every software or hardware RTA except the expensive ones seems to treat the audible spectrum as decimal math, when in reality, it must be treated like “Johann Sebastian Bach math”, where the fundamental part is the sequence of octaves, each twice as large as its predecessor in Hz.

For the desirable resolution of 1/3 octave, ISO standardises this as the R10 series, which we also know from resistor values.

A RTA that divides spectrum into frequency chunks, all alike, lacks resolution in the low frequency bands (where it is really needed) and wastes resolution in higher frequencies, where it matters less. I want to know from an analyser whether it is 63 or 80Hz that mess upp, but a resolution of 17Hz around 6K3Hz is not going to be of any use for musical or audio related measurements.

I did some calculations to distribute the frequency bins logarithmically to treat the audio spectrum properly, like “J.S. Bach”.

Suppose the following are given:

Fs: sampling frequency

Flow: lowest non-zero frequency bin (e.g. 20 Hz)

N: number of bins in FFT (keep in mind this is the total number of positive and negative frequency bins, so the actual number of bins displayed is N/2+1, for 0 to Fs/2 Hz)

Then compute the following:

a = (log10(Fs/2) – log10(Flow))/(N/2-1)

b = log10(Flow)-a

Fk = 0, if k = 0

= 10^(a*k+b), if k = 1,2,…N/2

= Fs – 10^(a*(N-k)+b, if k = N/2+1,…N-1

finally, k’ = N*Fk/Fs

Use k’ in place of k to compute the Twiddle factors (http://en.wikipedia.org/wiki/Twiddle_factor) for the FFT algorithm. That is, W_k = exp(2*pi*i/N*k’). Now you have logarithmically spaced frequency bins in your FFT.

I have no experience implementing the FFT efficiently, so I don’t know how hard this approach would be to implement on hardware, let alone something as resource-constrained as a PIC18.

@mansaxel: thanks for interesting insight.

And here’s the rather old but still cool analyzer by Elm-Chan: http://elm-chan.org/works/akilcd/report_e.html

Very nice result.

Now just port it over to an avr and enjoy

twice the speed :D

waveform != spectrum

Flip the ADC to 8 bit (from 10) and that will more than double the performance. I doubt 10 bits of resolution is required.

Nice, rarely do yo get to see fts in embedded projects

The Discrete Hartley transform maybe shave off some time as it is like the fourier transform, but deals with real inputs and real outputs. Pruning out the computation leading to redundant bins could reduce the time a smidge, but just isn’t worth the time to spend. I’d wouldn’t be suprised if pruning only leads to a 1% reduction in calculations if only the top bins (that are complex conjugates of other bins) are thrown out. I don’t know how much the DHT would save in comparison to the FFT.

The square root routine probably could be chopped to be just real^2+imag^2 as only the visual output matters in the end. The tables used for the linear scale and log scale output would have to be updated to reflect this change. I would expect this to be fairly appreciable change in speed, but I’m sort of expecting a memory increase.

Nice work.

Oh, and “mansaxel,” don’t worry. Adjusting the bins is not really a big problem. Decimal, octave, whatever. You write the code, you pick the bins. Octave bins is actually much _easier_. Actually requires _less_ math than decimal with integer samples.

@Jons

Actually, you (well, I, anyway) can see both the 10 Hz update caused by the processor speed /and/ the blur caused by the passive-matrix nematic LCD–the latter being what I was referring to.

I’m aware that the spectrogram would still only be updated at 10 Hz, but with that blurry screen it would just be a soupy fog with little discernable information.

@mansaxel,

Sounds like you want to use the discrete wavelet transform. It does exactly what you describe. Back in the early ’90s, I implemented a “wavelet analyzer” using a floating-point DSP. A wavelet transform can be done with integer math as well. In fact, the wavelet transform has less complexity, O(n), than an FFT, O(n log2(n). The execution time, though, depends upon the length of the wavelet functions used. They are, effectively, half-band finite impulse response filters. Do a Google search on wavelets and you’ll find a lot of material out there, including source code, libraries, and programs.

It is awesome that he was able to implement something that complex that I’m just now learning about in college on a PIC18. Though my real question at this point in time is what is that stand thing he’s using to hold the LCD and where can I get one?

I don’t pretend to be an expert in FFT or audio analysis, but I could see many uses for something simple that can detect frequencies in sound without requiring a complex processor. The concept behind the hardware/software was just to prove it could be done and show how. I’m hoping that, by realising it open source, other fellow hackers will help make it better and I welcome any suggestions (especially in the form of source code)!

@tripp – That’s a Weller ESF-120 anti-static PCB holder.

Argh… World, stop reminding me to study some more.

This is exactly what my math exam will be about ._.

@ dmcbeing

Elm-Chan’s one does it with an AVR and same performance but doesn’t need to run at 48MHz to acheive this ;-)

Elm-Chan does it at 16MHz, consuming 2.5 times less current, but keep saying PICs are the best ^^

AAAH! Warn someone before you go blasting loud sine sweeps on your vid!

Most of the challenge of FFT is understanding the algorithm and what it does. The actual code for it is less than terrible, even on a PIC platform.

That said, keeping it all going while driving the display that smoothly on an 8-bit platform is impressive.

ftorama:

PIC here runs at 12MIPS, Elm-Chan’s implementation runs ATMega at 16MIPS.

PIC18F4550@48MHz(12MIPS) draws 25mA@5V typical, ATMega8@16MHz(16MIPS) draws 20mA@5V typical.