Question

Radix-3 FFT (30 points) Suppose we want to calculate the DFT of a length N sequence where N is a power of 3.

a. Draw the data flow graph for a 9-point decimation-in-time FFT algorithm.
b. Determine (i) the number of butterflies per stage, (ii) the number of multiplies required for each butterfly, and (iii) the number of stages. Use this to determine the overall number of complex multiplies required.

Answer 1

The Radix-3 FFT algorithm is used to calculate the DFT of a length N sequence where N is a power of 3. The number of butterflies per stage, number of multiplies required for each butterfly, and the overall number of complex multiplies required can be determined using this algorithm.

Step-by-step explanation:

The Radix-3 FFT algorithm is used to calculate the DFT of a length N sequence where N is a power of 3. The data flow graph for a 9-point decimation-in-time FFT algorithm can be represented as:

Stage 1:

(3 butterflies, 1 multiply per butterfly)

Stage 2:

(3 butterflies, 1 multiply per butterfly)

Stage 3:

(3 butterflies, 1 multiply per butterfly)

The overall number of complex multiplies required can be calculated by multiplying the number of butterflies per stage by the number of stages and the number of multiplies per butterfly. In this case, it would be 9 (butterflies) * 3 (stages) * 1 (multiply per butterfly) = 27 complex multiplies required.