数字IC手撕代码（七）

问题：输入一个16bit的数，现在要求它除以3得到的商和余数？如何优化？

看到这个题目，第一个想到的方法就是最传统的减3，商加1，判断余数，然后一直减、一直加，直到最后的余数小于3，这个方法最蠢最直观。先用这个方法实现一下。
module divid( input clk, input rst_n, input [15:0] din, output reg [1:0]
y_dout, output reg[15:0] s_dout ); reg [15:0] temp_data; reg end_flag; always @
(posedge clk or negedge rst_n) begin if(!rst_n) begin temp_data <= din; end else
begin temp_data<= temp_data - 2'd3; end end always @ (posedge clk or negedge
rst_n) begin if(!rst_n) begin end_flag <= 1'b0; end else if(temp_data <= 2'd3)
begin end_flag <= 1'b1; end else begin end_flag <= 1'b0; end end reg [15:0]
cnt; always @ (posedge clk or negedge rst_n) begin if(!rst_n) begin cnt <= 16'd0
; end else if(end_flag) begin cnt <= 16'd0; end else begin cnt <= cnt + 1'b1;
end end always @(posedge clk or negedge rst_n) begin if(!rst_n) begin y_dout <=
2'd0; end else if(temp_data <= 2'd3) begin y_dout <= temp_data[1:0]; end end
always @(posedge clk or negedge rst_n) begin if(!rst_n) begin s_dout <= 16'd0;
end else if(temp_data <= 2'd3) begin s_dout <= cnt; end end endmodule
接下来这个才是比较优化的做法：
这个做法是参考别人的文章的，在一次做除以3的运算中，只需要考虑三个序列，也就是11,100，101。这是问什么呢？从下面式子中可以发现这个规律：


整理下就是，把被除数从高位到低位排列，从前到后依次找11、100、101这三个序列，遇到这三个数中的序列，商就写1，否则商就写0。做完之后移除这个序列。如果遇到100，将3’b100-2’b11
=
1’b1插入到原序列最高位；遇到101，则插入2’b10,遇到11，不做操作。在实际写代码的时候，将被除数一位一位从高到低输入进来，可以把商每次左移一位，这样做完整个序列以后最开始计算出来的商的位就到了高位上，避免了使用寄存器索引。

需要一个计数器来控制状态转移次数，理论上只要计数到被除数的位宽-1即可，但是实际中为了规避最后返回IDLE使得到的余数不正确的问题，将它计数到了被除数的位宽。最后得到商和余数。余数就是计数器结束时的下一个状态表示的二进制数。
module divide_by_three #( parameter DATAWIDTH = 16 )( input clk, input rst_n,
input vld_in, input[DATAWIDTH-1:0] data_in, output reg [DATAWIDTH-1:0]
quotient, output reg[1:0] reminder, output reg vld_out ); reg [1:0] c_state; reg
[1:0] n_state; reg [$clog2(DATAWIDTH):0] cnt; reg [DATAWIDTH-1:0] data_reg;
parameter IDLE= 2'b11; always @ (posedge clk or negedge rst_n) begin if(!rst_n)
begin c_state <= IDLE; end else begin c_state <= n_state; end end always @ (*)
begin case(c_state) IDLE : if(vld_in) n_state = 2'b00; else n_state = IDLE; 2
'b00 : if(cnt==DATAWIDTH) n_state = IDLE; else if(data_reg[DATAWIDTH-1])
n_state = 2'b01; else n_state = 2'b00; 2'b01 : if(cnt==DATAWIDTH) n_state = IDLE
; else if(data_reg[DATAWIDTH-1]) n_state = 2'b00; else n_state = 2'b10; 2'b10 :
if(cnt==DATAWIDTH) n_state = IDLE; else if(data_reg[DATAWIDTH-1]) n_state = 2'
b10; else n_state = 2'b01; default : n_state = IDLE; endcase end always @
(posedge clk or negedge rst_n) begin if(!rst_n) begin
{cnt,data_reg,reminder,quotient,vld_out} <= 0; end else begin case(c_state)
IDLE : begin {vld_out,cnt} <= 0; if(vld_in) begin data_reg <= data_in; end else
begin data_reg <= data_reg; end end 2'b00,2'b01,2'b10 : begin if(cnt==
DATAWIDTH-1) begin cnt <= cnt + 1; reminder <= n_state; vld_out <= 1; end else
begin cnt<= cnt + 1; vld_out <= 0; data_reg <= {data_reg[DATAWIDTH-2:0],1'b0};
end if(data_reg[DATAWIDTH-1]) begin quotient <= {quotient[DATAWIDTH-2:0],c_state
[1]|c_state[0]}; end else begin quotient <= {quotient[DATAWIDTH-2:0],c_state[1]}
; end end endcase end end endmodule


这个代码的第三段那里关于求商，为什么要左移拼接的是当前状态的状态值呢？具体原因就看上面的状态机，当最高为为1的时候，此刻这一位的商为1，只会发生在状态S01和状态S10,当最高为不为1的时候，如果在状态S10的时候，此刻为100，会商1，就取最高位，如果在S01状态时候，此刻为010，此刻商为1，会商0.（大概解释就是这样，具体自己细细品一下）

还有就是计数器计数到16的问题，其实在0到15就已经够了，但是16就是为了让其返回到IDLE。

• « 上一篇：建立单链表相关问题详解
• » 下一篇：在上海做什么赚钱快？这10个你可以试一试！