最富盛名的补码乘法器——Baugh-Wooley乘法器

yywyz

[size=18.6667px]最富盛名的补码乘法器——Baugh-Wooley乘法器

转发自微信公众号“纸上谈芯”

一、Baugh-Wooley算法

Baugh-Wooley算法是由Baugh和Wooley于1973年提出的二进制补码并行阵列相乘算法。该算法转化为等效并行阵列相加，其中每个部分和为乘数和被乘数比特相与，并且所有的部分和符号位为“+”。将n比特X，Y，乘法结果2n比特的P表示如下：

                              

从上式看出，XY相乘，结果P=XY相当于前两项减去后两项正数，设为A和B.

按顺序用字母表示以上项，即P = C+D-(A+B)。

将最后两项A和B，补0扩展表示成2n位，以便在阵列中相加：

其中ai=y(n-1)*xi

A的二进制表示如下：

-A，即A的二进制补码,对A“取反加一”，表示如下：

取反：

加一：

B的补码表示与A同理。

所以,-(A+B)的结果如下，即-A-B：

将-A-B代入P的表达式，所以P的结果如下：

以n=4比特X，Y相乘为例，P=XY为8比特：

该4*4 乘法器结构如下：

4*4Baugh-Wooley乘法器结构

以上结果中每个框均为全加器，有微小差距。

蓝色框，其中某个输入为xiyi相与；

绿色框，其中某个输入为xiyi相与后取反；

右下斜对角为P的传播路径，上下为进位传播路径，最长的进位传播链为P0的进位至P7的进位传播。

绿色框与蓝色框模块

二、Verilog设计

设计一个16比特或者32比特的Baugh-Wooley乘法器，位宽N可自定义，默认为16比特。

几个要点：

（1）蓝色框与绿色框全加器；

（2）橙色框模块，最后一级加法器，作为示例，此处采用RCA加法器；

（3）xiyi, ci, si, co, so信号生成；

（4）Baugh-Wooley结构连接；

（5）乘法结果输出P选择。

根据以上结构拓展成16比特的结构如下：

16*16 Baugh-Wooley乘法器结构

在Verilog中，可罗列出每个模块，并连接。为了便于参数化，根据如上结构划分为5部分，每一部分使用generate…endgenerate生成。

生成xi & yi

生成si和ci

全加器例化

最后一级加法器

最后一级乘法输出

32比特Baugh-Wooley乘法器测试部分打印信息

Baugh-Wooley乘法器，Verilog源码公众号回复“00e”。

参考资料：

《A Two's Complement Parallel Array Multiplication Algorithm》

《Baugh-Wooley Multiplier》

欢迎批评指正，更多阅读，关注“纸上谈芯”，不定期更新，共同学习:

syjuang@123

Thanks

zhuzhiqi

点赞！！！

wu_bo

点赞

scutlee

无符号数和有符号数都能算吗