2, 3, 4변수 카르노 맵과 무관 조건(X)

읽는 시간 7분 · bitGateLab 팀

부울 대수로도 간소화할 수 있지만, 어떤 법칙을 적용할지 "알아보는" 눈에 달려 있습니다. 카르노 맵은 그 탐색을 시각적인 작업으로 바꿔 줍니다. 진리표를 이웃한 칸끼리 변수 하나만 다르도록 격자에 배치하면, 간소화는 1을 묶는 일이 됩니다. 여기서는 2, 3, 4변수 맵을 만드는 법, ("반대편으로 이어지는" 가장자리를 포함해) 올바르게 묶는 법, 무관 조건을 활용하는 법을 배웁니다.

핵심 아이디어: 이웃한 칸은 변수 하나만 다르다

인접 법칙에 따르면 AB + AB = A입니다. 변수 하나만 다른 두 항은 하나로 합쳐지고 그 변수는 사라집니다. 카르노 맵은 한 변을 공유하는 칸의 쌍이 모두 이 조건을 만족하도록 최소항을 배치합니다. 이를 위해 행과 열의 머리글은 2진수 순서 00, 01, 10, 11이 아니라 그레이 코드 순서인 00, 01, 11, 10을 따릅니다. 연속한 두 값 사이에서는 비트 하나만 바뀌며, 마지막과 처음(10과 00) 사이에서도 마찬가지입니다. 그래서 맵은 마주 보는 가장자리끼리 붙어 있는 것처럼 동작합니다.

2변수와 3변수 맵

변수가 두 개인 맵은 칸이 4개이며, 행에 A, 열에 B를 둡니다. 변수가 세 개인 맵은 칸이 8개이며, 행에 A, 열에 BC를 그레이 코드 순서로 둡니다. 각 칸 안의 번호는 그 칸에 해당하는 최소항을 나타냅니다.

A \ BC	00	01	11	10
0	m0	m1	m3	m2
1	m4	m5	m7	m6

m3과 m2가 이 순서로 놓인다는 점에 주의하세요. 그레이 코드 때문이며, 맵을 손으로 채울 때 많은 실수가 여기서 나옵니다.

묶기 규칙

묶음에는 1(또는 뒤에서 볼 X)만 들어갈 수 있고, 0은 절대 들어갈 수 없습니다.
각 묶음의 크기는 2의 거듭제곱, 즉 1, 2, 4, 8, 16칸이어야 합니다.
묶음은 인접한 칸들로 이루어진 직사각형이며, 가장자리를 넘어가는 인접도 포함합니다. 대각선은 인접으로 치지 않습니다.
각 묶음은 가능한 한 크게 만듭니다. 2^k칸짜리 묶음은 변수 k개를 없앱니다.
모든 1을 덮는 최소 개수의 묶음을 사용합니다. 묶음끼리 겹쳐도 됩니다.

묶음을 읽으려면 변수를 하나씩 살펴봅니다. 묶음의 모든 칸에서 값이 같은 변수는 항에 나타나고(1이면 막대 없이, 0이면 막대를 붙여), 값이 바뀌는 변수는 사라집니다.

예제 1: 변수 세 개. F(A, B, C) = Σm(1, 3, 4, 5, 7)을 간소화하세요.

A \ BC	00	01	11	10
0	0	1	1	0
1	1	1	1	0

01열과 11열이 모두 채워져 있습니다: 4칸짜리 묶음(m1, m3, m5, m7). 이 묶음에서 A는 바뀌고, B도 바뀌며, C는 항상 1입니다. 항: C.
m4가 남습니다. m5(오른쪽 이웃)와 묶습니다: 두 칸 모두 A = 1, B = 0이고 C는 바뀝니다. 항: AB.
F = C + AB.

m6(110)으로 검산하면 C = 0이고 AB = 0이므로 F = 0이며, 맵과 같습니다.

4변수 맵과 가장자리 인접

변수가 네 개이면 맵의 칸은 16개이며, 행에 AB, 열에 CD를 모두 그레이 코드 순서로 둡니다.

AB \ CD	00	01	11	10
00	m0	m1	m3	m2
01	m4	m5	m7	m6
11	m12	m13	m15	m14
10	m8	m9	m11	m10

맨 왼쪽 열은 맨 오른쪽 열과 이웃하고, 맨 위 행은 맨 아래 행과 이웃합니다. 따라서 네 모서리(m0, m2, m8, m10)는 유효한 4칸짜리 묶음이 됩니다. 네 칸 모두 B = 0, D = 0이므로 BD로 읽습니다.

예제 2: 가장자리를 넘는 묶음. F(A, B, C, D) = Σm(0, 1, 2, 5, 8, 9, 10)을 간소화하세요.

AB \ CD	00	01	10
00	1	1	1
01	0	1	0
11	0	0	0
10	1	1	1

