Finite State Machines (from HDLBits)

前言

这篇博客主要来借助HDLBits上的几道题目谈一谈有限状态机。
刷题网站: HDLBits
题目路径: HDLBits →Circutis→Finite State Machines

  1. 分类:
    1. Moore,输出只和当前状态有关,f=(state)
    2. Mealy,输出与当前状态以及输入有关,f=(state,input)
  2. 三段式状态机(状态转化、状态更新、状态输出);
  3. 独热码状态机;
  4. 根据状态转换图、状态表,设计有限状态机。

Moore和Mealy可以互相转换,一般推荐Moore,组合逻辑输出时不用考虑输入,做法是将Mealy有不同输出的单一状态分为两个状态。

下面挑选了五个题目介绍一下,其余源码移步 Github

1. Design a Moore FSM

solution 1 作者的解

题解:题意容易理解,三位水位传感器(S)作为输入,将水位(level)分成了4档(A,B,C,D),根据上表可以知道不同水位(level)对应的额定流量(FR)。难点在于对于额外流量控制(ΔFR)的判断,当水位降低或者处于最低水位的时候要打开ΔFR。

水位降低这一动作意味着额外流量控制不仅和当前水位有关,还和传感器(S)有关,典型的Mealy FSM,但是题目”Design a Moore FSM“,所以把中间两个水位分成上升而得(1)和下降而得(2)两种情况,总共(A2,B1,B2,C1,C2,D1)六种状态。

module top_module (
	input clk,
	input reset,
	input [3:1] s,
	output reg fr3,
	output reg fr2,
	output reg fr1,
	output reg dfr
);


	// Give state names and assignments. I'm lazy, so I like to use decimal numbers.
	// It doesn't really matter what assignment is used, as long as they're unique.
	// We have 6 states here.
	parameter A2=0, B1=1, B2=2, C1=3, C2=4, D1=5;
	reg [2:0] state, next;		// Make sure these are big enough to hold the state encodings.
	


    // Edge-triggered always block (DFFs) for state flip-flops. Synchronous reset.	
	always @(posedge clk) begin
		if (reset) state <= A2;
		else state <= next;
	end



    // Combinational always block for state transition logic. Given the current state and inputs,
    // what should be next state be?
    // Combinational always block: Use blocking assignments.    
	always@(*) begin
		case (state)
			A2: next = s[1] ? B1 : A2;
			B1: next = s[2] ? C1 : (s[1] ? B1 : A2);
			B2: next = s[2] ? C1 : (s[1] ? B2 : A2);
			C1: next = s[3] ? D1 : (s[2] ? C1 : B2);
			C2: next = s[3] ? D1 : (s[2] ? C2 : B2);
			D1: next = s[3] ? D1 : C2;
			default: next = 'x;
		endcase
	end
	
	
	
	// Combinational output logic. In this problem, a procedural block (combinational always block) 
	// is more convenient. Be careful not to create a latch.
	always@(*) begin
		case (state)
			A2: {fr3, fr2, fr1, dfr} = 4'b1111;
			B1: {fr3, fr2, fr1, dfr} = 4'b0110;
			B2: {fr3, fr2, fr1, dfr} = 4'b0111;
			C1: {fr3, fr2, fr1, dfr} = 4'b0010;
			C2: {fr3, fr2, fr1, dfr} = 4'b0011;
			D1: {fr3, fr2, fr1, dfr} = 4'b0000;
			default: {fr3, fr2, fr1, dfr} = 'x;
		endcase
	end
	
endmodule

2. Lemmings4

See also: Lemmings1Lemmings2, and Lemmings3.

Although Lemmings can walk, fall, and dig, Lemmings aren’t invulnerable. If a Lemming falls for too long then hits the ground, it can splatter. In particular, if a Lemming falls for more than 20 clock cycles then hits the ground, it will splatter and cease walking, falling, or digging (all 4 outputs become 0), forever (Or until the FSM gets reset). There is no upper limit on how far a Lemming can fall before hitting the ground. Lemmings only splatter when hitting the ground; they do not splatter in mid-air.

Extend your finite state machine to model this behaviour.

Falling for 20 cycles is survivable:

Falling for 21 cycles causes splatter:

solution 2

题解:这一题是Lemmings系列的第四题,前面三题就略过,直接看第四题。作者依旧给出了状态转换图,挖、跌落都区分了左右。

未指定位宽的常量,默认32bit,所以定义[31:0] count

