카르노 맵 (K-Map) 솔버

카르노 맵(K-Map) 솔버는 2~5개 변수의 불 논리 함수를 최소화하고, 색상으로 구분된 그룹화가 포함된 클래식 K-map으로 간소화 과정을 시각화합니다. 최소항, 최대항을 입력하거나 대화형 진리표를 사용하세요. 솔버는 내부적으로 Quine-McCluskey 알고리즘을 실행하여 모든 주임시항을 찾고 필수 항목을 표시하며, 단계별 설명과 함께 최소화된 SOP(최소항의 합) 또는 POS(최대항의 곱) 식을 생성합니다. 주임시항 칩을 클릭하여 해당 셀을 강조 표시하고 그룹화가 논리를 어떻게 단순화하는지 확인해 보세요.

카르노 맵이란 무엇인가요?

카르노 맵(1953년 모리스 카르노 발명)은 진리표를 그래픽으로 표현한 것으로, 입력 변수가 하나만 다른 셀들이 물리적으로 인접하도록 배치됩니다. 핵심 비결은 행과 열의 그레이 코드(Gray-code) 순서 배치입니다. 00, 01, 11, 10과 같이 연속된 레이블은 정확히 한 비트만 다릅니다. 이러한 인접성을 통해 하나의 단순화된 항으로 결합될 수 있는 1(또는 0)의 그룹을 시각적으로 쉽게 찾을 수 있습니다.

n개의 입력 변수에 대해 K-map은 2^n개의 셀을 가집니다. 4변수 K-map은 16개 셀로 구성된 4×4 그리드이며, 5변수 맵은 두 개의 인접한 4×4 그리드로 그려집니다.

SOP vs POS: 어떤 형식을 선택해야 하나요?

최소항의 합 (SOP, Sum of Products)

SOP는 1-셀들을 그룹화합니다. 각 그룹은 리터럴의 곱(AND)이 되고, 모든 그룹은 서로 OR 연산됩니다. 예: AB'C + BD. SOP는 AND-OR 게이트 네트워크로 직접 매핑되기 때문에 보통 기본값으로 사용됩니다.

최대항의 곱 (POS, Product of Sums)

POS는 0-셀들을 그룹화합니다. 각 그룹은 보수 리터럴의 합(OR)이 되고, 모든 합은 서로 AND 연산됩니다. 예: (A + B')(C + D'). POS는 함수에 0보다 1이 더 많을 때 식의 크기가 더 작아지는 경우가 많습니다.

이 도구는 두 형식을 독립적으로 계산합니다. 출력 모드를 전환하여 리터럴 수를 비교하고 구현에 더 간단한 쪽을 선택하세요.

카르노 맵 그룹화 규칙

