배우기 › 주제 11
무어와 밀리 상태 기계: 설계 전 과정
읽는 시간 7분 · bitGateLab 팀
유한 상태 기계(FSM)는 어떤 과정이 몇 번째 단계에 있는지를 "기억하는" 순차 회로입니다. 신호등, 비밀번호 자물쇠, 엘리베이터 제어기, 직렬 통신 수신기가 모두 상태 기계입니다. 여기서는 고전적인 두 모델인 무어와 밀리를 살펴보고, 101 시퀀스 검출기를 예로 들어 말로 된 설명에서 플립플롭의 식에 이르기까지 설계 전 과정을 따라가 봅니다.
상태 기계의 구성 요소
동기 FSM은 모두 세 블록으로 이루어집니다.
- 상태 레지스터: 현재 상태를 저장하는 플립플롭 n개(거의 항상 D형)이며, 상태를 2n개까지 나타낼 수 있습니다.
- 다음 상태 논리: 조합 논리이며, 현재 상태와 입력으로부터 다음 상태를 계산합니다.
- 출력 논리: 조합 논리이며, 출력을 계산합니다.
두 모델의 차이는 마지막 블록에 있습니다.
- 무어: 출력이 현재 상태에만 의존합니다. 출력은 각 상태의 원 안에 적습니다(예: S3/1).
- 밀리: 출력이 상태와 입력에 의존합니다. 출력은 화살표 위에 적습니다(입력/출력, 예: 1/1).
문제: 101 시퀀스 검출기
직렬 입력 X가 클럭에 동기되어 주기마다 한 비트씩 들어옵니다. 출력 Z는 마지막으로 받은 세 비트가 1, 0, 1일 때마다 1이 되어야 합니다. 중첩을 허용합니다. 10101이라는 비트열에서는 첫 번째 시퀀스의 마지막 1이 다음 시퀀스의 첫 1이 되므로 검출이 두 번 일어납니다.
첫 단계는 기계가 무엇을 기억해야 하는지 정하는 것입니다. 각 상태는 "시퀀스를 어디까지 받았는가"를 나타냅니다.
- S0: 쓸모 있는 것을 아직 받지 못했습니다.
- S1: 마지막 비트가 1이었습니다.
- S2: 마지막 비트들이 1, 0이었습니다.
- S3: 방금 1, 0, 1을 받았습니다(Z = 1).
상태도와 상태표(무어)
각 상태와 X의 각 값에 대해 이렇게 물어보세요. 이 새 비트까지 포함했을 때, 101의 앞부분과 일치하는 가장 긴 접미사는 무엇인가? 그 접미사가 다음 상태를 결정합니다.
| 현재 상태 | X = 0 | X = 1 | Z |
|---|---|---|---|
| S0 | S0 | S1 | 0 |
| S1 | S2 | S1 | 0 |
| S2 | S0 | S3 | 0 |
| S3 | S2 | S1 | 1 |
자주 틀리는 두 전이를 눈여겨보세요. S1에서 1이 또 들어오면 비트열은 11로 끝나고, 마지막 1은 여전히 시작 부분으로 쓸 수 있으므로 기계는 S1에 머뭅니다. S3에서 0이 들어오면 비트열은 1010으로 끝나는데, 그 접미사 10이 101의 앞부분과 일치하므로 S0이 아니라 S2로 갑니다. 이것이 중첩을 가능하게 합니다.
상태 할당과 식
상태가 4개이면 D 플립플롭 2개(Q1 Q0)로 충분합니다. 가장 직접적인 할당은 2진 할당입니다: S0 = 00, S1 = 01, S2 = 10, S3 = 11. D 플립플롭에서는 D = Q+이므로 여기표가 자명합니다.
| Q1 | Q0 | X | Q1+ = D1 | Q0+ = D0 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
간소화:
- D0은 정확히 X = 1인 행에서 1이므로 D0 = X입니다. 이치에 맞습니다. 이 할당에서 Q0 = 1은 "마지막 비트가 1이었다"를 뜻하기 때문입니다.
- 변수 순서를 Q1 Q0 X로 할 때 D1 = Σm(2, 5, 6)입니다. 최소항 2(010)와 6(110)은 인접하므로 Q0·X를 이룹니다. 5(101)는 1인 이웃이 없어 혼자 남습니다: Q1·Q0·X. D1 = Q0·X + Q1·Q0·X.
- 무어의 출력은 상태에만 의존합니다: Z = Q1·Q0.
완성된 회로는 D 플립플롭 2개, Z를 위한 2입력 AND 하나, 그리고 D1을 위한 2입력 AND 하나, 3입력 AND 하나, 2입력 OR 하나로 이루어집니다(여기에 Q0과 X의 인버터가 더해집니다).
테스트 시퀀스로 검증하기
S0에서 시작해 입력 X = 1 0 1 0 1 1 0 1을 넣습니다. 각 에지 뒤의 상태는 다음과 같습니다.
| 에지 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| X | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 상태 | S1 | S2 | S3 | S2 | S3 | S1 | S2 | S3 |
| Z | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
검출은 세 번 일어납니다. 비트 1~3, 3~5(중첩), 6~8입니다. 식으로 에지 4를 확인해 봅시다. 상태 S3 = 11이고 X = 0이면 D1 = 1·1 + 1·0·0 = 1, D0 = 0이므로 다음 상태는 10 = S2입니다. 일치합니다.
밀리 버전
밀리에서는 출력이 전이에 붙으므로 상태 S3이 필요 없습니다. 검출은 "S2에 있을 때 1이 들어오는 순간" 일어납니다. 세 상태 A(없음), B(마지막 비트 1), C(마지막 비트들 1, 0)를 사용하면:
| 상태 | X = 0 | X = 1 |
|---|---|---|
| A | A / 0 | B / 0 |
| B | C / 0 | B / 0 |
| C | A / 0 | B / 1 |
여전히 플립플롭 2개가 필요하지만, 출력 Z = 1은 마지막 1이 들어오는 바로 그 주기에 나타나므로 무어 버전보다 한 주기 빠릅니다.
흔한 실수
- "실패한" 전이를 시퀀스의 어느 부분이 아직 쓸모 있는지 확인하지 않고 모두 S0으로 보내는 것. 이렇게 하면 중첩된 검출을 놓칩니다.
- 무어 기계에서 출력을 화살표 위에 적거나, 밀리 기계에서 상태 안에 적는 것.
- 사용하지 않는 플립플롭 조합(예: 밀리 버전의 코드 11)을 잊는 것: 어디로 갈지 정하거나, X로 표시한 뒤 기계가 원래 순서로 돌아오는지 확인해야 합니다.
- 밀리 기계의 출력을 아무 때나 읽는 것: 입력이 이미 안정된 에지 직전에 샘플링해야 합니다.
- 기계를 시험할 때 클럭 에지 바로 그 순간에 입력 X를 바꾸는 것.
시뮬레이터에서 해 보기
식을 구하고 나면 검출기를 만드는 데는 몇 분이면 충분하며, 타이밍도로 각 전이를 확인할 수 있습니다.
- 같은 클럭을 쓰는 D 플립플롭 두 개를 놓고 출력에 Q1과 Q0이라는 이름을 붙입니다.
- 입력 X를 D0에 직접 연결합니다.
- 인버터 두 개, AND 두 개, OR 하나로 D1 = Q0·X + Q1·Q0·X를 만들어 D1에 연결합니다.
- Q1과 Q0의 AND를 Z용 표시등에 연결합니다.
- 1 0 1 0 1 1 0 1 순서에 따라 각 에지 전에 X를 바꾸고, 타이밍도에서 에지 3, 5, 8 뒤에 Z가 켜지는 것을 관찰합니다.
연습문제
- 중첩을 허용할 때 기계는 비트열 1010101에서 101을 몇 번 검출합니까?
정답
세 번입니다. 비트 1~3, 3~5, 5~7에서 검출합니다.
- 중첩을 허용하지 않는(검출 뒤에는 처음부터 다시 시작하는) 101 검출기의 무어 상태표를 다시 만드세요.
정답
S3 행만 바뀝니다. X = 0이면 S0으로, X = 1이면 S1로 갑니다. 나머지 행은 그대로입니다.
- 밀리 버전에서 A = 00, B = 01, C = 10으로 할당했을 때 Z를 구하세요.
정답
Z = 1은 상태 C에서 X = 1일 때뿐입니다: Z = Q1·Q0·X. 코드 11이 절대 나타나지 않는다면 X로 표시할 수 있고, 그러면 Z = Q1·X가 됩니다.
- 상태가 9개인 기계에는 플립플롭이 최소 몇 개 필요합니까?
정답
4개입니다. 23 = 8로는 부족하고 24 = 16이면 충분하기 때문입니다.
상태 레지스터를 이루는 플립플롭을 복습하려면 래치와 플립플롭을 참고하세요.