问答题
在计算实数序列f(k)的FFT时，可以结合题设复数序列c(k)=x(k)+jy(k)，其中x(k)和y(k)是两个实数序列，分别对应于c(k)的实部和虚部。假设已知c(k)的DFT等于C(m)，求x(k)。进一步降低运算量。试推导此时计算过程，估计计算量(复数加法和乘法的次数)。
【正确答案】
【答案解析】解 先将实数序列f(k)的奇数项和偶数项分别构成两个长度为
的实数序列，f
o
(k)和f
c
(k)，再将二者合成一个复数序列。
则
且
而由基2时间抽取FFT算法的推导过程可知，f(k)的DFTF(m)为
于是我们可将求f(k)的DFT的过程分为以下几步：
(1)利用
点FFT计算得到C(m)，在此步需要的计算量为
乘法次数：
加法次数：
(2)分别求出F c (m)和F o (m)，此步需要的计算量为
乘法次数：
加法次数：
(3)求出F(m)和
，此步需要的计算量为
乘法次数：
加法次数：
所以总的计算量为
乘法次数：
加法次数：
的实数序列，f
o
(k)和f
c
(k)，再将二者合成一个复数序列。
则
且
而由基2时间抽取FFT算法的推导过程可知，f(k)的DFTF(m)为
于是我们可将求f(k)的DFT的过程分为以下几步：
(1)利用
点FFT计算得到C(m)，在此步需要的计算量为
乘法次数：
加法次数：
(2)分别求出F c (m)和F o (m)，此步需要的计算量为
乘法次数：
加法次数：
(3)求出F(m)和
，此步需要的计算量为
乘法次数：
加法次数：
所以总的计算量为
乘法次数：
加法次数：