【논리설계】 8강. 순차논리

8강. 순차논리(sequential logic)

 

추천글 : 【논리설계】 논리설계 목차

---

1. 개요 [본문]

2. 유한상태기계 [본문]

3. 여기표와 state encoding [본문]

4. state minimization [본문]

5. 순차논리회로의 종류 [본문]

6. 시스템의 설계 [본문]

---

 

1. 개요 [목차]

⑴ 조합논리회로(combinational logic circuit)

① 값을 저장하지 못함

② 클럭을 사용하지 않음

③ 입력의 변화가 출력에 바로 반영됨

④ 예 : adder, multiplexer, decoder, encoder, gate 

⑵ 순차논리회로(sequential logic circuit) : 조합논리회로와 메모리 소자의 조합

① 값을 저장하는 래치, 플립플롭, 레지스터, 메모리 등의 소자가 있어서 상태를 저장함

② 대부분 클럭을 사용하여 값을 저장 (예외 : 래치)

③ 예 : clock divider, counter, register, FSM

 

 

2. 유한상태기계 [목차]

⑴ 개요

① 유한상태기계(FSM, finite state machine) : state 간 상호작용 및 I/O를 맵핑하여 순차논리회로를 간략히 구현한 것

② (구별 개념) ASM(algorithmic state machine) 

③ (구별 개념) 튜링 머신(Turing machine) : 예를 들어, (2,4) 튜링 머신은 2개의 상태(A, B)와 4개의 기호(0, 1, 2, 3)를 가짐

⑵ Mealy machine

Figure 1. Mealy machine의 한 예시

 

① edge 상에 표시된 "L/R"에서 왼쪽은 입력값, 오른쪽은 출력값이다.

② 출력이 현재 state와 현재 입력의 함수로 표현된다.

③ 문제 1. 입력이 asynchronous하면 출력도 asynchronous하다. (& vice versa)

○ 이로 인해 Mealy machine은 glitch가 발생할 수 있다.

④ 문제 2. clock이 너무 느리면 입력을 주어도 state가 바뀌지 않을 수 있다.

⑤ 문제 3. clock이 너무 빠르면 입력을 여러 차례 준 것으로 인식될 수 있다.

⑥ 상기의 이유로 실제 시스템 설계 시 전혀 쓰지 않는 모델이다. 

⑶ Moore machine

Figure 2. Moore machine의 한 예시

 

① 출력이 현재 state의 함수로 표현된다; 따라서 synchronous하다.

② 출력을 state로 표현하는 과정이 추가돼 Mealy machine보다 어려운 편이다.

 

 

3. 여기표 및 state encoding [목차]

⑴ 여기표(excitation table, state transition table)

① 정의 : 순차논리회로에서 진리표를 여기표라고 지칭

② current state와 input에 대한 함수로 next state 및 output을 표현함

③ 여기표를 통해 조합논리회로 이론을 활용할 수 있음 (ref)^]

④ self-starting: 모든 don't-care를 활용하여 모든 무효 케이스가 유효해진 것

○ 어떤 상태로 초기화돼도 정상 작동할 것임을 확신할 수 있음

 

출처 : 이미지 클릭

Figure 3. self-starting 회로의 예시^]

 

⑵ state encoding

① 정의 : state, input, output의 이름들을 이진수로 나타내는 것

② state encoding과 bit 수

○ 더 적은 비트수의 state encoding은 적은 F/F를 필요로 하지만 복잡할 수 있음

○ 더 많은 비트수의 state encoding(e.g., one-hot)은 많은 F/F를 필요로 할 수 있음

○ one-hot encoding : n개의 state를 표현시 단 한 bit만 1인 n 비트 수로 표현하는 방법

○ 회로 구성 시 용이함

③ priority encoding^]

④ heuristic encoding

○ highest priority : 입력이 같으면 다음 state가 같은 state의 집합

○ medium priority : 한 state의 다음 states

○ lowest priority : 입력이 같으면 출력이 같은 state의 집합

⑶ shift register로 clock 주기 단위의 어떤 신호도 생성할 수 있다.

출처: 서울대학교 논리설계(유승주) 강의자료

Figure 4. shift register로 생성된 단위 시간 간격의 신호^]

 

 

4. state minimization [목차]

⑴ equilibrium state

① 서로 동등하게 취급할 수 있는 서로 다른 state를 지칭한다.

② Mealy machine : next state, next output 패턴이 같아야 한다.

③ Moore machine : next state, current output 패턴이 같아야 한다.

 

Current State	Next State		Output
	X = 0	X = 1
A	D	C	0
B	F	H	0
C	E	D	1
D	A	E	0
E	C	A	1
F	F	B	1
G	B	H	0
H	C	G	1

Table 1. excitation table의 예시

 

⑵ row matching method

① 새 연산 도입 : (A B) = (A)(B)

○ A, B는 부분집합을 가리키는 기호이다.

○ ^∀a ∈ A, ^∀b ∈ B, a ≢ b

