关于数字IC面试题“ 101101 序列检测”的思考

dodoee

原题：
用FSM实现101101的序列检测模块。
a为输入端，b为输出端，如果a连续输入为101101则b输出为1，否则为0。


例如 a： 0001100110110110100110
b： 0000000000100100000000

请画出state machine；请用RTL描述其state machine。

确定状态数，没有输入或输入0为S0，1为S1，01为S2,101为S3,1101为S4，01101为S5。知道了输入输出和状态转移的关系很容易写出状态机的verilog代码，一般采用两段式状态机

讨论： 首先，我认为这道题就是一个坑， 我曾去一家公司面试时做过这个题，当时的题目 没有给 “例如 a： 0001100110110110100110  b： 0000000000100100000000” 这部分，后来面试的人写了一串类似的序列，我一看，我说后面的那个嵌套的检测不到。
按照一般的思路，依次检测输入，符合101101 的顺序，状态机顺序跳转到下一状态，不符合则根据情况跳转到前面的相应状态， 貌似是考查状态机和基本的coding能力 ，实际上仔细看这个例如，低位先输入，a: 101101101 这段如果用一般的序列检测，只能检测到一个101101 序列， 实际这里面还嵌套了一个， 第二个101101是检测不到的， 需要流水线思想或者其他的方法解决，如上面蓝色字体给出的其他方法。


这是典型的为了考试而出的考题，在SOC设计或者常用的模块设计中根本不会遇到这样的问题， 中国试考试从高考延申到考研，再延申到工作面试，彻底扼杀了innovation，封闭了思想。


出这样面试题的公司不去也罢！

randolpha

分2种.一种是覆盖,另一种是不覆盖.例子为第一种情况.

senasdf

一个移位寄存器就能搞定

dodoee

//  test for checking 101101101

module test_101(
                input clk,
                input reset_n,
                input a,
                output b
                );
parameter [2:0] IDLE =    3'b110;
parameter [2:0] STATE_0 = 3'b0;
parameter [2:0] STATE_1 = 3'b001;
parameter [2:0] STATE_2 = 3'b010;
parameter [2:0] STATE_3 = 3'b011;
parameter [2:0] STATE_4 = 3'b100;
parameter [2:0] STATE_5 = 3'b101;
               
reg reg_a;
always@(posedge clk)
begin
    if(reset_n == 0)
       reg_a <= 1'b0;
    else reg_a <= a;
end
reg [2:0] state,next_state;
reg [2:0] state_1,next_state_1;

always@(posedge clk)
begin
    if(reset_n == 0)
       state <= IDLE ;
    else state <= next_state;
end

always @(*)
begin
    case(state)
          IDLE       : if(reg_a) next_state = STATE_0; else next_state = IDLE ;
          STATE_0  : if(reg_a) next_state = STATE_0; else next_state = STATE_1;
          STATE_1  : if(reg_a) next_state = STATE_2; else next_state = IDLE;
          STATE_2  : if(reg_a) next_state = STATE_3; else next_state = IDLE;
          STATE_3  : if(reg_a) next_state = STATE_0; else next_state = STATE_4;
          STATE_4  : if(reg_a) next_state = STATE_5; else next_state = IDLE;
          STATE_5  : next_state =  IDLE;
          default  : next_state =  IDLE;
      endcase
end
//____ state_1 ___
always@(posedge clk)
begin
    if(reset_n == 0)
       state_1 <= IDLE;
    else state_1 <= next_state_1;
end

always @(*)
begin
    case(state_1)
          IDLE     : if(reg_a && (state==2)) next_state_1 = STATE_0; else next_state_1 = IDLE;
          STATE_0  : if(reg_a) next_state_1 = STATE_0; else next_state_1 = STATE_1;
          STATE_1  : if(reg_a) next_state_1 = STATE_2; else next_state_1 = IDLE;
          STATE_2  : if(reg_a) next_state_1 = STATE_3; else next_state_1 = IDLE;
          STATE_3  : if(reg_a) next_state_1 = STATE_0; else next_state_1 = STATE_4;
          STATE_4  : if(reg_a) next_state_1 = STATE_5; else next_state_1 = IDLE;
          STATE_5  : next_state_1 =  IDLE;
          default  : next_state_1 =  IDLE;
      endcase
end

//____________
reg [5:0] reg_shift;


always@(posedge clk)
begin
    if(reset_n == 0)
       reg_shift <= 6'b0;
    else reg_shift <= {reg_shift[4:0],reg_a};
end

assign b = reg_shift ==6'b101101;

endmodule

用状态机只要3个寄存器，但是不能检测嵌套的101，用两个状态机实现类似流水线操作，要6个寄存器，即可检测嵌套的101;
用移位寄存器至少要6个寄存器。

testbench

//  tb for test_101

module tb_test_101();

reg tb_clk,tb_reset_n ,tb_a;
test_101 inst_test_101(
                .clk    (tb_clk    ),
                .reset_n(tb_reset_n),
                .a      (tb_a      ),
                .b      (      )
                );


always #10 tb_clk = !tb_clk ;
reg [21:0] reg_in= 22'b0001_1001_1011_0110_1000_00;
reg [7:0]  i ;

initial
begin
    tb_clk = 0;
    tb_reset_n =0 ;
    tb_a =0;
    #50;
    tb_reset_n =1 ;
    #1;
    for(i=0; i<22; i=i+1) begin  
      @(posedge tb_clk);
      tb_a = reg_in;
  end
  #100;
  $stop;
end               

endmodule

devindang

这个不可以用6位宽的寄存器来实现吗？非要用状态机写一大堆吗？