0
$\begingroup$

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).

$\endgroup$
  • $\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$ – Stanley Pawlukiewicz Apr 4 '18 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$ – pajczur Apr 5 '18 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$ – pajczur Apr 5 '18 at 5:19
1
$\begingroup$

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
$\endgroup$
  • $\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$ – pajczur Apr 5 '18 at 22:48
  • $\begingroup$ ok just remember this is partly a guess. you will need to test and verify $\endgroup$ – Stanley Pawlukiewicz Apr 5 '18 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 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... $\endgroup$ – pajczur Apr 5 '18 at 23:02
  • $\begingroup$ for help to understand reordering the matrix. (This is my full comment, before something went wrong :) $\endgroup$ – pajczur Apr 5 '18 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$ – Stanley Pawlukiewicz Apr 5 '18 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.