[Digital design] K-map(2), 주항과 필수주항

학부생의 입장에서 내용을 정리하였으며 피드백을 환영합니다.

 

---

 

 

K-map 예시

 2가지 예를 들겠다. 

가장 간략화된 수식은 항의 개수가 최소이고 각각의 항이 최소의 리터럴 수를 갖는 식을 의미한다.

1을 묶을 때 목적을 항상 생각해야한다.

 

1. 3변수 K-map

 

다음 불 함수를 간략화 해보겠다.

카르노 맵을 작성했다. 순서를 조심하자

1을 묶고 그것을 불 함수로 나타내면 된다.

 

2. 4변수 K-map

 

다음 불 함수를 간략화 해보자

카르노맵을 작성한다.

위의 카르노 맵을 보고 식을 작성하면

 

다음과 같이 불 함수를 간단하게 최적화 할 수 있다.

 

주항과 필수주항(PI, EPI)

1. 주항( prime implicant,PI)

맵 안의 인접한 네모 칸을 최대로 결합했을 때 얻어지는 곱의 항

이렇게 묶는 것은 우리가 지금까지 해오던 것이다. 1을 묶을 때 가장 크게 묶고 그 묶음의 수가 가장 적도록 하는 것이다.

가장 간략화된 수식은 항의 개수가 최소이고 각각의 항이 최소의 리터럴 수를 갖는 식을 의미한다.

이런 목표를 충족시키기 위함이다.

하지만 주항은 이런 목표를 신경쓰지 않고 최대한 크게 묶을 수 있는 모든 묶음을 찾는 것이다. 

다음과 같이 묶을 수 있다. 이를 토대로 주항을 찾으면 

다음과 같다. 주항은 곱의 항(product term)이므로 +를 하지 않는 것을 유의한다.

 

2. 필수주항(essential PI, EPI)

 어떤 최소항을 단 하나의 주항으로만 커버할 수 있을 때 이를 필수주항이라고 부른다.

필수주항을 찾았을 때 단 하나의 묶음에만 포함되는 1을 포함한 주항이라고 보면된다.

불 함수를 간략화 했을 때 무조건 들어가는 주항이다.

파란색으로 표시된 1은 단 한개의 묶음에만 포함되어있다. 이 묶음을 표시하면 

다음과 같이 되고 이 묶음이 곧 필수주항이 되는 것이다. 

 

EPI를 찾으면 모든 경우의 간략화 된 식을 찾을 수 있다.

 

 

주항과 필수주항을 이용한 간략화

EPI와 PI를 이용해 함수를 간략화 할 수 있다.

1. EPI를 구한다.

2. EPI에 묶이지 않은 1을 묶는다.

3. 그렇게 찾은 묶음과 EPI를 모두 더한다. 

말로 하면 복잡해보이지만 매우 간단하다.

 

다음 함수로 예를 들어 보겠다.

필수주항을 찾는 과정은 생략하도록 하겠다.

필수주항은 xz,x'z' 이다.

필수주항에 포함되지 않은 1을 묶는 주항을 찾아보면 

이렇게 4가지가 나오게되고 이중 포함되지 않은 1을 포함할 수 있는 조합을 찾으면 된다. 

1. wz, x'y

2. wz, yz

3. wx', x'y

4. wx', yz

이렇게 4가지 조합이 생긴다. 따라서 간략화된 식을 모두 쓰면

이렇게 간략화된 4가지 식을 얻을 수 있다.