Fast Fourier Transform (FFT) (Part 6)

Part 1234567891011

PlainFFT is a simple but effective library which contains all the previously described functions for running FFT on vectors of data.

Here is the example code from the library files which demonstrates the (pretty easy) use of the FFT. The content of the vectors of interest is printed on completion of each FFT stage

#include "PlainFFT.h"

PlainFFT FFT = PlainFFT(); // Create FFT object
// These values can be changed in order to evaluate the functions
const uint16_t samples = 64;
double signalFrequency = 1000;
double samplingFrequency = 5000;
uint8_t signalIntensity = 100;
// These are input and output vectors
double vReal[samples]; 
double vImag[samples];
uint8_t runOnce = 0x00;

#define SCL_INDEX 0x00
#define SCL_TIME 0x01
#define SCL_FREQUENCY 0x02

void setup(){
	Serial.begin(115200);
	Serial.println("Ready");
}

void loop() {
	if (runOnce == 0x00) {
		runOnce = 0x01;
		// Build raw data
		double cycles = (((samples-1) * signalFrequency) / samplingFrequency);
		for (uint8_t i = 0; i < samples; i++) {
			vReal[i] = uint8_t((signalIntensity * (sin((i * (6.2831 * cycles)) / samples) + 1.0)) / 2.0);
		}
		printVector(vReal, samples, SCL_TIME);
		FFT.windowing(vReal, samples, FFT_WIN_TYP_HAMMING, FFT_FORWARD);	// Weigh data
		printVector(vReal, samples, SCL_TIME);
		FFT.compute(vReal, vImag, samples, FFT_FORWARD); // Compute FFT
		printVector(vReal, samples, SCL_INDEX);
		printVector(vImag, samples, SCL_INDEX);
		FFT.complexToMagnitude(vReal, vImag, samples); // Compute magnitudes
		printVector(vReal, (samples >> 1), SCL_FREQUENCY);	
		double x = FFT.majorPeak(vReal, samples, samplingFrequency);
		Serial.println(x, 6);
	}
}

void printVector(double *vD, uint8_t n, uint8_t scaleType) {
	double timeInterval = (1.0 / samplingFrequency);
	for (uint16_t i = 0; i < n; i++) {
		// Print abscissa value
		switch (scaleType) {
		case SCL_INDEX:
			Serial.print(i, DEC);
			break;
		case SCL_TIME:
			Serial.print((i * timeInterval), 6);
			break;
		case SCL_FREQUENCY:
			Serial.print((i / (timeInterval * (samples-1))), 6);
			break;
		}
		Serial.print(" ");
		// Print ordinate value
		Serial.print(vD[i], 6);
		Serial.println();
	}
	Serial.println();
}

Attention:

  • The distributed code is slightly different from the posted code due to last minute changes and optimizations
  • Samples value must be a power of 2
  • Make sure you have enough memory before incresing the size of vectors
  • Vectors must contain unsigned integers (0 to 127), you can easily change that to 16 bits integers (signed or not) to the cost of doubling the vectors size…
  • Remember the Nyquist theorem when changing the sampling and the signal frequencies

Note: The huge popularity of PlainDSP (merge of PlainFFT and PlainADC libraries) and the numerous requests for help drove me to think about a convenient solution for all designers, artists, students, professors, R&D people, prototypists who need to understand, experiment, create applications featuring advanced Digital Signal Processing on Arduino. The result of intense thoughts, design and writing is the collection PlainDSP kits, starting with the audio kit.

Next post on same subject

