个人网站备案范围,商城类的网站一般怎么做,成都房产网站建设,施工企业税款缴纳基于Booth乘法和Wallace树的快速乘法器
为了理解Booth乘法和Wallace数如何让乘法器变得更快#xff1a;
先考虑不优化的8位乘法器实现#xff0c;即8个16位数字累积共进行7次加法运算#xff0c;可以认为一次16位加法用到16个全加器#xff0c;则共需要112个全加器件
先考虑不优化的8位乘法器实现即8个16位数字累积共进行7次加法运算可以认为一次16位加法用到16个全加器则共需要112个全加器件只计算全加器的开销至少需要112$\times$5560个门
Booth乘法
Booth乘法的实现依据在于补码乘法可写成以下的形式
相比起原始乘法器每次根据y的一位来决定当前是x/0补码乘法则需要每次观察y的两位以决定下一次加法是x/-x/0而Booth乘法则每次观察y的三位以决定下一次加法是x/2x/-x/-2x/0 布斯乘法每次观察完后y右移2位相当于一次完成了2位y的观察。
因此我们需要进行加法的操作数也从原来的8个变成了4个
例子
以4位乘法为例来看看布斯乘法如何减少了操作数的数量 如果提升y的判断位数是否可以进一步提升乘法器的效率 否Booth算法的三位判决在硬件实现中是一个平衡点如果使用更多位数虽然理论上可以减少生成的x数量但增加y带来的复杂性可能会抵消这些好处。 我们使用判断3位的布斯乘法则实际上减半了操作数的数量
原本是8个16位数字累积共进行7次加法运算需要112个全加器经由布斯乘法优化则仅需要4个16位数字进行3次加法需要48个全加器
Wallace树
Wallcace树基于半加器和全加器进行优化。
我们认为借用16位加法器来计算仅仅4个16位数字实在是太浪费了。因此我们不再横向地整个把16位数字加起来而是纵向地每次只考虑4位数字的加法在本位产生一个数字并把进位传递给后面的wallace_4模块
如下是wallace_4模块计算的一个例子。其中每个方框代表着一个wallace_4模块它接受cin作为输入计算出本位(S)并把进位©传递给下一位。值得注意的是所有的进位并不只能为1wallace_4模块会将所有本位处理不了的数字丢给下一个wallace_4 这里必须及时指出如上图所示的计算过程并不完全准确。实际上wallace模块不会把所有的进位都传递给下一位而是如果存在进位wallace会自己先保留1位然后剩下的向前传递。原因在我们讲完wallace模块的实现就会知道。
wallace_4实现
如下是wallace_4的实现输入4位计算数1位Cin计算的出本位的1位C和一位S并将一位进位传递到下一模块 当将共16个wallace_4堆叠起来就可以执行4个16位数的加法了计算结果得是两个16位数字C[15:0]和S[15:0]
因此我们需要16个wallace_4成本为32个全加器还需要将C和S相加以得到最终的结果即一次16位加法成本仍为48个全加器 为什么采用wallace_4优化得到的成本不变 因为输入只有4位太少导致优化空间不足wallace树对于器件的优化是log级的输入越多优化效果越好。但是我们这里作为例子介绍了wallace树的优化思想想必读者能够理解了
