问题:输入一个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。

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信