② 1^st. (A B C D E F G H) = (A B D G)(C E F H) (Output 기준)

 

Current State	Next State		Output
	X = 0	X = 1
A	A	C	0
A	C	C	0
C	C	A	1
A	A	C	0
C	C	A	1
C	C	A	1
A	A	C	0
C	C	A	1

Table 2. row matching method 과정 (1)

 

③ 2^nd. (A B D G)(C E F H) = (A D G)(B)(C E F H)

 

Current State	Next State		Output
	X = 0	X = 1
A	A	C	0
B	C	C	0
C	C	A	1
A	A	C	0
C	C	A	1
C	C	B	1
A	B	C	0
C	C	A	1

Table 3. row matching method 과정 (2)

 

④ 3^rd. (A D G)(B)(C E F H) = (A D)(G)(B)(C E H)(F)

 

Current State	Next State		Output
	X = 0	X = 1
A	A	C	0
B	F	C	0
C	C	A	1
A	A	C	0
C	C	A	1
F	F	B	1
G	B	C	0
C	C	G	1

Table 4. row matching method 과정 (3)

 

⑤ 4^th. (A D)(G)(B)(C E H)(F) = (A D)(G)(B)(C E)(H)(F)

 

Current State	Next State		Output
	X = 0	X = 1
A	A	C	0
B	F	H	0
C	C	A	1
A	A	C	0
C	C	A	1
F	F	B	1
G	B	H	0
H	C	G	1

Table 5. row matching method 과정 (4)

 

⑥ 5^th. 더이상 나뉘지 않으므로 A ≡ D, C ≡ E라고 결론지을 수 있다.

⑦ 자명하게 다항식 시간이 소요됨을 알 수 있다.

⑶ implication chart method

① 1^st. 다음과 같이 excitation table의 내용을 옮긴다.

 

B	DC / FH
C	DC / ED	FH / ED
D	DC / AE	FH / AE	ED / AE
E	DC / CA	FH / CA	ED / CA	AE / CA
F	DC / FB	FH / FB	ED / FB	AE / FB	CA / FB
G	DC / BH	FH / BH	ED / BH	AE / BH	CA / BH	FB / BH
H	DC / CG	FH / CG	ED / CG	AE / CG	CA / CG	FB / CG	BH / CG
	A	B	C	D	E	F	G

Table 6. implication chart method 과정 (1)

 

② 2^nd. 우선 output에 따라 equilibrium state가 아닌 것들을 지운다.

 

B
C
D
E
F
G
H
	A	B	C	D	E	F	G

Table 7. implication chart method 과정 (2)

 

③ 3^rd. 1회 반복(상 → 하, 좌 → 우)

 

B
C
D
E
F
G
H
	A	B	C	D	E	F	G

Table 8. implication chart method 과정 (3)

 

④ 4^th. 2회 반복(상 → 하, 좌 → 우)

 

B
C
D
E
F
G
H
	A	B	C	D	E	F	G

 

Table 9. implication chart method 과정 (4)

 

⑤ 5^th. 더 이상 지울 수 없는 경우 체크되지 않은 칸이 바로 equilibrium state 쌍이다.

○ 순환 논리적인 항들이 남아 있을 수도 있다.

⑥ 자명하게 다항식 시간이 소요됨을 알 수 있다.

⑷ 만약 FSM이 don't-care를 가지고 있는 경우 두 방법은 사용할 수 없다.

① 아래 예시에서 "S0 = S1, S1 = S2이므로 S0 = S2"인가?

 

 

Table 10. don't-care 조건을 포함하는 FSM의 예시

 

 

5. 순차논리회로의 종류 [목차]

⑴ 인터록(interlock) 회로 : 한쪽이 동작하면 다른 한쪽은 동작할 수 없는 논리회로

⑵ 신입 신호 우선 회로 : 한쪽이 동작하면 다른 한쪽이 복구되는 논리회로

⑶ 동작 우선 회로 : 정해진 순서대로 동작되는 논리회로 (예: X1이 동작해야 X2가 동작할 수 있다.)

⑷ 시한 회로(on delay timer; Ton) : 입력을 주면 설정시간이 지난 후 출력이 동작(OFF → ON)

⑸ 시한 복구 회로(off delay timer; Toff) : 정지입력을 주면 설정시간이 지난 후 출력이 복구(ON → OFF)

⑹ 단안정 회로(monostable) : 입력을 주면 설정시간이 지난 후 빠르게 동작 및 복구(ON → OFF → ON)

① 시한 회로나 시한 복구 회로와 달리 NOT 게이트와 연결돼 기본 상태가 ON 상태

 

 

6. 시스템의 설계 [목차]

⑴ 시스템은 크게 2가지 부분으로 나뉜다.

⑵ data unit : 데이터를 저장, 결합 또는 처리하는 부분

⑶ control unit : 프로세스를 시작, 중단, 검토, 통신 및 결정하는 부분

 

입력: 2016.11.20 21:40