最大公约数Stein算法之verilog实现

我不是女神ヾ 2022-05-23 08:40 206阅读 0赞

求最大公约数有几种算法：1、辗转相除法，2、更相减损术，3、Stein算法。

Stein算法跟更相减损术很像，而且只有比较、移位、减法，非常适合用FPGA实现。

不了解这个算法的，可以先到百度百科看一下，[Stein算法百度百科][Stein]，此外，还要看看C语言实现的算法，百科那里的示例只有30行。

1、算法步骤。

那么，我把百科里面的算法步骤改写一下，让它更适合用verilog实现。

a、先装载A和B的值，C清零。

b、若A＝0，则B是最大公约数；若B＝0，则A是最大公约数；若A＝B，则A是最大公约数。若上面三种情况都不成立，则跳到c，否则跳到d

c、若A是偶数，B是偶数；则A>>1，B>>1，C<<1（LSB填充1）；

若A是偶数，B是奇数；则A>>1，B不变，C不变；

若A是奇数，B是偶数；则A不变，B>>1，C不变；

若A是奇数，B是奇数；则if(A>B) A=A-B;else B=B-A，C不变;

d、输出结果。

同时，也把这四个步骤，抽象成状态机，分别是init，compare，calculate，finish。

接下来，要用状态机输出各种控制信号，来控制各个功能模块（always块），以实现不同的算法步骤。

2、示例代码。（请把代码copy到编辑器上观看，这里不容易排版）

module gcd(  
input n\_rst,clk,en,  
input \[7:0\] Ain,Bin,  
output reg \[7:0\] gcd\_out='b0  
);  
  
localparam \[1:0\] init='b00,compare='b01,calculate='b11,finish='b10;  
reg \[1:0\] cs='b0,ns='b0;  
reg load='b0,comp\_en='b0,cal\_en='b0,out\_en='b0,cal\_over='b0;  
  
reg \[7:0\] A\_tmp='b0,B\_tmp='b0,gcd\_tmp='b0,shift\_times='b0;  
wire \[1:0\] A\_B\_LSB;  
  
//three section FSM  
//timing sequence part of FSM  
always@(negedge n\_rst,posedge clk)  
if(!n\_rst)  
cs<=init;  
else  
if(en)  
cs<=ns;  
  
//combination part of FSM  
always@(\*)  
case (cs)  
init : ns<=compare;  
compare : if (cal\_over)  
  ns<=finish;  
 else  
  ns<=calculate;  
calculate : ns<=compare;  
finish : ns<=init;  
default : ns<=init;  
endcase  
  
//register output part of FSM  
always@(negedge n\_rst,posedge clk)  
if(!n\_rst)  
begin load<=1'b0;comp\_en<=1'b0;cal\_en<=1'b0; end  
else  
if(en)  
case(ns)  
init : begin load<=1'b1;comp\_en<=1'b0;cal\_en<=1'b0;out\_en<=1'b0; end  
compare : begin load<=1'b0;comp\_en<=1'b1;cal\_en<=1'b0;out\_en<=1'b0; end  
calculate : begin load<=1'b0;comp\_en<=1'b0;cal\_en<=1'b1;out\_en<=1'b0; end  
finish : begin load<=1'b0;comp\_en<=1'b0;cal\_en<=1'b0;out\_en<=1'b1; end  
default : begin load<=1'b0;comp\_en<=1'b0;cal\_en<=1'b0;out\_en<=1'b0; end  
endcase  
  
