1、即输入x(n)，输出为X(k)，分别讨论DFT与与FFT运算及系8.5 DFT与与FFT的有限字长影响的有限字长影响DFT与与FFT在数字滤波器、频谱分析中应用广泛，了解DFT有限字长影响很重要，不过要精确分析是很困难的，只对选择所需要寄存器长度的简化分析就足以。分析时为方便要做许多假设，也采用输入、输出方式进行分析，数量化误差的影响。knNNnWnxkX10knNW8.5.1、DFT直接定点舍入计算误差分析直接定点舍入计算误差分析DFT定义为k=0,1,2,N-1(8.5-1)若将上式中的X(k)当作输出，x(n)当作输入，而的作用相当于单位脉冲响应，的运算流图如图所示。则无限精度下第k个X
2、(k)值2NW1NNW1NW0NWx(0)x(1)x(2)x(N1)X(k)kFkXkX2NW1NNW1NW0NWknNW knNWnx不考虑的量化误差，仅讨论运算引起的误差。因为定点舍入运算每次相乘都会产生误差，与前面的分析类似，将每次舍入误差等效为一个噪声源，此时第k个X(k)值的等效统计模型如图所示。x(0)x(1)x(2)x(N1)(0,k)(2,k)(1,k)(N 1,k)kX knkFNn,10 kFkXkX图8.5-2中X(k)是无限精度下第k个X(k)值的运算结果，是有限精度下第k个X(k)值的运算结果，F(k)是第k个X(k)值运算结果的误差。由图8.5-2可见，各误差直接加
3、至输出端，因此总的误差输出为有限精度运算下的输出为(8.5-2)(8.5-3)通常x(n)、knNW均为复数，计算 knNWnx knNWnxQ knNjknNnxjnxQ2sin2cosImRe的一次复数乘法是由四次实数乘法实现的，因此一次复数乘法会产生四次误差，即 knknjknknWnxknN,4321 knWnxknN,(8.5-4)knknNnxknknNnx,2sinIm,2cosRe21 knknNnxjknknNnxj,2sinRe,2cosIm43为了简化计算对输出噪声F(k)方差的计算，对i(n,k)bi222121(1)所有误差i(n,k)是平稳的零均值白噪声序列；在(i
4、=14)的统计特性作如下假设：2b/2 2b/2均匀分布，故方差；(2)各i(n,k)噪声源彼此不相关；且某一次复乘的四个误差源与其他复乘的噪声源互不相关；(3)各误差i(n,k)与输入x(n)不相关，从而与输出X(k)也不相关。复乘误差的模平方为1224,2242322212bknE22231Bb(8.5-5)由于各i(n,k)噪声源彼此不相关，则 bNnNknEkFE2210223,由得到输出噪声F(k)方差(噪声功率)为(n,k)=1(n,k)+2(n,k)2+3(n,k)4(n,k)2 bNnNknEkFE2210223,由此得到输出噪声F(k)方差(噪声功率)为与FIR系统直接型相同
5、，输出噪声的方差正比于N。(8.5-6)10NknNnX kx n W由于定点运算受到动态范围的限制，要防止X(k)溢出，因此要求 1110001NNNknknNNnnnx n Wx n Wx n(8.5-7)11max00NNnnx nx再由上式可得出输出不溢出的充分条件为(8.5-8)即输入只要乘以1/N因子，就可保证X(k)不溢出。xmax1/N =Nxmax1假设输入x(n)是在1/N 1/N之间均匀分布的白色随机信号，输入信号的方差为2223131Nxmx(8.5-9)2102102nxEWnxEkXENnknNNnNNNNxxNn313122210输出信号的方差为(8.5-10)b
6、bNNNkXEkFE2222223/13/2输出噪信比为(8.5-11)上式表明噪信比与N2成正比，即N增加一倍时，为了保持噪信比不变或运算精度不变，字长必须要增加1位。8.5.2、FFT定点舍入计算误差分析定点舍入计算误差分析1、输出噪信比以基2、时选法为例，分析定点舍入的运算误差，其他FFT算法的误差分析可作相应修改。N=2M点的基2、时选FFT分为M级，每级有N/2各碟形，表示由m列到m+1列的基本模型如图8.5-3所示蝶形定点舍入运算的统计rNW iXm 1 jXm 1Xm(i)Xm(j)(m,j)1bjmE222231,图中基本蝶形节点的下标m+1=M表示输出序列X(k)。由图可见，
7、每个基本蝶形有一次复数乘法，产生一个误差源(m,j)。该误差源与DFT分析中的误差源具有相同的统计特性，所以一次复数乘法引入误差的方差为(8.5-12)m=0表示输入序列x(n)，rNW iXm 1 jXm 1Xm(i)Xm(j)(m,j)12,rNWjmE22,rNWEm jrNW由于定点的加法运算无误差，不影响方差；并且所以乘以系数对方差也没有影响。2,Em j因此各误差源(m,j)通过后级碟形时，即误差从源头传输到输出端时方差不会变化。所以计算第k个X(k)值运算结果的总输出误差F(k)，只要计算从输入端到输出端所涉及的蝶形数量即可。图8.5-4 是N=8点的FFT时选流图，图中红粗线条
8、标明了与X(3)计算相关的蝶形。10NW0NW0NW1NW3NW2NW2NW2NWx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)11111111111第第(1)级四个蝶形级四个蝶形第第(2)级两个蝶形级两个蝶形第第(3)级一个蝶形级一个蝶形第一级四个。由图可见与X(3)有关的蝶形：第三级一个；第二级两个F(3)=7(m,j)，一共有碟形1+2+22=7个 输出噪声源输出噪声方差EF(3)2 =7q2/3=722b/3 由此可以类推N=2M点时噪声输出的一般情况，共有M级1+2+22+2M-1=2M 1=N 1 (
9、8.5-13)蝶形，与第k个X(k)有关的蝶形：M(末级)级一个；M1级(末前级)两个；M2级四个；，总共有碟形 221 NkFE总的输出噪声方差 2221NNkFE jXWiXiXmrNmm1当N很大时(8.5-14)由图8.5-3的可见蝶形的运算关系为(8.5-15)jXWiXiXmrNmm1由上式可以得到 jXWiXiXmrNmm1(8.5-16)的两倍。一个N点FFT有M=log2N级蝶形，所以FFT的最这说明，蝶形结的输出最大值不超过，但有可能为输入后输出不超过，但有可能为输入的N=2M倍。即=Xm(i)+Xm(j)2maxXm(i),Xm(j)maxX(k)2Mmax x(n)=N
10、 maxx(n)所以若要保证X(k)不溢出，即maxX(k)1，就(0nN 1)(8.5-17)2223131Nxmx假设信号是在1/N1/N之间均匀等概分布的白色随机信号，其方差为(8.5-18)maxX(k)2Mmax x(n)=N maxx(n)要求x(n)1/N 2102102nxEWnxEkXENnknNNnNNx312 bbNNNkXEkFE2222223/13/2 FFT输出的方差为(8.5-19)输出噪信比为(8.5-20)bbNNNkXEkFE2222223/13/2噪信比与N2成正比。说明FFT算法仅提高运算速度，噪信比与直接算法相同。每增加一级(M加1)，噪信比增加4倍。
11、或为了保持噪信比不变或运算精度不变，N增加一倍时字长要增加1位。2、改善噪信比的方法输出信噪比不高的原因在很大程度上是由于输入幅度限制的过小所至，这种状况是可以改善的。由前分析可知，一个蝶形结的输出最大不超过输入的两倍。如果如图运算不会溢出。所示，对每个蝶形结都乘以系数1/2，就可以保证蝶形2/rNW1/2Xm(i)Xm(j)1Xm+1(j)Xm+1(i)不同，是把1/N的比例因子分解到每级运算中。因为共有M=log2N级碟形，所以对全部FFT运算相当设置了比例因子(1/2)M=1/N。与前面所讨论的FFT处理因此在保持输出信号方差不变的情况下，输入幅度增加了N倍，即(8.5-21)这种处理输
12、出信号方差不变，但输出噪声却小得多。x(n)1 1/22/rNWbjmEimE2222231,bjmEimE22222322,由图可见，由于多乘了一个系数，每个蝶形噪声源由一个变为两个，且这样每个蝶形噪声方差为Xm+1(j)Xm+1(i)Xm(i)Xm(j)(m,j)(m,i)1用，其幅度被衰减到1/2，而方差被衰减到1/4。这个误差每通过后一级蝶形，受1/2比例因子的加权作注意到噪声源所处的运算级不同，则最后的影响不同。2E F k因此输出噪声的总方差为222212211112222444MBBBBM222212211112222444MBBBBM12221212112MBMBMB2/114
13、2/112/11222 bBkFE2222344若M1，则输出方差为(8.5-22)上式证明，噪声方差一次次的被(1/2)2衰减，使得输出 222411/21/3MBE F kNEX k这个结果正比 N 而不是 N 2。输出噪信比：的方法好。噪声越来越小的处理方法，比一次性乘以1/N比例因子(8.5-23)22423423bbNN说明保持噪信比或运算精度不变的情况下，每增加一级蝶形只要增加二进制的半个数位(字长)；或每增加两级蝶形只要增加二进制的一个数位(字长)。因此把1/N的衰减分解到每级蝶形，以改善输出噪信比，应该是更好的选择。rNmmmmWjXiXejX11rNW rNmmmmWjXiX
14、eiX11Xm(j)Xm(i)(m,j)8.5.3、FFT浮点舍入计算误差分析浮点舍入计算误差分析与定点情况相同，对不同的FFT算法，相应的有限字长效应不同。仍以基2、时选N=2M 为例，从一个蝶形运算产生的误差开始讨论。图中符号意义与定点运算统计模型相同。单个蝶形浮点运算统计模型如图所示，1 11mrNmmmeWjXiXiX蝶形上端输出为(下端输出的讨论相同)(8.5-24)其中em+1具有实部和虚部，即em+1=er+j eier、ei分别由Xm+1(i)的实部和虚部运算所决定。浮点运算不论加法、乘法都产生误差，而在这个运算中有两次乘法、两次加法，均引入舍入误差，均用相对误差表示，即以1、
15、2表示乘积引入的相对误差，以1、2表示加法引入的相对误差。iXjXWjXWiXmmrNmrNmReImImReReRe1(8.5-25)先分析实部误差er(虚部误差ei可以类推)，因为 qXWmrNReRe qXWmrNImIm pXepXmrm11eRReReXm(i)各噪声源与运算的关系如图所示。1+21+11+11+2 2111111ReReeRjXWiXmrNm 22121Re111ImImiXjXWmmrN由图8.5-7得到浮点实部运算的输出为式中ReXm+1(i)为无限精度实部运算结果，er为有限精度=ReXm+1(i)+er(8.5-26)实部运算结果的误差。从表达式中略去、的所
16、有高次项，可得：112ReRerrNmeWXq bBnEnEnEnE2222212221231为分析简便，作如下假设(1)、所有误差源与信号x(n)不相关、独立；都是彼此独立、白色、等概分布，具有相同方差，因此 2122ImImRerNmmWXqXp(2)、x(n)是白色；实、虚部方差相同；且同一级各节点方差相同，即EReXm(q)2=EImXm(q)2EXm(q)2=EXm(q)2=(1/2)E Xm(q)2由此得到实部误差的方差为 222221Re3qXEWeEmrNBr 222222121Im3pXEqXEWmBmrNB 222qXEmB(8.5-27)2222pXEeEmBi 2222
17、21214pXEeEeEeEmBirmm同理可得到虚部误差的方差为(8.5-28)上式表明浮点制的输出节点噪声与其输入节点变量相关。(8.5-29)则输出节点噪声em+1的方差为 21222122224qXEqXEqXEkFEMMMB与定点分析情况相同，因为前一级误差通过后一级蝶形时其方差保持不变，所以浮点FFT总的输出误差与从输入x(n)到输出X(k)经过的蝶形个数相关，与第k个F(k)有关的蝶形：M(末级)级一个；M1(末前级)级两个；M2级四个；，即在输出端总的输出误差方差为(8.5-30)rNmmmWjXiXiX1因为每级蝶形输出信号的方差是输入信号方差的2倍，即(8.5-31)求式(
18、8.5-31)的方差，可得(8.5-32)EXm+1(i)2=EXm(i)2+EXm(j)2=2 EXm(i)2=2 EXm(j)2利用这一关系类推，将所有Xm(j)的方差用X(k)的方差表示为EXM1(j)2=0.5 EX(k)2；EXM2(j)2=(0.5)2 EX(k)2；Ex(j)2=(0.5)M EX(k)2；22kFEF MMBkXE2122122141222 2222224kXEMMkXEBB bBMMkXEkFE22222322将上面的关系代入(8.5-30)式，得到最后总的输出误差方差为 输出噪信比(8.5-34)(8.5-33)小变化，这也是所有浮点制运算的共同特点。由上式
19、可见，输出噪信比正比M，远远小于定点制的N=2M。这一结果表明相同尾数字长情况下，浮点噪信比比定点小(运算精度高)。当然，这是由浮点制数字表达的复杂性换来的；另外浮点噪信比不随信号幅度大 nkNNnWnxkX108.5.4、FFT的系数量化效应的系数量化效应无限精度表示的DFT为化误差等效为随机噪声，用统计的方法分析系数量化效了解FFT系数量化效应影响很有必要，但要精确分析也不易。所以分析时为方便要做许多假设，也采用输入、输出方式分析，即输入为 x(n)，输出为X(k)。将系数量应。kFkXWnxkXnkNNn10nkNW均是WN的各次幂系数，其中一些可能是不需相乘的1。(i=1,2,M)，总
20、的乘积为nkNaNMiWWi1iaNW系数量化后，上式可表示为(8.5-35)式中F(k)是由系数量化引起的DFT计算误差由某个 x(n)计算X(k)要经过M=log2N个碟形，故中有M个因子，为了分析方便，也为了得到最差情况下误差的影响，假定这M个因子都有误差，即x(n)通过每级碟形时，都乘了系数。kFkXWnxWnxkXiaNMiNnnkNNni11010iaNWiaNiW成为系数量化后，每个支路的，从而(8.5-36)nkNnkNNnWWnxkXkXkF10iMiaNMijjiNnaNMiiaNMinkNjiiWWWW111011则系数量化后的误差为因为(8.5-37)jiiaNMijj
21、iNnaNMiiaNMinkNWWWW11011jaNMijjiNnnkNnkNWWW110与前相同，假定i是统计独立、白色等概的随机变量，0110110jjaNMijjiNnaNMijjiNnnkNnkNWEWEWWE一般i 很小，忽略与其有关的高次项，(8.5-38)故(8.5-39)则有 010nkNnkNNnWWEnxkFE 6/26/2ImRe2222222beiiiqEEiiaNMijjbWj1nkNnkNWW20002iiMniiMniiMnnkNnkNbEbbEWWE220iiMnbE所以(8.5-40)i的方差为令，的方差为11jaNMijjiWb6/222MqMEWWEin
22、kNnkN 21022nkNnkNNnFWWnxEkFE 6/22102210MqnxWWEnxNnnkNnkNNn bNnMnx221026因为，所以(8.5-41)由式(8.5-37)的输出误差的方差为(8.5-42)2F 2102101kXNnxNkNn实际上系数量化误差与运算误差不同，对一个确定的滤波器，系统的字长b一定，每个系数量化后的数值是可知的，其系数的量化误差也是确定值。在分析中将其假设为随机变量，用统计方法分析是为了对误差的大小作概率估计，即是最有可能出现的估值。由上式估计的误差比实际误差稍大，可做大致估计之用。根据帕塞维尔定理(8.5-43)bNkFMkXN22102261式(8.5-43)是输出序列的平均功率，假定输入x(n)是统计独立、白色等概的随机变量，则X(k)也是统计独立、白色等概的随机变量，序列的平均功率与序列的方差相等，由此得到噪信比为(8.5-44)差，但仍不失其粗略估计，选择所需要寄存器长度(字上式表明噪信比与M=log2N成正比，因而随N增加而增加的速度很慢。当N加倍时，M只增加1，噪信比增加不大。上述有关误差的所有统计分析与实际情况都有一定的误长)的意义。
