Problem with FFT

I've been trying to learn how to implement FFT using Arduino for a project (Assembly or C). Been reading about FFT for a while but I'm still confused and I don't have the concrete idea of how FFT is implemented. I came across this old forum post here: http://forum.arduino.cc/index.php?topic=38153.0 (Modified 8bit FFT in c)

Where can i get the value for these constants and What are they for?

const prog_int8_t Sinewave[N_WAVE-N_WAVE/4] PROGMEM = { 0, 3, 6, 9, 12, 15, 18, 21, 24, 28, 31, 34, 37, 40, 43, 46, 48, 51, 54, 57, 60, 63, 65, 68, 71, 73, 76, 78, 81, 83, 85, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 109, 111, 112, 114, 115, 117, 118, 119, 120, 121, 122, 123, 124, 124, 125, 126, 126, 127, 127, 127, 127, 127,

127, 127, 127, 127, 127, 127, 126, 126, 125, 124, 124, 123, 122, 121, 120, 119, 118, 117, 115, 114, 112, 111, 109, 108, 106, 104, 102, 100, 98, 96, 94, 92, 90, 88, 85, 83, 81, 78, 76, 73, 71, 68, 65, 63, 60, 57, 54, 51, 48, 46, 43, 40, 37, 34, 31, 28, 24, 21, 18, 15, 12, 9, 6, 3,

0, -3, -6, -9, -12, -15, -18, -21, -24, -28, -31, -34, -37, -40, -43, -46, -48, -51, -54, -57, -60, -63, -65, -68, -71, -73, -76, -78, -81, -83, -85, -88, -90, -92, -94, -96, -98, -100, -102, -104, -106, -108, -109, -111, -112, -114, -115, -117, -118, -119, -120, -121, -122, -123, -124, -124, -125, -126, -126, -127, -127, -127, -127, -127,

/*-127, -127, -127, -127, -127, -127, -126, -126, -125, -124, -124, -123, -122, -121, -120, -119, -118, -117, -115, -114, -112, -111, -109, -108, -106, -104, -102, -100, -98, -96, -94, -92, -90, -88, -85, -83, -81, -78, -76, -73, -71, -68, -65, -63, -60, -57, -54, -51, -48, -46, -43, -40, -37, -34, -31, -28, -24, -21, -18, -15, -12, -9, -6, -3, */ };

empty213: Where can i get the value for these constants and What are they for?

This is a lookup table for the value of sin(x*K)*127. The values are as you see them here.

The OpenMusicLabs websit has quite a bit of information and several FFT/FHT programs for you to try. http://wiki.openmusiclabs.com/wiki/ArduinoFFT

Be sure to read the fine print, for example:

The serial output of the examples is in binary, not ASCII. This means it will not be human readable on the serial port. Change serial.write() to serial.print() to fix this. You may need to write a for() loop to manually output each frequency bin.

Put look up tables into program memory, as you will run out of ram if you don’t.

thanks for the quick answers!

if i connect my audio input signal to Analog 0 of Arduino Uno, in using the OpenMusicLab FFT Library, what does the N - number of samples mean? Is is it the readings in the ADC? Just wanted to say again that I'm new to Arduino and still a student, does N (number of samples mean 256 readings on serial port if i go to Arduino IDE -> Tools -> Serial Monitor?

I'm kinda confused where do i get the samples if i wanted to input an audio signal say from my phone to the arduino -> perform FFT -> display (amp and freq) using LED Matrix.. I know there are ICs available that can do this, but for an academic requirement I need to understand FFT and then implement the algorithm in assembly.

also, is the look up table always a sine wave? Thanks,

The FFT works on (transforms) an array of N numbers. For audio signal processing you might choose N to be 128 or 256.

You cannot sample audio signals directly from the Arduino, as they are AC voltages and the inputs to the ADC must be positive voltages. A DC offset is required. See this example circuit http://interface.khm.de/index.php/lab/experiments/arduino-realtime-audio-processing/

jremington:
The FFT works on (transforms) an array of N numbers. For audio signal processing you might choose N to be 128 or 256.

You cannot sample audio signals directly from the Arduino, as they are AC voltages and the inputs to the ADC must be positive voltages. A DC offset is required. See this example circuit http://interface.khm.de/index.php/lab/experiments/arduino-realtime-audio-processing/

thanks, this was really helpful… so i’m guessing 127 is from the datasheet of the Arduino Uno? But what is 127? 127 mV?
the output of the ADC are my samples right?

for an academic requirement I need to understand FFT and then implement the algorithm in assembly

When do you have to have this done? Writing an FFT in assembler when you don't even understand what an FFT is, is going to be mighty difficult.

Pete

I agree with Pete. The first step is to understand what a Fourier transform is, and Googling for "fourier transform" brings up 1.2 million pages. Plenty of reading material! Try this one: http://www.thefouriertransform.com/

It is very simple to implement a classical Fourier transform and I would recommend to start there.

However, it is slow to calculate the standard Fourier transform, so various people have developed and refined the Fast Fourier Transform, which is much more complicated to implement.

el_supremo:

for an academic requirement I need to understand FFT and then implement the algorithm in assembly

When do you have to have this done? Writing an FFT in assembler when you don't even understand what an FFT is, is going to be mighty difficult.

Pete

Still have about a month's time to do this..

jremington: I agree with Pete. The first step is to understand what a Fourier transform is, and Googling for "fourier transform" brings up 1.2 million pages. Plenty of reading material! Try this one: http://www.thefouriertransform.com/

