博客

‘10010’序列检测器的两种实现方法（有限状态机、移位寄存器）

  • Post author:
  • Post category:其他


1、序列检测器？

序列检测器指的就是将一个指定的序列（以‘10010’为例）从数字码流中识别出来，是一个经典的数字电路实例。通常的序列检测方法有2种：有限状态机法（FSM）；移位寄存器法。

序列检测还分为重复检测和非重复检测。假设在输入码流“10010010”中进行重复检测，则会在检测到第一个“10010”和第二个“10010”后分别拉高输出表示成功检测；若非重复检测则只在检测到第一个“10010”拉高输出。

接下来就几种情况分别进行说明并提供代码、仿真及仿真结果说明。

2、有限状态机法

FSM（有限状态机）又可分为两种，根据状态机的输出是否与输入条件相关，可将状态机分为两大类，即摩尔(Moore)型状态机和米勒(Mealy) 型状态机。可参考

FPGA状态机（一段式、二段式、三段式）、摩尔型（Moore）和米勒型（Mealy）


  • Moore 状态机：组合逻辑的输出只取决于当前状态，而与输入状态无关。

  • Mealy 状态机：输出不仅取决于当前状态，还取决于输入状态。

2.1、

Moore 状态机

先将状态转移图贴出：

  • IDLE：初始状态，对输入的码流进行检测，若为1则跳转到状态A，则为0保留在该状态
  • A： 对输入的码流进行检测，若为0则跳转到状态B（10），则为1保留在该状态
  • B： 对输入的码流进行检测，若为0则跳转到状态C（100），则为1则跳转到状态A（101）
  • C： 对输入的码流进行检测，若为1则跳转到状态D（1001），则为0则跳转到状态IDLE（1000）
  • D： 对输入的码流进行检测，若为0则跳转到状态E（10010），则为1则跳转到状态A（10011）
  • E： 此时已经成功检测到了序列”10010“，可以拉高输出。

    • 重复检测：然后对输入的码流进行检测，若为0则跳转到状态C（100_100，后面的100可视为新的一轮检测），则为1则跳转到状态A（10010_1）
    • 非重复检测：然后对输入的码流进行检测，若为0则跳转到状态IDLE（10010_0，后面的100不可视为新的一轮检测），则为1则跳转到状态A（10010_1）

2.1.1、Verilog代码

根据状态转移图可编写Verilog代码如下：需要注意的是，将是否进行重复检测设为了参数REPEAT，1–重复检测；0–非重复检测，提供程序复用性。 

//检测序列“10010”，使用三段式Moore型状态机
module seqdet_moore
#(
	parameter	REPEAT = 1'b1		//1--重复检测；0--非重复检测
)
( 
	input 		x		,			//输入
	input		clk		, 			//时钟
	input		rst_n	,			//复位信号，低电平有效
	output 	reg	z					//输出采用时序逻辑，避免毛刺
);
//reg define
reg [2:0] 	cur_state	,			//现态
			next_state	;			//状态
//parameter define
localparam 	IDLE = 3'd0,
			A	 = 3'd1, 
			B	 = 3'd2,
			C	 = 3'd3, 
			D	 = 3'd4,
			E	 = 3'd5;

//三段式状态机第1段
always @(posedge clk or negedge rst_n)begin
	if(!rst_n)
		cur_state <= IDLE;
	else             
		cur_state <= next_state;
end
//三段式状态机第2段
always@(*)begin
	next_state = IDLE;
	case(cur_state)
		IDLE:	next_state = x ? A : IDLE;	
		A	:	next_state = x ? A : B;		
		B	:	next_state = x ? A : C;		
		C	:	next_state = x ? D : IDLE;	
		D	:	next_state = x ? A : E;		
		E	:	next_state = REPEAT ? (x ? A : C) : (x ? A : IDLE);		
		default:next_state = IDLE;
	endcase
end
//三段式状态机第3段
always @(posedge clk or negedge rst_n)begin
	if(!rst_n)
		z <= 1'b0;	
	else
		case(cur_state)
			E		:	z <= 1'b1;	
			default	:	z <= 1'b0;	
		endcase
end

endmodule

2.1.2、testbench

在测试代码我们分别例化两个检测模块，一个用来检测重复输出，另一个用来检测非重复输出。 

