[Computer Circuit] Lec 05-4: Synchronous Sequential Logic Part 4

해당 글은 건국대학교 홍상우 교수님의 컴퓨터회로 수업 내용을 정리한 글입니다.

 

Mealy and Moore Model

 

sequentail circuit을 출력(output)이 어떻게 결정되는지에 따라 크게 두 가지 모델로 분류할 수 있습니다:

 

1. Mealy Model: 출력이 현재 상태(present state)와 현재 입력(input) 모두에 의해 결정됩니다. Lec05-3에서 분석한 Z = Q1Q0X회로가 바로 mealy model입니다. 이는 입력이 변하면, clock edge가 아니어도 출력이 즉시 바뀔 수 있습니다.

 

2. Moore Model: 출력이 오직 현재 상태(present state)에 의해서만 결정됩니다. 입력이 아무리 변해도 출력이 바로 바뀌지 않으며, 오직 clock edge에서 state가 바뀔 때만 출력이 바뀔 수 있으므로, 출력이 clock과 동기화되어 매우 안정적입니다.

 

State Reduction

 

회로 설계를 마친 후, 혹시 낭비되는(중복되는 상태)는 없는지를 점검하여 회로를 최적화하는 단계입니다. 외부에서 보이는 입출력 동작(기능)은 완벽히 동일하게 유지하면서, 상태의 개수를 줄이는 것입니다. 상태의 개수(M)가 줄면, 필요한 플립플롭의 개수(n = log_2(M))가 줄어들 수 있습니다(예: 5개 상태 -> 3개의 FF, 4개 상태 -> 2개의 FF). 이 과정의 핵심은 equivalent한 두 상태를 찾는 것입니다. 이는 1) 모든 입력에 대래 출력이 정확히 같고, 2) 다음 상태(next state)가 서로 같거나 혹은 동등한 상태로 가는 경우를 말합니다.

 

아래의 예시에 대해서 state reduction을 수행해보겠습니다:

ex

 

상태가 a, b, c, d, e, f, g 총 7개 입니다. 상태가 7개이므로, 이 회로를 구현하려면 최소 3개의 FF가 필요합니다. 우선 state를 줄이기 위해 state table을 그려야 합니다:

state table

 

해당 테이블을 보면 상태 e와 상태 g가 동등함을 알 수 있습니다(두 상태 모두 입력 0에 대해 출력 0/다음 상태 f, 입력 1에 대해 출력 1/다음 상태 a로 가기 때문에 '출력'과 '다음 상태'가 완벽히 동일합니다). 따라서 g 상태를 삭제하고, 테이블의 모든 g를 e로 바꿀 구 있습니다.

 

state table

 

이렇게 줄어든 state table에서도 상태 d와 상태 f가 동등함을 찾을 수 있습니다. 따라서 f대신 d로 바꿀 수 있습니다. 이를 고려하여 다시 state diagram을 그려보면 다음과 같습니다:

state diagram

 

State assignment

 

최적화가 끝난 5개의 추상적인 상태에, 실제 하드웨어가 알아들을 수 있도록 2진수 bit를 할당하는 단계를 state assignment단계라고 합니다. 5개의 상태는 최소 3개의 비트가 필요하며, 3개의 FF가 필요합니다. 할당의 방법은 1) binary(000, 001, ...) 순서대로 할당하는 방법, 2) gray code(000, 001, 011, ...) 과 같이 인접한 상태끼리 1비트만 차이 나게 할당하는 방법(전력 소모나 노이즈에 유리할 수 있습니다), 3) one-hot(00001, 00010, ...) 과 같이 상태 개수만큼의 FF를 쓰고, 매 순간 하나만 1이 되게 하는 방법을 쓸 수 있습니다. 아래의 예시는 binary로 할당한 방법입니다:

state assignment

 

Sequential Circuit Design

 

지금까지는 최적화와 관련된 얘기였고, 이제 설계에 대해서 다루겠습니다. "1001"이라는 비트 패턴을 인식하는 회로를 설계하는 예씨를 풀어보겠습니다. 입력(X)으로 매 클럭마다 1비트씩 데이터가 들어옵니다. 출력(Z)은 평소 0이다가, 입력 패턴이 "1001"로 완성되는 그 순간 1이 됩니다. 이 회로는 "1", "10", "100" 등을 기억하고 있어야 하므로 순차 회로가 필요합니다:

ex

 

아래는 순차 회로 설계를 의한 표준 레시피 5단계입니다:

 

1. 요구사항을 분석하여 state table/diagram을 만듭니다.

2. 각 상태에 binary code를 할당합니다.

3. Excitation table을 사용하여, 현재 상태 -> 다음 상태 를 만들기 위해 필요한 FF 입력값을 찾습니다.

4. K-맵 등을 이용해, FF 입력과 최종 출력(Z)을 위한 단순화된 논리 방정식을 구합니다.

5. 이 방정식대로 gate와 FF을 연결하여 회로를 만듭니다.

 

Step 1. Making a state table

 

이 단계는 우선 state diagram을 그린 후, state table을 만드는 것이 유리합니다. "1001" 예제의 경우 어디까지 맞췄는지를 상태로 정의합니다:

 

State A: "아무것도 못 맞춤" (초기 상태)State B: "1"까지 맞춤State C: "10"까지 맞춤State D: "100"까지 맞춤

 

이를 기본 뼈대로 하여 state diagram을 그리면 다음과 같습니다:

