how can use the lib?

[jinxiangwzh]

1.which function can get the result of the FFT transform? 2.where to configure the sampling rate or other parameter for input data?

[jones139]

I use this library in my analysis - you can see it in the do_analysis function here. https://github.com/OpenSeizureDetector/Pebble_SD/blob/master/src/analysis.c

You do not tell it the sample frequency - instead the output units depend on the sample frequency.

Hope that helps. Graham

[stg]

Thank you jones139 :)

1. Transform is done in-place: after performing the FFT on an array of data, that array will contain the result.
2. Fourier transforms are sample rate agnostic. nthBinFrequency=(n∗sampleFreq)/numFFTpoints.

Let us know in more detail what you want to do, perhaps show some code, and we can help further in how to do it.

[puzrin]

@stg, thanks for awesome lib. I'm looking for CMSIS DPS replacement with less flash use. Here are my thoughts how to make you work more easy to use:

1. Make it use-able with PlatformIO (reorganize folders)
   • move .h to include/ or Includes
   • move main.c out of root (to benchmark/, for example)
2. Add couple of examples into examples folder.
3. Make library configure-able via -D, without need no change config.h
   • add namespace prefix to all #define-s (SYLT_FFT_, for example).
   • check everywhere if variable already set (use #ifdef).
4. Add version tags.
5. I would add more variants of sin tables (with possibility to select preferable size via single #define)
6. Reorganize readme
   • keep minimal info on top (why lib is awesome)
   • add signatures description (fft, ffti, rfft, rffti)
   • move the rest to bottom
7. Other
   • I'd prefer to pass FFT size (128, 256, 512, ...) instead of "bits" - more easy to understand/read code.

Right now user have to apply some extra efforts to use code - copy files, edit config, investigate sources to understand how to use. I would prefer more simple way:

• Add your repo to lib_deps in PIO project
• add sine table selector if desired.

https://github.com/speedcontrols/ac_sc_grinder/blob/master/platformio.ini#L24-L25 - here is example of how i "attach" libfixmath & etl.

If you agree with this proposal, i can prepare draft PR.

---

Also, some things are unclear for me from readme:

• "Minimal twiddle tables (512 bytes for max N=512 FFT)" - i did not found those tables at all
• "Designed for optimal performance, not optimal accuracy" - what this mean?
• "Care must be taken with input data to ensure no overflows" - what exactly care should be taken?

[stg]

Dear Puzrin,

Thank you for your kind comments, interest and involvement.

1. Yes, sounds good to me if ./include/
2. Yes, been meaning to do this, but never got around to it. There are so many examples to be made... I only wrote this for real inverse FFT in a synthesizer and never used it for anything else. Rest is pretty much just OCD to make it feel like a complete set of FFT primitives.
3. Yes, but fixed point math should use a different namespace - it is useful for many other things beyond FFT and I often use this subset for other projects.
4. Yes, as long as #ifdefs are used such that config.h still works as-is when -D is not used.
5. Yes, I don't see why not. I think SINE_BITS should be used. A #warning if a table is missing for specified SINE_BITS might be prudent.
6. Sure, why not. I'd lvoe to see what you had in mind.
7. No, while more readable does not make mathematical sense and will require some additional processing (CLZ is fast on ARM but not all targets have this) - this was a very conscious choice. Having predefined constants/enum for FFT_[size] for readability perhaps?

The library is laid out the way I personally prefer things - as simple as possible so that it can be refactored into whatever layout is required for a given project. That said, I don't mind any changes long as they are more or less standard for a wide variety of environments and not specific to PlatformIO or any other. Using -D defines and moving headers to ./include/ are good examples of very well adopted layouts. If anyone wants to do more specific things, such as a library for Arduino for example, it is best to fork.

I don't quite understand "Add your repo to lib_deps in PIO project" or "add sine table selector if desired".

"Minimal twiddle tables": twiddle (factor) tables are trigonometric tables (FFT lingo, see Wikipedia article for example). In this case, the one quadrant of a sine in config.h

"Optimal performance": FFT can be implemented in so many ways and the accuracy of results could be increased (at a performance loss) by additional steps between each successive step in the FFT algorithm to maximize data integer use range. This would result in more bits of useful information at the end of a transformation but is not done for performance reasons.

"Care must be taken": For example doing IFFT on multiple frequency bins having amplitudes such that their combined output would exceed the possible range of integers resulting in overflows. I have not investigated all cases to see if there are further areas where care must be taken, hence the vague note.

Best regards

[puzrin]

I don't quite understand "Add your repo to lib_deps in PIO project"

One of boring thing in C/CPP is dependency management. PlatformIO solves that in nice way. User just add libraries & versions in project config, and PIO cares about install & build. That significantly reduce entry level & maintenance cost.

"add sine table selector if desired".

I mean, one may wish to save flash for small FFT size, or bigger table for 1024 points. Currently user can only select -D SINE_USE_TABLE. It could have choice:

-D SYLT_FFT_SINE_TABLE_256
-D SYLT_FFT_SINE_TABLE_512 (default)
-D SYLT_FFT_SINE_TABLE_1024
...

And have SINE_BITS auto-configured for selected table size

2\. Yes, been meaning to do this, but never got around to it. There are so many examples to be made... I only wrote this for real inverse FFT in a synthesizer and never used it for anything else. Rest is pretty much just OCD to make it feel like a complete set of FFT primitives.

It would be enough to add simple snippets on demand. Just an /examples/README.md

For example, i have 10-12bits ADC samples, and need 512 points FFT to get magnitudes (squared magnitudes will be ok). What's the best way to do that?

7\. No, while more readable does not make mathematical sense and will require some additional processing (CLZ is fast on ARM but not all targets have this) - this was a very conscious choice. Having predefined constants/enum for FFT_[size] for readability perhaps?

enum is great alternative. It solves the problem.

Using -D defines and moving headers to ./include/ are good examples of very well adopted layouts. If anyone wants to do more specific things, such as a library for Arduino for example, it is best to fork.

Sure, i propose only "universal" changes.

---

One more question. I need to run this code on Cortex M0+ (512 or may be 1024 points). Does it worth to increase sine table and drop sine interpolation? Or this will not impact performance significantly?

---

Summary. I can start suggested modifications in my own project, and then show result for your review. Then you could apply acceptable changes to mainstream. After that, we discuss the rest & do one more iteration.

[stg]

All sounds good to me!

Cortex M0 sadly does not have some of the DSP functions that make this as fast as on M4 but it still works well.

"Significantly" is relative :) When you need to squeeze those last few CPU cycles out of a processor it might be significant. Minor details were important in my use case since I was hitting 99.something% CPU use in my project, which was the reason I wrote this - nothing I could find at the time was fast enough and I needed some 10-20% better performance.

I do not have exact metrics but a larger table would definitely be faster than interpolation.

However, the actual FFT functions only use direct lookup into the table (never interpolation or function calls) so it is actually necessary to have a sine table of adequate size for the required FFT conversions.

Interpolated variants are used only by helper functions to construct data sets for inverse FFT. If these are being used significantly, dropping interpolation would have an impact for sure.

The speed of the library comes from carefully optimizing the C code for register use to eliminate the need for push and pops. I literally compiled hundreds of times using different variations of the code to find combinations that result in the best assembly code. Any, even minor, changes have a significant impact on performance. Interpolation would be catastrophic on an M4, but the additional math required to replace DSP functions on M0 likely results in more memory access already, so interpolation might have a relatively low impact here.