카르노 맵 솔버 (K-Map 계산기)

카르노 맵으로 부울 함수 간소화하기

카르노 맵(K-Map)은 한 개의 변수만 다른 입력 조합이 서로 인접하도록 부울 함수를 배치합니다. 긴 논리식을 직접 비교하는 대신, 어떤 변수들이 그룹 안에서 변하고 어떤 변수들이 그대로 유지되는지 눈으로 확인할 수 있습니다.

이 solver는 2, 3, 4, 5변수 부울 함수를 지원합니다. 카르노 맵을 직접 클릭할 수도 있고, 진리표를 수정하거나 부울 표현식, 최소항, 최대항을 입력할 수도 있습니다.

각 입력 방식은 같은 함수를 나타냅니다. 한 곳에서 값을 바꾸면 다른 화면도 같은 부울 함수에 맞게 업데이트됩니다.

0, 1, X는 무엇을 뜻하나요?

각 K-Map 셀은 다음 값 중 하나를 가질 수 있습니다.

• 1 — 해당 입력 조합에서 함수가 참입니다.
• 0 — 해당 입력 조합에서 함수가 거짓입니다.
• X — 해당 조합의 출력값이 중요하지 않습니다.

X는 don't-care 조건입니다. 더 큰 그룹을 만들어 표현식을 줄이는 데 도움이 된다면 사용할 수 있지만, 반드시 그룹에 포함할 필요는 없습니다.

진리표에서 K-Map으로 변환하기

진리표는 가능한 모든 입력 조합과 각 조합의 출력을 행으로 보여 줍니다.

카르노 맵은 같은 데이터를 사용하지만 셀을 Gray code 순서로 배치합니다. 그래서 인접한 두 셀은 한 변수에서만 차이가 납니다.

예를 들어:

A'B'

A'B

에서는 B만 달라집니다.

두 항은 다음과 같이 간소화할 수 있습니다.

A'

그룹 안에서 값이 바뀌는 변수는 간소화된 항에서 사라집니다.

이 원리는 2개 셀뿐 아니라 4개, 8개, 16개 셀 그룹에도 적용됩니다.

최소항, 최대항, 부울 표현식 입력

문제에서 최소항 번호가 이미 주어졌다면 K-Map을 셀마다 채울 필요가 없습니다.

예:

Σm(1,3,5,7)

은 함수의 출력이 1인 최소항을 나타냅니다.

반대로:

ΠM(0,2,4,6)

은 출력이 0인 최대항을 나타냅니다.

부울 표현식을 직접 입력하는 방법도 있습니다.

Solver는 표현식을 평가하고 같은 함수에 해당하는 진리표, K-Map, 최소항, 최대항을 생성합니다.

덕분에 하나의 함수가 여러 형식으로 어떻게 표현되는지 한 화면에서 비교할 수 있습니다.

K-Map 그룹 규칙

유효한 그룹의 셀 수는 2의 거듭제곱이어야 합니다.

1, 2, 4, 8, 16

일반적으로 유효한 그룹이 클수록 결과 항에 남는 리터럴 수가 줄어듭니다.

카르노 맵의 반대쪽 가장자리도 논리적으로 인접합니다.

왼쪽 끝 셀은 오른쪽 끝 셀과 그룹을 만들 수 있고, 위쪽 끝과 아래쪽 끝도 같은 방식으로 연결됩니다.

따라서 네 모서리 셀도 하나의 그룹을 만들 수 있습니다.

필요하면 그룹은 서로 겹칠 수 있습니다. 같은 셀이 두 개 이상의 그룹에 포함되더라도 더 간단한 표현식을 만드는 데 필요하다면 올바른 그룹입니다.

Solver는 사용된 그룹을 K-Map 위에 표시해 최종 식과 쉽게 비교할 수 있도록 합니다.

SOP와 POS 비교

SOP (Sum of Products)는 주로 출력이 1인 셀을 기준으로 간소화합니다.

예:

A'B + BC

POS (Product of Sums)는 출력이 0인 셀에서 시작합니다.

예:

(A + B')(B + C)

SOP가 항상 더 짧은 것은 아닙니다.

어떤 함수는 SOP가 더 단순하고, 다른 함수는 POS가 더 적은 항이나 리터럴을 사용할 수 있습니다.

문제에서 특정 형식을 요구하지 않는다면 두 결과를 비교해 볼 수 있습니다.

Quine-McCluskey와 Petrick's Method

작은 카르노 맵에서는 좋은 그룹을 눈으로 찾기 쉽습니다.

하지만 4변수나 5변수 함수에서는 여러 개의 유효한 커버가 존재할 수 있습니다.

Solver는 Quine-McCluskey를 사용해 implicant를 체계적으로 찾습니다.

더 이상 확장할 수 없는 implicant를 prime implicant라고 합니다.

그중에는 다른 prime implicant가 커버할 수 없는 필수 최소항을 포함하는 항도 있습니다.

이런 필수 항을 선택한 뒤에도 여러 커버가 남으면 Petrick's Method를 이용해 가능한 조합을 비교합니다.

이는 K-Map만 보고 어떤 그룹 조합이 더 좋은지 판단하기 어려운 경우에 특히 유용합니다.

2~5변수 K-Map

2변수 K-Map은 4개의 셀로 구성됩니다.

3변수 K-Map은 8개의 셀을 가지며, 반대쪽 가장자리도 인접한다는 점을 확인하기 좋습니다.

4변수 카르노 맵은 16개의 셀을 가지며 디지털 논리 문제에서 자주 사용됩니다.

5변수 K-Map은 32개의 입력 조합을 표현합니다. prime implicant나 don't-care 조건이 많아지면 손으로 간소화하기가 더 어려워질 수 있습니다.

Solver는 모든 지원 크기에서 K-Map, 진리표, 표현식, 최소항, 최대항을 같은 함수로 동기화합니다.

논리 회로와 PDF 내보내기

간소화 결과는 식으로만 확인할 필요가 없습니다.

결과를 논리 회로로 표시해 SOP 또는 POS 식이 AND, OR, NOT 게이트와 어떻게 연결되는지 볼 수 있습니다.

항 수, 리터럴 수, 게이트 수 같은 정보도 함께 확인할 수 있습니다.

풀이를 나중에 다시 보고 싶다면 K-Map, 그룹, 풀이 단계, 회로를 포함한 PDF로 내보낼 수 있습니다.