Part 1. Schematic and construction
The firmware is completely written in C and can be downloaded from the downloads section below. The firmware is split into 4 parts:
ADC Sampling
The ADC sampling routine samples the voltage level on RA0 every 50 uS. This gives us a sampling rate of 20 Khz (20,000 times a second). It is important for the FFT that the samples are evenly and accurately placed. To ensure this there is a small delay in the sampling loop which is calibrated using an oscilloscope on the W4 pin of the demo board. The total duty-cycle of the square wave on W4 should be exactly 50 uS. The ADC is sampled at the full 10-bit resolution and then shifted down by 512 to place the virtual ground of the input signal back at zero. This means that the resulting samples are in the range of -512 to +512 exactly as the FFT mathematics requires.
The ADC sampling routing takes a little over 64x50 uS = 32 mS (3200 uS) in execution time for each loop.
16-bit FFT
The FFT routine was taken from an example found on the web (references to the original code can be found in the source code). FFT maths is complex and I don't pretend to fully understand it! The code was stripped down to the minimum required commands and ported over to the PIC18F. Since the PIC18F4550 has a hardware 8x8 multiplication function within the processor's ALU I also optimised the calculations to allow the compiler to correctly use the chip's capabilities.
The fact that the 18F has a 8x8 hardware multiplier is really the key to how such a low power chip can perform real-time FFT. The cycle-speed advantage even with 16 bit calculations is massive.
Absolute value calculation
The output from the FFT is 32 'complex' numbers which consist of both a real and imaginary part represented by two arrays (you will need to read up about FFTs via Google if you want to know more). In order to show the result in a meaningful way it is necessary to calculate the absolute value of the complex number which is done using a Pythagoras calculation to calculate the complex number's distance from the origin of 0. This involves performing square-root operations on the numbers so the software implements a very fast integer-based SQRT() equivalent since any floating point operations would be way too slow.
The FFT routine and the absolute value calculations combined take approximately 70 mS (7000 uS) for each loop
Updating the LCD
The 128×64 LCD has to be updated as fast as possible. To do this I used a very simple bar graph drawing algorithm which requires the minimum possible number of commands to the display. The routine takes advantage of the way the LCD display is addressed in order to make the update as fast as possible.
The two switches on the PCB allow the user to switch between x1 and x8 magnification of the output (since for music the frequency averages are pretty low) and also either a linear output or a logarithmic output (based on dB). These are simply different ways of showing the output depending on if you want accurate frequency level representations, or more eye-candy based output :)
The LCD update routine takes approximately 45 mS for each update.
Overall FFT speed
The approximate speed of the spectrum analysis display is one frame per 150 mS resulting in an overall frame rate of about 6.5 frames per second (or about 10 FPS without the LCD). This can be easily improved by either reducing the required number of frequency buckets (which would reduce both the sampling and FFT execution times) or by using a display device with a faster update time. If you wished to use the FFT to control LEDs for a colour-organ you could quite easily do both.
Frequency buckets
The FFT's Nyquist frequency (the highest frequency it can detect) is 10 Khz. The 32 frequency buckets are split evenly over the range, however, due to the way the FFT routine works you cannot use the lowest bucket. This means the displayed frequency for each bucket is as follows (in Hz):
- 1 : 312.5 - 625
- 2 : 625 - 937.5
- 3 : 937.5 - 1250
- 4 : 1250 - 1562.5
- 5 : 1562.5 - 1875
- 6 : 1875 - 2187.5
- 7 : 2187.5 - 2500
- 8 : 2500 - 2812.5
- 9 : 2812.5 - 3125
- 10 : 3125 - 3437.5
- 11 : 3437.5 - 3750
- 12 : 3750 - 4062.5
- 13 : 4062.5 - 4375
- 14 : 4375 - 4687.5
- 15 : 4687.5 - 5000
- 16 : 5000 - 5312.5
- 17 : 5312.5 - 5625
- 18 : 5625 - 5937.5
- 19 : 5937.5 - 6250
- 20 : 6250 - 6562.5
- 21 : 6562.5 - 6875
- 22 : 6875 - 7187.5
- 23 : 7187.5 - 7500
- 24 : 7500 - 7812.5
- 25 : 7812.5 - 8125
- 26 : 8125 - 8437.5
- 27 : 8437.5 - 8750
- 28 : 8750 - 9062.5
- 29 : 9062.5 - 9375
- 30 : 9375 - 9687.5
- 31 : 9687.5 - 10000
Conclusions
I've no doubt that both the software and the hardware can be improved. I'm no expert in FFT but I would love to hear any ideas on how to get it going even faster over on my forums. In addition the anti-aliasing filter on the demo board is really not that effective and could easily be replaced by an opamp based filter. I simply didn't want to include any more than the bare minimum hardware to make it all run.
At this point I'd also like to say a special thank-you to my good friend Richard Stagg; without his mathematical perseverance this project would have probably never been completed!
