- 2020-08-11 10:43
*views 5*- number IC interview
- IC
- Hand tear code

problem ： Enter a 16bit Number of , Now ask it to divide by 3 Obtained quotient and remainder ? How to optimize ?

See this topic , The first way to think of is the most traditional subtraction 3, Shangjia 1, Judgment remainder , Then keep decreasing , Keep adding , Until the last remainder is less than 3, This method is the stupidest and most intuitive . Use this method to realize it first .

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

Next, this is a more optimized approach ：

This practice refers to other people's articles , Divide by at one time 3 In operation , Only three sequences need to be considered , that is 11,100,101. What is this ? This law can be found from the following formula ：

Just sort it out , Arrange the divisor from high to low , Look from front to back 11,100,101 These three sequences , A sequence of these three numbers was encountered , Business write 1, Otherwise, I will write 0. Remove this sequence when done . If encountered 100, take 3’b100-2’b11

=

1’b1 Insert to the highest bit of the original sequence ; encounter 101, Then insert 2’b10, encounter 11, No operation . When actually writing code , Enter the divisor bit by bit from high to low , The quotient can be shifted to the left one at a time , In this way, after the complete sequence, the quotient calculated at the beginning will reach the high position , Avoid using register index .

A counter is required to control the number of state transitions , In theory, just count to the bit width of the divisor -1 that will do , But in practice, in order to avoid the final return IDLE The problem of making the remainder incorrect , Count it to the bit width of the divisor . Finally, quotient and remainder are obtained . The remainder is the binary number represented by the next state at the end of the counter .

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

The third paragraph of this code is about quotient , Why do you want to shift the state value of the current state to the left ? The specific reason depends on the state machine above , When the maximum is 1 When , Now this one's business is 1, Only occurs in the state S01 And status S10, When the highest is not 1 When , If in state S10 When , Now for 100, Consult 1, Take the highest position , If in S01 State time , Now for 010, Now Shang Wei 1, Consult 0.（ That's probably the explanation , Take a closer look ）

And the counter counts to 16 Question of , Actually 0 reach 15 That's enough , however 16 Just to get it back to IDLE.

Technology

- Java296 blogs
- Python265 blogs
- Vue125 blogs
- C Language122 blogs
- Algorithm108 blogs
- MySQL96 blogs
- Flow Chart83 blogs
- JavaScript79 blogs
- More...

©2020-2022 ioDraw All rights reserved