식의 간소화 - 카르노맵

동일한 기능을 한다면 당연히 비용이 저렴한, 간단한 식을 원할 것이다.

따라서 다음과 같은 2가지 방법을 이용해서 식을 간소화 시켜야 한다.

1. 부울 대수의 성질 이용

2. 카르노 맵

우선 부울 대수의 성질을 이용해보자. 기본적으로는 다음과 같다.

그냥 넘어가기엔 좀 그러니 간단한 예제를 몇가지 들어보도록 하겠다.

 1) ab + b'c + ac

  = ab + b'c + a(b+b')c

  = ab + b'c + abc + ab'c

  = ab(1 + c) + b'c(1 + a)

  = ab + b'c

 2) (a' + b)(a' + c)(c + d)(b + d)

  = (a' + bc)(d + bc)

  = bc + a'd

등과 같이 식을 간소화시킬 수 있다.

가끔씩 product-of-sum을 sum-of-product로 바꾸라고 하는데 이건 우선 F'을 구해서 간소화시켜준 후 다시 F를 구해주는 방식으로 풀 수 있다. 

마찬가지로 예를 들어보자면

 1) a + bc' + d'e

  이 경우 우선 식에 not을 취해 F'을 구해준다.

  F' = a'(b' + c)(d + e')

  F'을 계산해서 중복식을 잘 걸러주면 다음과 같다.

  F' = a'b'd + a'b'e' + a'cd + a'ce'

  다시 not을 취해서 F를 구해주면 된다.

  F = (a + b + d)(a + b + e)(a + c' + d')(a + c' + e)

위와 같이 식으로 계산해서 풀기엔 역시 너무 힘들다.

게다가 진리표의 결과값이 0이나 1이 아닌 X가 등장할 때도 있다. 

예를 들자면 BCD code를 사용할 경우 0~9까지밖에 표현이 안되므로 10이 넘어가면 X로 표현해야 한다.

이러한 경우 식을 쓰는 것이 불가능하기에, 카르노 맵 이라는 방식을 사용한다.

카르노 맵은 X가 나와도 상관없는데 이를 don't care condition이라 한다.

우선 카르노맵에서 식을 뽑는 방법에는 2가지가 있다.

예상되다시피 sum-of-product와 product-of-sum이다.

다시 한번 예시로 설명하자면..

위와 같은 카르노맵이 있다 치자.

우선 sum-of-product는 인접한 1끼리 다 묶어준다. 이 때 제일 윗줄과 제일 아랫줄, 양 끝줄은 서로 인접한 상태라고 생각해야한다.

그림이 많이 조잡하지만..(식부터 짜서 예상치 못했다..) 위와 같은 형태가 나올 것이다.

이제 식을 뽑아내면 된다.

"묶었을 때 변하지 않는 변수값을 적어주면 된다."

즉, 파란 동그라미의 경우 위쪽 AB변수를 살펴보면 A'B' , A'B 이다. 

A'은 변하지 않으므로 적어주고 B는 변했으니 안적어준다. 

CD도 마찬가지로 해주면 A'D'이란 식을 뽑아낼 수 있다.

마찬가지로 주황 동그라미는 B'C'

초록 동그라미는 AB'D' 이다.

뽑아낸 식들을 sum해주기만 하면 된다.

F = A'D' + B'C' + AB'D'

그렇다면 이번엔 product-of-sum으로 만들어보겠다. 인접한 0끼리 묶어준다는 점만 유의하면 된다.

위와 같은 형태가 나올 것이다.

마찬가지로 식을 구해주되 0끼리 묶었으니 F가 아닌 F'임에 유의하자.

파란 동그라미는 BD

주황 동그라미는 AB

초록 동그라미는 CD 임을 알 수 있다.

뽑아낸 식들을 sum해주면

F' = BD + AB + CD

따라서 not을 취해주면 F = (B' + D')(A' + B')(C' + D') 가 된다.

그렇다면 위 두 식은 당연히 같을 것이다. 이번에도 LogicWorks로 확인해보자.

input값을 바꿔봐도 항상 0이 나오므로 같음을 알 수 있다.

카르노맵은 식으로도 나타낼 수 있다. 형태는 다음과 같다.

F(a, b, c, d) = ∑m(1, 2, 4, 6, 13, 14) + d(5, 9, 11, 12, 15)

m은 해당 값이 1임을 뜻하고 d는 don't care 즉 X를 뜻한다.

카르노 맵에서의 위치는 위 사진과 같다.

즉, 위 식은 다음 사진과 같은 식이 된다.

그렇다면 X가 있을 때는 어떻게 묶을까..

X는 자신이 원하는 숫자로 생각하면 된다.

묶기 좋게 1이 있다면 X를 1로 생각해서 함께 묶어도 되고, 마땅치 않다면 0으로 생각해서 버려도 된다.

위와 같이 묶어서 A'CD' + C'D + BD'라는 식으로 뽑아낼 수 있다.

그림 진짜 조잡하다..ㅠ 식이 많다 보니 오타가 있을 수 있어요..