• 2의 거듭제곱 크기 그룹만 가능: 그룹은 1, 2, 4, 8 또는 16개의 셀을 포함해야 합니다. 3개나 5개 그룹은 허용되지 않습니다.
• 직사각형 모양: 그룹 내의 셀들은 직사각형 형태(가로, 세로 또는 모서리를 가로지름)를 이루어야 합니다.
• 순환 인접성(Wrap-around): 맨 윗행은 맨 아랫행과 인접하며, 맨 왼쪽 열은 맨 오른쪽 열과 인접합니다. 이것이 그레이 코드 순서가 중요한 이유입니다.
• 가장 큰 그룹부터: 그룹이 클수록 더 많은 변수가 제거되어 더 짧은 곱항이 생성됩니다. 8개 셀 그룹은 3개의 변수를 제거하고, 4개 셀 그룹은 2개, 2개 셀 그룹은 1개를 제거합니다.
• 모든 1은 반드시 포함되어야 함: 각 1-셀(SOP의 경우) 또는 0-셀(POS의 경우)은 적어도 하나의 그룹에 포함되어야 합니다.
• 중첩 허용: 더 큰 그룹을 만들 수 있다면 동일한 1이 여러 그룹에 포함될 수 있습니다.
• 무관항의 유연성: 무관항(Don't-cares)은 더 큰 그룹을 만드는 데 도움이 된다면 그룹화할 수 있지만, 반드시 포함될 필요는 없습니다.

주임시항과 필수 주임시항

주임시항(Prime Implicant)은 더 이상 확장할 수 없는 그룹입니다. 더 확장하면 0-셀을 포함하게 됩니다(SOP 기준). 솔버는 발견된 모든 주임시항을 나열합니다. 그런 다음 최소 커버(Minimal Cover)를 선택합니다. 즉, 필요한 모든 최소항을 덮는 가장 작은 주임시항 세트를 찾습니다.

필수 주임시항(Essential Prime Implicant)은 특정 최소항을 덮는 유일한 주임시항일 때 ESSENTIAL로 표시됩니다. 모든 최소 식에는 모든 필수 주임시항이 반드시 포함되어야 합니다. 필수 항목을 먼저 선택한 후, 남은 최소항들은 가장 효율적인 추가 주임시항들로 채워집니다.

무관항(Don't-Care) 조건

무관항(K-map에서 X로 표시)은 출력이 상관없는 입력 조합입니다. 실제 회로에서 절대 발생하지 않거나 값이 중요하지 않은 경우입니다. 알고리즘은 각 X를 0 또는 1 중 더 간단한 식을 만드는 쪽으로 자유롭게 처리합니다. 실제 사례에서 무관항은 종종 리터럴 수를 30~60% 줄여줍니다. 흔한 예로, 16개의 4비트 조합 중 10개만 사용하는 10진수 디코더에서 나머지 10~15번 조합은 무관항이 됩니다.

Quine-McCluskey 알고리즘

K-map은 시각적인 방법이지만 4~5개 이상의 변수에는 부적합합니다. Quine-McCluskey (QM) 알고리즘은 수학적으로 엄격하고 확장 가능한 표 형태의 대응 방식입니다. 이 솔버는 내부적으로 QM을 사용합니다:

1. 최소항을 이진수로 나열하고 1의 개수에 따라 그룹화합니다.
2. 인접 그룹 간의 쌍을 결합합니다(한 비트만 다른 경우). 다른 비트는 대시(-)로 바꿉니다. 예: 0011 + 0111 → 0-11.
3. 더 이상 결합이 불가능할 때까지 반복합니다. 결합되지 않은 항들이 주임시항입니다.
4. 주임시항 차트를 작성합니다. 행은 주임시항, 열은 필요한 최소항입니다. 필수 주임시항(체크 표시가 하나만 있는 열)을 식별합니다.
5. Petrick 방법 / 전수 조사: 남은 최소항들에 대해 이를 덮는 가장 작은 추가 주임시항 세트를 찾습니다.

이 계산기 사용 방법

1. 변수 개수 선택: 2, 3, 4 또는 5. K-map 그리드가 자동으로 조정됩니다.
2. 입력 방식 선택:
   • 최소항 (Minterms): F = 1인 인덱스(예: 1, 3, 5, 7)와 무관항을 입력합니다.
   • 최대항 (Maxterms): F = 0인 인덱스를 입력합니다. 솔버가 나머지를 자동으로 1로 계산합니다.
   • 진리표 (Truth Table): 각 행을 클릭하여 출력을 0, 1, X 사이에서 순환시킵니다. 수동 논리 설계에 최적입니다.
3. SOP 또는 POS 출력 선택. 전환을 통해 두 형식을 비교해 보세요. 보통 한쪽이 더 짧습니다.
4. 풀기(Solve) 클릭. 각 주임시항이 고유한 색상으로 표시된 K-map이 나타납니다. 칩을 클릭하여 해당 셀을 확인하세요.
5. 단계 확인: Quine-McCluskey 분석을 통해 각 주임시항이 어떻게 도출되었고 어떤 것이 필수인지 확인하세요.

실전 예제: 무관항을 포함한 4-변수 함수

F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5)를 생각해 봅시다.

무관항이 없다면 최소 SOP에는 여러 항이 필요합니다. 하지만 {0, 2}를 1로 취급하면 솔버가 4개 셀 그룹인 A'B'(0, 1, 2, 3 포함)를 만들 수 있습니다. 5를 1로 취급하면 CD 커버리지를 확장할 수 있습니다. 결과적인 간소화 식은 다음과 같습니다:

무관항 트릭이 없었다면 10개 이상의 리터럴이 필요했겠지만, 단 4개의 리터럴로 줄었습니다. 위의 "4-변수 무관항 포함" 퀵 예제를 클릭하여 이 예시를 바로 로드할 수 있습니다.

불 함수를 최소화해야 하는 이유

• 게이트 수 감소 = 하드웨어 비용 절감, 칩 면적 축소, 전력 소비 감소.
• 회로 속도 향상: 임계 경로의 게이트 지연이 줄어듭니다.
• 명확한 문서화: 간결한 식은 검증과 유지보수가 더 쉽습니다.
• 디지털 설계의 기초: 모든 FPGA 합성 도구는 Quine-McCluskey의 후손(Espresso-II 등) 알고리즘을 실행합니다.

제한 사항 및 다른 도구 사용 시점

• 5개 초과 변수: K-map은 시각적으로 너무 복잡해집니다. 이 도구는 4×4 맵 두 개로 나누어 5개까지 지원합니다. 그 이상은 Quine-McCluskey 단계를 참고하거나 ABC / Espresso 같은 합성 도구를 사용하세요.
• 해저드(Hazards) 및 글리치: 최소 커버에는 정적 해저드가 포함될 수 있습니다. 해저드가 없는 설계를 위해서는 중복 주임시항을 포함해야 합니다. 이 도구는 이를 표시하지만 자동으로 추가하지는 않습니다.
• 다중 출력 최소화: 여러 함수가 변수를 공유하는 경우 공동 최소화(게이트 공유)가 하드웨어를 더 줄일 수 있습니다. 이 도구는 한 번에 하나의 함수만 최소화합니다.

자주 묻는 질문

카르노 맵이란 무엇인가요?

카르노 맵(K-map)은 불 대수식을 시각적으로 간소화하는 방법입니다. 인접한 셀이 단 하나의 변수만 다르도록 배열됩니다(그레이 코드 순서). 1, 2, 4, 8 또는 16 크기의 직사각형으로 1들을 그룹화하면 최소화된 SOP 식을 얻을 수 있습니다.

SOP와 POS의 차이점은 무엇인가요?

SOP(Sum of Products, 최소항의 합)는 1-셀을 그룹화하고 그 곱항들을 OR 연산합니다(예: A'B + CD). POS(Product of Sums, 최대항의 곱)는 0-셀을 그룹화하고 그 합항들을 AND 연산합니다(예: (A + B')(C' + D)). 둘 다 동일한 함수를 설명하지만 보통 한쪽 형식이 더 간결합니다.

무관항(Don't-cares)이란 무엇이며 왜 사용하나요?

무관항(X로 표시)은 출력값이 상관없는 입력 조합입니다. 실제 발생하지 않거나 값이 중요하지 않은 경우입니다. 솔버는 식을 더 간단하게 만들 수 있는 방향으로 이를 0 또는 1로 취급합니다. 무관항은 종종 리터럴 수를 획기적으로 줄여줍니다.

주임시항(Prime Implicant)이란 무엇인가요?

주임시항은 더 이상 확장할 수 없는 가장 큰 인접 1-셀 그룹(2의 거듭제곱 크기)입니다. 필수 주임시항은 적어도 하나의 최소항을 유일하게 포함하는 항으로, 모든 최소 식에 반드시 포함되어야 합니다.

Quine-McCluskey 알고리즘은 어떻게 작동하나요?

Quine-McCluskey는 많은 변수에 적합한 K-map의 표 형태 방식입니다. 모든 최소항을 이진수로 나열하고, 1의 개수에 따라 그룹화한 뒤, 정확히 한 비트만 다른 쌍을 반복적으로 결합합니다. 더 이상 결합할 수 없는 항이 주임시항이 되며, 주임시항 차트를 통해 최소 커버를 선택합니다.

이 K-map 솔버는 몇 개의 변수까지 지원하나요?

이 도구는 2개에서 5개까지의 변수를 지원합니다. 5변수 K-map은 두 개의 인접한 4x4 맵(A=0 하나, A=1 하나)으로 표시됩니다. 5변수를 넘어가면 K-map은 비실용적이므로 더 큰 함수에는 Quine-McCluskey 단계를 사용하세요.

더 읽어보기

• 카르노 맵 — 위키백과 (영문)
• Quine-McCluskey 알고리즘 — 위키백과 (영문)
• Petrick 방법 — 위키백과 (영문)