11-1주차 (Chapter 6)

Design procedure

1. Specification
2. Formulation - Obtain a state digram or state table
3. State Assignment - Assign binary codes to the states
4. Filp-Flop Input Equation Determination - Select flip-flop types and derive flip-flop equations from next state entries in the table
5. Output Equation Determination - Derive output equations from output entries in the table
6. Optimization - Optimize the equations
7. Technology Mapping - Find circuit from equations and map to flip-flops and gate technology
8. Verification - Verify correctness of final design

여태까지 구해진 것을 해석하는 방법을 배웠다면 이제는 직접 회로를 design하는 법을 배운다. 여태 배웠던 것을 거꾸로 한다고 생각하면 된다.

---

Example : Recognize 1101

1101을 인식하는 Mealy machine을 State Diagram을 그려보자.

위를 바탕으로 State table을 그려보자.

Present State	Next State		Output
	x = 0	x = 1	x = 0	x = 1
A	A	B	0	0
B	A	C	0	0
C	D	C	0	0
D	B	A	0	1

---

Example : Moore Model for Sequence 1101

Moore Model은 input을 고려하지 않으므로 Mealy Model보다 state의 개수가 많이 필요하다.

1101을 인식하는 Moore model의 State Diagram

 

Present State	Next State		Output
	x = 0	x = 1	z
A	A	B	0
B	A	C	0
C	D	C	0
D	A	E	0
E	A	C	1

---

Finite State Machines

• A finite state machine(FSM) consists of three sets I, O, and S and two functions f and g.
  • I 는 input들의 집합
  • O 는 ouput들의 집합
  • S 는 state들의 집합
  • f는 I와 S가 들어왔을 때 next state를 알려준다. f(I,S)
  • g는 S가 들어왔을 때 output을 알려준다. g(S) [Moore model], g(I,S) [Mealy model] 

---

위 내용을 바탕으로 D flip-flop을 이용하여 101을 인식하는 Sequential System을 만들어 보자.(Mealy model)

State	Next State(q1*,q2*)		Output(z)
	x = 0	x =1	x = 0	x = 1
A(00)	A(00)	B(01)	0	0
B(01)	C(10)	B(01)	0	0
C(10)	A(00)	B(01)	0	1
x(11)	x	x	x	x

D1=q1*이라 하고 위를 바탕으로 D1의 Knaugh Map을 그리자.

x \ q1q2	00(A)	01(B)	11	10(C)
0		1	x
1			x

따라서 D1 = x'q2 이다.

D2 = q2*이라 하고 D2의 Knaugh Map을 그리자

x \ q1q2	00(A)	01(B)	11	10(C)
0			x
1	1	1	x	1

따라서 D2 = x이다.

z에 대한 Knaugh Map을 그려보자.

x \ q1q2	00(A)	01(B)	11	10(C)
0			x
1			x	1

z=xq1 이다.