【FPGA(cyclone4)第二期 】 时序与仿真学习2-优化乘法器

wsdymg

【FPGA(cyclone4)第二期 】 时序与仿真学习2-优化乘法器 [复制链接]

Verilog HDL语言所描述的乘法器是以消耗时钟作为时间单位，反之组合逻辑所建立的乘法器是以广播时间作为事件单位，说简单点是，Verilog HDL语言所描述的乘法器快不快是根据时钟消耗作为评估。
策略一：如果被乘数小于乘数，那么被乘数和乘数互换。
{Multiplier，Multiplicand}=Multiplicand 与普通乘法器相比，优化乘法器在进行累加操作之间多了一个步骤出来，就是被乘数和乘数的比较的步骤。
（一）在初始化之际，取乘数和被乘数的正负关系，然后取被乘数和乘数的正直。
（二）乘数和被乘数比较，如果被乘数小于乘数，结果乘数和被乘数互换
（三）每一次累加操作，递减一次乘数，直到乘数的值为零，表示操作结束
（四）输出结果根据正负关系取得。

test2.zip (5.8 MB, 下载次数: 125)

2013-9-6 10:52 上传

点击文件名下载附件

wsdymg

Booth算法
································································································································································································ test3.zip (5.77 MB, 下载次数: 29)

2013-9-6 20:30 上传

点击文件名下载附件

相关文献：
基于补码等价定义的Booth算法证明.pdf (190.27 KB, 下载次数: 16, 售价: 1 分芯积分)

2013-9-6 20:30 上传

点击文件名下载附件
售价: 1 分芯积分  [记录]

乘法器模块在FPGA中的实现.pdf (751.23 KB, 下载次数: 26, 售价: 1 分芯积分)

2013-9-6 20:30 上传

点击文件名下载附件
售价: 1 分芯积分  [记录]

==================================================================================================
Booth算法是一种加码乘法运算。file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/enhtmlclip/Image.png
在千奇百怪的位操作 乘法中，Booth算法是唯一几个可以容纳补码，亦即Booth算法可以容纳负数来执行操作中。





相比于传统的乘法器，大大节约了计算时间！


file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/enhtmlclip/Image(1).png
file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/enhtmlclip/Image(2).png

[ 本帖最后由 wsdymg 于 2013-9-6 20:30 编辑 ]

kdy

不错不错，:carnation: 非常深入。

wsdymg

