ChineseJournalofElectronDevices
电子器件
Vol.34摇No.6Dec.2011
PerformanceComparisonsforFPGA鄄BasedDigitalMultipliers*
JUFang,MAXin*,TIANLan
(CollegeofInformationScience&Engineering,ShandongUniversity,Jinan250100,China)
Abstract:TheprinciplesandrealizingprocessesoffourkindsofFPGAdigitalmultiplierswhicharenamedarray,digitalmultipliersinAlteraFPGAchip,theperformancesinspeedandresourcesconsumptionarealsopresentedKeywords:digitalmultiplier;FPGA;computingspeed;logicresourcesconsumptionEEACC:7220摇摇摇摇doi:10.3969/j.issn.1005-9490.2011.06.027
whenMultiplierhaslargerdatawidthwhiletheshift鄄addmultipliercaneconomizeresourcesinchip.
look鄄uptable,shift鄄addandBootharedescribedindetail.BysimulationandsynthesizingofthefourkindsofFPGA
with4伊4and16伊16digitalmultipliersasexamples.TheresultsshowtheBoothmultiplierhasevidentadvantages
基于FPGA的数字乘法器性能比较*
鞠摇芳,马摇昕*,田摇岚
(山东大学信息科学与工程学院,济南250100)
摘摇要:详细描述了四种基本的FPGA数字乘法器设计方法即阵列法、查找表法、移位相加法、Booth法的原理和实现过程。
以4伊4和16伊16数字乘法器的设计为例,通过在AlteraFPGA芯片上的仿真与综合,给出了这四种数字乘法器的运算速度和占用逻辑资源情况。结果表明随着位宽的变化,各方法的相对效果会有变化,对于具有较宽数据位的乘法器来说,使用Booth方法有明显的优势,而移位相加法可明显的节省片上硬件资源。
关键词:数字乘法器;FPGA;Booth方法、移位相加法
中图分类号:TN431.2摇摇摇摇文献标识码:A摇摇摇摇文章编号:1005-9490(2011)06-0718-05摇摇在通信与信号处理系统中,乘法器是数字运算的重要单元,高性能乘法器是完成高性能实时数据运算和处理的关键。随着FPGA(FieldProgrammableGateArray,现场可编程门阵列)技术地替代ASIC和DSP用于信号处理的运算[1],然而常见的FPGA芯片一般不具有现成的乘法运算单元,因而研究基于FPGA的数字乘法器设计具有非常重要的意义。
针对FPGA的乘法器设计,已有前人做了大量的工作,总结起来主要有阵列法[2]、查找表法、移位相加法[3]和Booth法[4],此外,还有以这几种方法为基础的改进方法,如有限域乘法器[5]等。实际应用中,有时需要乘法运算有较快的速度,有时则需要较少的硬件资源和适中的速度,乘法器的速度和面积优化对于整个CPU的性能来说是非常重要的,因而
收稿日期:2011-07-18摇摇修改日期:2011-08-08
有必要对乘法器的算法、结构及电路的具体实现做深入的分析并给出性能比较。本文针对查找表法、移位相加法和Booth法等几种常用数字乘法器的设计方法在ALTERA公司FPGA系列进行了设计,并利用Quartus域9.0对这些设计进行了综合和仿真验证。最后从运算速度和所占用逻辑资源两方面对数字乘法器的性能进行了比较。
的发展,FPGA以其高度的灵活性和正在越来越多
1摇数字乘法器设计方法
乘法运算可以利用组合电路或时序电路来实现。组合电路乘法器比时序电路乘法器耗用硬件资源更多,但是运算速度更快。时序电路乘法器则需要几个时钟周期才能完成乘法运算,但是耗用的硬件资源较少。常见的组合电路乘法器有阵列乘法器和查找表乘法器,常见的时序电路乘法器有移位相加乘法器和Booth乘法器,其它的乘法器多为以此
项目来源:山东省中青年科学家科研奖励基金:基于光纤激光技术的丰富音感知仿生耳系统研究(2010BSE27237)
摇第6期鞠摇芳,马摇昕等:基于FPGA的数字乘法器性能比较
719
为基础进行组合变形的,如有限域乘法器等。
设计组合电路乘法器需要根据乘法运算的原理由逻辑门实现,设计思路相对简单,而时序电路乘法器设计通常需有两个步骤:(1)选择数据通路结构(2)设计状态机以控制数据通路。对于给定的数据通路结构,状态机必须能生成适当的控制信号序列来控制数据的移动以产生乘积[6-8]。下面对阵列乘法器、查找乘法器、移位乘法器以及Booth乘法器的1.设计方法作分析比较1摇阵列乘法器。
阵列乘法器是纯组合类型的乘法器,完全由逻辑门实现。乘数、被乘数和乘积都以并行方式提供[9]。
图1给出了4伊4阵列乘法器的一种结构。该结构包括16个与门、8个全加器和4个半加器。在同步操作中,控制乘法器数据传输的时钟周期必须与电路中的最长路径相适应,该路径从乘数的最低位开始,途经加法器,到达乘积的最高位。加法器的进位路径和求和路径对最长路径都有影响,应将其延时均匀分布。
图1摇阵列乘法器的一种结构
对于现在的FPGA来讲,进位计算执行的速度要比和累加的速度快[10]FPGA,因此图两个相邻的部分积相加来讲效率更高。该结构的思想是2所示的结构对于,使部分积的数目减半:第一步将。然
图2摇FPGA的快速阵列乘法器后重复上述过程直到形成最终乘积。通过引入流水线技术1.2摇查找表乘法器
,可以提高阵列乘法器的工作频率。
查找表乘法器是将乘积直接存储在存储器中,将乘数和被乘数作为地址访问存储器,得到的输出数据就是乘法运算的结果。图3给出了查找表乘法器的原理。查找表乘法器的速度只局限于所使用的存储器的存取速度,但是查找表的规模随着操作数位数的增加迅速增大。因此,查找表乘法器不适合位数较高的乘法。当乘数位数较高时可以将乘数分成几个部分,然后用低位数的查找表实现乘法运算。
图3摇查找表乘法器原理图
1.3摇移位相加乘法器
ASMD图图表4给:出控制器初始状态为了4伊4移位相加S_idle乘法,器复位完成后控制器的
据Ready。然后控制器等待外部输入信号有效,表示时序乘法器空闲Start信号,可以接收数
。Start信号成立时,如果输入数据全0,则清空乘积寄存器并保持在状态S_idle,否则控制器应撤销Ready信号,输出Load_words信号并进入状态S_running。在状态S_running判断计数器的值,如果计数器的值为操作数字节长度,控制器进入状态S_idle,乘法运算完成,否则判断乘积寄存器的最低位,如果乘积寄存器
图4摇移位相加乘法器的控制器方框图和ASMD图表
720
电摇子摇器摇件第34卷
最低位为1,输出Add_shift信号,如果乘积寄存器最低位为0则输出Shift信号。此间控制器运行在状态S_running,直到计数器的值等于操作数字节长度[10]。
图5给出了4伊4移位相加乘法器的数据通路结构:该数据通路结构由存储被乘数的寄存器、一个加法器、一个存储乘数和乘积的移位寄存器组成。该结构把被乘数寄存器通过硬件连线与加法器相连,并作为乘积寄存器最左边的5位。乘数的值最初存储在乘积寄存器最右边的4位。所求得的部分积放在乘积寄存器的最左边,并将乘积寄存器的内容右移。在每一步中,由乘积寄存器的最低位决定是否将被乘数与乘积寄存器相加,直到乘数的所有位被移出乘积寄存器为止,最后留在乘积寄存器中的内容就是乘法运算的结果。
图5摇移位相加乘法器的结构单元
移位相加乘法器的控制器产生的控制信号对数据通道的作用为:Flush清空乘积寄存器Load_words控制数据通路将乘数和被乘数装入寄存器同时将计数器清零;Shift控制乘积寄存器的移位;Add_shift控制被乘数和部分积的相加以及乘积寄存器的移1.位4摇;IncrementBooth乘法器
控制计数器计数。
使用Booth算法的乘法器对乘数的位进行重新编码以减少完成乘法运算周期所需的加法运算次数。Booth算法可以应用于以2补形式表示的有符号数。因此使用Booth重编码的硬件乘法器不需要修改就可以使用于负数运算[11-12]字符串Booth,而将一系列加法运算用一次加法和一次减
算法的关键在于它跳过了乘数中全。
1的
法来替代。例如,二进制数11110000等于(28(24-1)=28-24-1)-
的全1字符串,并用加减法运算得到的有符号数来=240。Booth编码方案将检测乘数取代它们,以对乘数重新进行编码。
表1给出了Booth重编码规则,该规则从最低位到最高位依次读取,两个相邻位(Mi,Mi-1)的值确定了Booth重编码乘数的各个位BRCi,当算法读
取两个相邻位时可形成BRCi,并用BRCi来判断在跳到下一位之前是进行加法运算还是减法运算。该算法第一步放置一个0到乘数最低位的右边,处理过程将遇到的第一个1编码为1,跳过任何连续的1直到出现0,该0可被编为1以表示全1字符串的结束,然后进行下一步的处理。
表1摇补数的Booth重编码规则
mi00
mi-10
BRCi0
全0状态
字符串
11101末尾为开始为1的字符串110中间全11的字符串字符串
控制器初始状态为摇摇图6给出了4伊4S_idleBooth,复位完成后乘法器的状态转移图Ready信号:
有效,表示时序乘法器空闲,可以接收数据。然后控制器等待外部输入Start信号。Start信号成立时,控制器撤销Ready信号,输出Load_words信号并进入状态BRCi下一状态,S_1如果。,如果BRCi此后的状态转移取决于BRCi为1则输出Booth重编码为2则输出Add_shiftSub_shift信号并进入信号并进入下一状态,如果BRCi为0或3则输出Shift信号并进入下一状态。直到进入状态S_5,此时控制
器将输出Ready信号并保持在状态S_5,直到外部words输入Start信号控制器才进入状态S_1并输出Load_
法运算信号重新装载乘数和被乘数。图7给出了4伊4Booth乘法器的数据通路,开始新一次的乘结构:该数据通路结构由存储被乘数和乘数的两个移位寄存器、一个加法器和一个存储乘积的寄存器组成。
图6摇Booth时序乘法器的STG
数据通道的作用为4伊4Booth乘法器的控制器产生的控制信号对
:Load_words控制数据通路将乘
摇第6期鞠摇芳,马摇昕等:基于FPGA的数字乘法器性能比较
721
图7摇Booth乘法器的数据通路结构
数和被乘数装入寄存器;Shift控制乘数寄存器和被乘数寄存器的移位;Add_shift控制部分积和被乘数_shift的相加以及乘数寄存器和被乘数寄存器的移位控制部分积和被乘数的相减以及乘数寄存器;Sub
和被乘数寄存器的移位。
2摇各种数字乘法器设计方法的性能比较
16伊16根据上述原理分别设计了乘法器数字乘法器进行编译、,综利用合及Quartus4功能仿域伊4真9.数字乘法器和
(0目对各种数字cyclone标芯片为
法器的综合结果见表域系列中的EP2C8Q208C82。16伊16位数字乘法器的仿)。4伊4位数字乘真结果见表3。
表2摇4伊4位乘法器的综合结果
乘法器类型Worst占用的片内资源Tpd(nscase)Logicelements
Memorybits
阵列乘法器20.37320查找表乘法器18.7302048移位相加乘法器65.21280Booth乘法器
61.78
42
0
表3摇16伊16位乘法器的综合结果
乘法器类型Worst占用的片内资源Tpd(nscase)Logicelements
Memorybits
阵列乘法器109.395650查找表乘法器118.7530432768移位相加乘法器182.38730Booth乘法器
73.34
138
0
器摇,摇阵列乘法器通过增加硬件资源耗用提高了运算由以上综合及仿真结果可知:对于4伊4位乘法
速度。查找表乘法器运算速度高于阵列乘法器,其硬件资源耗用也高。移位相加乘法器完成一次乘法
需要5个时钟周期,运算时间较长,但其硬件资源的耗用最少。Booth乘法器速度上与移位相加乘法器
Booth差不多乘法器结构的性能没有优势,但资源消耗较大,由此可见对于位宽较小时
对于16伊16位乘法器,阵列乘法器通过增加硬
。
件资源耗用并适当的使用流水线技术提高了运算速度,而查找表乘法器通过使用存储单元存储乘法结果达到运算速度的提高,但是其速度已明显低于阵列乘法器,只是其逻辑单元资源的消耗比阵列乘法
器少,但却要占用较多的片内存储器资源。移位相加乘法器完成一次乘法需要17个时钟周期,运算时间比其他三种乘法器的都长,但硬件资源的耗用最少。Booth乘法器速度最快,而同时资源消耗仅高于移位相加乘法器,综合优势明显,由此可见对于位宽较大时,Booth乘法器体现出了明显的性能优势。
组合乘法器的硬件资源耗用随着乘法器字节长度增加而大幅度增长,而时序乘法器的硬件资源耗用随字节长度增加增长速度较缓,除Booth乘法器之外,其他三种乘法器同时完成乘法运算所需的时钟周期将随字节长度呈明显增长趋势。
3摇结束语
本文应用Verilog语言,设计了四种数字乘法器,并对它们的性能进行了比较。从仿真和综合的结果看,随着位宽的变化,方法的相对效果会发生改变。对于具有较宽数据位的乘法器来说,使用Booth乘法器有明显的优势。而位宽较小时,阵列乘法器的综合优势明显。如果仅考虑资源占用,移位相加乘法器是较好的选择。在实际应用中应根据系统的要求选择合适的乘法器设计方法。数字乘法器的结构多种多样,本文仅针对四种常见乘法器做了分析和比较,实际应用时可根据实际情况选择合适的乘法器设计方法。参考文献:
[1]摇马秀娟,牛进鹏,考丽,等.高速数据采集系统中的FPGA的设
计[J].电子器件,2007,30(4):1372-1379.[2]HabibiA,WintzPA.FastMultipliers[J].IEEETransactionson[3]Computers王江,黄秀荪,1970,陈刚,C-19,等(.2一种):153-157.
RISC微处理器的快速乘除法运算设计与实现[J].电子器件,2007,30(1):162-166.
[4]汤晓慧,杨军,吴艳,等辉.基于Booth算法的32伊32乘法器IP核设计[J].电子器件,2005,28(1):218-220.
[5]鲍可进,郑博.基于FPGA的有限域乘法算法的分析和比较[J].计算机工程,2008,34(23)247-248.
[6]
DonaldEThomas,PhilipRMoorby著.刘明业,蒋敬旗,刁岚松等译.硬件描述语言Verilog[M].北京:清华大学出版社,2001.[7]
UweMeyer鄄Baese著.刘凌译.数字信号处理的FPGA实现
722
[M].北京:清华大学出版社,2006.[8][9]
电摇子摇器摇件第34卷
[10]GnanasekaranR.AFastSerial鄄ParallelBinaryMultiplier[J].[11]BoothAD.ASignedBinaryMultiplicationTechnique[J].
QuarterlyJournalofMechanicsandAppliedMathematics,1951,4(2):236-240.
[12]WallaceCS.ASuggestionforaFastMultiplier[J].IEEE
TransactionsonElectronicComputers,1964,13(2):14-17.IEEETransactionsonComputers,1985,34(8):741-744.
MichaelDCiletti著.张雅绮,李锵,摇摇摇等译.VerilogHDL高级数字设计[M].北京:电子工业出版社,2005.
AmbergP.PinckneyHarris,ParallelN.High鄄RadixMontgomerySignals,SystemsandComputers.PacificGrove,CA,Oct.26-29,Multipliers[C]//proceedingsof42ndAsilomarConferenceon
2008:772-776.
鞠摇芳(1976-),女,汉族,山东威海人,山东大学信息学院助理工程师,在读硕士研究生,研究领域包括信号与信息处理及光电一体化及嵌入式系统应用设计等,已在国际国内刊物上发表多篇文章,jufang@sdu.edu.cn;
马摇昕(1969-),男,山东泰安人,副教授,硕士生导师,博士毕业于中国科学院声学研究所,现于山东大学从事教学与科研工作,研究领域包括信号与信息处理及光电检测技术等,已在国际国内刊物上发表多篇文章,max@sdu.edu.cn。
因篇幅问题不能全部显示，请点此查看更多更全内容