# FFT - mixed radix - bit reversal

I wonder what is bit reversal for mixed radix FFT. Is there any algorithm that compute the bit reversal for various mixed radix FFT? Here should be mention why I want that. For example if I have signal with N=48 points. There is some method (which I still understand very little) to make DFT by prepare matrix 2x2x2x2x3, and make 5 dimensional DFT calculations. And because I can’t understand that idea but I understand radix-2 and radix-4 I wonder if I can make the matrix like 3x16 and on each 16 point row make the radix-2 or radix for. But not sure how to prepare bit reversal for input data (or for output if I make decimation in frequency).

• If you look at what I posted to your last question. You read data into that matrix, by rows but you read out by columns. – user28715 Apr 4 '18 at 23:57
• I’ve read your answer for my last post very carefully and many times, I’ve also read the fragment of book you adviced, also carefully, also many times. Actually I read your post and that book - bigger fragment about fft at all - every day about 10 times (it's not joke), and it doesn’t help me. Today I am going to write separate question about that what exactly I don’t understand. But now please just tell me if it’s possible to make bit reversal for mixed radix fft, and how to do that? – pajczur Apr 5 '18 at 5:12
• Actually I developed my last question (where you gave comprehensive answer). And I tried to explain which part of the book and your answer I don't understand. – pajczur Apr 5 '18 at 5:19

3 by 16 or 16 by 3 or 4 by 12 or 12 by 4

Hope this helps, not the mixed case , but I think this is the right direction

I don't have a copy of Brigham, E. Oran, and E. Oran Brigham. The fast Fourier transform and its applications. Vol. 1. Englewood Cliffs, NJ: prentice Hall, 1988.

handy. I have a vague recollection that he had some mixed fft examples but I think was radix 4. If you go to the fftw website and look at the papers section, there might be more help.

x=reshape(1:25',5,5)'  % read in row order fortran index
x =
1     2     3     4     5
6     7     8     9    10
11    12    13    14    15
16    17    18    19    20
21    22    23    24    25
reshape(x,25,1)        % read out column order
ans =
1
6
11
16
21
2
7
12
17
22
3
8
13
18
23
4
9
14
19
24
5
10
15
20
25

[y,i]=digitrevorder(0:24,5)  % c indexing
y =
Columns 1 through 20
0     5    10    15    20     1     6    11    16    21     2     7    12    17    22     3     8    13    18    23
Columns 21 through 25
4     9    14    19    24
i =
1
6
11
16
21
2
7
12
17
22
3
8
13
18
23
4
9
14
19
24
5
10
15
20
25
echo off

• Great thanks man, now it's much more clear for me. But as I understand the idea with reshape(x,25,1) = 1; 6; 11; 16; 21; 2; 7; ..... – pajczur Apr 5 '18 at 22:48
• ok just remember this is partly a guess. you will need to test and verify – user28715 Apr 5 '18 at 22:54
• Great thanks man, now it's much more clear for me. But as I understand the idea with reshape(x,25,1) = 1; 6; 11; 16; 21; 2; 7; ..... But still not sure what do you mean by [y,i]=digitrevorder(0:24,5) % c indexing which is 0; 5; 10; 15; 20; 1; 6; 11..... What is that? is this output order or what? And then again you write i = 1; 6; 11; 16; 21; 2; 7 .... This is the same order as on the begining for x reshape. I don't know what does it mean. And on the very begining you write 3 by 16 or 16 by 3 or 4 by 12 or 12 by 4. Also not sure what do you mean by that. But still great thanks... – pajczur Apr 5 '18 at 23:02
• for help to understand reordering the matrix. (This is my full comment, before something went wrong :) – pajczur Apr 5 '18 at 23:02
• in the c language a[0] is the first element of a vector. in fortran c[1] is the first element. most DFT summation is zero based. bit reversal is zero based but fortran and matlab need to add one for their index convention – user28715 Apr 5 '18 at 23:19