按时间抽取基-2快速傅里叶变换的误差分析

按时间抽取基-2快速傅里叶变换的误差分析

由于2-2傅里叶变换（dft）的运算量从二维减少到nlbn，因此该算法在实时处理器中得到了广泛应用。如Welch讨论了定点运算的防溢出问题,给出了块浮点FFT输出的误差限;Thong和Liu考虑了块浮点FFT输出误差的直流分量;Meyer分析了蝶算中不同量化位置对FFT性能的影响;Ma和Reddy考虑了截断误差相关性;Chowdary和Steenaart通过增加运算字长的方法减小了FFT误差。但均没有给出明确的误差分析模型,且有的推导依据不充分,实际应用性不强。FFT算法的误差分析对于FFT硬件处理器的设计非常重要,利用它可大致估计出所需的运算字长和变换点数,并可得到较准确的FFT输出结果精度和信噪比。作者对DIT基-2FFT算法的误差进行了分析,给出了明确的误差分析模型,得到了准确的FFT输出误差限。为简化分析和推导过程,只考虑蝶形运算中的有限字长引入的均方误差,不考虑FFT输出误差的直流分量。1fft的算法对N点DFT运算,有X(k)=Ν-1∑n=0x(n)WnkΝ,k=0,1,…,N-1。(1)DIT基-2FFT算法按输入数据时标的奇偶逐级进行分解,最终将N=2υ(υ为正整数)点的DFT运算转化为υ=lbN级,每级N/2个2点蝶形运算,每一蝶算结构完成如下迭代运算:{Xs(i)=Xs-1(i)+Xs-1(j)WkΝ‚Xs(j)=Xs-1(i)-Xs-1(j)WkΝ‚(2)式中:s为蝶形运算的级数,s=1,2,…,υ;i,j为数据所在行数和列数;WN=exp(-j2π/N)。根据DIT基-2FFT算法的信号流图,可以得到FFT蝶算误差的规律如下:①复乘误差源从第三级蝶算开始,第s级蝶算的复乘误差源数目为2υ-s+1(2s-2-1);②第s级蝶算的每个复乘误差源传播到FFT输出结果中的2υ-s+1个频点;③复移误差源从第一级蝶算开始,每个FFT输出结果的复移误差源数目都是υ∑s=12υ-s=2υ-1。2复加运算的信息输出算法FFT算法实现中常用的是定点和块浮点两种数据格式,块浮点FFT以定点运算的高速度达到了浮点运算的高精度。一次基-2蝶算最大溢出为2bit,复乘运算时可能溢出1bit,复加运算时又可能溢出1bit,故需对这两级运算进行符号扩展,以防止输入信号动态范围过大时定点加法运算溢出。块浮点FFT算法的实现由溢出检测单元和指数累加单元两部分组成。溢出检测单元对每级FFT蝶算结果进行溢出检测,输出结果为本级蝶算的最大溢出位数,范围为0～2bit。指数累加单元对每级FFT的溢出检测结果进行累加,最后得到一帧FFT结果的块浮点指数。根据上述讨论可知,DIT基-2FFT算法的定点FFT的蝶算误差分析模型如图1所示,块浮点FFT的蝶算误差分析模型如图2所示。3fft的均方误差对实数乘法和实数移位运算,假设数据格式为(b+1)bit的二进制补码,截断、舍入和收敛舍入(舍入到最近偶数)3种量化方法的均值与方差如表1所示,Q=2-b为量化步长。假设FFT输入数据的块浮点指数为0,误差上限时每级FFT蝶算发生一次溢出,且溢出由复加运算引入,误差下限时无溢出,各误差源之间无关。根据表1以及图1、图2所示的误差分析模型,可以得到第s级蝶算的均方误差如表2所示。由表2可以看出,舍入与收敛舍入两种量化方法的均方误差大小相等,所以下面只计算FFT输出的截断均方误差和舍入均方误差。3.1中断量化误差3.1.1输出频点复乘均方误差误差上限时,由于第s级蝶算有2υ-s+1(2s-1-1)个复乘误差源,每个复乘误差源传播到FFT输出结果中的2υ-s+1个频点,第s级蝶算的复乘均方误差为7Q222(s-1)/3,所以FFT所有输出频点复乘均方误差的总和为δmut=υ∑s=32υ-s+1(2s-2-1)2υ-s+17Q2322(s-1)=7Q26(Ν3-2Ν2lbΝ)。(3)平均每个输出频点的复乘均方误差为δmu=δmutΝ=7Q26(Ν2-2ΝlbΝ)。(4)误差上限时,由于每个FFT输出频点的复移误差源数目都是υ∑s=12υ-s=2υ-1,第s级蝶算的复移均方误差为Q222s/4,所以每个FFT输出频点的复移均方误差为δsu=υ∑s=12υ-sQ2422s=Q22(Ν2-Ν)。(5)误差下限时,第s级蝶算的复乘均方误差为7Q2/3,故此时FFT所有输出频点复乘均方误差的总和为δmlt=υ∑s=32υ-s+1(2s-2-1)2υ-s+17Q23=7Q218(Ν2-6Ν+8)。(6)平均每个输出频点的复乘均方误差为δml=δmltΝ=7Q218(Ν-6+8Ν)。(7)由于误差下限时没有溢出,所以此时的复移均方误差为0,即δsl=0。(8)3.1.2复移均方误差误差上限时,定点FFT的复乘均方误差与块浮点FFT误差下限时相同,见式(6)(7),复移均方误差为δsu=υ∑s=12υ-sQ24=Q24(Ν-1)。(9)误差下限时,定点FFT的复乘、复移均方误差与块浮点FFT时误差下限时相同,见式(6)(7)(8)。3.2单元源的量化误差根据表2,同上述分析方法,可以求得舍入量化时块浮点、定点两种FFT输出的误差上限和下限。3.2.1复移均方误差的上限和下限误差上限时,FFT所有输出频点复乘均方误差的总和为δmut=υ∑s=32υ-s+1(2s-2-1)2υ-s+1Q2322(s-1)=Q26(Ν3-2Ν2lbΝ)。(10)平均每个输出频点的复乘均方误差为δmu=δmutΝ=Q26(Ν2-2ΝlbΝ)。(11)复移均方误差与截断量化方法块浮点FFT的误差上限时相同,见式(5)。误差下限时,FFT所有输出频点复乘均方误差的总和为δmlt=υ∑s=32υ-s+1(2s-2-1)2υ-s+1Q23=Q218(Ν2-6Ν+8)。(12)平均每个输出频点的复乘均方误差为δml=δmltΝ=Q218(Ν-6+8Ν)。(13)误差下限时没有溢出,此时的复移均方误差为0,即δsl=0。(14)3.2.2复移均方误差与断续量化方法的关系误差上限时,定点FFT的复乘均方误差与块浮点FFT误差下限时相同,见式(12)(13)。复移均方误差与截断量化方法定点FFT的误差上限时相同,见式(9)。误差下限时,定点FFT的复乘、复移均方误差与块浮点FFT时误差下限时相同,见式(12)(13)(14)。4fft输出噪信比比较为了简化分析,假定FFT输入数据x(n)对不同的n值无关,且x(n)的实部、虚部均匀分布在[-1,1)上且无关,则有E{|x(n)|2}=2/3,E{|X(k)|2}=2N/3。根据本文3中得到的平均每个FFT输出频点的均方误差,可以得到误差上、下限时平均每个FFT输出频点相应的噪信比(RNS)如表3所示。由表3可以得到,误差下限时,对相同的量化方法,块浮点、定点两种FFT算法的RNS相等;舍入(收敛舍入)量化时的RNS比截断量化时低了大约8dB。误差上限时,对相同的量化方法和固定的FFT点数N,块浮点FFT的RNS上限比定点FFT低了大约