6.0引言:直接计算DFT的运算量分析 k X(k)∑ 复数乘法复数加法 x(ne 每一个X(k) ∑ nk N个X(k) N(N-1) r(n N点DFT) (e+j)+(g+j)=(e+g)+j(f+h) a+ jb(c+ jd)=(ac-bd)+j(ad+cb) 实数乘法 实数加法 复加的加 次复乘 4 复乘的加 2 法次数 法次数 次复加 每一个X(k) AN 2N+2(N-1)=2(2N-1) N个X(k)N点DFT)4N2 2N(2N-1)6.0 引言：直接计算 DFT 的运算量分析 10 复数乘法 复数加法 每一个X(k) N N – 1 N 个X(k) (N 点 DFT) N 2 N (N – 1) 实数乘法 实数加法 一次复乘 4 2 一次复加 2 每一个 X (k) 4N 2N+2 (N – 1)=2 (2N – 1) N个X (k) (N点DFT) 4N 2 2N (2N – 1) 1 0 1 0 2 X(k)= ( ) ( ) N n N nk N n j nk N x n n e W x          a jb c jd ac bd j ad cb             复乘的加 法次数 复加的加 法次数 e jf g jh e g j f h              