Problem

In computing the DFT, it is necessary to multiply a complex number by another complex nu...

In computing the DFT, it is necessary to multiply a complex number by another complex number whose magnitude is unity, i.e., (X +jY)e^jθ. Clearly, such a complex multiplication changes only the angle of the complex number, leaving the magnitude unchanged. For this reason, multiplications by a complex number e^jθ are sometimes called rotations. In DFT or FFT algorithms, many different angles θ may be needed. However, it may be undesirable to store a table of all required values of sin θ and cos θ, and computing these functions by a power series requires many multiplications and additions. With the CORDIC algorithm given by Volder (1959), the product (X + jY)e^jθ can be evaluated efficiently by a combination of additions, binary shifts, and table lookups from a small table.

(a) Define θ_i = arctan(2⁻ⁱ ). Show that any angle 0 < θ < π/2 can be represented as

where α_i = ±1 and the error is bounded by

(b) The angles θ_i may be computed in advance and stored in a small table of length M. State an algorithm for obtaining the sequence {α_i} for i = 0, 1, . . . , M − 1, such that α_i = ±1. Use your algorithm to determine the sequence {α_i} for representing the angle θ = 100π/512 when M = 11.

(c) Using the result of part (a), show that the recursion

will produce the complex number

where and GM is real, is positive, and does not depend on θ. That is, the original complex number is rotated in the complex plane by an angle and magnified by the constant GM.