state diagram

 

그 후 다른 화살표들을 채워야하는데, 이때 중첩 패턴을 고려해야 합니다. 만약 상태 D("100"을 본 상태)에서 입력 "1"을 받으면 어떻게 될까요?

 

1) "1001" 패턴이 완성되었습니다! -> 출력(Z) = 1 이어야 합니다.

2) 그런데 이 마지막 1은 다음 "1001" 패턴의 시작 1일 수 있습니다(예: 1001001).

3) 따라서 다음 상태는 1을 본 상태인 B로 가야합니다.

 

그러므로 diagram에 D --(1/1)--> B 화살표가 추가됩니다. 그 후 패턴이 깨졌을 때 어디로 가야 할지 나머지 화살표를 모두 채웁니다:

state diagram

 

이렇게 완선된 state diagram을 그대로 state table로 옮겨 적으면, 설계 1단계가 끝납니다. 참고로, 이렇게 state table이 만들어진 후 state reduction을 수행해야 합니다. 해당 예시의 경우는 state reduction을 수행할 수 없기 때문에 그대로 step 2로 넘어갑니다:

fig

 

Step 2. Assigning binary codes to states

 

설계 2단계입니다. 4개의 상태(A, B, C, D)에 2진 코드를 할당합니다. 상태 4개는 최소 2비트가 필요하며, FF 2개로 이 회로를 만들 수 있습니다. 사실 state assignment는 회로 복잡도에 중요한 영향을 미칠 수 있지만, 해당 수업에서는 그렇게 중요하게 다루지 않습니다:

Step 2

 

Step 3. Finding FF inputs values

 

설계 3단계입니다. 현재 상태 -> 다음 상태의 변화를 만들기 위해, 우리가 사용할 JK FF의 입력에 무엇을 줘야 하는지 계산해야 합니다. JK FF는 설계 3단계가 조금 복잡하지만, Don't care(X)가 생겨서 4단계에서 큰 이득을 볼 수 있습니다. 이때 JK FF의 state table을 보고 요소들을 채울 수 있지만, Excitation table을 보고 채울 수도 있습니다. Excitation table을 state table과 달리 present state와 next state의 모든 조합에 대해서 JK값을 정리한 표이기 때문에, present state와 next state를 보고 JK 값을 찾아야하는 step 3에서 잘 사용할 수 있습니다:

excitation table

 

아래는 각 FF들의 excitation table입니다:

Excitation tables for all FF

 

다시 돌아와서 우리 예시에 대해 excitation table을 이용해 state table을 채우면 다음과 같습니다:

ex

 

Step 4. Find equations for the FF inputs and output

 

이렇게 완성된 테이블을 보고, 5개(J1, K1, J0, K0, Z)의 3입력(Q1, Q0, X) K-맵을 각각 그립니다. JK FF를 사용했기 때문에 K-맵에 'X' 항이 많고, 이를 통해 방정식을 매우 간단하게 묶을 수 있습니다. 그 결과 다음과 같은 단순화된 방정식을 얻습니다:

K-map

 

Step 5. Build the circuit

 

step 4에서 얻은 5개의 논리 방정식을 gate로 연결하고 2개의 JK FF, 1개의 clock을 배치하면 "1001" 인식기 회로가 완성됩니다:

step 5

 

Timing diagram

 

설계한 회로가 1001 을 제대로 잡는지 시뮬레이션한 것입니다:

timing diagram

 

1. 초기 상태 Q1Q0 = 00(A)

2. clock 1 edge: X=1 -> 상태 01(B)가 됨.

3. clock 2 edge: X=0 -> 상태 10(C)가 됨.

4. clock 3 edge: X=0 -> 상태 11(D)가 됨.

5. clock edge 3 이후: 상태(Q1Q0)는 11이고 입력(X)은 1이기 때문에, 출력 방정식 Z = Q1Q0X = (1)(1)(1) = 1 이 되어, 출력 Z가 clock edge와 상관없이 "즉시 1이 됩니다"(mealy model의 특징).

6. clock 4 edge: X=1 -> 상태 01(B)가 됨.

 

Building the same circuit with D flip-flops

 

이를 D FF로 설계할 수도 있습니다. step 1, 2까지는 동일하며, step 3(FF 입력 찾기)가 훨씬 쉬워집니다. D-FF의 excitation table은 D = Q(t+1)입니다. 즉, state table의 next state 열이 그대로 FF input(D1, D0)가 됩니다. 그 후 D1, D0 열을 K-map으로 단순화하여 D1, D0의 방정식을 구합니다(Z는 동일):

D-FF

 

Step 5을 수행하면 다음과 같은 circuit이 나옵니다:

circuit w/ D-FF

 

FF comparison

 

설계자 입장에서 두 FF를 비교하면 다음과 같습니다:

 

1. JK FF
   1. 장점: Don't care(X)항이 많아, 4단계(K-map)에서 combinational logic(gate)가 매우 단순해집니다.
   2. 단점: 3단계(excitation table) 계산이 귀찮고, FF 입력 배선이 2개(JK)입니다.
2. D FF
   1. 장점: 3단계(excitation table)가 매우 쉽습니다. 또한 FF 입력 배선이 1개(D)입니다.
   2. 단점: Don't care(X)가 없어서, 4단계(K-map)에서 나온 combinational logic이 JK보다 복잡할 수 있습니다.