module top_module(
    input clk,
    input areset,    // Freshly brainwashed Lemmings walk left.
    input bump_left,
    input bump_right,
    input ground,
    input dig,
    output walk_left,
    output walk_right,
    output aaah,
    output digging ); 
	
    // delcaration
    parameter wl=3'b000,wr=3'b001,fl=3'b010,fr=3'b011,dl=3'b100,dr=3'b101,splat=3'b110;
    reg [2:0] state, next;
    reg [31:0] count;
    
    // state transition logic
    always @(*) begin
        case(state)
            wl:begin
                if(~ground)			next = fl;
                else if(dig)		next = dl;
                else if(bump_left)  next = wr;
                else				next = wl;
            end
            wr:begin
                if(~ground)			next = fr;
                else if(dig)		next = dr;
                else if(bump_right) next = wl;
                else				next = wr;
            end
            fl:begin
                if(ground) begin
                    if(count>19)    next = splat;
                    else            next = wl;
                end
                else 				next = fl;
            end
            fr:begin
                if(ground) begin
                    if(count>19)    next = splat;
                    else            next = wr;
                end
                else 				next = fr;
            end
            dl:begin
                if(~ground)			next = fl;
                else				next = dl;
            end
            dr:begin
                if(~ground)			next = fr;
                else				next = dr;
            end
            splat:begin
                					next = splat;
            end
        endcase
    end
    
    // state flip-flop DFF
    always @(posedge clk, posedge areset) begin
        if (areset)
            state <= wl;
        else if(state == fl || state == fr) begin
            state <= next;
            count <= count + 1;
        end
        else begin
            state <= next;
            count <= 0;
        end
    end
    
    
    // output logical
    assign walk_left 	= (state == wl);
    assign walk_right 	= (state == wr);
    assign aaah 	= (state == fl)||(state == fr);
    assign digging 	= (state == dl)||(state == dr);
    
endmodule

3. Serial receiver with parity checking

See also: Serial receiver and datapath

We want to add parity checking to the serial receiver. Parity checking adds one extra bit after each data byte. We will use odd parity, where the number of 1s in the 9 bits received must be odd. For example, 101001011 satisfies odd parity (there are 5 1s), but 001001011 does not.

Change your FSM and datapath to perform odd parity checking. Assert the done signal only if a byte is correctly received and its parity check passes. Like the serial receiver FSM, this FSM needs to identify the start bit, wait for all 9 (data and parity) bits, then verify that the stop bit was correct. If the stop bit does not appear when expected, the FSM must wait until it finds a stop bit before attempting to receive the next byte.

You are provided with the following module that can be used to calculate the parity of the input stream (It’s a TFF with reset). The intended use is that it should be given the input bit stream, and reset at appropriate times so it counts the number of 1 bits in each byte.

module parity (
    input clk,
    input reset,
    input in,
    output reg odd);

    always @(posedge clk)
        if (reset) odd = 0;
        else if (in) odd = ~odd;

endmodule

Note that the serial protocol sends the least significant bit first, and the parity bit after the 8 data bits.

Some timing diagrams

No framing errors. Odd parity passes for first byte, fails for second byte.

solution 3

题解:这题依旧是循序渐进,由前两题铺垫而来:

  1. 串行接收(低电平开始,传输一字节,高电平结束);
  2. 成功接收后,并行输出该字节;
  3. 接收一字节后,进行奇校验,校验成功并正常结束后,并行输出该字节。

把传输过程用8个状态表示。作者提供了奇校验模块。

由于clocked always中使用了非阻塞复制,状态转换和串行输入同时进行,所以case中判断的是next状态。

module top_module(
    input clk,
    input in,
    input reset,    // Synchronous reset
    output [7:0] out_byte,
    output done
); //

    // Modify FSM and datapath from Fsm_serialdata
    parameter [3:0] idle = 4'ha,start = 4'hb,stop = 4'hc,err=4'hd,odd_check=4'he;
    parameter [3:0] d0=4'h0,d1=4'h1,d2=4'h2,d3=4'h3,d4=4'h4,d5=4'h5,d6=4'h6,d7=4'h7;

    reg [3:0] state,next;
    reg [7:0] rcv;
    
    always @(posedge clk)begin
        if(reset)
            state <= idle;
        else
            state <= next;
        
	case(next)
            d0: 	rcv <= {in,rcv[7:1]};
            d1: 	rcv <= {in,rcv[7:1]};
            d2: 	rcv <= {in,rcv[7:1]};
            d3: 	rcv <= {in,rcv[7:1]};
            d4: 	rcv <= {in,rcv[7:1]};
            d5:		rcv <= {in,rcv[7:1]};
            d6:		rcv <= {in,rcv[7:1]};
            d7: 	rcv <= {in,rcv[7:1]};
            default:    rcv <= rcv;
        endcase
    end
    
    always @(*)begin
        case(state)
            idle: 		next = (~in)? start : idle;
            start:		next = d0;
            d0: 		next = d1;
            d1: 		next = d2;
            d2: 		next = d3;
            d3: 		next = d4;
            d4: 		next = d5;
            d5:			next = d6;
            d6:			next = d7;
            d7: 		next = (odd^in)	? odd_check : err ; // XOR the odd of input byte and parity bit, confirm odd parity
            odd_check:	        next = in 	? stop	    : err ; // high end bit
            stop: 		next = (~in)	? start     : idle;
            err:  		next = (~in)	? err       : idle;
            default:            next = idle;
        endcase
    end
    
    // New: Datapath to latch input bits.
	assign done = (state == stop);
    assign out_byte = done ? rcv : 8'bx;
    // New: Add parity checking.
	
    // record odd of the input 8 bytes [7:0] 
    wire odd;
    parity parity1(
        .clk(clk),
        .reset(state == idle),	// reset when idle
        .in(in),
        .odd(odd));