//检测序列“10010”，使用三段式Moore型状态机
`timescale 1ns/1ns

module tb_seqdet_moore;

reg		x		;
reg 	clk		; 
reg		rst_n	;

wire	z1		;			//重复检测输出结果
wire	z0		;			//非重复检测输出结果

parameter	REPEAT1 = 1'b1;	//重复检测
parameter	REPEAT0 = 1'b0; //非重复检

initial begin
 	clk = 1'b1;
 	rst_n <= 1'b0;
	x <= 1'b0;
 	#30 rst_n<=1; 						//拉高复位信号
	forever	#20	x <= ({$random} % 2);	//生成1bit的随机数
end

always #10 clk <= ~clk; 				//时钟信号50M
 
//例化序列检测器模块--重复检测
seqdet_moore
#(
	.REPEAT	(REPEAT1	)
)
seqdet_moore_isnt1( 
	.x		(x			),
	.clk	(clk		), 
	.rst_n	(rst_n		),
	.z		(z1			)	
);
//例化序列检测器模块--非重复检测
seqdet_moore
#(
	.REPEAT	(REPEAT0	)
)
seqdet_moore_isnt0( 
	.x		(x			),
	.clk	(clk		), 
	.rst_n	(rst_n		),
	.z		(z0			)	
);

endmodule

2.1.3、仿真结果

仿真结果如下：

可以看到重复检测的结果比非重复检测的结果还是多一些的，接下来选取几个典型的局部：

上图中，成功检测到序列”10010“,因为后续输入不满足条件，所以不存在重复检测。检测到序列 ”10010“后系统进入状态E，在状态E拉高输出表示一次成功的检测，由于输出采用时序逻辑，输出会延迟一个时钟周期，所以总体看来，Moore状态机的输出要落后序列 ”10010“1个时钟周期。

重复检测的结果如下：

上图中，输入码流为”10010_010“，在重复检测模式中，后面的10010又组成了一次成功的序列输入，所以一共输出两次成功检测标志；而非重复检测标志则只输出一次成功检测标志。

2.2、

Mealy 状态机



Mealy 状态机的输出不仅取决于当前状态，还取决于输入状态。所以在检测到序列”1001“后，若下一个输入为0则会拉高输出；若下一个输入为1则无输出。据此可以画出状态转移图如下：

  • IDLE：初始状态，对输入的码流进行检测，若为1则跳转到状态A，则为0保留在该状态
  • A： 对输入的码流进行检测，若为0则跳转到状态B（10），则为1保留在该状态
  • B： 对输入的码流进行检测，若为0则跳转到状态C（100），则为1则跳转到状态A（101）
  • C： 对输入的码流进行检测，若为1则跳转到状态D（1001），则为0则跳转到状态IDLE（1000）
  • D： 对输入的码流进行检测，则为1则跳转到状态A（10011）；若为0则成功检测到了序列”10010“，可以拉高输出。

    • 重复检测：则跳转到状态E（100_10，后面的10可视为新的一轮检测）
    • 非重复检测：则跳转到状态IDLE（10010_，开始新的一轮检测）

2.2.1、Verilog代码

根据状态转移图可编写Verilog代码如下：需要注意的是，将是否进行重复检测设为了参数REPEAT，1–重复检测；0–非重复检测，提供程序复用性。 

//检测序列“10010”，重复检测，使用三段式Mealy型状态机
module seqdet_mealy
#(
	parameter	REPEAT = 1'b1		//1--重复检测；0--非重复检测
)
( 
	input 		x		,			//输入
	input		clk		,   		//时钟
	input		rst_n	,   		//复位信号，低电平有效
	output 	reg	z					//输出采用时序逻辑，避免毛刺
);		
//reg define		
reg [2:0] 	cur_state	,   		//现态
			next_state	;			//状态
//parameter define
localparam 	IDLE= 3'd0,
			A	= 3'd1, 
			B	= 3'd2,
			C	= 3'd3, 
			D	= 3'd4;
//三段式状态机第1段
always @(posedge clk or negedge rst_n)begin
	if(!rst_n)
		cur_state <= IDLE;
	else             
		cur_state <= next_state;
end
//三段式状态机第2段
always@(*)begin
	next_state = IDLE;
	case(cur_state)
		IDLE:	next_state = x ? A : IDLE;	
		A	:	next_state = x ? A : B;		
		B	:	next_state = x ? A : C;		
		C	:	next_state = x ? D : IDLE;	
		D	:	next_state = REPEAT ? (x ? A : B) : (x ? A : IDLE);	
		default:next_state = IDLE;
	endcase
end
//三段式状态机第3段
always @(posedge clk or negedge rst_n)begin
	if(!rst_n)
		z <= 1'b0;	
	else begin
		case(cur_state)
			D: begin
				if(x == 1'b0)	//10010
					z <= 1'b1;	
				else			//10011
					z <= 1'b0;	
			end			
			default	:	z <= 1'b0;	
		endcase
	end
end

endmodule

2.2.2、testbench

在测试代码我们分别例化两个检测模块，一个用来检测重复输出，另一个用来检测非重复输出。 

//检测序列“10010”，使用三段式MEALY型状态机
`timescale 1ns/1ns

module tb_seqdet_mealy;

reg		x		;
reg 	clk		; 
reg		rst_n	;

wire	z1		;						//重复检测输出结果
wire	z0		;						//非重复检测输出结果

parameter	REPEAT1 = 1'b1;				//重复检测
parameter	REPEAT0 = 1'b0;             //非重复检测

initial begin
 	clk = 1'b1;
 	rst_n <= 1'b0;
	x <= 1'b0;
 	#30 rst_n<=1; 						//拉高复位信号
	forever	#20	x <= ({$random} % 2);	//生成1bit的随机数
