[Q] Bit-Reversed FFT?

Hi,

I am puzzled at Bit-Reversed FFT algorithm and not very certain if my
understanding is correct.

For example, for an 8 point Radix-2 FFT, the input to the first stage
is {0, 4, 2, 6, 1, 5, 3, 7}, a Bit-Reversed form, so the Bit-Reverse
addressing mode is very useful. And the output is from 0 to 7, a very
nice form too!

But what happen to the following two stages? For example, the second
stage needs input ordered as {0, 2, 1, 3, 4, 6, 5, 7} which is not in
Bit-Reversed form, I still could see a regularity but it seems to be
some bit-manipulation (bit extraction, shifting, padding...) is needed,
which may not be very efficient in processor execution.

Is there any point I am missing or it is just like this?

Thanks.

heliboy2003@yahoo.com.tw wrote:
> Hi,
>
> I am puzzled at Bit-Reversed FFT algorithm and not very certain if my
> understanding is correct.
>
> For example, for an 8 point Radix-2 FFT, the input to the first stage
> is {0, 4, 2, 6, 1, 5, 3, 7}, a Bit-Reversed form, so the Bit-Reverse
> addressing mode is very useful. And the output is from 0 to 7, a very
> nice form too!
>
> But what happen to the following two stages?

Bit-reversed addressing is used for the last stage. Decimation-In-Time
divides the input into even- and odd-indexed data, and performs a
smaller FFT on each subset. So for the first stage you divde the
8-point data x = x(0), x(1), ...., x(7) into two subsets

x_0 = x(0), x(2), x(4), x(6)

and

x_1 = x(1), x(3), x(5), x(7).

Continuing with the recursion, one again divides x_0 and x_1 into even
and odd:

x_00 = x(0), x(4)
x_01 = x(2), x(6),
x_10 = x(1), x(5),
x_11 = x(3), x(7),

and performs a two-point FFT (simple butterflies) on each of the four
subsets. This is the last stage (conceptually, as it stands at the end
of the recursion), and it is computed first. To directly access the
data for the two-point FFTs, one uses bit-reversed addressing to access
the data in the order given by the decimation-in-time recursion:

x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7).

Regards,
Andor