27 Comments

  1. Nikos says:

    I have been following all posts on FFT and I can honestly say this is a complete, detailed and easy to understand guide that far exceeded my expectations!

    My sincere congratulations!

    The library works perfectly on my Arduino Duemilanove, but I cannot increase the number of samples over 128.

    Unless I am doing something wrong, even setting the vectors to 16 bits does not help any.

    Maybe this is an Arduino’s SRAM limitation?

    • Didier says:

      Thanks for the kind comment.
      The size and variable type of the vectors is limited by the amount of SRAM available from your Arduino platform (2048 bytes for the Duemilanove, half that of the Diecimila!). I propose to cover this question in comming post.

  2. Axel says:

    Hello Didier,
    many thanks for the excellent explaination.
    Unfortunately I still stumble over a few points… 🙁

    double cycles = (((samples-1) * signalFrequency) / samplingFrequency);

    ok, you do not really have a time scale but you need some substitute for the frequency. So you know the frequency of your signal is 1000 while you sample with 5000.
    Now you calculate the cycles over one FFT block with 64 samples.
    But why is it 64-1?

    Next you have the equation for a harmonic oscillation.

    f(t) = A*sin(2*pi*f*t) =
    (signalIntensity * (sin((i * (6.2831 * cycles)) / samples) + 1.0)) / 2.0)

    But anyway… thanks again for the excellent work!

    Why is it again +1.0 and /2.0?

    • Didier says:

      Your comments are welcome Axel.

      Q1:But why is it 64-1?
      A1: Because the scale ranges from 0 to 63, in 64 steps!

      Q2: Why is it again +1.0 and /2.0?
      A2: Because I wanted my signal to be alike the one I expect to sample from a microphone (after amplification), check schematics in http://didier.longueville.free.fr/arduinoos/?p=1057 and expecially the voltage divider bridge R3/R4 which offsets the output signal to half VCC.

  3. Axel says:

    Ouch! Thank’s a lot. The counter to 64 should have been obvious.
    My accelerometer arrived yesterday.
    But it is the pure smd chip. I won’t have a chance to solder this at home…
    Maybe I will try to get a Bosch knock sensor on ebay…

  4. Simon says:

    Thanks for all this informations, it’s quite complex but it’s easy to follow and to understand wich variable goes where.
    Now i see that i’m not a pro with programming arduino, i was looking for the input value, when i input some signals in it via an analogRead, where do i put this variable to get it analysed by the FFT ?

    It i suit to your example, the fft.majorpeak is the amplitude of wich frequency ?

  5. Axel says:

    Hi again,
    the knock sensors can be bought at some internet auctions for about 22 Euros…
    not that much, but I got myself the Wii NunChuk.
    Did not try them though, yet.

    Anyway, I have taken your code as a template to understand the FFT better and to experiment with it I am using Qt.

    I have to admit I have some trouble to follow when you create your vectors.
    vReal[i] contains the amplitude of your signal at i.
    vImag[i] contains only zeroes.
    Is not y = Im(y), and therefore y = Im(y) = vReal[i]= A*sin(wt)?

    Where do you actually transform to complex numbers before you start FFT.compute?

    I must be missing something, and I have to admit I never liked complex numbers…

    • Didier says:

      I am interested in the links to the knock sensors!

      I am investigating the accelerometers too! Plenty post are pending related to some exciting projects. Next to come shall be a (calibrated) tilt sensor.

      You do not have to perform any calculation of any kind (except windowing) prior to computing FFT. Abscissa data points are supposed to be equally spaced, and you just care about ordinates! Please check the litterature about these specific aspects.

  6. kd7eir says:

    I am a little confused. I read through your article about FFT, in which you promised the code at the end of the article. Then when I go to get the code, you are demanding that I provide my complete biography to you in order to get the code.

    Why do you waste people’s time like this? It would have been very simple to state at the BEGINNING of the article that the code was not available unless I was willing to give you intimate details of my use of the code, as well as a lengthy explanation of who I am and why I want to use the code. This is the EXACT OPPOSITE of the open source philosophy that Arduino is built upon. Sadly, this little game of yours has soured me on the entire Arduinoos site.

    Please change your ridiculous policies or at least stop promising something that you really do not want to deliver.

    • Didier says:

      You wrote “I am a little confused”
      In this case, this is a perfect euphemism

      You wrote “I read through your article about FFT”
      Some people thank me for writing it

      You wrote “in which you promised the code at the end of the article”
      I never promised anything like this. S far, I made to promesses in my life: as a boy scout, and to my wife on our wedding day. Regarding software, I announced “PlainFFT is available from the download area”

      You wrote “Then when I go to get the code, you are demanding that I provide my complete biography to you in order to get the code.”
      I never ask for any complete biography. I ask for a clear description about who you are. All visitors but you and an other guy made such an interpretation. It might be my poor English, sorry for that.

      You wrote “Why do you waste people’s time like this? It would have been very simple to state at the BEGINNING of the article that the code was not available unless I was willing to give you intimate details of my use of the code, as well as a lengthy explanation of who I am and why I want to use the code.”
      Why do not you just read the blog from the beginning? The link to the download area and to the comments is at the very top of my blog? Please, do not give any intimate details in this blog!

      You wrote “This is the EXACT OPPOSITE of the open source philosophy that Arduino is built upon.”
      Does this philosophy that you seem to know so well includes the right to shout at me? I took the time to explain which is my philosophy, if you do not like it, please, skip my blog.

      You wrote “Sadly, this little game of yours has soured me on the entire Arduinoos site.”
      Just a few more posts like yours and Arduinoos will close.

      You wrote “Please change your ridiculous policies or at least stop promising something that you really do not want to deliver.”
      41 people asked for code this year. 40 received what they asked for. I will not change my policy for you.

      Thanks anyway for your comment.

  7. rodrigo says:

    I don’t understand why it doesn’t compile in my Arduino IDE!

    I have the library(PlainFFT.h) and the arduino file(speak.pde).
    I have problems how:

    PlainFFT.h:18:6: error: ‘PlainFFT’ has not been declared
    PlainFFT.h: In function ‘void windowing(double*, uint8_t, uint8_t, uint8_t)’:
    PlainFFT.h:31:46: error: ‘pi’ was not declared in this scope
    PlainFFT.h:31:56: error: ‘cos’ was not declared in this scope
    PlainFFT.h: At global scope:
    PlainFFT.h:60:6: error: ‘PlainFFT’ has not been declared
    PlainFFT.h: In function ‘void compute(double*, double*, uint8_t, uint8_t)’:
    PlainFFT.h:67:24: error: ‘swap’ was not declared in this scope
    PlainFFT.h:81:42: error: ‘exponent’ was not declared in this scope
    PlainFFT.h:100:29: error: ‘sqrt’ was not declared in this scope
    PlainFFT.h: At global scope:
    PlainFFT.h:113:6: error: ‘PlainFFT’ has not been declared

    Can someone help me? 🙂

    Thank you!!!

  8. Didier says:

    What is in speak.de?
    Actually, Arduinoos code is Arduino 1.0 compatible!

  9. rodrigo says:

    speak.pde is a arduino code.

    I will try download the arduino 1.0.

    • Didier says:

      Your answer does not help much! Or I did not phrased it correctly… Can you copy/paste speak.pde code for us so that we can help diagnosing it?

  10. rodrigo says:

    I sent a email for you.

    😀

    Thanks

  11. rodrigo says:

    Can I put the code here, but is very extensive.

  12. rodrigo says:

    Hi Didier, but before I will say my project.

    I want read one wav file in my computer, after apply FFT and other things because I’m tried build a voice recognize.

    It’s possible with your library?
    how to read wav files?

    Best Regards Didier.

    • Didier says:

      Hi Rodrigo,

      Arduinoos is dedicated to … Arduino projects. I did not write a PlainWAV library. For two reasons:
      One is that reading a WAV supposes that you have a wav file recorded on SD using a light but still memory greedy code
      Second is that Arduino is not fast enough for reading 44KHz sound files.

      WAV format is available from the web. The complexity of wav files is medium, because of some tricks and precautions.

  13. rodrigo says:

    Ok, I understand, but do you know anyway for build a voice recognize with arduino and fft library?

    Best Regards!

    • Didier says:

      Nope Rodrigo. Depending upon the type of recognition that you are looking for, it may be doable with Arduino thanks to some sound spectrum libraries (stored on good ol’ SD cards), that’s my guess. I do not plan to invest this domain for the time being, may be later… 😉
      Sound compression is an other fascinating domain, which may be linked to the voice recognition question.
      May be you should check this site: http://interface.khm.de/ they released very well written posts on sound management.
      Keep well, work hard!

  14. farhad says:

    I have the same question as asked by Simon, moreover i want to know how to access the individual frequency bins of the fft? i want to make a project in which i have to enhance certain frequencies and then take its ifft and play on speaker. kindly guide me as i have to submit the project in 2 weeks.

  15. farhad says:

    i just cannot make the plain fft library as i am totally new to arduino , i hope im not doing anything wrong by copieng the functions in a text file with a .h extension?

    • Didier says:

      There are very good tutorials on how to build libraries on the official arduino web site. Please try easy things first before trying to program complex applications.
      We’ve all been beginers once, all of us.

Leave a Reply

You must be logged in to post a comment.