1
$\begingroup$

Can anyone tell me how does bit reversal order technique works for FFT when you are trying to break down the FFT to small sizes. Like I want to only for the when the index is odd because that involve some reverse carry propagation, but when the index is even you just add N/2 to it to get your reverse index r. An example of N=8 would be perfect if someone can explain me.

$\endgroup$
  • 5
    $\begingroup$ DX, you are asking many, very specific questions. You get good answers, and you NEVER accept any of the answers. Please play nicely with the many good answerers here and start accepting answers to your previous questions before asking any more questions (or expecting any answers!). $\endgroup$ – Peter K. Apr 23 '13 at 11:40
  • $\begingroup$ I think i should leave this forum because no body answer properly they just copy paste it from google and never understand what i am asking. The things they tell me i already know them 95 % of times. Like for this question i am asking what is reverse carry propagation and matt keeps on telling me what i already know. Anyway thanks for your nice answers :) $\endgroup$ – D X Apr 23 '13 at 12:36
  • 4
    $\begingroup$ Do not expect to get answers to questions you do not ask. Please update the question to ask for the specific information you're after. Please accept answers to questions that you've asked previously if you expect us to keep answering your questions. $\endgroup$ – Peter K. Apr 23 '13 at 12:56
5
$\begingroup$

If I understand your question correctly you want this (index | binary | bit rev. | bit rev. index):

$$ 0\quad 000\quad 000\quad 0\\ 1\quad 001\quad 100\quad 4\\ 2\quad 010\quad 010\quad 2\\ 3\quad 011\quad 110\quad 6\\ 4\quad 100\quad 001\quad 1\\ 5\quad 101\quad 101\quad 5\\ 6\quad 110\quad 011\quad 3\\ 7\quad 111\quad 111\quad 7\\ $$

$\endgroup$
  • $\begingroup$ Yeah right. Can you explain me for odd numbers how do you do it. For even numbers we just add N/2 and do it like r =r + N/2 where r is the reverse index. How to calculate it when we have odd number because it will involve some reverse carry propagation I don't understand this. $\endgroup$ – D X Apr 23 '13 at 9:31
  • 1
    $\begingroup$ You simply swap the bits around. Bit reversal means mirror imaging your binary numbers. Some signal processors can do this in hardware. You probably need to do it in software. $\endgroup$ – Matt L. Apr 23 '13 at 9:34
  • $\begingroup$ ok. But kindly give me an example because I am not understanding it. I have to implement it in C, so we don't have a swap function in C thats why. $\endgroup$ – D X Apr 23 '13 at 9:37
  • $\begingroup$ I'm afraid you have to write this function yourself. You do have bitwise operations in C, so it's no big deal. $\endgroup$ – Matt L. Apr 23 '13 at 9:41
  • 2
    $\begingroup$ Some good solutions here: graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious $\endgroup$ – Paul R Apr 23 '13 at 9:52
5
$\begingroup$

To find the next bit-reversal address, you simply add N/2 to the present address, from left to right (not our usual right-to-left addition).

Consider the case as in the image given by Matt's answer, N = 8. that corresponds to 1000. Therefore, N/2 = 4 = 100.

Take first address, X = 000 | add N/2 => 100, ie bit_reverse address = 4 (100)

Now take new one, X = 100 | add N/2, be careful here.

You need to add from left-to-right, just opposite of what you normally do during addition.

address  1 0 0 +
N/2      1 0 0
         ------
result   0 1 0  ----> 2
carry    1 0 0

Now you continue this steps, and you will generate address like this, 0-->4-->2-->6-->1-->5-->3-->7.

Let's us do one more example. Suppose you reached bit-reversed address Y = 5. You need to find next address, simply add N/2 to that. (We know answer is 3).

address  1 0 1 +
N/2      1 0 0
         ------
result   0 1 1  ----> 3
carry    1 0 0

This is how you generate bit-reversed address.

$\endgroup$
  • $\begingroup$ Thanks abid I understand it. I appreciate your effort in explaining everything to me. $\endgroup$ – D X Apr 24 '13 at 12:48
  • $\begingroup$ Hey that’s great answer, it’s simplifying everything. But still the question is there any possible way to make that “left to right bit adding” in place, without loop, in C++? $\endgroup$ – pajczur Sep 19 '18 at 7:22
0
$\begingroup$

Assuming random memory access of all previously computed bit-reversal is possible, the following algorithm works, assuming N is power of 2:

  1. Start with first index, 0.
  2. Add N/2 to first index to get the second index.
  3. Add N/4 to the previous 2 indices to get the next 2 indices.
  4. Add N/8 to the previous 4 indices to get the next 4 indices.
  5. Repeat until you reach N/N, which is equivalent to adding 1 to the already computed N/2 indices.

An example for N=8 is:

  1. Start with 0.
  2. Next index is [0] + 8/2 = [4].
  3. Next 2 indices are [0,4] + 8/4 → [2,6]
  4. Next 4 indices (the last) are [0,4,2,6] + 8/8 → [0,4,2,6,1,3,5,7]

The drawback of this method is that it requires memory lookup, which could be expensive depending on the hardware used.

$\endgroup$

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.