Karnaugh maps and don’t-care assumptions

진리표를 구현 비용으로 연결하기

진리표가 기능을 정의한다면 논리 최소화는 그 기능을 어떤 식으로 구현할지 결정하는 단계입니다. 입력이 세 개일 때 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가 결과에 영향을 줍니다. 이번 단계에서는 기능 등가성과 입력 가정을 확실히 하고, 물리적 비용은 합성·타이밍 결과로 판단합니다.

추가 읽기: Computation Structures — Combinational Logic