题解 | #不重叠序列检测#
不重叠序列检测
http://www.nowcoder.com/practice/9f91a38c74164f8dbdc5f953edcc49cc
方案一：使用6+1型状态机（6个状态+1个IDLE状态）
方案二：使用5+1型状态机（5个状态+1个IDLE状态）
首先分析题目：
1、序列检测，可以使用序列缓存或者状态机；题目要求使用状态机，则用状态机记录每一位是否匹配
2、无重叠。题目要求1bit 的data信号六位为一组，按组进行检测。如是不匹配则直接跳过剩下bits，检测下一组。关键需要处理“如何跳过剩下的bits”，这里选择空跑的方式，直接跳到下一组首位
3、not_match和match信号。match信号简单，关键是正确理解not_match信号。本来我是以为not_match信号是match信号的取反信号，但并不是！！！not_match信号也是脉冲信号，平时置零，只有（检测到最后一位）确定不匹配时，才置1，match置零。其余时刻两者均置0。看代码就懂了。
解题：（基于三段式状态机）
使用方案一，6+1型状态机，即设置6个状态+1个IDLE状态，实际可以检测七位，可以在state=SIX时直接跳到ONE状态，而非跳到IDLE状态；值得注意的是，为了完成空跑，实际上需要6+1+6个状态。
使用方案二，5+1型状态机，即设置5个状态+1个IDLE状态，实际可检测6位，在state=FIVE的时候，不论第六位是什么，直接跳到IDLE状态；区别在于match=1的条件为：state==FIVE && data==0 .完美衔接下一组。
代码如下：
//方案一:6+1
`timescale 1ns/1ns
module sequence_detect(
input clk,
input rst_n,
input data,
output reg match,
output reg not_match
);
parameter IDLE = 4'd0,
ONE = 4'd1,
TWO = 4'd2,
THREE = 4'd3,
FOUR = 4'd4,
FIVE = 4'd5,
SIX = 4'd6,
Z1 = 4'd7, Z2=4'd8, Z3=4'd9,Z4=4'd10,Z5=4'd11,Z6=4'd12;
reg [3:0] state,n_state;
always @(posedge clk or negedge rst_n)
if(!rst_n) state <= data;
else state <= n_state;
always @(*)
if(!rst_n) state <= IDLE;
else case(state)
IDLE : n_state = data ? Z1 : ONE;
ONE : n_state = data ? TWO : Z2;
TWO : n_state = data ? THREE : Z3;
THREE : n_state = data ? FOUR : Z4;
FOUR : n_state = data ? Z5 : FIVE;
FIVE : n_state = data ? Z6 : SIX;
SIX : n_state = data ? Z1 : ONE;
Z1 : n_state = Z2;
Z2 : n_state = Z3;
Z3 : n_state = Z4;
Z4 : n_state = Z5;
Z5 : n_state = Z6;
Z6 : n_state = data ? Z1 :ONE;
default : ;
endcase
always @(posedge clk or negedge rst_n)
if(!rst_n) begin
match <= 1'b0;
not_match <= 1'b0;
end
else if(n_state == SIX) begin
match <= 1'b1;
not_match <= 1'b0;
end
else if(n_state == Z6) begin
match <= 1'b0;
not_match <= 1'b1;
end
else begin
match <= 1'b0;
not_match <= 1'b0;
end
endmodule
//方案二：5+1
`timescale 1ns/1ns
module sequence_detect(
input clk,
input rst_n,
input data,
output reg match,
output reg not_match
);
parameter IDLE = 4'd0,
ONE = 4'd1,
TWO = 4'd2,
THREE = 4'd3,
FOUR = 4'd4,
FIVE = 4'd5,
SIX = 4'd6,
Z1 = 4'd7, Z2=4'd8, Z3=4'd9,Z4=4'd10,Z5=4'd11,Z6=4'd12;
reg [3:0] state,n_state;
always @(posedge clk or negedge rst_n)
if(!rst_n) state <= data;
else state <= n_state;
always @(*)
if(!rst_n) state <= IDLE;
else case(state)
IDLE : n_state = data ? Z1 : ONE;
ONE : n_state = data ? TWO : Z2;
TWO : n_state = data ? THREE : Z3;
THREE : n_state = data ? FOUR : Z4;
FOUR : n_state = data ? Z5 : FIVE;
FIVE : n_state = IDLE;
Z1 : n_state = Z2;
Z2 : n_state = Z3;
Z3 : n_state = Z4;
Z4 : n_state = Z5;
Z5 : n_state = IDLE;
default : ;
endcase
always @(posedge clk or negedge rst_n)
if(!rst_n) begin
match <= 1'b0;
not_match <= 1'b0;
end
else if(state == FIVE && data == 1'd0) begin
match <= 1'b1;
not_match <= 1'b0;
end
else if((state == FIVE && data == 1'd1) || state == Z5) begin
match <= 1'b0;
not_match <= 1'b1;
end
else begin
match <= 1'b0;
not_match <= 1'b0;
end
endmodule
