2
$\begingroup$

I am trying to understand how FFT works in order to measure the vibrations of a 3D printer. I will be doing this with an Arduino Nano and a MPU6050 accelerometer.

In order to program the Arduino correctly I need to understand some things about FFT first. So various sources state that FFT works with 2^n samples, for example "The FFT-algorithm works with a finite number of samples. This number needs to be 2^n where n is an integer (resulting in 32, 64, 128, etc)". What does this actually mean? From my understanding, if I will be measuring accelerations at a constant sample rate of 600Hz for 10 seconds, I will end up with 6000 samples. Does this mean that I will have to remove some of the measured data in order to end up with 4096 samples, which meets the 2^n samples condition? Or fill up my samples with zeroes to end up with 8196 samples, which also meets the stated condition?

Thank you!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The Arduino Nano has only 2 kilobytes of RAM. Your 6000 samples won't fit in its memory - never mind having space left over to do the FFT. $\endgroup$
    – JRE
    Apr 15, 2021 at 8:10
  • $\begingroup$ Hey Darius, @JRE is 100% right – I was assuming you'd be streaming your recorded samples to a PC. The Arduino nano is really the wrong platform to do this; you'd need something with more RAM, and ideally a less anemic CPU core. $\endgroup$
    – Marcus Müller
    Apr 15, 2021 at 8:19
  • $\begingroup$ I won't be doing the FFT on the Nano, I will be sending the data to a PI and work from there. $\endgroup$
    – Darius Curt
    Apr 16, 2021 at 10:39
  • $\begingroup$ yeah, then you don't have to worry about FFT performance, so the power-of-2 requirement isn't true. $\endgroup$
    – Marcus Müller
    Apr 16, 2021 at 14:48

2 Answers 2

Reset to default
1
$\begingroup$

Yes, that's correct, the FFT is an algorithm that improves the efficiency of the DFT, and doing so by calculating the DFT recursively. The DFT is samples of the DTFT, by padding your sample you simply making your DTFT sample resolution bigger, therefor if you do not have any calculation limits, do that. Another option for you is to calculate the DFT straight forward, Or to use other algorithms such as Cooley–Tukey.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Cooley-Tukey is the dominant FFT algorithm? Not quite sure what you thus mean... $\endgroup$
    – Marcus Müller
    Apr 15, 2021 at 14:20
  • $\begingroup$ The cooly-Tukey algorithm takes N=L*M samples and divides them into L subsamples, then preforms L DFT's of the size M, uses its periodic property and saves calculations by doing the same prosses recursively. Which means you can find the right, L and M that fits your 6000 samples. And compute the DFT $\endgroup$
    – Ran Greidi
    Apr 16, 2021 at 12:13
  • $\begingroup$ Yes, but that's exactly what is used when you compute an FFT. $\endgroup$
    – Marcus Müller
    Apr 16, 2021 at 14:48
  • $\begingroup$ That's not because L and M are for your choice, whereas the FFT limits you have a number of samples that is a power of 2. which means insteed of padding your smaples with a large number of zeros ( so it will have a number of samples that is a power of 2), you would only have to pad it so the samples number matches your L and M choice $\endgroup$
    – Ran Greidi
    Apr 16, 2021 at 14:52
  • $\begingroup$ Again, that's not true. FFTs in non-power-of-2 lengths are very common. There's not only Radix-2 FFTs, but also Radix-3, -5, -7, -11, and Radix-13. Cooley-Tukey is indeed used to break down a DFT of some length N into DFTs of prime factors of N (which you then solve with the FFTs of the appropriate prime factor (potences)). $\endgroup$
    – Marcus Müller
    Apr 16, 2021 at 14:55
1
$\begingroup$

The following is written assuming you do the signal analysis on your PC, and only use the Arduino to acquire the samples and send them to your PC.

Your Arduino Nano's microcontroller doesn't have the memory necessary to store a second of data.

various sources state that FFT works with 2^n samples

FFTs in length of powers of 2 are especially computationally efficient to compute. Since you probably don't care about how efficient your computation is, you don't care. The FFT is just a fast way to calculate the DFT of a vector, and worst case, any length is possible when just calculating the DFT plain from the textbook formula for the DFT.

This number needs to be 2^n

That's plain wrong. FFTs exist for many lengths, usually for any length that can be decomposed into prime factors < 17. (As far as I know. Maybe we can do better today.)

From my understanding, if I will be measuring accelerations at a constant sample rate of 600Hz for 10 seconds, I will end up with 6000 samples.

That sounds right.

Does this mean that I will have to remove some of the measured data in order to end up with 4096 samples, which meets the 2^n samples condition? Or fill up my samples with zeroes to end up with 8196 samples, which also meets the stated condition?

you can do either, but you don't have to; 6000 = 2·3·10³ = 2⁴·3·5³ and there's multiple FFT implementations for such lengths. Again, you don't even have to use an FFT to calculate the DFT.

So, I'd really rather adjust the FFT (DFT) length to your measurement problem than the other way around.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The OP is planning to do the Fourier analysis on an Arduino Nano. Efficiency is probably a major consideration - even though the OP is not aware of it yet. $\endgroup$
    – JRE
    Apr 15, 2021 at 8:09
  • $\begingroup$ @JRE hmmm I was assuming the analysis would be taking place on a PC which records the data; with 2kB of RAM, doing a > 2¹⁰-sized FFT wouldn't be possible without having external memory. $\endgroup$
    – Marcus Müller
    Apr 15, 2021 at 8:17
  • 1
    $\begingroup$ "In order to program the Arduino correctly I need to understand some things about FFT first." That reads like doing the FFT on the Arduino. $\endgroup$
    – JRE
    Apr 15, 2021 at 8:18
  • $\begingroup$ @JRE you're absolutely right! $\endgroup$
    – Marcus Müller
    Apr 15, 2021 at 8:19
  • $\begingroup$ Again, my bad. I will be using the Nano just to measure accelerations and send them to a PI. $\endgroup$
    – Darius Curt
    Apr 16, 2021 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.