试商法除法器

一、原理介绍

过程类似于十进制除法。
对于32位的除法，至少需要32个时钟周期，才能得到除法的结果。

设被除数是m, 除数是n, 商保存在s中, 被除数的位数是k, 计算步骤如下:

1. 取出被除数的最高位m[k], 使用被除数的最高位减去除数n ,如果结果大于等于0， 则商的s[k] 为1，反之为0
2. 如果上一步得到的结果为0，表示当前被减数小于除数，则取出被除数剩下的值的最高位m[k-1]，与当前被减数组合作为下一轮被减数。如果上一轮得到的结果是1，表示当前被减数大于除数，则利用上一轮中减法的结果与被除数剩下的值的最高位m[k-1]组合作为下一轮的被减数。然后，设置k等于k-1。
3. 新的被减数减去除数，如果结果大于等于0，则商的s[k]为1，否则s[k]为0，后面的步骤依次重复，直到k等于0。

二、状态机实现

2.1 状态转移图

部分状态介绍:

1. idle
2. divbyzero: 除数为0。
3. divinit: 进行有符号相关的处理，以及相关信号初始化赋值。
4. divon: 进行试商法除法。
5. 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