Chapter 30 examines an important algorithm called the fast Fourier transform, or FFT. The first step of the FFT algorithm performs a bit-reversal permutation on an input array A[0 . . n - 1] whose length is n = 2^k for some nonnegative integer?k. This permutation swaps elements whose indices have binary representations that are the reverse of each other.

We can express each index?a?as a?k-bit sequence??a_k-1, a_k-2, . . . , a₀?, where?a?=?^k-1_i=?0 a_i 2ⁱ. We define revk.??a_k-1, a_k-2, . . . ,a₀?)?=??a₀, a₁, . . . ,a_k-1?;

thus,

For example, if?n?=?16?(or, equivalently,?k?=?4), then rev_k(3)?=?12, since the?4-bit representation of?3?is?0011, which when reversed gives?1100, the?4-bit representation of?12.

a.?Given a function rev_k that runs in ?(k) time, write an algorithm to perform the bit-reversal permutation on an array of length n = 2_k in O(n_k)?time.

We can use an algorithm based on an amortized analysis to improve the running time of the bit-reversal permutation. We maintain a "bit-reversed counter" and a procedure BIT-REVERSED-INCREMENT?that, when given a bit-reversed-counter value?a, produces rev_k?(rev_k(a) + 1). If k = 4, for example, and the bit-reversed counter starts at 0, then successive calls to BIT-REVERSED-INCREMENT produce the sequence 0000, 1000, 0100, 1100, 0010, 1010, . . . = 0, 8, 4, 12, 2, 10, . . . .

b.?Assume that the words in your computer store?k-bit values and that in unit time, your computer can manipulate the binary values with operations such as shifting left or right by arbitrary amounts, bitwise-AND, bitwise-OR, etc. Describe an implementation of the BIT-REVERSED-INCREMENT?procedure that allows the bit-reversal permutation on an?n-element array to be performed in a total of?O(n)?time.

c. Suppose that you can shift a word left or right by only one bit in unit time. Is it still possible to implement an O(n)-time bit-reversal permutation?

Transcribed Image Text:

k-1 rev (a) = ax-i-12' . i=0