[디지털 시스템] Sequential Circuit - Sequence detector

Moore vs Mealy Machine

유한개의 현재상태 (current state)를 가질 수 있는 Finite State Machine은

output을 최종적으로 결정하는 logic에 따라 Moore과 Mealy machine으로 크게 나눌 수 있다.

Moore machine은 OUTPUT이 현재 FSM의 state에 의해서만 결정된다.

반면 Mealy machine은 OUTPUT이 현재 state와 INPUT 모두에 의해 결정된다.

위 그림에서 OUTPUT 을 계산하는, output combinational logic에

Mealy machine은 input값이 들어가는 화살표가 있는것을 확인할 수 있다.

따라서 clock에 의해 state가 바뀌지 않더라도, input이 바뀌면 clock과 상관없이 output이 바뀔 수있다.

 

같은 FSM도 Moore과 Mealy버전으로 모두 구현할 수 있다.

Mealy Machine은 input이 output combinational logic에 끼어드는 복잡성이 생기는 대신,

같은 기능을 하기 위해 필요한 minimal state의 개수를 줄일 수 있다.

이것은 state를 보존하기 위한 register수를 줄일 수 있다는 등의 장점이 있다.

 

Synchronous Mealy Machine: using extra D-flipflop

Mealy machine의 문제점 - input이 바뀌면 clock과 상관없이 output이 바뀌는 

asynchronous behaviour가 발생할 가능성 - 은

output을 clock edge에 맞추어 값을 flip flop에 update해주면 해결된다!

FSM의 Moore/Mealy 버전 구현

drawing the state diagram

아래에서는 sequence detector를 만든다. 

sequence detector는 하나하나 순차적으로 들어오는 input sequence가

특정한 sequence(비밀번호라고 생각해도 좋다)와 일치하는 것을 감지하는 회로이다.

 

간단히 010 이라는 seq를 감지하는 FSM의 state diagram이다.

Moore 먼저 보면 Zero,One,Two,Match 의 4가지 state가 있다. (state register = 2bits)

Zero 의 오른쪽 위에 화살표는 Zero가 initial state임을 가리킨다.

그리고 각 state에서 다음 input에 따라 다음 state를 결정하는 next state logic 이 화살표로 표시되어 있다.

output 이 1인 state는 Match뿐이고, 색칠되어 있다. (output logic)

Mealy의 경우 1/0 에서 앞의 1은 해당 화살표를 따라가는 input이고, 뒤의 0은 output이다.

예를 들어 state One 에 있다가 input이 0이면, 다음 state는 다시 One이고, output은 0이다.

state개수가 하나 줄었지만 여전히 3개이기 때문에, state register는 2bits를 써야한다.

Coding the Moore machine

우리는 Moore방식으로 코딩하기로 한다. 

먼저 code의 뼈대를 잡아준다. 코드는 크게

state/register definitons, nextState logic, output logic으로 구성된다. nextState logic만 뺴고 일단 구현했다.

`timescale 1ns / 1ps

//detects 010
module seq_detector(
    input in,
    input clk,
    //reset on zero!
    input reset_n,
    output reg out
    );
    
    //define names for the states.
    parameter zero=0, one=1, two=2, match=3;
    
    reg[1:0] state;
    reg[1:0] nextState;
    
    //initial state
    initial begin
        state <= zero;
    end
    
    //update state every clock.
    always@(posedge clk) begin
        state <= nextState;
    end
    
    always@(posedge clk or negedge reset_n) begin
        if(~reset_n) state <= zero;
    end
    
    always@(in or state) begin
        //nextState logic
    end
    
    //output logic
    always@(state) begin
        case(state)
            zero: out <= 0;
            one: out <= 0;
            two: out <= 1;
            default: out <= 0;
        endcase
    end
endmodule

그리고 case 문을 통해서 위 FSM diagram 의 nextState logic을 구현한다.

        //nextState logic
        case(state)
            zero:
            begin
                if(in==0) nextState <= one;
                else nextState <= zero; 
            end
            one:
            begin
                if(in==0) nextState <= one;
                else nextState <= two; 
            end
            two:
            begin
                if(in==0) nextState <= match;
                else nextState <= zero; 
            end
            match:
            begin
                if(in==0) nextState <= one;
                else nextState <= two; 
            end
            default:
            nextState <= zero;
        endcase

default 빼고는(default로 빠질일이 있을까는 모르겠다만..) 그냥 위의 diagram을 고스란히 적은 것에 불과하다.

 

이제 testbench 를 작성하자. 뭐 clock이 있긴 한데,

그냥 input을 걸고 CLOCK_PERIOD만큼 기다려서

@posedge clk에 따라 다음state로 업데이트 하기를 기다린 후.

output을 정답과 비교하는 정도로만 쓰인다.

 

`timescale 100ps / 100ps

`define CLOCK_PERIOD 10
`define PATTERN_LEN 128
module detector_tb;

/* input to the detector */
reg CLK;
reg reset_n;
reg in;

/* output from the detector */
wire out;

/* internal counter for test */
integer i;
integer Passed;

// Connect the detector to detector_tb
// Please follow name specified here.
seq_detector UUT (
    .clk(CLK),
    .reset_n(reset_n),
    .in(in),
    .out(out));

/* Clock generator */
always #(`CLOCK_PERIOD/2) CLK = ~CLK;

reg [0 : `PATTERN_LEN - 1] pattern;
reg [0 : `PATTERN_LEN - 1] ans;

initial begin 
    CLK = 0;
    in = 0;
    reset_n = 1;

    /* if you change the input stream, change the below */
    pattern = `PATTERN_LEN'b00001101111101000010110010110011110000101101010111011011100000101111101011011011101010100001010001001100001110010000110011010010;
    ans     = `PATTERN_LEN'b00000000000000100001000001000000000000010000101000000000000000010000000100000000000101010000101000100000000000001000000000001001;
    
    /* Checking # of passes */
    Passed = 0;

    // reset
    #(`CLOCK_PERIOD/2) reset_n = 0; 
    #(`CLOCK_PERIOD + `CLOCK_PERIOD/2) reset_n = 1; 
    
    #(`CLOCK_PERIOD);

    for (i = 0 ; i < `PATTERN_LEN; i = i + 1) begin
        in = pattern[i];
        #(`CLOCK_PERIOD);

        if (out == ans[i]) Passed = Passed + 1;
    end

       
	$display("Passed = %0d, Failed = %0d", Passed, `PATTERN_LEN - Passed);	
    $finish;
end

endmodule // detector_tb

그리고 시뮬레이션 결과:

아 reset 테스트는 아무래도 reset 버튼의 동작이 불안해서 그냥 아래와 같이 reset 코드를 변경해서

실험한 거다.

 

    always@(negedge reset_n) begin
        if(~reset_n) begin 
            state <= zero;
            $display("reset: state = %0d", state);
        end
    end