Verilog |
您所在的位置：网站首页 › verilog符号位扩展 › Verilog |
Verilog
|
Verilog -- 乘法器Booth算法
目录Verilog -- 乘法器Booth算法1. 原理2. 一般化推论3. 实际算法4. Verilog代码
1. 原理
Booth算法的原理其实小学初中就学过，比如下面这道题： 简便计算：\(8754 \times 998 = ?\) 随便抓个娃娃来都知道应该这么算： \(8754 \times 998 = 8754 \times 1000 - 8754 \times 2\) 我们都知道在十进制里，10的倍数的乘法很容易，就是后面加几个0的事情，而上面这种简便计算都有个特点，就是会有999,1001,997,1002这种数，0和9出现的次数很多，这样就可以通过变为化简变为简单的乘法和加减法。 对于二进制数，这种简便计算的情况往往更多。因为计算机中为了计算方便，往往将数据转换为补码的形式，而补码形式在计算时会扩展符号位，比如有符号数补码5'b10110 = -10，在计算与一个8位数相加时会扩展为8‘b11110110，可以发现，这种数往往会有很多连续的1出现，这跟上面的简便计算的例子非常相似。比如： \[0011110 = 0100000 - 0000010 = 2^5-2^1 \]这就是booth算法分解乘数的基本原理。 2. 一般化推论假设A和B是乘数和被乘数，且有： \[\begin{align} A &= a_{n-1}a_{n-2}\dots a_{1}a_{0} \tag{1}\\ B &= b_{n-1}b_{n-2}\dots b_{1}b_{0} \tag{2}\\ A*B &= (0-a_0)\times B\times 2^0 + (a_{0}-a_1)\times B\times 2^1 + \tag{3}\\ &(a_{1}-a_2)\times B\times 2^2 + \dots +(a_{n-2}-a_{n-1})\times B\times 2^{n-1} \tag{}\\ &=B\times [-a_{n-1}\times2^{n-1}+\sum_{i=0}^{n-2}a_i\times 2^i] \tag{} \\ &=B\times Val(A) \tag{} \end{align} \]最后的Val(A)的表达式实际上就是补码A表示的原码。 3. 实际算法上面的公式推导了booth乘法对乘数的分解原理，实际上在编码时只需要公式3，可以做如下的编码表： \(a_i\) \(a_{i-1}\) \(a_{i-1}-a_i\) 操作 0 0 0 无 1 0 -1 减B 1 1 0 无 0 1 1 加B举个栗子： \(N=7, B = 22 = (0010110)_2,A=-34=-(0100010)_2\) 首先计算-B的补码(算法中要用到）：\(\overline{-B} = (1101010)_2\) 以及A的补码：\(\overline{A} = (1011110)_2\) 硬件计算过程如下： 
首先初始化p空间:\(p=2N+1\).[A]和[Q]是两个寄存器。其中[Q]是N+1位的。 首先将乘数A的补码放到[Q]的高N位上，Q的最低为默认为0.（这步是为了\(i=0\)时，让\(a_{-1}=0\)。 在Q中检查\(a_{i-1}-a_i\)，得00，查表得无操作，直接将[A]和[Q]合起来右移（算数移位） 在Q中检查\(a_{i-1}-a_i\)，得10，查表得减B,相当于加-B的补码，在[A]寄存器中加上-B的补码，之后右移 ...最后的结果11110100010100就是结果的补码，也就是： \(B\times A = \overline{11110100010100} = (10001011101100)_原 = -748_{10}\) 算法跟公式的匹配： 实际上，对于公式中的每一项\((a_{i-1}-a_i)\times B\times 2^i\)都对应实际算法中的每一步。\((a_{i-1}-a_i)\)决定了B的系数，右移操作因为作用在[A][Q]寄存器上，所以实际上是相当于将积右移，等价于B左移，所以这一步对应\(\times 2^i\)操作。加减B的操作都作用在[A]寄存器上，保证了\(\times 2^i\)后的B能够作用在正确的位上。 4. Verilog代码这里只放一种状态机实现的时序逻辑电路，计算过程基本跟上面的算法一样。 参考了 https://mp.weixin.qq.com/s?__biz=MzU3ODgwMzI5NA==&mid=2247483685&idx=1&sn=d06f3a4ced52b42c48bd978e63e2d1bf&chksm=fd6e8214ca190b023383add3c7b60a2eeffae1f747ea2c1059ebee273e7241116d411384682d&scene=126&sessionid=1589012994&key=826ecc1d344963fb89a1fe763a3a0a3c6d8d706a9ef97ba15b329db58590b56ea54262ec5c331c21ac89e81717147cec8824d56cd54abdbb95c5cf0a5a692b36cc66ac50b6dada9f71b68e893f8cb271&ascene=1&uin=MTk3NDE3MDgyMg%3D%3D&devicetype=Windows+10+x64&version=62090070&lang=zh_CN&exportkey=AQ4%2BwrjRyeNZJrEsZxPofPE%3D&pass_ticket=dkwMmft8fNv1TNAobItN6BuADVUY3SXqwDEWdgd1XXquz3xUPDTVW48UvhGe4gkz 的代码,提供者fanhu， [email protected] `timescale 1ns/1ps module booth_fsm # (parameter DATAWIDTH = 8) ( input clk, input rstn, input en, input [DATAWIDTH-1:0] multiplier, input [DATAWIDTH-1:0] multiplicand, output reg done, output reg [2*DATAWIDTH-1:0] product ); parameter IDLE = 2'b00, ADD = 2'b01, SHIFT = 2'b11, OUTPUT = 2'b10; reg [1:0] current_state, next_state; // state registers. reg [2*DATAWIDTH+1:0] a_reg,s_reg,p_reg,sum_reg; // computational values. reg [DATAWIDTH-1:0] iter_cnt; // iteration count for determining when done. wire [DATAWIDTH:0] multiplier_neg; // negative value of multiplier always @(posedge clk or negedge rstn) if (!rstn) current_state = IDLE; else current_state |
【本文地址】
今日新闻 |
推荐新闻 |