endmodule

4.1 Serial two’s complementer (Moore FSM)

You are to design a one-input one-output serial 2’s complementer Moore state machine. The input (x) is a series of bits (one per clock cycle) beginning with the least-significant bit of the number, and the output (Z) is the 2’s complement of the input. The machine will accept input numbers of arbitrary length. The circuit requires an asynchronous reset. The conversion begins when Reset is released and stops when Reset is asserted.

solution 4.1

题意:串行输出二进制补码,低位先输入。补码可以通过取反加1,即低位遇到第一个1后,后续各位取反。

Moore FSM设计4个状态,遇到第一个1前,状态为A,后续状态为B,下标分别表示输入0或1。

module top_module (
    input clk,
    input areset,
    input x,
    output z
); 
	parameter A0 = 2'b00,A1 = 2'b01, B0 = 2'b10, B1 = 2'b11;
    reg [1:0] state,next;
    
    always@(*) begin
        case(state)
            A0: next = x ? A1 : A0;
            A1: next = x ? B1 : B0;
            B0: next = x ? B1 : B0;
            B1: next = x ? B1 : B0;
        endcase
    end
    
    always@(posedge clk, posedge areset) begin
        if(areset)
            state <= A0;
        else
            state <= next;
    end
    
    always@(*) begin
        case(state)
            A0: z = 1'b0;
            A1: z = 1'b1;
            B0: z = 1'b1;
            B1: z = 1'b0;
        endcase
    end
    
endmodule

4.2 Serial two’s complementer (Mealy FSM)

The following diagram is a Mealy machine implementation of the 2’s complementer. Implement using one-hot encoding.

solution 4.2

题解:实现的功能与上一题相同,作者给出了状态图,本题使用两个状态,根据当前状态和输入决定输出。

module top_module (
    input clk,
    input areset,
    input x,
    output z
); 
	parameter A = 1'b0,B = 1'b1;
    reg state,next;
    
    always@(*) begin
        case(state)
            A: next = x ? B : A;
            B: next = B;
        endcase
    end
    
    always@(posedge clk, posedge areset) begin
        if(areset)
            state <= A;
        else
            state <= next;
    end
    
    always@(*) begin
        if(areset)
            z <= x;
        else
            case(state)
                A: z = x;
                B: z = ~x;
            endcase
    end
endmodule

5 FSM one-hot next-state logic

Consider the state machine shown below, which has one input w and one output z.

Exams m2014q6.png

For this part, assume that a one-hot code is used with the state assignment ‘y[6:1] = 000001, 000010, 000100, 001000, 010000, 100000 for states A, B,…, F, respectively.

Write a logic expression for the next-state signals Y2 and Y4. (Derive the logic equations by inspection assuming a one-hot encoding. The testbench will test with non-one hot inputs to make sure you’re not trying to do something more complicated).

solution 5

题解:作者给了状态图,很容易根据状态转换的边写出独热码状态机。

module top_module (
    input [6:1] y,
    input w,
    output Y2,
    output Y4);
    
	parameter A=1,B=2,C=3,D=4,E=5,F=6;
    reg [6:1] state;
    
    // State transition logic: Derive an equation for each state flip-flop.
    assign state[A] = w&(y[A]|y[D]);
    assign state[B] = (~w)&y[A];
    assign state[C] = (~w)&(y[B]|y[F]);
    assign state[D] = w&(y[B]|y[C]|y[E]|y[F]);
    assign state[E] = (~w)&(y[C]|y[E]);
    assign state[F] = (~w)&(y[D]);


    // Output logic: 
    assign Y2 = state[B];
    assign Y4 = state[D];
endmodule

Finite State Machines (from HDLBits)》有1个想法

  1. Pingback引用通告: HDLBits 刷题总结 | My ignorance

发表评论

邮箱地址不会被公开。 必填项已用*标注