-
Notifications
You must be signed in to change notification settings - Fork 1.1k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Generation of bit reversal tables for CMSIS-DSP #858
Comments
Hello, Thank you for the guide, why do you think that index type for bit reversal has to be changed from uint16_t to uint32_t to support 8192, please? I've generated tables for radix 4 and radix 8 and they all seem to fit in 0xFFFF. If someone is struggling with this one too, I prepared code snippet here: Currently radix 4, 4x2 and radix 8. |
Hello @rosek86, I have had some warnings with the compiler. |
Hello @christophe0606, I confirm that arm_cfft_q15 and arm_bitreversal_16 (both c/asm) works fine. I haven't compiled tested anything else apart from q15. |
I updated code snippet to support 8x4 and 8x2, maybe someone will find this useful. |
How to generate bitreversal tables ? Do you know? I couldn't understand?Can you send me the code? |
Hi @Lijiugen, Have you tried the code I posted above? |
Thank you very much. I'm so excited. You returned to me so soon. I just opened the link, but I couldn't open it before. It's so slow for us to visit GitHub here |
Thanks for sharing this guide! Just one issue, by looking through the code comments in arm_common_tables.c in Revision v1.9.0, I've noticed that all of the bit reversal tables follow a periodic sequence of 8x2, 8x4 and radix-8, except 2048! 16 -> 8x2 Is there any reason for this? Or is it a bug? Or just a wrong comment? Screenshot attached below as evidence. |
@alireza-tabatabaee It should work in theory with both 8x2 and 8x4. But once you choose to use 8x2 or 8x4 then the code has to take it into account. You cannot just replace the table. The code for 2048 (arm_cfft_f32.c) is using arm_cfft_radix8by4_f32 So, I assume the comment is wrong and the table is a 8x4 (Otherwise tests would fail). |
Generating bit reversal tables for CMSIS-DSP is a question which is coming back often.
In this post, I'll explain how to do it. (I'll use the naming "bit reversal" even if not totally correct).
Pure radix
Pure radix case is the simplest. The reversal formula is obvious and the
out of place reversal and in-place reversal are the same.
In CMSIS the bit reversal tables are in bytes and take into account the fact that the FFT is complex. So there is a factor of 8 applied to the sample indexes.
In this post I'll just consider the index. So you'll need to multiply by 8 to generate the final CMSIS-DSP tables.
Radix-8
Let's take the example of the 64 samples CFFT F32.
The index of a sample is written
The reversal of this index is just a reversal of the values n1, n2 and is written
The correspondence
is giving the transposition required to implement the bit reversing table.
You must of course remove the cases where 8 n1 + n2 is equal to 8 n2 + n1.
And if you include the case a -> b, don't include the case b -> a.
This list of transpositions is working for an out of place reversal and also for an in-place one because the transpositions are always disjoint ones. It won't be the case any more with mixed radix as we will see. And since CMSIS-DSP is doing an in-place reversing, it will have to be taken into account.
Radix-4
The radix-4 FFT in CMSIS-DSP are implemented in such a way that the bit reversal is in fact a base 2 one. So, if you decompose your index as:
and reverse it as
then you'll get the tables for the radix-4 FFT and radix 4x2 of CMSIS.
Mixed radix
Mixed radix is more complex for two reasons:
Radix 8x2
Example with 16 samples
Let's take as example a 16 sample FFT.
The reversal formula is:
If we compute all the values we get:
We see a problem with the transform 8 -> 4 and 4 -> 2. They are not disjoint since both involve the position 4.
If we compute the out-of-order reordering by applying above rules to the sequence [1..15], we get:
Permutations
To go from [1..15] to the above order, the permutation required is:
Where (a b c d) is a cycle representing the transform a -> b -> c -> d -> a
This permutation can be computed using FindPermutation in Mathematica, or Permutation.from_sequence using the Python symbolic package sympy.
So, we see that the effect of having overlap in the transformation rules is to generate a cycle in the final permutation.
To do this permutation in place we need to decompose the cycle in a sequence of transpositions.
There is not an unique way to do it. So you may not (and will not) recover the table of the CMSIS-DSP but you'll get tables with the same length and the same effect on the array of samples.
In addition to that, the disjoint cycles being independent they can be reordered in the permutation. It means that the order in the final CMSIS-DSP table is also a bit arbitrary.
So the best way to check that the resulting table is correct is to compute its equivalent permutation. You don't need to be bit exact with the CMSIS-DSP bit reversal tables to be right.
I choose to decompose a cycle
So I finally get the following list of transpositions:
If we flatten the list of numbers and multiply by 8, we get the following table:
The original CMSIS-DSP table is:
First obvious difference : the order is different. But it is not the only difference.
In our table we have the pairs (56,88), (112,88) and (104,88).
In CMSIS-DSP table, we have (56,88), (88,104) and (104,112).
And you can check that:
So both tables are representing the same permutation of the samples.
Example with 8192 samples
For a 8192 table, the correspondence formula would be:
Radix 8x4
Formula for 32 samples
For a 32 samples FFT, the correspondence formula is:
Formula for 2028 samples
For a 2048 FFT, the correspondence formula is:
I have attached the bit reversal table and twiddle table to implement the 8192 CFFT.
Note that the index type for bit reversal has to be changed from uint16_t to uint32_t to support 8192. So it impacts the API and other bit reversal tables.
TablesFor8192.zip
The text was updated successfully, but these errors were encountered: