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).
$\begingroup$
$\endgroup$
3
-
$\begingroup$ 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. $\endgroup$– user28715Apr 4, 2018 at 23:57
-
$\begingroup$ 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? $\endgroup$– pajczurApr 5, 2018 at 5:12
-
$\begingroup$ 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. $\endgroup$– pajczurApr 5, 2018 at 5:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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
-
$\begingroup$ 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; ..... $\endgroup$– pajczurApr 5, 2018 at 22:48
-
$\begingroup$ ok just remember this is partly a guess. you will need to test and verify $\endgroup$– user28715Apr 5, 2018 at 22:54
-
$\begingroup$ 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 is0; 5; 10; 15; 20; 1; 6; 11.....What is that? is this output order or what? And then again you writei = 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... $\endgroup$– pajczurApr 5, 2018 at 23:02 -
$\begingroup$ for help to understand reordering the matrix. (This is my full comment, before something went wrong :) $\endgroup$– pajczurApr 5, 2018 at 23:02
-
$\begingroup$ 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 $\endgroup$– user28715Apr 5, 2018 at 23:19