It is very simple to implement a classical Fourier transform and I would recommend to start there.

However, it is slow to calculate the standard Fourier transform, so various people have developed and refined the Fast Fourier Transform, which is much more complicated to implement.

I've been reading and my question does not pertain to how to do FFT as it can be learned through reading but with specifics on Arduino-FFT matters like I'm just confused on what are those N-samples, are those the readings on the ADC?

The N samples can be anything you want. Quite obviously, if you download and inspect the FFT code from Open Music Labs, the samples are ADC readings

Thanks! <3 :slight_smile:

Can someone help me? I'm kind of confused on how to get the Real and Imaginary coefficients using Arduino Uno.. From what i understood, from the input audio signal the ADC ouputs a corresponding value between 0-1023, I don't know where to get the real and imaginary coefficients to perform FFT on..

Thanks in advance!

If you are using this function:

int fix_fft(char fr[], char fi[], int m, int inverse);

Then the array fr[] initially contains your audio samples (in the range -128 to 127) and the array fi[] is set to zero, initially.

When fix_fft is done, it returns numbers in the arrays fr[] and fi[]. You can interpret those numbers by calculating

amplitude = sqrt(fr[i]*fr[i] + fi[i]*fi[i]);

where amplitude is the "amount" of pure sinewave tone at frequency index i, in the original audio sample. It is only in the case that you are doing an inverse FFT that you need to worry about the imaginary components.

but theoretically I'd like to confirm if what I think is right --- that is, to get the real and imaginary input values, the ADC readings needs to be multiplied by a cosine function for the real and a sine function for the imaginary, where the there's a lookup table for both cosine and sine?

Edited: Also I have a few confusions I want to ask for confirmation, I'm currently analyzing the Arduino FFT Library from Open Music Labs - http://wiki.openmusiclabs.com/wiki/ArduinoFFT to reaffirm what I got from reading about FFT. I downloaded the library, based on the read me file

the final output is kept in fft_input[], with the even bins being the real magnitude, and the odd bins being the imaginary magnitude. the bins are in sequence of increasing frequncy. for example:

fft_input[0] & fft_input[1] = bin0 magnitudes (0hz -> Fs/N) fft_input[2] & fft_input[3] = bin1 magnitudes (Fs/N -> 2Fs/N)

in the above code, fr[] is fft_input[] with even bits, and fi[] are the odd ones.

if I wanted to synchronize a matrix of LED to the audio input and I have 256 samples I will get 255 bins and 255 frequencies, does it mean that I need 255 columns, 1 columns for each frequency? or can I skip what I don't want to use? is it possible to have 2 columns for 1 frequency? also, do i send the amplitude directly to a LED driver IC?

but theoretically I’d like to confirm if what I think is right — that is, to get the real and imaginary input values, the ADC readings needs to be multiplied by a cosine function for the real and a sine function for the imaginary, where the there’s a lookup table for both cosine and sine?

That is exactly what the Fourier transform does. A lookup table just saves some computing time. A cosine table is also a sine table, with the index shifted by 90 degrees.

If you have 255 entries in the transform, you can group them any way you want to create a smaller number of audio bands. You can add the magnitudes of several output terms together. For example, to produce 127 magnitudes from 254 frequency entries:

for (int i=1;  i<256; i+=2) {  //i=0 is the DC offset
mag = sqrt(fr[i]*fr[i] + fi[i]*fi[i]) + sqrt(fr[i+1]*fr[i+1] + fi[i+1]*fi[i+1]);
output_to_LED(i, mag);
}

In the OpenMusicLabs case you describe, the array indexing is different than the split-array version I’ve used.

You will probably have to scale “mag” to an appropriate range for the LED array.

How does one get 16bits of data from the ADC for the Open Music Lab FFT Library?

void loop() {
while(1) { // reduces jitter
cli(); // UDRE interrupt slows this way down on arduino1.0
for (int i = 0 ; i < 512 ; i += 2) { // save 256 samples
while(!(ADCSRA & 0x10)); // wait for adc to be ready
ADCSRA = 0xf5; // restart adc
byte m = ADCL; // fetch adc data
byte j = ADCH;
int k = (j << 8) | m; // form into an int
k -= 0x0200; // form into a signed int
k <<= 6; // form into a 16b signed int
fft_input = k; // put real data into even bins

  • fft_input[i+1] = 0; // set odd bins to 0*
  • }*
    [/quote]
    is this what i think it is? shifting?
    Also, in the lookup tables for cosine and sine, why does it multiply the input # of bits to the cosine/sine function i.e., 2^7 for the 8bit FFT and 2^15 for the Open Music Lab to get the lookup tables? If my question is not clear, I tried to get/recreate/find out how the lookup tables in the Open Music Labs FFT Library is made, and its sine/cosine(2pik/N)*2^15… From what I read, e^(-j2pik/N) = cos(2pik/N) - sin(2pik/N), isn’t the lookup table is for the precomputed values for cosine and sine and the cosine/sine function multiplied to the input sample?

Both questions have to do with how the math is performed, which includes scaling the numbers appropriately, and that is irrelevant to the theory of the Fourier transform.

I haven't looked at the Open Music Labs code closely, but fixed point algorithms use integers as decimal fractions, i.e. for 8-bit calculations 0x7F (decimal 127) can be interpreted as 127/128, which is slightly less than 1.0. Keep in mind that the values of sine and cosine are never greater than 1.0.

Here is some reading material, google for plenty more: https://en.wikipedia.org/wiki/Fixed-point_arithmetic