综合课程设计报告第三组

综合课程设计报告

基于ADSP-2191的数字信号处理实现题目：基二频率抽取的快速傅立叶变换算法小组成员:安海鹏04008220高轩04008213 王康蔚04008215朱峻岗04008212蒋骏宁（组长）04008236东南大学信息科学与工程学院二○一一年一月综合课程设计—基于ADSP-2191的数字信号处理实现-PAGE4-题目概述快速傅立叶变换是一种快速有效地计算离散傅立叶变换的方法。一般情况下输入的时间序列及其离散傅立叶变换是用复数表示的，直接计算DFT及IDFT需要次复数乘法以及次复数加法，由于1次复数乘法对应4次实数惩罚和2次实数加法，1次复数加法需要做2次实数加法，所以1次离散傅立叶变换需要做次实数乘法及次实数加法。20世纪60年代Cooley和Tukey提出了一种离散傅立叶变换的快速算法，将其运算量下降为次复数乘法和次复数加法。本次基于ADSP-2191的数字信号处理实现基二频率抽取的算法就是对上述功能在DSP平台上的利用汇编语言的实现。算法介绍基二频率抽取FFT运算流图图2.1.1图2.1.1为N=16的基二频率抽取的FFT运算流图，构成了课题目标算法的理论基础，流图包含：蝶形运算和序数重排两个部分，总的蝶形个数为，果重新排序得到正确的结果。在N=16的情况下，一共有32次蝶形运算，即一共需要32次复数乘法运算和64次复数加法运算。图2.1.2输入稀疏度为4的N=16的基二频率抽取的FFT运算流图图2.1.2为本课程要求的输入稀疏度为4基二频率抽取的FFT运算流图，从图上可以得到需要进行12次半蝶形运算和16次蝶形运算，一共需要进行28次复数乘法和32次复数加法运算。对比图2.1.1的流图，N=16的FFT运算流图需要32次复数乘法和64次复数加法，图2.蝶形运算与半蝶形运算复数加法与减法复数加法一次复数加法包含行两次实数加法过程。对于实数加法，设输入X操作数X,Y操作数Y，X,Y，且X,Y均为16位有符号数，加法得到的结果Z,Z为17位有符号数。如果输入的X,Y操作数均为，得到的结果就是溢出的，如果将存入寄存器继续运算的话，将带来链式错误。考虑上述情况，需要Z和X,Y具有相同的范围即，本程序采取先将X,Y均算术右移一位，即可使得Z的范围满足要求。同时考虑到，最后一位的舍入误差，在右移后，先将X,Y的最后一位进行加法运算，在考虑进位的情况下，进行主值加法。此方法的误差为不考虑末位进位的1/2，降低的误差率。复数减法一次复数减法包含两次实数减法过程。对于实数减法，设输入X操作数X,Y操作数Y，X,Y，且X,Y均为16位有符号数，加法得到的结果Z,Z为17位有符号数。如果输入的X,Y操作数为和，得到的结果就是溢出的，如果将存入寄存器继续运算的话，将带来链式错误。考虑上述情况，需要Z和X,Y具有相同的范围即，本程序采取先将X,Y均算术右移一位，即可使得Z的范围满足要求。同时考虑到，最后一位的舍入误差，在右移后，先将X,Y的最后一位进行减法运算，在考虑借位的情况下，进行主值减法。此方法的误差为不考虑末位借位的1/2，降低的误差率。复数乘法一次复数乘法包含四次实数乘法和二次实数加法，设输入数据，为一次复数乘法运算的结果，其中为的实部和虚部，其绝对值都不超过1。为输入数据的实部和虚部，其均的范围。在极端情况下，假设均为，在阻止溢出的情况下，可以采取复数加减法的策略，即对进行算术右移后再进行运算，也可以预先设计的输入数格式，将通用的1.15的表示格式变成2.14的表示格式。这样，在输入均为的情况下，依然能够防止输出溢出。序数重排表2.3.1N=16基二频率抽取序号重排位置序号与实际序号输出数据位置序号输出数据实际序号0000X(0)00000001X(8)10000010X(4)01000011X(12)11000100X(2)00100101X(10)10100110X(6)01100111X(14)11101000X(1)00011001X(9)10011010X(5)01011011X(13)11011100X(3)00111101X(11)10111110X(7)01111111X(15)1111模块划分整个程序分为半蝶形运算模块、蝶形运算模块、比特反转模块、源地址与目标地址交换模块。各个模块包含的运算如下表：表3.1模块功能表实数加法实数减法复数乘法数据读写寄存器读写半蝶形运算模块无无有有有蝶形运算模块有有有有有比特反转模块无无无有有源地址与目标地址交换模块无无无无有地址重置与操作间隔改写模块无无无无有实数加法：为2.2.1.1复数加法中描述的实数加法。实数减法：为2.2.1.2复数减法中描述的实数减法。复数乘法：为2.2.2复数乘法中描述的复数乘法，因ADSP2191的乘法加法累加器（MAC）特性，故实数乘法中包含的复数加法减法与2.2.1.1与2.2.1.2中描述无关。数据读写：利用ADSP2191寻址方式，涉及数据寄存器和存储器之间的数据交互。寄存器操读写：包含寄存器读入写出，寄存器特殊位赋值操作。半蝶形运算模块图3.1.1一组N=4的半蝶形运算一次半蝶形运算包含一次数据移动和一次复数乘法运算。全蝶形运算模块图3.2.1一组N=2的全蝶形运算一次全蝶形运算包含一次复数加法、一次复数减法、一次复数乘法。比特反转模块利用ADSP2191自带的比特反转功能实现2.3中的序数重排功能。源地址与目标地址交换模块为了提高ADSP系统存储器的利用率，将上次半蝶形或蝶形运算的源地址作为本次半蝶形或蝶形运算的目标地址，可以减少存储单元的浪费。地址重置与操作间隔改写模块由于中的数据在每次运算中由固定地址读入，而非将数据全部存储于寄存器中，每次蝶形操作或半蝶形操作后，见图2.1.1需要将数据指针重新置于顶部，叫做地址重置。操作间隔改写在于半蝶型运算中一个输入数据需要同时作为两个目标数据的输入数据，而且两个目标数据的间隔在2级半蝶形运算间是变化的。同时，2级全蝶形运算中，一次加法和一次减法乘法的输入数据间隔和目标数据间隔也不一样，所以需要改写操作间隔。定点数处理和各模块中定点数的配置对于，如2.2.1.2所述，将其定义为2.14格式。对于4个输入数据，其实部和虚部均为4.12。一次复数加法、减法、乘法都将提高数据的位数，即4.12格式成为5.11格式，5.11格式成为6.10格式，以此类推。图4.1块浮点数下的数据格式上图为在极端情况下，每次复数加法、减法、乘法都存在进位的情况下的块浮点数格式，输出的数据从6.10格式到10.06格式，在理论精度达到最大的情况下，带来了格式的不统一，数据操作的困难。图4.2定点数下数据格式上图为在极端情况下，每次复数加法、减法、乘法都存在进位的情况下的定点数格式，每一级输出的格式都是相同的，最后的输出格式为10.06。定点实现与浮点结果对比测试序列：（4.12输入格式）I路（实数部分）：Q路（虚数部分）：用复数表示为：块浮点计算结果与MATLAB仿真对比仿真I计算I(MATLAB)误差仿真Q计算Q(MATLAB)误差FC00FC000FC00FC0000CF70CF8029302941B361B37F4BAF4BA00B0D0B0D0EF74EF75000000000D800D8000F7EAF7EA0F3E6F3E60FB77FB770FE1FFE20030A030BFF65FF66160016000EA00EA000040004000EBE1EBE10F865F8650EDA3EDA30FA0FFA0F0FC07FC08FA00FA00000000000000CD00CD0FF77FF7801440145FCF0FCF1FFAFFFB0FE6CFE6DMALTAB计算使用ROUND函数，CEIL,FLOOR差距均不大参考流图4.1中所对应的数据格式，所有的误差均不超过对应块浮点最后一位的绝对值，误差来源有：精度误差，即值用2.14格式的16位数表示带来的误差；舍入误差，因为运算进位的关系，若干位值被自动忽略。定点计算结果与MATLAB仿真对比仿真I计算I(MATLAB)误差仿真Q计算Q(MATLAB)误差FFC0FFC00FFC0FFC00019E019F0052005303660367FE97FF97002C302C4FBDDFBDD0000000000FB00FB000FDFAFDFA0FCF9FCF90FEDDFEDEFF87FF88018501850FFB2FFB302C002C00FD40FD400010001000FAF8FAF80FE19FE190FB68FB69FD07FD070FE04FE040FE80FE800000000000006600660FFBBFFBC00A200A20FE78FE780FFAFFFB0FE6CFE6C0MALTAB计算使用ROUND函数，CEIL,FLOOR差距均不大。参考流图4.2中所对应的数据格式，所有的误差均不超过对应块浮点最后一位的绝对值，误差来源有：精度误差，即值用2.14格式的16位数表示带来的误差；舍入误差，因为运算进位的关系，若干位值被自动忽略。算法复杂度统计对于最终的程序，即定点数法图4.2流图，经过统计一共进行了16次复数加法，16次复数减法，28次复数乘法，28次位移操作。一共进行了3次半蝶形函数调用，每次进行4次半蝶形运算；8次全蝶形函数调用每次进行2次全蝶形运算；1次比特反转。1次实数加法对应8个指令周期，1次实数减法对应8个指令周期，1次复数乘法对应5个指令周期。主体含103个指令周期（不含最后RTS），比特反转占74个指令周期，一次半蝶形函数含91个指令周期，一个全蝶形函数含135个指令周期，整个程序调用需要1530个指令周期。小结这次基于ADSP2191平台的课程设计给予了我们一次用实践检验理论正确性的机会，增进了团队间的合作，提高了小组成员间协作分工的能力。在此过程中，实际中的很多限制，比如定点数等给予了我们在设计算法中提出了许多挑战，也让增进了我们，在现实环境中去应用理论的能力参考文献[1]吴镇扬数字信号处理第二版高等教育出版社[2]胡广书数字信号处理理论算法与实现第二版清华大学出版社源代码/************************************************************************//filename:test.asm//purpose:bodyofprogram#definenum4#definecoe8#definegap1=8;#definegap2=4;#definegap3=2;.externadd;.externsub;.externmulti;.externhalfbutterfly;.externtotalbutterfly;.externsoudes;.externbitrev;/*DMdata*/.section/datadata1;.varinput_i[num]="input_i.dat"; //inputitakes8000-8003.varinput_q[num]="input_q.dat";//inputqtakes8004-8007.var coeff_i[coe]="coeff_i.dat";//coeffitakes8008-800f.var coeff_q[coe]="coeff_q.dat";//coeffqtakes8010-8017/*PMinterruptvectorcode*/.section/pmIVreset;JUMPstart;NOP;NOP;NOP;/*Programmemorycode*/.section/pmprogram;start: i0=input_i; i1=input_q; i2=coeff_i; i3=coeff_q; m0=1; // m3=1;//forcos m4=1;//increaseindatareadandwrite m5=8;//gap m6=1;//increasebetweentwo i4=0x8040;//resultaddressfori i5=0x8050; //resultaddressforq //layerone callhalfbutterfly; //atthistimewedon'tneedi0i1sowechoosei0i1asournextdestinationaddress //i0=0x8040; //i1=0x8050; //i4=0x8020; //i5=0x8030; //callsoudes; //callcossinrst; i2=coeff_i;//returncostostart i3=coeff_q;//returnsintostart //layertwo i0=0x8040; i1=0x8050; i4=0x8020; i5=0x8030; m3=2; m5=4;callhalfbutterfly;// callcossinrst; i2=coeff_i;//returncostostart i3=coeff_q;//returnsintostart ax0=dm(i0+=4); ax0=dm(i1+=4); ax0=dm(i4+=4); ax0=dm(i5+=4); callhalfbutterfly; //callcossinrst; i2=coeff_i;//returncostostart i3=coeff_q;//returnsintostart //callsoudes; i0=0x8020; i1=0x8030; i4=0x8040; i5=0x8050; //layerthree m0=1;//gapbetweentwooutput m1=2;//gapininput m5=2;//gapinoutput m6=1;//gapbetweentwooutput m3=4; cntr=4; docir_3untilce; calltotalbutterfly; ax0=dm(i0+=2); ax0=dm(i1+=2); ax0=dm(i4+=2); ax0=dm(i5+=2); // callcossinrst; i2=coeff_i;//returncostostart i3=coeff_q;//returnsintostart cir_3:nop; // callsoudes; i0=0x8040; i1=0x8050; i4=0x8020; i5=0x8030; //layerfour m3=0; m0=2; m1=1; m5=1; m6=2; cntr=4; docir_4untilce; calltotalbutterfly; // callcossinrst; i2=coeff_i;//returncostostart i3=coeff_q;//returnsintostart //ax0=dm(i0+=2) cir_4:nop; //callsoudes; i4=0x8020; i5=0x8030; i0=0x0201; i1=0x0a01; //bitrev callbitrev;rts; //filename:add.asm//purpose:addopcode//.globaladd;.globaladd;/*programmemorycode*///input:ax0,ay0,outputar.section/pmprogram;add: se=-1; sr=ashiftax0(hi); ax0=sr1;ax1=sr0; sr=ashiftay0(hi); ay0=sr1;ay1=sr0; ar=ax1+ay1; ar=ax0+ay0+c; rts; //filename:sub.asm//purpose:subopcode//inputax0,ay0,outputar.globalsub;.section/pmprogram;sub: se=-1; sr=ashiftax0(hi); ax0=sr1;ax1=sr0; sr=ashiftay0(hi); ay0=sr1;ay1=sr0; ar=ax1-ay1; ar=ax0-ay0+c-1; rts;//filename:multi.asm//purpose:multiplyopcode.globalmulti;.section/pmprogram;//(a+bi)*(c+di)=ac-bd+(ad+bc)imulti: mr=mx0*my0(ss); mr=mr-mx1*my1(ss); sr=mx0*my1(ss); sr=sr+mx1*my0(ss); rts;//filename:halfbutterfly.asm//purpose:halfbutterflyopcode.globalhalfbutterfly;.section/pmprogram;halfbutterfly: cntr=4;//doitfor4timesdocircleuntilce; ax0=dm(i0+=m0);//readIdata ax1=dm(i1+=m0);//readQdata my0=dm(i2+=m3);//readcosdata my1=dm(i3+=m3);//readsindata mx0=ax0;//formultiply mx1=ax1;//formultiply callmulti; mx0=mr1;//Idata mx1=sr1;//Qdata dm(i4+m5)=mx0;//saveIdata dm(i5+m5)=mx1;//saveQdata se=-1; sr=ashiftax0(hi); ax0=sr1; dm(i4+=m4)=ax0;//saveIdata sr=ashiftax1(hi); ax1=sr1;circle: dm(i5+=m4)=ax1;//saveQdata rts;//filename:totalbutterfly.asm//purpose:totalbutterflyopcode.globaltotalbutterfly;.section/pmprogram;totalbutterfly:cntr=2;//do2timesdocircle2untilce; m2=0; my0=dm(i2+=m3);//readcosdata my1=dm(i3+=m3);//readsindata //ar=ax0-ay0;//realI-realQ ay0=dm(i0+m1);//readIdata ax0=dm(i0+m2);//readIdata callsub; mx0=ar; //ar=ax1-ay1;//imageI-imageQ ay0=dm(i1+m1);//readQdata ax0=dm(i1+m2);//readQdata callsub; mx1=ar; callmulti; dm(i4+m5)=mr1;//saveIdata dm(i5+m5)=sr1;//saveQdata //calladd; //ar=ax0+ay0;//realI+realQ ay0=dm(i0+m1);//readIdata ax0=dm(i0+=m0);//readIdata calladd; se=-1; s