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

wsdymg 2013-9-6 10:52 楼主

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

test2.zip (5.8 MB)
(下载次数: 125, 2013-9-6 10:52 上传)

回复评论（23）

沙发 wsdymg

【FPGA(cyclone4)第二期】时序与仿真学习3-Booth算法乘法器

Booth算法
································································································································································································
test3.zip (5.77 MB)
(下载次数: 29, 2013-9-6 20:30 上传)

相关文献：

基于补码等价定义的Booth算法证明.pdf (190.27 KB)
(下载次数: 16, 2013-9-6 20:30 上传)

乘法器模块在FPGA中的实现.pdf (751.23 KB)
(下载次数: 26, 2013-9-6 20:30 上传)

==================================================================================================
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 编辑 ]

点赞 2013-9-6 20:28

板凳 kdy

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

Net：Wxeda.taobao.com QQ：1035868547 Blog：https://home.eeworld.com.cn/space-uid-390804.html

点赞 2013-9-7 01:56

4楼 wsdymg

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

`````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````
优化的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使用了阻塞赋值，换句话说是即使结果。
`````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````
原来的仿真：

优化后的仿真：

点赞 2013-9-7 19:27

5楼灰狼小鱼

不错，不错，不过没看懂

点赞 2013-9-7 19:35

6楼 wsdymg

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

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 编辑 ]

点赞 2013-9-9 19:45

7楼 kdy

赞一个

果然很给力

Net：Wxeda.taobao.com QQ：1035868547 Blog：https://home.eeworld.com.cn/space-uid-390804.html

点赞 2013-9-9 22:51

8楼 wsdymg

回复 7楼kdy 的帖子

多谢鼓励，继续努力

点赞 2013-9-10 08:42

9楼 wsdymg

【FPGA(cyclone4)第二期】时序与仿真学习——关于补码的继续讨论

前面的例子中，两个八位二进制数做加减运算，扩展为一个九位二进制数，对于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 上传)

点赞 2013-9-10 12:14

10楼 wsdymg

【FPGA(cyclone4)第二期】时序与仿真学习5-Modified Booth乘法器

我们可以把Modified Booth算法看成是Booth算法的升级版本。
Modified Booth对B[1:-1]执行加码。
程序：

test6.zip (6.05 MB)
(下载次数: 4, 2013-9-10 19:54 上传)

仿真图：

点赞 2013-9-10 19:54

11楼 wsdymg

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

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

test7.zip (7.72 MB)
(下载次数: 7, 2013-9-11 14:33 上传)

点赞 2013-9-11 14:33

回复 13楼灰狼小鱼的帖子

谢谢，共同学习！

点赞 2013-9-12 09:39

15楼灰狼小鱼

回复 14楼wsdymg 的帖子

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

点赞 2013-9-12 15:25

16楼孔子

学习下

点赞 2013-9-13 13:33

17楼 wsdymg

不好意思，复习了下，看到自己修改的程序即改进方法一存在明显的错误，现在修改一下。

test4.1.zip (5.84 MB)
(下载次数: 7, 2013-9-13 22:22 上传)

仿真时序图：

点赞 2013-9-13 22:22

18楼 xuyiyi

写的不错，非常给力。

点赞 2013-9-19 06:26

19楼 wsdymg

回复 18楼xuyiyi 的帖子

谢谢

点赞 2013-9-20 15:37

20楼 yufubin

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

做到最好

点赞 2013-12-6 14:16

12 / 2 页下一页

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

回复评论（23）

沙发 wsdymg

【FPGA(cyclone4)第二期】时序与仿真学习3-Booth算法乘法器

板凳 kdy

4楼 wsdymg

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

5楼灰狼小鱼

6楼 wsdymg

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

7楼 kdy

8楼 wsdymg

回复 7楼kdy 的帖子

9楼 wsdymg

【FPGA(cyclone4)第二期】时序与仿真学习——关于补码的继续讨论

10楼 wsdymg

【FPGA(cyclone4)第二期】时序与仿真学习5-Modified Booth乘法器

11楼 wsdymg

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

12楼 wsdymg

13楼灰狼小鱼

14楼 wsdymg

回复 13楼灰狼小鱼的帖子

15楼灰狼小鱼

回复 14楼wsdymg 的帖子

16楼孔子

17楼 wsdymg

18楼 xuyiyi

19楼 wsdymg

回复 18楼xuyiyi 的帖子

20楼 yufubin

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

回复评论 （23）

【FPGA(cyclone4)第二期 】 时序与仿真学习3-Booth算法乘法器

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

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

回复 7楼kdy 的帖子

【FPGA(cyclone4)第二期 】 时序与仿真学习——关于补码的继续讨论

【FPGA(cyclone4)第二期 】 时序与仿真学习5-Modified Booth乘法器

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

回复 13楼灰狼小鱼 的帖子

回复 14楼wsdymg 的帖子

回复 18楼xuyiyi 的帖子

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

回复评论（23）

【FPGA(cyclone4)第二期】时序与仿真学习3-Booth算法乘法器

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

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

【FPGA(cyclone4)第二期】时序与仿真学习——关于补码的继续讨论

【FPGA(cyclone4)第二期】时序与仿真学习5-Modified Booth乘法器

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

回复 13楼灰狼小鱼的帖子