Talk:Bit-reversal permutation

Help

This article at the present state can only be understood by people who allready know it, both the text and the uncommentated graphics and examples. What does a "Bit-Reversal" do, what is the result and why is this desired? How can it be performed?

So it could be mentioned that a bit-reversal permutation stores all elements with even indices into one half of the result and the odds into the other half. The elements of the even half are separated in elements which are dividable by 4 and only by 2, the odd half is halfed into elements with modulo 4 results (remainder of a division by 4) 1 and 3. Two more bit-reversals performed just to the even and the odd half rearranges the elements into their original relative order with the additional feature, that the even and odd elements are still separated. This is useful some times and can be done "in place" with the following procedure:

void	BitReversal(AnyDataType x[], int N)
	{	// Put N elements of AnyDataType into a 2-based BitReversal order
	for (int i=1, j=N/2, k=0; i<N; ++i, j+=k)
		{				// i and j shall be bit-reverted over N
		if (i < j)			// for i>j the swap was allready done when i<j
			swap(x[i], x[j]) ;
		for (k=N/2; k<=j; k>>=1)
			j -= k	;		// bit-reversal incrementation of j
		}
	}	// There are some accelerations possible e.g. for the end of the outer loop set to 
		//  N - int(sqrt(2*N)), because all those bitreversals of i are <i and allready done

The advantage of a FFT with an initial bit-reversal is, that the FFT can be performed "in place" and not recursively, which makes it some faster. One bit-reversal of little and linear expense (less than 3*N/2 assignments of data elements and some minor interger operations) arranges the elements for all levels of the divide&conquer! The expense of a recursive FFT in textbook-style with its typically indirect bitreversal needs at least N/2 extra data elements once and 3*N/2 additional data assignment operations on each dividing level (log2(N)). --46.115.49.155 (talk) 19:43, 14 March 2013 (UTC)

An FFT can be performed non-recursively without an initial bit reversal, and in-place without a separate bit-reversal pass. Nor is recursion necessarily slow, as long as the leaves are coarse enough. FFTW uses explicit recursion, and does not use a separate bit-reversal pass, for example. Nor does a recursive-out-of-place implementation of an FFT need more array reads/writes (see e.g. the pseudocode on the Cooley-Tukey FFT page. What is true is that a separate bit-reversal pass leads to the simplest way to perform an FFT in-place for power-of-two sizes. (Even simpler FFT implementations can be achieved by working out-of-place.) — Steven G. Johnson (talk) 20:02, 14 March 2013 (UTC)