m0, m1, m8, m9: 맨 위 행과 맨 아래 행(가장자리로 이웃)의 00열과 01열입니다. B = 0이고 C = 0입니다. 항: BC.
m0, m2, m8, m10: 네 모서리입니다. 항: BD.
m5(0101)가 남습니다. 1이 들어 있는 가장 좋은 이웃은 m1(0001)입니다: A = 0, C = 0, D = 1이고 B가 바뀝니다. 항: ACD.
F = BC + BD + ACD.

리터럴 4개짜리 최소항 7개(리터럴 28개)가 항 3개, 리터럴 모두 7개로 줄었습니다.

무관 조건(X)

어떤 입력 조합은 절대 일어나지 않거나, 그때의 출력이 아무 영향을 주지 않는 경우가 있습니다. 예를 들어 BCD 숫자에는 1010부터 1111까지의 코드가 없습니다. 이런 행에는 X(don't care라고도 합니다)를 적고, 따로 d(...)로 표기합니다. 묶을 때 X는 더 큰 묶음을 만드는 데 도움이 되면 1로 취급하고, 그렇지 않으면 무시할 수 있습니다. X를 반드시 덮을 필요는 없습니다.

예제 3: 무관 조건이 있는 경우. F(A, B, C, D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5)를 간소화하세요.

AB \ CD	00	01	11	10
00	X	1	1	X
01	0	X	1	0
11	0	0	1	0
10	0	0	1	0

CD = 11열이 모두 채워져 있습니다(m3, m7, m15, m11): 항 CD.
m1이 남습니다. m0과 m2의 X를 1로 취급하면 맨 위 행 전체가 4칸짜리 묶음이 됩니다: 항 AB.
F = CD + AB.

똑같이 좋은 풀이가 하나 더 있습니다. m5의 X를 사용해 m1, m3, m5, m7을 묶으면 AD가 나옵니다. 그러면 F = CD + AD입니다. 두 풀이 모두 항 2개, 리터럴 4개이며, 의미가 있는 모든 행에서 결과가 일치합니다. 한 함수에 최소형이 둘 이상 있는 것은 흔한 일입니다.

X가 없다면 m1은 m3하고만 묶을 수 있어서 리터럴이 하나 더 많은 ABD가 됩니다. 무관 조건은 공짜로 얻는 절약이니 놓치지 마세요.

흔한 실수

머리글을 그레이 코드가 아니라 2진수 순서(00, 01, 10, 11)로 적는 것. 맵의 이웃이 더 이상 변수 하나 차이가 아니게 되어 묶음이 틀리게 나옵니다.
3칸이나 6칸짜리 묶음을 만드는 것. 2의 거듭제곱만 허용됩니다.
가장자리 인접과 네 모서리의 인접을 잊어서 묶음이 필요 이상으로 작아지는 것.
모든 칸이 이미 다른 묶음에 덮여 있는 묶음을 추가하는 것. 불필요하며 게이트만 늘어납니다.
X를 억지로 덮으려는 것. X는 묶음을 키울 때만 사용합니다.

시뮬레이터에서 해 보기

카르노 맵 모듈은 함수를 그레이 코드 순서로 배치하고, 묶음을 표시하고, 최소식을 적어 주므로 여러분이 묶은 결과를 도구가 제안하는 묶음과 비교할 수 있습니다.

변수가 네 개인 함수를 만들고 예제 2의 1을 입력합니다.
먼저 종이에 직접 묶어 보고 결과를 적습니다.
맵이 표시하는 묶음과 결과 식을 살펴봅니다. 여러분의 것과 다르면 어느 묶음이 최대가 아니었는지 확인합니다.
0, 2, 5번 칸을 X로 표시해 예제 3을 입력하고, 그 X를 없애면 간소화 결과가 어떻게 달라지는지 관찰합니다.
결과를 회로로 변환하고 입력을 바꿔 가며 진리표와 일치하는지 확인합니다.

연습문제

F(A, B, C) = Σm(0, 2, 4, 6)을 간소화하세요.
정답
BC = 00열과 BC = 10열은 가장자리로 이웃하며 모두 채워져 있습니다. 네 칸 모두 C = 0이므로 F = C입니다.
F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15)를 간소화하세요.
정답
모서리: BD. 가운데 블록 m5, m7, m13, m15: BD. F = BD + BD이며, B와 D의 XNOR입니다.
F(A, B, C, D) = Σm(4, 5, 6, 7, 12, 13, 14, 15)를 간소화하세요.
정답
AB = 01행과 AB = 11행이 8칸짜리 묶음을 이루며, B만 1로 유지됩니다. F = B.
BCD 숫자(A가 최상위 비트)가 5 이상일 때 출력이 켜져야 합니다. F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15)를 간소화하세요.
정답
X를 포함하면 AB = 11행과 AB = 10행이 8칸짜리 묶음을 이룹니다: A. 블록 m5, m7, m13, m15에서 BD가, 블록 m6, m7, m14, m15에서 BC가 나옵니다. F = A + BD + BC = A + B(C + D).

변수가 네다섯 개를 넘으면 맵을 읽기 어려워집니다. 그런 경우를 위한 표 형식의 절차가 퀸-매클러스키 방법입니다.