`````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````
优化的Booth算法
test4.zip (5.67 MB, 下载次数: 13)

2013-9-7 19:27 上传

点击文件名下载附件

test4.1.zip (5.78 MB, 下载次数: 16)

2013-9-7 19:27 上传

点击文件名下载附件

原来的程序：
case(i)
               0:
               begin a<=A;s<=(~A+1'b1);p<={8'd0,B,1'b0};i<=i+1'b1;end
               1:
               begin
               if(p[1:0]==2'b01) p[16:9]<=p[16:9]+a;
               else if(p[1:0]==2'b10) p[16:9]<=p[16:9]+s;
               i<=i+1'b1;
               end
               2:
               if(X==8)begin X<=4'd0;i<=i+1'b1;end
               else begin p<={p[16],p[16:1]};X<=X+1'b1;i<=i-1'b1;end
               3:
               begin isDone<=1'b1;i<=i+1'b1; end
               4:
               begin isDone<=1'b0;i<=4'd0;end
          endcase
按照常理说8位的乘数和被乘数，位操作会是使用8个时钟而已，但是以上程序需要先操作后移位的关系，所以多出来8个时钟的消耗！
`````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````
改进方法一：
case(i)
               0:
               begin a<=A;s<=(~A+1'b1);p<={8'd0,B,1'b0};i<=i+1'b1;end
               1,2,3,4,5,6,7,8:
               begin
               if(p[1:0]==2'b01) p<={p[16]+a[7],p[16:9]+a,p[8:1]};
               else if(p[1:0]==2'b10) p<={p[16]+a[7],p[16:9]+s,p[8:1]};
               else p<={p[16],p[16:1]};
               i<=i+1'b1;
               end
               9:
               begin isDone<=1'b1;i<=i+1'b1; end
               10:
               begin isDone<=1'b0;i<=4'd0;end
          endcase
优化算法将消耗的8个时钟的移位操作压缩在同一个步骤内，这样节约了8个时钟！
·························································································································································································································································································
改进方法二：
case(i)
               0:
               begin a<=A;s<=(~A+1'b1);p<={8'd0,B,1'b0};i<=i+1'b1;end
               1,2,3,4,5,6,7,8:
               begin
               Temp1=p[16:9]+a;
               Temp2=p[16:9]+s;
               if(p[1:0]==2'b01) p<={Temp1[7],Temp1,p[8:1]};
               else if(p[1:0]==2'b10) p<={Temp2[7],Temp2,p[8:1]};
               else p<={p[16],p[16:1]};
               i<=i+1'b1;
               end
               9:
               begin isDone<=1'b1;i<=i+1'b1; end
               10:
               begin isDone<=1'b0;i<=4'd0;end
          endcase
上面的代码表示了：定义了寄存器Temp1寄存了p[16:9]+a的即使结果，反之Temp2寄存了p[16:9]+s的即使结果，然后判断p[1:0]再来决定p的结果是取决了Temp1，Temp2或者其他。在这里重要的是Temp1，Temp2使用了阻塞赋值，换句话说是即使结果。
`````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````
原来的仿真：

优化后的仿真：

灰狼小鱼

不错，不错，不过没看懂

wsdymg

LUT乘法器——查表乘法器


我们可以通过查表的方法，快速的实现乘法运算！
实际上，有以下公式：

我们只需要建立乘方表就可以了！
===================================================================================================================
因为涉及到整数的乘法运算，我们有必要了解一下补码的相关知识。

负数的加法要利用补码化为加法来做，减法运算当然也要设法化为加法来做。其所以使用这种方法而不使用直接减法，是因为它可以和常规的加法运算使用同一加法器电路，从而简化了计算机的设计。

补码减法的公式是：  

[x-y]补=[x]补-[y]补=[x]补+[-y]补

( 2.2.2 )

这里只要证明 - [y]补 = [ - y]补，上式即得证。现证明如下：

∵                     [x]补 + [y]补 =  [x + y]补 　　　　(mod  2)

∴                     [y]补 =  [x + y]补 - [x]补                             　       (2.2.3)

∵                     [x - y]补 = [x + ( - y)]补 =  [x]补  + [ - y]补

∴                     [ - y]补 = [x - y]补  -  [x]补           　　　　　         　  (2.2.4)

将式(2.2.3)与(2.2.4)式相加，得

[ - y]补 + [y]补   = [x + y]补 + [x - y]补  -  [x]补 -  [x]补

                    = [x + y + x - y]补 -  [x]补 -  [x]补

                    = [x + x]补 -  [x]补 -  [x]补

　　　　　　　　　　= 0

所以

[－ｙ]补＝－[ｙ]补即减去y补相当于加上-y的补

(2.2.5)

不难发现，只要能通过[y]补求得[ - y]补，就可以将补码减法运算化为补码加法运算。

已知[y]补求[ - y]补的法则是：对 [y]补各位(包括符号位)取反且末位加1，就可以得到[ - y]补。
===================================================================================================================
于是有了一下的实验：
test5.zip (5.81 MB, 下载次数: 4)

2013-9-9 19:52 上传

点击文件名下载附件

不过由仿真图如下：

我们发现当乘数为0时，算法发生了错误，主要因为两个八位二进制数加减运算扩展为九位二进制数时，符号位发生错误，为了避免这种错误，我们有了一下实验：
test5.1.zip (5.82 MB, 下载次数: 5)

2013-9-9 19:52 上传

点击文件名下载附件

仿真图如下：

5从图中可以看到，程序已经正确！

[ 本帖最后由 wsdymg 于 2013-9-9 19:52 编辑 ]

kdy

赞一个
果然很给力

wsdymg

多谢鼓励，继续努力

wsdymg

前面的例子中，两个八位二进制数做加减运算，扩展为一个九位二进制数，对于B=0时的情况做出了区别处理，主要是符号位没有处理好，今天整理下，这几天的心得体会：
原来的处理方法：
I1 <= { A[7], A } + { B[7], B };
I2 <= { A[7], A } + { ~B[7], ( ~B + 1'b1 ) };
在这里对符号位进行了扩展，错误就出在这里，当进行减法运算时，对符号位进行扩展应该是，取（( ~B + 1'b1 )的第7位作为新的符号位，而不是只取（~B）的第7位。
所以处理方法可以是这样：
reg[7:0] C;
C<=~B + 1'b1;
I1 <= { A[7], A } + { B[7], B };
I2 <= { A[7], A } + { C[7], C };
具体实例程序见：
test5.2.zip (5.9 MB, 下载次数: 8)

2013-9-10 12:14 上传

点击文件名下载附件

wsdymg

我们可以把Modified Booth算法看成是Booth算法的升级版本。
Modified Booth对B[1:-1]执行加码。
程序：
test6.zip (6.05 MB, 下载次数: 4)

2013-9-10 19:54 上传

点击文件名下载附件

仿真图：

wsdymg

Modified Booth算法用位操作虽然它可以提升乘法运算的速度，由于它的操作步骤是不规则的，很多时候用它要看运气，因为不同的乘数与被乘数都有不同的时钟消耗。
站在数学的角度，传统的Modified Booth算法是从p[16:9]开始加码，做向右移位的运算，为简化运算，我们可以从p[7:0]做加码运算，将被乘数做向右移位的运算。
test7.zip (7.72 MB, 下载次数: 7)

2013-9-11 14:33 上传

点击文件名下载附件

wsdymg

加精了，居然加精了，呵呵，真好

灰狼小鱼

好深入啊，跟楼主一起学习

wsdymg

谢谢，共同学习！

灰狼小鱼

嗯，今天做了下仿真，挺好的，学到了写新东西

孔子

学习下

wsdymg

不好意思，复习了下，看到自己修改的程序即改进方法一存在明显的错误，现在修改一下。
test4.1.zip (5.84 MB, 下载次数: 7)

2013-9-13 22:22 上传

点击文件名下载附件

仿真时序图：

xuyiyi

写的不错， 非常给力。

wsdymg

谢谢

yufubin

test 4 和test 4.1程序是不是有问题，一直不对啊。