end

always #10 clk <= ~clk; 				//时钟信号50M
 
//例化序列检测器模块--重复检测
seqdet_mealy
#(
	.REPEAT	(REPEAT1	)
)
seqdet_mealy_isnt1( 
	.x		(x			),
	.clk	(clk		), 
	.rst_n	(rst_n		),
	.z		(z1			)	
);
//例化序列检测器模块--非重复检测
seqdet_mealy
#(
	.REPEAT	(REPEAT0	)
)
seqdet_mealy_isnt0( 
	.x		(x			),
	.clk	(clk		), 
	.rst_n	(rst_n		),
	.z		(z0			)	
);

endmodule

2.2.3、仿真结果

仿真结果如下：

可以看到重复检测的结果比非重复检测的结果还是多一些的，接下来选取几个典型的局部图：

在检测到后1001后，接下来的输入为0构成10010所以立即输出成功检测标志。

重复检测的结果如下：

上图中，输入码流为”10010_010“，在重复检测模式中，后面的10010又组成了一次成功的序列输入，所以一共输出两次成功检测标志；而非重复检测标志则只输出一次成功检测标志。

3、移位寄存器法

3.1、说明

移位寄存器法比较简单粗暴，直接使用一个5位的寄存器寄存每一个码流，并在下一个时钟周期对其移位，再与需要的结果（10010）进行对比，根据对比结果输出检测结果。

非重复检测：最少都是码流”10010——10010“，那么两次成功输出会间隔最少5个时钟。所以我们可以设计一个计数器，当成功检测时将其清零，其他时候递加1。

实际上重复检测的时候直接输出即可，而非重复检测则需要根据计数器的值进行判断。每次成功输出时需要判断此时计数器的值，若非重复检测则计数器的值应大于等于4（0-4共5个时钟）。

3.2、Verilog代码

将是否进行重复检测设为了参数REPEAT，1–重复检测；0–非重复检测，编写Verilog代码如下： 

//检测序列“10010”，使用移位寄存器法
module seqdet_reg
#(
	parameter	REPEAT = 1'b1			//1--重复检测；0--非重复检测
)                                       
(                                       
	input 		x		,				//输入	
	input		clk		,               //时钟
	input		rst_n	,               //复位信号，低电平有效
	output 	reg	z			            //输出采用时序逻辑，避免毛刺
);

reg	[4:0]	z_reg;						//移位寄存器
reg	[9:0]	cnt;						//计数器，这里位宽设置大点，留点余量1024
reg			first_flag;					//第一次检测标志，拉高则表示已经检测到了第一个“10010”

//将输入向左移位寄存
always @(posedge clk or negedge rst_n)begin
	if(!rst_n)
		z_reg <= 5'd0;	
	else
		z_reg <= {z_reg[3:0],x};		//向左移位
end
//对比结果进行输出
always @(posedge clk or negedge rst_n)begin
	if(!rst_n)begin
		z <= 1'b0;	
		first_flag <= 1'b0;		
		cnt <= 10'd0;	
	end
	else if(REPEAT)begin				//重复检测到序列
			first_flag <= 1'b0;		
			cnt <= 10'd0;	
		if(z_reg == 5'b10010)			//捕捉到10010
			z <= 1'b1;		
		else
			z <= 1'b0;	
	end
	else begin							//非重复检测到序列
		if(z_reg == 5'b10010)begin		//捕捉到10010
			if(!first_flag)begin		//是第一个“10010”
				z <= 1'b1;
				first_flag <= 1'b1;		//拉高标志信号
				cnt <= 10'd0;			//计数器清零
			end
			else begin					//不是第一个“10010”
				if(cnt >= 'd4)begin		//间隔5个时钟以上（0-4）
					z <= 1'b1;
					cnt <= 10'd0;		//计数器清零
					first_flag <= first_flag;		
				end
				else begin
					z <= 1'b0;
					cnt <= cnt + 1;		//计数器累加1	
					first_flag <= first_flag;		
				end
			end
		end
		else begin						//没有捕捉到10010
			z <= 1'b0;
			cnt <= cnt + 1;				//计数器累加1	
			first_flag <= first_flag;		
		end
	end	
end

endmodule

3.3、 testbench

在测试代码我们分别例化两个检测模块，一个用来检测重复输出，另一个用来检测非重复输出。基本和FSM的tb文件一致。

3.4、仿真结果

仿真结果见下图：

方框内都是进行了重复检测的部分，由于重复检测的逻辑比较简单，所以我们只截取重复部分的非重复检测的典型图：

4、其他

  • 想要整个工程的朋友可以在评论区留下邮箱
  • 原创不易，能否给个三连~_~!

版本信息

文件：V1.0

编号：4

Vivado：无

Modelsim：Modelsim SE-64 10.4

Quartus II：无


版权声明：本文为wuzhikaidetb原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。