基于fpga的乘法器的设计与实现

基于fpga的乘法器的设计与实现

1fpga器件在系统中应用的必要性过去，数字信号系统（pd）的构建主要以通用sd芯片为核心。在需要率高的情况下，需要使用特殊的sd芯片或专用于瑞士军（ios）的电路进行设计和实现。随着现场可编程门阵列(FPGA)的快速发展,数字信号处理系统的构建又多了一种选择方案。FPGA器件作为ASIC的一个重要分支,是一种已经完成了全部工艺制造,可以直接从市场购买的产品,用户只需对它编程就可以实现所需要的功能,并且在保持了传统ASIC低功耗、轻小型化、高可靠性等优点的同时,还具有较高的设计灵活性和适应性,具体体现在以下几个方面:①开发周期短,可以迅速投放市场;②同微处理器一样,FPGA几乎可以无限次重复编程,一旦想要升级你的设计,无需更换芯片,只要对其重新编程即可;③FPGA具有动态可重构特性,这使得一个系统具有多种功能成为了可能,设计者只需要根据变化了的条件改变FPGA内部电路的配置即可;④开发成本低,具有较大的价格优势。虽然FPGA器件具有如此诱人的优势,但是在采用FPGA器件构建DSP系统时却存在着一些困难,原因在于:基于FPGA的DSP设计工具还不够完善,大多数设计者缺乏设计运算密集型器件的实际经验,以前为微处理器开发的软件算法很难转换为硬件实现。有鉴于此,讨论分析并设计实现适应FPGA结构的有关DSP算法很有意义。乘法是DSP运算中的基本算法,应用也最为广泛。我们知道,乘法最基本的操作就是移位相加,各类乘法最终都要归结为这一点。然而如何实现移位相加却有多种方法,其中有一些更为适合FPGA应用。本文主要讨论分析移位累加乘法器、查询表乘法器、Booth乘法器、加法器树结构乘法器。2加法器至2n位移位累加是最基本的硬件乘法器实现方式,大多数的单片机和微处理器的乘法运算都采用这种方法。基本原理如图1所示:将两个操作数分别以串行和并行模式输入到乘法器的输入端,用串行输入操作数的每一位依次去乘并行输入的操作数,每次的结果称之为部分积,将每次相乘得到的部分积加到累加器里,形成部分和,部分和在与下一个部分积相加前要进行移位操作。传统的移位累加乘法器实现起来相对比较简单,考虑到二进制乘法中,两个操作数位宽都为N位时,其积的位数一般为2N位,所以8位乘8位的乘法需要一个16位的移位寄存器和一个16位的加法器就可以实现。由于这种乘法器需要移位——加两步才能得到一个部分和,因此若两个操作数位宽都为N,则整个运算需要2N个时钟周期。仔细观察传统的移位累加乘法器可以发现:第一,虽然两个N位的操作数相乘结果为2N位,但是中间过程的每一个部分积都为N位,移位相加的有效宽度也是N位,因此可以考虑用N位的加法器来代替2N位的加法器以减少资源耗费;第二,可以考虑将移位和累加合在一起进行,实现一步得到部分和,这样对于两个位宽都为N位的操作数相乘,只需要N个时钟周期就可以完成。具体实现方法为:将串行操作数存于寄存器A中,并行操作数存于寄存器B中,部分和存于寄存器S中,这三个寄存器位宽都为N,另外设置一个一位的寄存器C用以存放临时进位。运算框图如图2所示。首先,将寄存器S清零,部分积由A决定(或者为零,或者为B),将位宽都为N的部分积和寄存器S中的值输入到一个N位的加法器中求和,结果(包括一位进位)与A[N-1:1]合并在一起形成2N位的部分和,然后将这2N位部分和的高N位送到寄存器S中,低N位送到寄存器A中继续进行运算,直到N个周期为止。这样,这个运算只需要一个N位的加法器,N个时钟周期就可完成。相对于传统的移位累加乘法器来讲,既简化了逻辑,又提高了性能。上面讨论的仅是无符号数相乘,对于符号数相乘,可以将符号与绝对值分别处理,即:绝对值相乘,符号异或。3进行扩展实现方法布思算法(Boothalgorithm)是由布思夫妇首先提出来的。他们发现:当乘数中连续出现“1”位时,可以通过使用减法来减少所需进行累加的部分积的数量。如图3所示,用乘数15(A)去乘被乘数89(B),这需要四个1XB的部分积移位累加,而这同下图右侧的减法所得的结果是一致的。我们这里只讨论比较简单的一种情况。即为了提高乘法的运算速度,在一拍中考虑两位乘数,根据两位乘数的组合决定本拍内应进行什么操作,从而在一拍内求得与两位乘数相对应的部分积。这种一拍处理两位乘数的方法反映了布思算法的基本思想,也称作两位乘法,其速度比一位乘法提高近一倍。具体实现方法如下:首先假设乘数A位宽为N,若N为奇数,则需对其高位进行扩展,使之位数为偶数。扩展的实现只需在高位前添零即可(这里只考虑A为无符号数;如果A为有符号数,则可用补码表示:以补码表示的二进制数据,扩展其最高位,并无影响。)这样经过处理后,乘数A位宽为M,M为偶数。则编码做表如下:其中+3B的运算,用普通的加法器不能一次完成。如果分为两次执行,则又降低了速度。我们可将3B当作(4B-B)来处理,本次操作执行-B,用一个欠账触发器CJ记下欠账,下一次操作时再补上+4B。由于本次累加后部分积要右移两位,从相对关系来看,相当于被乘数左移了两位,因而下一次实际上只需执行+B,就等于前次完成了+4B操作。据此,可得布思编码表如下:表2即为Booth2位乘法编码表。运算原则如下:①参加运算的操作数取其绝对值;②符号位单独处理Z0=X0⊕Y0;③欠账触发器CJ初始值为0;④每次根据乘数的相应两位A2nA2n-1和欠账触发器CJ的值决定应执行的操作;⑤减B通过加[-B]补实现,对于2B的实现,只需要将B左移一位;⑥当乘数的数值位为N位(不连符号位),应作N/2次累加和移位,如有欠账,再作一次加。可见,上述布思编码一次处理了两位,确定运算量0、B、2B、-B,形成(M/2)项编码项、乘积项,若乘数有效位为N,则需作N/2次移位,最多作N/2+1次累加。因此,不管从哪方面来说,相对于移位累加乘法器来讲,布思算法方便又快捷。然而,由于引入了欠账触发器CJ,相当于在高二位和低二位之间存在着借位传播。如果用迭代方式,则用一位寄存器保存此借位,也非常简单、方便。但最高两位可能会出现借位,可能增加一次特殊运算,对此需特别注意。无符号数二位Booth乘法与符号数二位Booth乘法,只是在布思编码上有区别,其余全都相同。因此这里不再赘述。4引入部分积技术把乘积放在存储器中,使用操作数作为地址访问存储器,得到的输出数据就是乘法运算的结果。查询表方式的乘法器速度等于所使用的存储器的速度,小型乘法器使用这种技术非常合适。例如,在256字节的查询表中实现4位×4位乘法器可以很轻松地在不到25ns的时间内完成一次乘法运算。下面是一个6输入查找表,表格里的内容就是一个3位乘3位乘法运算的结果。Xilinx公司的现场可编程器件(FPGA)就是基于查找表结构的,因而在其中实现查找表型乘法器非常方便,同时速度也非常快,但是随着操作数精度的提高,查找表变得非常庞大。例如,8位乘法器需要28+8×16这样大的存储器。那么如何能够在充分利用现场可编程器件中查找表这一结构优势的同时,又能够有效的降低资源耗费呢?我们可以考虑引入部分积技术,考虑手算乘法,如图4所示。这里分别计算每一位数字的乘法,然后将各个部分积进行移位和相加,就可得到最后的结果,通过这种方法可以大大的降低查找表的规模。虽然这里所举的例子是十进制的,但是它同样适用于其它进制的数字,只是移位时基数不同而已。下面给出了一个具体的例子来进一步说明上述实现思想,如图5所示。图5中例子说明了部分积技术在硬件中的具体实现,这里采用四个3×3的LUT乘法器实现一个6×6的乘法器。图4中的LUT是完全一样的,各部分积可以同时获得,然后进行相应的移位相加,在这里LUT后面用到了一个加法器树结构,这种结构可以保证在最短的延迟内获得最后的和(后面还会详述)。基于这种思想我们可以利用小型的LUT型乘法器合成任意大规模的乘法器。当然,这里乘法器的资源消耗可以进一步降低,即只采用一个3×3的LUT乘法器和一个累加器,对部分积进行如上一节所述的移位累加,只是这样一来速度也相应要下降。上述乘法器采用小规模的LUT来获得部分积之后进行移位相加,这一方案有效地对性能和资源耗费进行了折衷。目前的现场可编程器件(FPGA)大都是基于4输入的LUT结构,查找表的输入线较少,因此可以考虑采用2×2的LUT乘法器作为这种方案下的基本单元,这样易于实现,并且可以较好地兼顾性能和资源消耗两个方面的要求。5加法器树乘法器结构的改进加法器树实际上由移位相加器和查询表组成,如图6所示,图中的8位×1位乘法器可以用8个与门实现,最终的移位相加器是通过一个并行的加法器来实现的。加法器树需要的加法器数目等于操作数位数减1,加法器精度为操作数位数的2倍,需要的与门数等于操作数的平方。8位乘法器需要7个16位加法器和64个与门。仔细观察图6可以发现,这7个16位加法器中至少有6个可以进一步缩小规模,从而降低资源消耗。同时,为了提高加法器的工作速度,可以采用流水线技术。流水线技术将每一步运算都用寄存器暂存。尽管单个运算需要多个时钟周期才能得到结果,但由于操作数是不断的加入到运算输入端的,所以总的效果是每个加法运算平均消耗的事件等于锁存时钟的周期。8位流水线加法器可以用图7来说明。这样,相应地减小参加运算的加法器的规模,并采用流水线技术,就可以得到改进的加法器树乘法器结构。需要注意的是,这种乘法器最后进行相加运算时,必须对高位乘积进行加权,对低位乘积高位补零,如下图8所示。如果采用流水线技术,加法器树乘法运算需要的时间仅为1个时钟周期。但是要注意:对于所采用的流水线加法器,并不是流水深度越深越好,详见下一节结果分析。6fpga器件使用分析本文在Xilinx公司提供的ISE4.1i软件环境下,使用VHDL和VERILOG语言实现了上面分析设计的几种乘法器,其中4位X4位查找表乘法器中采用了4个4输入LUT并进行了2级移位加运算,8位X8位查找表乘法器中采用了16个4输入LUT并进行了4级移位加运算,加法器树乘法器中所采用的流水线加法器流水深度为4级。综合工具选用FPGAEXPRESS,仿真工具选用ModelSimSE-EE5.44,FPGA器件选择为Spartan2系列的xc2s30-5pq208。结果详见表4。从速度的角度来讲,采用流水线技术的加法器树乘法器最优,从资源占用的角度来讲,移位累加乘法器占用资源最少。总的来看,性能(速度)和开销(资源消耗)是一对矛盾,如何设计器件以提高性价比才是我们首要解决的问题。移位累加乘法器易于在FPGA中实现,资源占用也比较少,但是它有个最大的缺点,就是速度慢,8位乘法需要8个时钟周期才能得到结果,即使时钟选100MHz乘法运算也需要80ns以上,因此一般大量用于单片机和微处理器的乘法运算中,而在运算量大、实时性要求高的领域不推荐使用这种乘法器;Booth乘法器在进行符号数乘法运算时可以不必单独考虑符号位的处理,但是在进行无符号数乘法运算时并没有显著优势;综合考虑,实现规模较小的乘法运算可以使用查找表乘法器,规模较大的乘法运算可以使用采用了流水线技术的加法器树结构乘法器来实