카르노 맵과 don’t-care의 조건

진리표에서 구현 방법 찾기

진리표^{i진리표 가능한 입력 조합을 빠짐없이 나열하고 각 조합의 출력을 적은 표입니다. 시간에 따른 변화는 파형으로 따로 확인합니다. 자세히 보기}가 기능을 정의한다면 논리 최소화는 그 기능을 어떤 식으로 구현할지 결정하는 단계입니다. 입력이 세 개일 때 minterm 번호는 A를 최상위 비트로 놓은 이진수 ABC로 정의하겠습니다.

예를 들어 minterm 4는 ABC=100입니다. 나열되지 않은 0, 2, 6에서는 출력이 0입니다. 다섯 개의 곱 항을 모두 사용하는 대신, 한 비트만 다른 항들을 묶어 그 비트를 식에서 없앨 수 있습니다.

카르노 맵은 순서가 다른 진리표입니다

열을 BC=00, 01, 11, 10 순서로 배치합니다. 이 순서는 인접한 열 사이에서 한 비트만 바뀌는 그레이 코드 순서입니다. 맨 왼쪽과 맨 오른쪽도 인접합니다.

묶음은 직사각형으로 만들고 셀 수는 $1,2,4,8,\ldots$이어야 합니다. 0인 셀을 포함하면 기능이 달라집니다. 같은 1을 여러 묶음에 포함하는 것은 허용됩니다.

1. C=1인 두 열의 네 셀을 묶으면 A와 B가 변해도 출력이 1입니다. 남는 항은 C입니다.
2. A=1인 행의 BC=00과 01을 묶으면 C만 변합니다. 남는 항은 $A\overline B$입니다.
3. 두 묶음을 OR로 합치면 모든 1을 덮고 모든 0을 피합니다.

8개 입력 조합에서 원래 정의와 최소화한 식의 출력이 같은지 확인하세요. 식이 짧아졌다는 사실과 기능이 같다는 사실을 별도로 확인하는 습관이 중요합니다.

아래 그림은 위 카르노 맵의 두 묶음을 식으로 옮기는 과정을 보여 줍니다. C 묶음에서는 A와 B가, 두 셀 묶음에서는 C가 변하므로 그 변수를 항에서 제거합니다.

don’t-care로 최적화할 때는 입력 조건이 필요합니다

시스템에서 ABC=000이 절대 들어오지 않는다고 가정해 봅시다. 그 한 셀을 X로 놓으면 필요에 따라 0 또는 1로 사용할 수 있습니다. B=0인 네 셀을 묶어 더 단순한 식을 얻습니다.

새 식은 ABC=000에서 1입니다. 기존의 완전한 진리표와는 다릅니다. 따라서 ‘같은 회로’라고 말하려면 입력이 000이 아니라는 조건을 포함해야 합니다. 초기화 중이나 오류 복구 중에 000이 나타날 수 있다면 이 최적화는 시스템 요구사항을 충족하지 못할 수 있습니다.

식의 최소화와 칩의 최소화는 다릅니다

리터럴 수가 적은 식이 특정 표준 셀 라이브러리에서 면적·지연·전력까지 항상 최적인 것은 아닙니다. 부하, fan-out, 사용 가능한 복합 게이트, 배선, glitch가 결과에 영향을 줍니다. 이번 단계에서는 두 식의 기능이 같은지, 어떤 입력 조건을 가정했는지 확인하고, 물리적 비용은 합성·타이밍 결과로 판단합니다.

추가 읽기: MIT OpenCourseWare — Combinational Logic

실습 · 묶음의 겹침과 don’t-care의 조건 확인하기

1. C 묶음을 누릅니다. 네 셀 안에서 A와 B가 모두 변하므로 C만 남습니다.
2. A·¬B 묶음을 누릅니다. m4와 m5를 덮고, m5는 C 묶음과 겹칩니다. 겹침은 허용되지만 0인 셀을 포함하는 것은 허용되지 않습니다.
3. m0을 두 번 눌러 0 → 1 → X로 바꿉니다. X로 바꾸면 d(0)을 포함한 불완전 명세가 됩니다. B=0인 셀을 더 큰 묶음으로 합칠 수 있어 식은 $C+\overline B$가 됩니다.
4. m0을 한 번 더 눌러 0으로 되돌립니다. m0의 출력을 다시 0으로 지정했으므로 더 큰 묶음은 사라져야 합니다.

묶음을 선택해도 셀의 값은 바뀌지 않습니다. 모든 1을 덮는 전체 식은 유지되고 지금 살펴보는 항 하나만 테두리로 강조됩니다. 여기서는 곱 항 수가 가장 적은 식을 찾고, 그 수가 같으면 리터럴 수가 가장 적은 식을 찾습니다. 이런 식이 여러 개면 한 가지만 보여 줍니다.