Butterfly Computation Flow graph of basic butterfly computation (m-1)st mth (m-1)st mth stage stage stage stage WN)-WW ww 2=-1 We can implement each butterfly with one multiplication Final complexity for decimation-in-time FFT (N/2)log2N complex multiplications and Nlog2N additions mN/2 m=log2N mN23 Butterfly Computation ◆Flow graph of basic butterfly computation ◆We can implement each butterfly with one multiplication ◆Final complexity for decimation-in-time FFT (N/2)log2N complex multiplications and Nlog2N additions r WN ( / 2) / 2 = r N r N W W W N N N + r WN / 2 1 N WN = − mN/2 m=log2N mN