FFT Longer than 4086 samples

Can CMSIS-DSP support complex FFTs longer than 4096 samples on Cortex-M ?

The quick answer is yes with some changes.

The limitations and problems are coming from the "bit reversal" phase : the reordering of the samples in the output buffer. It is implemented with a permutation table using indexes in bytes.

A 8192 complex FFT needs 8192 x 2 x 4 bytes in the output = 65536. As consequence, longer FFTs would require indexes in the permutation table on 32 bits instead of 16. If you don't need long FFTs, you don't want to double the size of all the permutaton tables by changing the type of the indexes from uint16 to uint32.

So, complex FFTs of length above 8192 require a change of datatype in the structure like arm_cfft_instance_f32. In addition to this change, functions used to implement the permutation and read the permutation table (like arm_bitreversal_f32) must be changed and new initialization functions are required for the new sizes.

Change of the bit reverse functions should be easy in scalar but can be a bit tricky with the vectorized Helium versions.

The branch https://github.com/ARM-software/CMSIS-DSP/tree/bigfft is giving an example for CFFT F32 and size up to 16384. It is a bit old and has not integrated the latest changes from main.

Finally, the twiddle tables and bit reverse tables for the new lenghts need to be generated using the provided scripts in: Scripts/genBitReversal.py and Scripts/genScalarTwiddleCoefs.py ... Those scripts are only available in the bigfft branch

The indexes in permutation tables are in bytes because it makes it easier to vectorize the bit reverse fubnctions. If the indexes were in samples in the permutation table, it would enable a few more lengths but at some point we would still reach the limitation of having indexes on 16 bits.