试商法除法器
文章目录
- 一、原理介绍
- 二、状态机实现
- 2.1 状态转移图
- 2.2 代码
- 2.2.1 div.sv
- 2.2.2 tb_div.sv
- 三、流水线实现
- 3.1 参考
- 3.2 代码
- 3.2.1 divider_cell.sv
- 3.2.2 divider.sv
- 3.2.3 tb_divider.sv
一、原理介绍
过程类似于十进制除法。
对于32位的除法,至少需要32个时钟周期,才能得到除法的结果。
设被除数是m, 除数是n, 商保存在s中, 被除数的位数是k, 计算步骤如下:
- 取出被除数的最高位m[k], 使用被除数的最高位减去除数n ,如果结果大于等于0, 则商的s[k] 为1,反之为0
- 如果上一步得到的结果为0,表示当前被减数小于除数,则取出被除数剩下的值的最高位m[k-1],与当前被减数组合作为下一轮被减数。如果上一轮得到的结果是1,表示当前被减数大于除数,则利用上一轮中减法的结果与被除数剩下的值的最高位m[k-1]组合作为下一轮的被减数。然后,设置k等于k-1。
- 新的被减数减去除数,如果结果大于等于0,则商的s[k]为1,否则s[k]为0,后面的步骤依次重复,直到k等于0。
二、状态机实现
2.1 状态转移图
部分状态介绍:
- idle
- divbyzero: 除数为0。
- divinit: 进行有符号相关的处理,以及相关信号初始化赋值。
- divon: 进行试商法除法。
- divend: 除法运算结束。
2.2 代码
2.2.1 div.sv
/**************************************
@ filename : div.sv
@ author : yyrwkk
@ create time : 2024/09/09 11:18:46
@ version : v1.0.0
**************************************/
module div # (parameter N_WIDTH = 32
)(input logic i_clk ,input logic i_rst_n ,input logic i_divsigned ,input logic i_divstart ,input logic [N_WIDTH-1:0] i_dividend ,input logic [N_WIDTH-1:0] i_divisor ,output logic [N_WIDTH-1:0] o_quotient ,output logic [N_WIDTH-1:0] o_remainder ,output logic o_done_vld ,output logic o_ready
);localparam s_idle = 3'd0;
localparam s_divinit = 3'd1;
localparam s_divbyzero = 3'd2;
localparam s_divon = 3'd3;
localparam s_divend = 3'd4;logic [2:0] curr_state ;
logic [2:0] next_state ;logic [4:0] cnt ;logic [31:0] dividend_temp ;
logic [31:0] divisor_temp ;logic [31:0] dividend ;
logic [31:0] divisor ;
logic div_signed ;
logic dividend_signed ;
logic divisor_signed ;logic [31:0] div_temp ;
logic [32:0] div_sub ;logic [31:0] quotient ;
logic [31:0] remainder ;assign dividend_temp = (i_divsigned & i_dividend[31]) ? (~i_dividend + 1'b1) : i_dividend;
assign divisor_temp = (i_divsigned & i_divisor[31]) ? (~i_divisor + 1'b1) : i_divisor;always_ff @( posedge i_clk or negedge i_rst_n ) beginif(!i_rst_n ) begindividend <= 'b0;divisor <= 'b0;div_signed <= 'b0;end else beginif( (o_ready == 1'b1 ) && (i_divstart == 1'b1 ) ) begindividend <= dividend_temp;divisor <= divisor_temp;div_signed <= i_divsigned;dividend_signed <= i_dividend[31];divisor_signed <= i_divisor[31];end else begindividend <= dividend ;divisor <= divisor ;div_signed <= div_signed ;dividend_signed <= dividend_signed;divisor_signed <= divisor_signed ;endend
endalways_ff@(posedge i_clk or negedge i_rst_n ) beginif( !i_rst_n ) begincurr_state <= s_idle;end else begincurr_state <= next_state;end
endalways_comb begincase(curr_state )s_idle : beginif( (o_ready == 1'b1 ) && (i_divstart == 1'b1 )) beginif( i_divisor == 'b0 ) beginnext_state = s_divbyzero;end else beginnext_state = s_divinit;endend else beginnext_state = s_idle;endends_divinit : beginnext_state = s_divon;ends_divbyzero: beginnext_state = s_divend;ends_divon : beginif( cnt == 'd0 ) beginnext_state = s_divend;end else beginnext_state = s_divon;endends_divend : beginnext_state = s_idle;enddefault : beginnext_state = s_idle;endendcase
endassign div_sub = {1'b0,div_temp}-{1'b0,divisor};always_ff@(posedge i_clk or negedge i_rst_n ) beginif( !i_rst_n ) begino_ready <= 1'b1;div_temp <= 'b0;cnt <= 'd31;quotient <= 'b0;remainder <= 'b0;o_done_vld <= 1'b0;end else begino_ready <= 1'b0;div_temp <= div_temp;cnt <= cnt;quotient <= quotient;remainder <= remainder;o_done_vld <= 1'b0;case( next_state )s_idle : begino_ready <= 1'b1;div_temp<= 'b0;cnt <= 'd31;ends_divinit : begindiv_temp <= dividend_temp[31];cnt <= 'd31;ends_divbyzero: beginquotient <= 'b0;ends_divon : beginif(div_sub[32]=='b0) beginquotient <= (quotient << 1'b1) | 1'b1;div_temp <= {div_sub[30:0],dividend[cnt-1'b1]};end else beginquotient <= (quotient << 1'b1);div_temp <= {div_temp[30:0],dividend[cnt-1'b1]};endcnt <= cnt - 1'b1;ends_divend : beginif( cnt == 'd31 ) beginremainder <= 'b0;end else beginremainder <= (div_sub[32]==1'b0)?div_sub[31:0]:div_temp;if(div_sub[32]=='b0) beginquotient <= (quotient << 1'b1) | 1'b1;end else beginquotient <= (quotient << 1'b1);endendo_done_vld <= 1'b1;enddefault : beginendendcaseend
endalways_comb beginif( o_done_vld == 1'b1 ) beginif( (div_signed == 1'b1 ) && ( dividend_signed ^ divisor_signed ) ) begino_quotient = ~quotient + 1'b1;end else begino_quotient = quotient;endend else begino_quotient = 'b0;end
end always_comb beginif( o_done_vld == 1'b1 ) beginif( (div_signed == 1'b1 ) && ( dividend_signed ^ remainder[31] )) begino_remainder = ~remainder + 1'b1;end else begino_remainder = remainder;endend else begino_remainder = 'b0;end
end
endmodule
2.2.2 tb_div.sv
/**************************************
@ filename : tb_div.sv
@ author : yyrwkk
@ create time : 2024/09/08 22:45:47
@ version : v1.0.0
**************************************/
module tb_div();
parameter N_WIDTH = 32 ;logic i_clk ;
logic i_rst_n ;
logic i_divsigned ;
logic i_divstart ;
logic [N_WIDTH-1:0] i_dividend ;
logic [N_WIDTH-1:0] i_divisor ;
logic [N_WIDTH-1:0] o_quotient ;
logic [N_WIDTH-1:0] o_remainder ;
logic o_done_vld ;
logic o_ready ; div div_inst (.i_clk (i_clk ),.i_rst_n (i_rst_n ),.i_divsigned (i_divsigned ),.i_divstart (i_divstart ),.i_dividend (i_dividend ),.i_divisor (i_divisor ),.o_quotient (o_quotient ),.o_remainder (o_remainder ),.o_done_vld (o_done_vld ),.o_ready (o_ready )
);initial begini_clk = 'b0;i_rst_n = 'b0;i_divsigned = 'b0;i_divstart = 'b0;i_dividend = 'b0;i_divisor = 'b0;
end initial beginforever #5 i_clk = ~i_clk;
end initial begin@(posedge i_clk );i_rst_n <= 1'b1;@(posedge i_clk );i_divsigned = 'b1;i_divstart = 'b1;i_dividend = {{29{1'b1}},3'b010};i_divisor = 'd5;@(posedge i_clk );i_divsigned = 'b0;i_divstart = 'b0;i_dividend = 'd0;i_divisor = 'd0;repeat(100) @(posedge i_clk);$stop;
end
endmodule
三、流水线实现
3.1 参考
参考自菜鸟教程: https://www.runoob.com/w3cnote/verilog-dividend.html
在原有基础上增加了对有符号数除法的处理。
流水线结构相较于状态机方案,只是将状态机中的循环处理进行了展平。以32bit被除数为例,在除法处理部分增加了额外的31块硬件资源( 一共需要32块 ), 以面积的增加换来吞吐率的提高,实际上感觉没有什么必要。
3.2 代码
3.2.1 divider_cell.sv
/**************************************
@ filename : divider_cell.sv
@ author : yyrwkk
@ create time : 2024/09/09 15:28:19
@ version : v1.0.0
**************************************/
module divider_cell # (parameter N_DIVIDEND = 32,parameter N_DIVISOR = 32
)(input logic i_clk ,input logic i_rst_n ,input logic i_en ,input logic i_div_signed ,input logic i_dividend_signed ,input logic i_divisor_signed ,input logic [N_DIVISOR+1-1:0] i_dividend , // last remainder + 1 bit origin dividend data -> N_DIVISOR + 1'b1input logic [N_DIVISOR-1:0] i_divisor ,input logic [N_DIVIDEND-1:0] i_quotient_last ,input logic [N_DIVIDEND-1:0] i_dividend_origin ,output logic [N_DIVIDEND-1:0] o_dividend ,output logic [N_DIVISOR-1:0] o_divisor ,output logic [N_DIVIDEND-1:0] o_quotient ,output logic [N_DIVISOR-1:0] o_remainder ,output logic o_div_signed ,output logic o_dividend_signed ,output logic o_divisor_signed ,output logic o_ready
);always_ff @(posedge i_clk or negedge i_rst_n ) beginif( !i_rst_n ) begino_ready <= 1'b0;o_dividend <= 'b0;o_divisor <= 'b0;o_quotient <= 'b0;o_remainder<= 'b0;o_div_signed <= 'b0;o_dividend_signed<= 'b0;o_divisor_signed <= 'b0;end else if( i_en ) begino_ready <= 1'b1;o_dividend <= i_dividend_origin;o_divisor <= i_divisor;o_div_signed <= i_div_signed ;o_dividend_signed<= i_dividend_signed;o_divisor_signed <= i_divisor_signed ;if( i_dividend >= {1'b0,i_divisor}) begino_quotient <= (o_quotient << 1'b1) | 1'b1;o_remainder<= i_dividend - {1'b0,i_divisor};end else begino_quotient <= (o_quotient << 1'b1);o_remainder<= i_dividend;endend else begino_ready <= 1'b0;o_dividend <= 'b0;o_divisor <= 'b0;o_quotient <= 'b0;o_remainder<= 'b0;o_div_signed <= 'b0;o_dividend_signed<= 'b0;o_divisor_signed <= 'b0;end
end
endmodule
3.2.2 divider.sv
/**************************************
@ filename : divider.sv
@ author : yyrwkk
@ create time : 2024/09/09 19:21:58
@ version : v1.0.0
**************************************/
module divider # (parameter N_DIVIDEND = 32,parameter N_DIVISOR = 32
)(input logic i_clk ,input logic i_rst_n ,input logic i_divsigned,input logic [N_DIVIDEND-1:0] i_dividend ,input logic [N_DIVISOR-1:0] i_divisor ,input logic i_divstart ,output logic [N_DIVIDEND-1:0] o_quotient ,output logic [N_DIVISOR-1:0] o_remainder,output logic o_res_vld
);logic [N_DIVIDEND-1:0] dividend_temp [N_DIVIDEND-1:0];
logic [N_DIVISOR-1:0] divisor_temp [N_DIVIDEND-1:0];
logic [N_DIVISOR-1:0] remainder_temp [N_DIVIDEND-1:0];
logic [N_DIVIDEND-1:0] rdy_temp ;
logic [N_DIVIDEND-1:0] quotient_temp [N_DIVIDEND-1:0];logic [N_DIVIDEND-1:0] div_signed_temp ;
logic [N_DIVIDEND-1:0] dividend_signed_temp ;
logic [N_DIVIDEND-1:0] divisor_signed_temp ;logic [N_DIVIDEND-1:0] dividend ;
logic [N_DIVISOR-1:0] divisor ;always_comb beginif( (i_divsigned==1'b1) && (i_dividend[N_DIVIDEND-1] == 1'b1 )) begindividend = ~i_dividend + 1'b1;end else begindividend = i_dividend;end
endalways_comb beginif( (i_divsigned==1'b1) && (i_divisor[N_DIVISOR-1] == 1'b1 )) begindivisor = ~i_divisor + 1'b1;end else begindivisor = i_divisor;end
endgenvar i;
generate for( i=0;i<N_DIVIDEND;i=i+1) begin: div_blockif( i==0 ) begindivider_cell #(.N_DIVIDEND(N_DIVIDEND),.N_DIVISOR (N_DIVISOR ))divider_cell_inst(.i_clk ( i_clk ),.i_rst_n ( i_rst_n ), .i_en ( i_divstart ),.i_div_signed ( i_divsigned ),.i_dividend_signed ( i_dividend[N_DIVIDEND-1]),.i_divisor_signed ( i_divisor[N_DIVISOR-1] ),.i_dividend ( {{N_DIVISOR{1'b0}},dividend[N_DIVIDEND-1]} ), // last remainder + 1 bit origin dividend data -> N_DIVISOR + 1'b1.i_divisor ( divisor ),.i_quotient_last ( {N_DIVIDEND{1'b0}} ), // init quotient is zero.i_dividend_origin ( dividend ),.o_dividend ( dividend_temp [i]),.o_divisor ( divisor_temp [i]),.o_quotient ( quotient_temp [i]),.o_remainder ( remainder_temp [i]),.o_ready ( rdy_temp [i]),.o_div_signed ( div_signed_temp [i]),.o_dividend_signed ( dividend_signed_temp [i]),.o_divisor_signed ( divisor_signed_temp [i]));end else begindivider_cell #(.N_DIVIDEND(N_DIVIDEND),.N_DIVISOR (N_DIVISOR ))divider_cell_inst(.i_clk ( i_clk ),.i_rst_n ( i_rst_n ), .i_en ( rdy_temp [i-1]),.i_div_signed (div_signed_temp [i-1]),.i_dividend_signed (dividend_signed_temp[i-1]),.i_divisor_signed (divisor_signed_temp [i-1]),.i_dividend ({remainder_temp[i-1],dividend_temp[i-1][N_DIVIDEND-i-1]}), // last remainder + 1 bit origin dividend data -> N_DIVISOR + 1'b1.i_divisor (divisor_temp [i-1]),.i_quotient_last (quotient_temp [i-1]),.i_dividend_origin (dividend_temp [i-1]),.o_dividend (dividend_temp [i]),.o_divisor (divisor_temp [i]),.o_quotient (quotient_temp [i]),.o_remainder (remainder_temp [i]),.o_div_signed (div_signed_temp [i]),.o_dividend_signed (dividend_signed_temp [i]),.o_divisor_signed (divisor_signed_temp [i]),.o_ready (rdy_temp [i]) );endend
endgeneratealways_comb beginif( (div_signed_temp[N_DIVIDEND-1] == 1'b1 ) && ( dividend_signed_temp[N_DIVIDEND-1] ^ divisor_signed_temp[N_DIVIDEND-1] ) ) begino_quotient = ~quotient_temp[N_DIVIDEND-1] + 1'b1;end else begino_quotient = quotient_temp[N_DIVIDEND-1];end
end always_comb beginif( (div_signed_temp[N_DIVIDEND-1] == 1'b1 ) && ( dividend_signed_temp[N_DIVIDEND-1] ^ remainder_temp[N_DIVIDEND-1][N_DIVISOR-1] )) begino_remainder = ~remainder_temp[N_DIVIDEND-1] + 1'b1;end else begino_remainder = remainder_temp[N_DIVIDEND-1];end
end assign o_res_vld = rdy_temp [N_DIVIDEND-1];endmodule
3.2.3 tb_divider.sv
/**************************************
@ filename : tb_divider.sv
@ author : yyrwkk
@ create time : 2024/09/09 20:15:01
@ version : v1.0.0
**************************************/
module tb_divider() ;
parameter N_DIVIDEND = 32;
parameter N_DIVISOR = 32;logic i_clk ;
logic i_rst_n ;
logic i_divsigned;
logic [N_DIVIDEND-1:0] i_dividend ;
logic [N_DIVISOR-1:0] i_divisor ;
logic i_divstart ;
logic [N_DIVIDEND-1:0] o_quotient ;
logic [N_DIVISOR-1:0] o_remainder;
logic o_res_vld ; divider # (.N_DIVIDEND (N_DIVIDEND),.N_DIVISOR (N_DIVISOR )
)divider_inst(.i_clk (i_clk ),.i_rst_n (i_rst_n ),.i_divsigned(i_divsigned),.i_dividend (i_dividend ),.i_divisor (i_divisor ),.i_divstart (i_divstart ),.o_quotient (o_quotient ),.o_remainder(o_remainder),.o_res_vld (o_res_vld )
);initial begini_clk = 'b0;i_rst_n = 'b0;i_divsigned= 1'b0;i_dividend = 'b0;i_divisor = 'b0;i_divstart = 'b0;
endinitial beginforever #5 i_clk = ~i_clk;
end initial begin@(posedge i_clk);i_rst_n <= 1'b1;@(posedge i_clk);for(int i=0;i<64;i++) begini_dividend <= ~i + 1'b1;i_divsigned<= 1'b1;i_divisor <= i+1;i_divstart <= 1'b1;@(posedge i_clk);endrepeat(100) @(posedge i_clk);$stop;
end
endmodule