基于改进的布斯算法FPGA嵌入式18×18乘法器

摘要：设计了一款嵌入FPGA的乘法器，该乘法器能够满足两个18 b有符号或17 b无符号数的乘法运算。该设计基于改进的布斯算法，提出了一种新的布斯译码和部分积结构，并对9-2压缩树和超前进位加法器进行了优化。该乘法器采用TSMC 0．18μn CMOS工艺，其关键路径延迟为3．46 ns。

关键词：布斯算法；部分积；9-2压缩；两级超前进位加法器

目前，FPGA作为可编程逻辑器件(PLD)的主要产品，在通信、消赞电子、汽车电子、工业控制、国防安全等领域得到广泛的应用。由于在性能和灵活性方面的完美组合，FPGA的使用范围越来越广，客观上要求加强FPGA数字处理功能(如嵌入乘法器，数字信号处理器(DSP)等)。现住几乎每一款商用FPGA内部几乎都嵌入了乘法器或数字信号处理器，如Xilinx公司的VirtexⅡ系列、Spartan-3／3A系列等。相对来说我国的FPGA仅仅处于起步阶段，FPGA的发展特别是高性能FPGA的发展刻不容缓。本文紧跟国家重大项目，对嵌入到FPGA的乘法器进行了深入的研究提出了一个低功耗、高速度的乘法器。该乘法器采用了高速布斯译码、基于全加器的9-2压缩树和35 b两级超前进位加法器。高速布斯译码器采用了改进的布斯算法，使得部分积经过3个门的延迟得到，提高速度约为50％；9-2压缩树由3个3-2压缩和一个4-2压缩组成，使得部分积阵列仅经过7个异或门延迟；35 b两级超前进位加法器采用的是基于4 b超前进位加法器，使得加法器仅仅经过10个门的延迟。

1 整体结构

图1为18×18位乘法器的整体结构，它包含了布斯译码模块、压缩树模块和超前进位加法模块。部分积是通过本文采取的布斯译码器快速产生，然后其通过9-2压缩树被压缩成两个35 b的二进制数，最后通过超前进位加法器生成无符号位的35 b的结果。通过乘数和被乘数的符号位异或产生最终积的符号位，这样就得到了36 b的最终结果。从图1可以看出该乘法器整体结构和传统的结构是一样的。

2 布斯译码和部分积

通常进行两个数相乘，是通过所有的部分积相加得到。这样，不仅乘法器的速度都得不到保证，而且会浪费芯片的面积。因此采取现在比较流行的布斯算法，因为它可以使部分积的数目减半，这样对面积和速度都比较有利。在原算法的基础上进行了改进并得到一种新的布斯译码和部分积结构。我们将布斯算法分解为“sig”，“sht”，“add”三个个因子，分别用来代表对被乘数的不同操作。其中“sig”用来决定被乘数是取反还是保持不变；“sht”代表是否对被乘数进行左移一位；而“add”则表示决定最终得到部分积。改进的算法用表达式表示则为：

从图2可以看出，改进的布斯译码器由1个异或门、2个与门和1个或门构成而部分积则是有3个二选一多路选择器构成，其关键路径为3个门的延迟。因此结构要比传统的更为简单、延迟更小。

3 9-2压缩树

华莱士树(Wallace Tree)算法通过并行相加来提高速度。在华莱士树中所有部分积列在同一时间各自独立的进行相加。采用的是一种基于保留进位全加器的9-2压缩树用来压缩部分积阵列的，在每一个9-2压缩树的最顶层有9 b的部分积。9-2压缩树中用到了3个3-2压缩和1个4-2压缩。对于那些少于9 b的部分积列，为了进一步减小芯片面积，根据部分积的数目采用相应的压缩树，并且可以用半加器用来代替3-2压缩(全加器)。

典型的4-2压缩是由2个3-2压缩构成的，其延迟为4个异或。图3为一个优化了的4-2压缩，其延迟为3个异或的延迟。因此9-2压缩树从顶层到最终输出仅过了7个异或门的延迟。

4 35 b两级超前进位加法器

超前进位加法器对乘法器的整体性能的影响至关重要，要想提高乘法器的速度，超前进位加法器也必须进行必要的优化。在此采取基于4 b超前进位加法器的两级加法器。

由于进位链延迟时间随着输入的增加而增加，必须考虑到输入信号的个数，在面积和速度中进行折中发现4 b超前进位加法器是最适合作为基本的模块。

从图4(b)中可以看到在4 b超前进位加法器中，除了P和G由与门实现的，其他的都是有与非门实现的。

图4(a)为1位全加器的变形，有3个输入Ai，Bi，Ci和三个输出Pi，Si和Gi，其中Ai和Bi为两个加数，Cin为进位输入，Pi和Gi分别为进位传输和进位产生，而Si为第i位的和。

采用基于4 b的超前进位加法器来组成16 b超前进位加法器，进位链采取与4 b超前进位链相同的结构。同样的分析方法，发现16 b的P和G延时为5个门的延迟。用2个16 b的超前进位加法器和一个3 b超前进位加法器组成35 b超前进位加法器，其进位链采取与上面相同的方法。研究不难发现，经过7个门延迟进位到达3 b超前进位加法器，再经过3个门的延迟得到第35位的结果。也就是说整个加法器仅仅经过10个门的延迟。

5 设计总结

5．1 综合条件说明

采用TSMC0．18μm CMOS工艺和Synopsis DC进行的综合并进行延迟分析。并在DC命令窗口输入了命令“set_dont_use”和“set_dont_ touch”。

5．2 布斯译码和部分积

把传统的布斯译码和部分积与本文采取的布斯译码和部分积进行了比较，并把结果列在了表2中。从表中发现本设计关键路径与OhkuBo相比减少了50％，生成部分积的速度相应的提高了50％。

5．3 与其他的乘法器进行比较

本文的乘法器与表3中乘法器相比速度有明显提高，与Xilinx公司的Spartan-3A系列嵌入到FPGA的乘法器相比本文乘法器的速度更提高40％。更为关键的是在没有增加芯片面积的情况下把速度提高40％。

6 结语

本文基于改进的布斯算法的18×18乘法器是特意为嵌入到FPGA而设计的，它解决了乘法器占用FPGA较多资源的问题，并为以后DSP嵌入到FPGA做了必要的准备工作。采用了一种新的布斯译码和部分积、9-2压缩和两级超前进位加法器以使乘法器达到较好的性能。经过仿真验证，这里提出的基于改进的布斯乘法器各项指标均能很好的满足嵌入到FPGA的要求。