6-2강 - Sequential Circuit Design 2 (Sequence Detector example - Mealy & Moore)

4. Sequence Recognizer Example

1) Mealy Machine

0> example에 대한 소개

1101 sequence를 인식하는 sequence recognizer를 만듭니다.

(주의 : 1101101은 1101이 2번 등장한 것입니다.)

 

cf> Mealy Machine의 결정적인 특징

현재 state와 현재 input을 통해 다음 state를 결정합니다.

1. (state diagram) 그래서 arg(화살표)에 현재 input을 표기합니다.

2. (state table) 현재 input에 따라 output은 다르기 때문에 현재 input(x)에 따라 output을 따로 표기합니다.

 

1> State Diagram 만들기

(sequence 인식에 필요한 state들을 각각 정의합니다.)

[1] sequence 내부의 순서대로 하나씩 state를 정의합니다.

=> 이 때 중간 과정에서는 output이 0입니다.

=> sequence 모두가 다 주어지면 output이 1이라고 합니다. 

[2] sequence 모두가 다 주어진 뒤의 state 결정 (무조건 초기 state가 아닙니다.)

=> sequence를 완료와 동시에 sequence의 일부가 시작되었는지 확인합니다. (주의)

[3] input과 state 조합 중 남은 경우를 입력하기

=> 현재 state까지 입력된 input만 고려하여 state 결정하기 (주의)

 

2> State Table 만들기

[1] (column) Present state, next state(x=0, 1), output(x=0, 1) 항목을 만듭니다.

(Mealy Machine은 현재 input(x)에 따라 output을 따로 표기합니다.)

[2] (row) state를 모두 적습니다.

[3] 완성한 Diagram을 토대로 빈칸을 채워넣습니다.

[4] state assignment

 

---

 

1> (예시) State Diagram 만들기

[1] (예시) state 정의

A : 최초의 state를 A라고 정의합니다.

B : 처음 "1"이 나온 이후 "A"라는 state로 정의 (output = 0)

C : B 이후 "1"이 나오면 (subsequence 11) "C"라는 state로 정의 (output = 0)

D : C 이후 "0"이 나오면 (subsequence 110) "D"라는 state로 정의 (output = 0)

(D 이후 "1"이 나오면 output이 1입니다.)

- subsequence : 우리가 recognize하려는 sequence의 일부를 이야기합니다.

- A : 적절한 subsequence를 하나도 입력받지 못한 상태

- B : subsequence "1"을 입력받은 상태

- C : subsequence "11"을 입력받은 상태

- D : subsequence "110"을 입력받은 상태

 

 

[2] (예시) 마지만 state 이후의 state

1101이 완료된 것은

동시에 4번째의 1로 인해 다시 sequence의 시작을 의미합니다.

그러므로 D이후에는 첫번째 "1" 입력받은 상태인 B로 가야합니다.

 

[3] (예시) 남은 경우의 state

남은 경우의 수는 아래 4가지 입니다.

[1]과 [2]에서 정의한대로 남은 경우들을 채워넣습니다.

예를 들어, C에서 1이 입력되면 B가 아닙니다. 

이미 A에서 B로 오기까지 1이 입력되었기 때문에 현재 subsequence "11"이 입력되어 C로 가야합니다.

 

 

2> State Table 만들기

 

---

2) Moore Machine

0> example에 대한 소개

1101 sequence를 인식하는 sequence recognizer를 만듭니다.

(주의 : 1101101은 1101이 2번 등장한 것입니다.)

 

cf> Moore Machine의 결정적인 특징

현재 state로 다음 state를 결정합니다. (그래도 현재 input이 다음 state 결정에 영향을 미칩니다.)

0. Mealy Machine과 달리 state의 개수는 sequence 길이보다 1개 더 많아야 합니다. 

1. (state diagram) 그래서 state에 output을 표기합니다. (state가 곧 output입니다.)

2. (state table) 현재 input과 관계 없이 현재 state만으로 output이 같기 때문에

현재 input(x)을 구분하지 않고 output을 그냥 표기합니다.

 

1> State Diagram 만들기

(sequence 인식에 필요한 state들을 각각 정의합니다.)

[1] sequence 내부의 순서대로 하나씩 state를 정의합니다.

=> 이 때 중간 과정에서는 output이 0입니다.

=> sequence 모두가 다 주어진 직후의 state가 있습니다. 이 때만 output이 1입니다.

[2] sequence 모두가 다 주어진 뒤의 state 결정 (무조건 초기 state로 가는 것이 아닙니다.)

=> sequence를 완료와 동시에 sequence의 일부가 시작되었는지 확인합니다. (주의)

[3] input과 state 조합 중 남은 경우를 입력하기

=> 현재 state까지 입력된 input만 고려하여 state 결정하기 (주의)

 

2> State Table 만들기

[1] (column) Present state, next state(x=0, 1), output(x=0, 1) 항목을 만듭니다.

(Moore Machine은 현재 input(x)과 상관없이 output을  표기합니다.)

[2] (row) state를 모두 적습니다.

[3] 완성한 Diagram을 토대로 빈칸을 채워넣습니다.

[4] state assignment

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

어떤 state에서 출발하든 상관 없어야 한다.