We have seen that an FFT algorithm can be viewed as an interconnection of butterfly comp...

We have seen that an FFT algorithm can be viewed as an interconnection of butterfly computational elements. For example, the butterfly for a radix-2 decimation-in-frequency FFT algorithm is shown in Figure P9.34-1. The butterfly takes two complex numbers as input and produces two complex numbers as output. Its implementation requires a complex multiplication

by where r is an integer that depends on the location of the butterfly in the flow graph of the algorithm. Since the complex multiplier is of the form the CORDIC (coordinate rotation digital computer) rotator algorithm (see Problem 9.46)

can be used to implement the complex multiplication efficiently. Unfortunately, while the CORDIC rotator algorithm accomplishes the desired change of angle, it also introduces a fixed magnification that is independent of the angle θ. Thus, if the CORDIC rotator algorithm were used to implement the multiplications by , the butterfly of Figure P9.34-1 would be replaced by the butterfly of Figure P9.34-2, where G represents the fixed magnification factor of the CORDIC rotator. (We assume no error in approximating the angle of rotation.) If each butterfly in the flow graph of the decimation-in-frequency FFT algorithm is replaced by the butterfly of Figure P9.34-2, we obtain a modified FFT algorithm for which the flow graph would be as shown in Figure P9.34-3 for N =8. The output of this modified algorithm would not be the desired DFT.

(a) Show that the output for the modified FFT algorithm is Y [k] = W[k]X[k], where X[k] is the correct DFT of the input sequence x[n] and W[k] is a function of G, N, and k.

(b) The sequence W[k] can be described by a particularly simple rule. Find this rule and indicate its dependence on G, N, and k.

(c) Suppose that we wish to preprocess the input sequence x[n] to compensate for the effect of the modified FFT algorithm. Determine a procedure for obtaining a sequence from x[n] such that if is the input to the modified FFT algorithm, then the output will be X[k], the correct DFT of the original sequence x[n].