배우기 › 주제 5
퀸-매클러스키 방법 단계별 풀이
읽는 시간 7분 · bitGateLab 팀
카르노 맵은 변수가 네 개일 때는 빠르지만, 눈에 의존하며 다섯 개 이상에서는 실용적이지 않습니다. 퀸-매클러스키 방법은 같은 일을 표와 기계적인 규칙으로 해냅니다. 직관이 필요 없고, 언제나 모든 주항을 찾아내며, 논리 함수를 간소화하는 프로그램의 바탕이 됩니다. 여기서는 이 방법의 두 단계를 이해하고, 필수 주항을 가려내며, 변수가 네 개인 예제를 처음부터 끝까지 풀어 봅니다.
용어: 내포항과 주항
- F의 내포항은 그 값이 1이면 F도 반드시 1이 되는 곱 항입니다. F의 최소항은 모두 내포항이며, 카르노 맵의 유효한 묶음도 모두 내포항입니다.
- 주항은 더 이상 키울 수 없는 내포항입니다. 변수를 하나 빼면 F가 0인 행을 덮게 됩니다. 맵에서 최대 크기의 묶음에 해당합니다.
- 필수 주항은 다른 어떤 주항도 덮지 않는 최소항을 하나 이상 덮는 주항입니다. 어떤 최소 해에도 반드시 들어가야 합니다.
이 방법은 두 단계로 이루어집니다. 먼저 항을 결합해 모든 주항을 찾고, 그다음 모든 최소항을 덮는 가장 작은 주항 집합을 고릅니다.
1단계: 항 결합하기
각 항은 2진수로 적고, 소거된 변수의 자리는 대시로 표시합니다. 예를 들어 변수가 A, B, C, D일 때 항 0-11은 ACD를 뜻합니다(B가 소거됨).
- 최소항을 2진 코드에 들어 있는 1의 개수에 따라 그룹으로 나눕니다.
- 한 그룹의 각 항을 다음 그룹의 각 항과 비교합니다. 비트 하나만 다르면 그 자리에 대시를 넣어 결합하고, 원래의 두 항에는 사용했다는 표시를 합니다.
- 새 목록으로 같은 과정을 반복합니다. 대시가 같은 자리에 있는 항끼리만 결합할 수 있습니다.
- 더 이상 결합할 것이 없을 때, 한 번도 표시되지 않은 항들이 주항입니다.
2단계: 주항표
주항마다 한 행, 함수의 최소항마다 한 열을 두어 표를 만듭니다(무관 조건에는 열을 두지 않습니다). 각 주항이 어떤 최소항을 덮는지 표시합니다. 그런 다음:
- 표시가 하나뿐인 열을 찾습니다. 그 행의 주항이 필수 주항입니다. 그 주항을 선택하고 그것이 덮는 열을 모두 지웁니다.
- 남은 열에 대해서는 그 열들을 덮는 가장 적은 수의 주항을 고릅니다. 두 주항이 같은 것을 덮는다면 어느 쪽이든 괜찮지만, 리터럴이 적은 쪽을 고르세요.
전체 풀이 예제. F(A, B, C, D) = Σm(0, 2, 3, 5, 7, 8, 10, 11, 13, 15)를 간소화하세요.
순서 1. 1의 개수로 그룹 나누기.
| 1의 개수 | 최소항 |
|---|---|
| 0 | 0 (0000) |
| 1 | 2 (0010), 8 (1000) |
| 2 | 3 (0011), 5 (0101), 10 (1010) |
| 3 | 7 (0111), 11 (1011), 13 (1101) |
| 4 | 15 (1111) |
순서 2. 첫 번째 결합(쌍). 이웃한 그룹끼리 비교합니다. 8은 3이나 5와 비트가 둘 이상 다르므로 결합되지 않습니다.
| 그룹 | 만들어진 쌍 |
|---|---|
| 0과 1 | (0,2) 00-0; (0,8) -000 |
| 1과 2 | (2,3) 001-; (2,10) -010; (8,10) 10-0 |
| 2와 3 | (3,7) 0-11; (3,11) -011; (5,7) 01-1; (5,13) -101; (10,11) 101- |
| 3과 4 | (7,15) -111; (11,15) 1-11; (13,15) 11-1 |
최소항 열 개가 모두 사용된 것으로 표시되었고, 쌍은 13개입니다.
순서 3. 두 번째 결합(네 개 묶음). 대시가 같은 자리에 있고 비트 하나만 다른 쌍끼리 결합합니다.
- (0,2)와 (8,10), 또는 (0,8)과 (2,10): -0-0, 0, 2, 8, 10을 덮습니다.
- (2,3)과 (10,11), 또는 (2,10)과 (3,11): -01-, 2, 3, 10, 11을 덮습니다.
- (3,7)과 (11,15), 또는 (3,11)과 (7,15): --11, 3, 7, 11, 15를 덮습니다.
- (5,7)과 (13,15), 또는 (5,13)과 (7,15): -1-1, 5, 7, 13, 15를 덮습니다.
쌍 13개가 모두 어느 네 개 묶음엔가 사용되었습니다. 네 개 묶음 넷은 더 이상 서로 결합되지 않습니다(대시가 같은 자리에 있으면서 비트 하나만 다른 것이 없습니다). 따라서 주항은 다음과 같습니다.
- P1 = -0-0 = BD
- P2 = -01- = BC
- P3 = --11 = CD
- P4 = -1-1 = BD
순서 4. 주항표.
| 주항 | 0 | 2 | 3 | 5 | 7 | 8 | 10 | 11 | 13 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|
| P1 BD | ✔ | ✔ | ✔ | ✔ | ||||||
| P2 BC | ✔ | ✔ | ✔ | ✔ | ||||||
| P3 CD | ✔ | ✔ | ✔ | ✔ | ||||||
| P4 BD | ✔ | ✔ | ✔ | ✔ |
순서 5. 필수 주항. 0열과 8열은 P1에만 표시가 있으므로 P1은 필수입니다. 5열과 13열은 P4에만 표시가 있으므로 P4도 필수입니다. 둘이 함께 0, 2, 5, 7, 8, 10, 13, 15를 덮습니다.
순서 6. 나머지 덮기. 최소항 3과 11이 남았습니다. P2가 둘 다 덮고, P3도 둘 다 덮습니다. 둘 중 어느 것을 골라도 같은 수의 리터럴로 해가 완성됩니다.
결과: F = BD + BD + BC, 또는 F = BD + BD + CD. 둘 다 항 세 개, 리터럴 여섯 개입니다.
이 함수를 카르노 맵에 그려 보면 P1은 네 모서리, P4는 가운데 블록, P2는 11열과 10열에서 00행과 10행에 해당하는 칸(가장자리로 이어짐), P3은 11열 전체입니다. 표를 쓰는 이 방법은 맵을 보지 않고도 같은 결과에 도달합니다.
무관 조건과 순환 표
무관 조건(X)은 더 큰 내포항을 만드는 데 도움이 될 수 있으므로 1단계에서는 1인 것처럼 포함합니다. 2단계에서는 뺍니다. 반드시 덮어야 하는 것이 아니므로 열을 두지 않습니다. X로만 이루어진 주항은 전혀 필요하지 않습니다.
때로는 필수 주항을 고른 뒤에, 또는 처음부터 모든 열에 표시가 둘 이상 있어서 무엇을 골라야 할지 분명하지 않을 때가 있습니다. 이런 상황을 순환 표라고 합니다. 이때는 시도해 보며 풉니다. 주항 하나를 고르고, 그것이 덮는 것을 지우고, 이를 반복하면서 나오는 해들을 비교합니다. 큰 표에는 가능한 모든 덮개를 열거하는 대수적 절차(페트릭 방법)가 있습니다.
흔한 실수
- 0-01과 00-1처럼 대시의 자리가 다른 항을 결합하는 것. 비트 하나만 다른 것처럼 보여도 유효하지 않습니다.
- 결합할 때마다 두 항에 사용 표시를 하는 것을 잊고, 나중에 주항이 아닌 것을 주항으로 나열하는 것.
- 주항표에 무관 조건(X)의 열을 넣어서 불필요하게 덮어야 하게 만드는 것.
- 필수 주항보다 필수가 아닌 주항을 먼저 고르는 것. 먼저 필수 주항을 확보한 다음 나머지를 결정하세요.
- 코드에서 항을 잘못 옮겨 적는 것: -0-1에서 B는 부정되고(값이 0), D는 부정되지 않으며(값이 1), A와 C는 사라집니다.
시뮬레이터에서 해 보기
시뮬레이터는 이런 종류의 절차로 함수를 간소화하므로, 손으로 한 작업의 각 단계를 확인하는 데 쓸 수 있습니다.
- 변수가 네 개인 진리표를 만들고 예제의 최소항을 1로 표시합니다.
- 1단계와 2단계를 종이에 풀고 결과를 적습니다.
- 도구가 내놓는 최소식과 그 카르노 맵을 살펴보고, 각 주항에 해당하는 묶음이 어느 것인지 찾아봅니다.
- 가능한 두 해를 같은 캔버스에서 회로로 변환하고, 입력을 바꿔 가며 항상 같은 출력을 내는지 확인합니다.
연습문제
- F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 11, 15)의 주항과 최소식을 구하세요.
정답
주항: -00- (BC), -0-1 (BD), --11 (CD). 0열은 BC만 덮고, 7열은 CD만 덮습니다. 둘 다 필수이며 함께 전체를 덮습니다. F = BC + CD. 주항 BD는 필요 없습니다.
- F(A, B, C) = Σm(0, 1, 2, 5, 6, 7)을 푸세요. 필수 주항이 있습니까?
정답
쌍은 00-, 0-0, -01, -10, 1-1, 11-이며 어느 것도 네 개 묶음으로 결합되지 않습니다. 주항은 여섯 개입니다. 각 최소항을 정확히 두 주항이 덮으므로 필수 주항은 없습니다(순환 표). 최소 해는 두 가지입니다: AB + BC + AC, 또는 AC + BC + AB.
- F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15)를 간소화하세요.
정답
1단계에 X를 포함하면 주항 네 개가 나옵니다: -0-1 (BD), -01- (BC), --11 (CD), 1--1 (AD). 1, 10, 15의 열이 없는 표에서 2는 BC만, 7은 CD만, 13은 AD만 덮습니다. 셋 모두 필수이며 3, 9, 11도 덮습니다. F = BC + CD + AD.
- 1단계에서 1이 하나인 그룹과 1이 세 개인 그룹을 비교하지 않는 이유는 무엇입니까?
정답
1이 하나인 코드와 세 개인 코드는 적어도 두 비트가 다른데, 결합하려면 정확히 한 비트만 달라야 하기 때문입니다.