// whether the value is zero or not  
always @(negedge n\_rst or posedge clk) begin  
if (!n\_rst) begin  
cal\_over <= 1'b0;  
gcd\_tmp <= 'b0;  
end  
else  
if (en) begin  
if (comp\_en) begin  
 if (A\_tmp=='b0) begin  
 cal\_over <= 1'b1;  
 gcd\_tmp <= B\_tmp;  
 end  
 else begin  
 if (B\_tmp=='b0) begin  
 cal\_over <= 1'b1;  
 gcd\_tmp <= A\_tmp;  
 end  
 else begin  
 if (A\_tmp==B\_tmp) begin  
  cal\_over <= 1'b1;  
  gcd\_tmp <= A\_tmp;  
  end  
 else begin  
 cal\_over <= 1'b0;  
 gcd\_tmp <= 'b0;  
 end   
 end  
 end  
end  
end  
end  
  
// calculate the gcd  
assign A\_B\_LSB = \{A\_tmp\[0\],B\_tmp\[0\]\};//if A\_tmp\[0\] = 0 , A\_tmp is even and A\_tmp >> 1,also as B\_tmp;  
always @(negedge n\_rst or posedge clk) begin  
if (!n\_rst) begin  
 A\_tmp <= 'b0;  
 B\_tmp <= 'b0;  
 shift\_times<='b0;  
end  
else  
if (en) begin  
 if (load) begin// load the initialization values  
 A\_tmp <= Ain;  
 B\_tmp <= Bin;  
 shift\_times<='b0;  
 end  
 else begin  
 if (cal\_en) begin  
 case (A\_B\_LSB)  
 2'b00 : begin A\_tmp<=\{1'b0,A\_tmp\[7:1\]\};B\_tmp<=\{1'b0,B\_tmp\[7:1\]\};  
 shift\_times<=\{shift\_times\[6:0\],1'b1\};end  
 2'b01 : begin A\_tmp<=\{1'b0,A\_tmp\[7:1\]\};B\_tmp<=B\_tmp;  
 shift\_times<=shift\_times;end  
 2'b10 : begin A\_tmp<=A\_tmp;B\_tmp<=\{1'b0,B\_tmp\[7:1\]\};  
 shift\_times<=shift\_times;end  
 2'b11 : begin if (A\_tmp>B\_tmp) begin  
 A\_tmp <= A\_tmp-B\_tmp;B\_tmp <= B\_tmp;  
 end  
 else begin  
 B\_tmp <= B\_tmp-A\_tmp;A\_tmp <= A\_tmp;  
 end  
 shift\_times<=shift\_times;  
 end  
 default : begin A\_tmp<=A\_tmp;B\_tmp<=B\_tmp;shift\_times<=shift\_times;end  
 endcase  
 end  
 end  
end  
end  
  
// output result , if enable  
always @(negedge n\_rst or posedge clk) begin  
if (!n\_rst)  
gcd\_out <= 'b0;  
else  
if (en) begin  
if (out\_en)  
if(cal\_over)  
 case (shift\_times)  
  8'h00 : gcd\_out <= gcd\_tmp;  
  8'h01 : gcd\_out <= \{gcd\_tmp\[6:0\],1'b0\};  
  8'h03 : gcd\_out <= \{gcd\_tmp\[5:0\],2'b0\};  
  8'h07 : gcd\_out <= \{gcd\_tmp\[4:0\],3'b0\};  
  8'h0f : gcd\_out <= \{gcd\_tmp\[3:0\],4'b0\};  
  8'h1f : gcd\_out <= \{gcd\_tmp\[2:0\],5'b0\};  
  8'h3f : gcd\_out <= \{gcd\_tmp\[1:0\],6'b0\};  
  8'h7f : gcd\_out <= \{gcd\_tmp\[0\],7'b0\};  
  default : gcd\_out <= gcd\_tmp;  
 endcase  
 else begin  
 gcd\_out <= gcd\_out;  
 end  
end  
end  
  
endmodule

3、仿真结果。

![20150903202036549][]

![20150913192144553][]

4、其它问题。

a、为什么要装载A和B的值，而不用A和B端口的值？

端口上的值，只能读不能写，所以需要把A和B的值，装载到寄存器当中，这样，可读可写。而且，寄存器当中的值不受端口影响。

b、如何判断A和B的奇偶性？

很简单的，取A或B的最低位（LSB），LSB是1就是奇数，是0就是偶数。

c、为什么同样一个算法，用C只有30行，而verilog则用150行？

这就是软件和硬件的区别，由于C语言是交给算术逻辑单元（ALU）处理的，ALU本身具有串行的特性，这也就意味着你可以不用写状态机。而verilog则不同，需要你来写状态机。

d、为什么verilog不能像C语言一样，用while、函数嵌套？

这跟上面c的问题一样，区别在于有没有ALU。此外，用verilog的，必须考虑各个always块之间的协作关系，这也导致了verilog语言局部容易看懂，但是整体很难理解的特点。

5、进一步优化。

a、用parameter把上面的代码改成为位宽可以任意设定的。

b、比较用的if (A\_tmp>B\_tmp) 会因为位宽变大，而导致面积变大。可以把它换成减法，再判断MSB，以减小面积。

c、由于A\*B＝最大公约数\*最小公倍数，那么，你应该可以写出最小公倍数算法。

文章标签： [FPGA][] [verlog][] [算法][Link 1]

个人分类： [FPGA][FPGA 1]

[Stein]: http://baike.baidu.com/link?url=xdBikAjnrXzIiwUWnytn70yAnHbWd7hTtU19_In2_WTa5aNmaPuYCCji8Ak66KRfAaav-Qra6ArOHQCf17uioq
[20150903202036549]: /images/20220523/38c173e8c7184c46986264b56429483a.png
[20150913192144553]: /images/20220523/20a83c7a447546a587ce3f0d1d14a838.png
[FPGA]: http://so.csdn.net/so/search/s.do?q=FPGA&t=blog
[verlog]: http://so.csdn.net/so/search/s.do?q=verlog&t=blog
[Link 1]: http://so.csdn.net/so/search/s.do?q=%E7%AE%97%E6%B3%95&t=blog
[FPGA 1]: https://blog.csdn.net/k331922164/article/category/3051115