[Karnaugh Map] 2-variable

유용성

지금까지의 simplification 방법은 물론 유용하긴 하지만 일반적으로 적용하기 어려운 것이 사실이다.
좀 더 간단하게 simplify하기 위한 방법 중 하나가 Karnaugh map이다.
Variable이 2~5개 정도인 expression이나 equation에 대해서 상당히 유용한 방법이다.
해야할 일은 Karnaugh map을 만들고, 'looping' 과정을 통해서 minimum solution을 얻는 것이다.
그 과정이 몇 줄에 걸쳐서 식을 쓰는 것에 비해 비교적 간단하기 때문에 자주 사용되며,
Boolean algebra를 이용해 얻은 식이 minimum solution인지 확인하는데 쓰이기도 한다.

모양

위 그림은 2개의 variable에 대해 Karnaugh map의 틀을 그려놓은 것이다.
사각형의 표 왼쪽 위에 A, B가 표시되어 있는데, 이는 식에 사용된 variable들을 적어 놓은 것이다.
위 그림에서 A는 행(가로축)에, B는 열(세로축)에 할당되어 있다.
A와 B는 binary이므로 0 또는 1 의 값만 가진다.
각 축 머리에는 0과 1을 표시함으로써 최종적으로는 4개의 빈 칸이 생성된다.
가로 축과 세로 축의 0, 1의 표시는 각각의 variable에 해당하는 값들이다. 
사각형의 각 칸은 위에서 표시한 것과 같이, 각 A, B에 대해 어떤 특정한 값을 갖는다.

0과 1의 위치를 서로 바꾸어 쓰는 것이 큰 문제가 되는 것은 아니지만
특별한 이유가 없는 이상 일반적으로 위와 같이 쓰도록 한다.
Karnaugh map은 이 사각형의 빈 칸에 0 또는 1을 채워넣음으로써 그 진가를 발휘하기 시작한다.

Looping

차례로 살펴보면, (a)는 간단한 2-variable truth table이다. 4가지의 경우에 대해서 F값이 설정되어있다.
이 truth table을 보면서 Karnaugh map의 빈 칸에 해당하는 값들을 하나하나 채워넣는다.
A=0, B=0 일때 F=1 이므로, 상단 왼쪽에 1을 채워 넣는다. 나머지 값들에 대해서도 같은 방법으로 채운다.
그러면 (b)와 같은 그림이 완성된다. 
F를 기존에 우리가 알던 방법으로 표현해 보면 (c)그림에서 보는 것과 같이 된다.
각각은 minterm인 A'B', A'B에 해당하는 것이다.

이제 Karnaugh map을 만든 최종적인 이유가 되는 looping을 할 차례다.
Looping은 인접해 있는 같은 숫자을 묶는 것이다. (d)번이 looping의 형태를 보여주고 있다.
(이것이 정확한 표현은 아니지만, 아직 여기서는 이 정도로만 설명해 둔다.)
인접한 B와 B'가 묶여서 곧 A'B' + A'B = A' 가 됨을 보여주고 있다.

즉, 공식을 이리저리 굴려가면서 simplification을 하던 이전 방법에서 벗어나
좀 더 간단하게 simplification을 수행하고 있는 모습이다.
여기서 A'B' + A'B 라는 식을 굳이 쓸 필요가 없이, 위의 모양처럼 loop가 A = 0 부분에 걸쳐져 그려져 있기 때문에,
그냥 F = A' 라는 식이 곧바로 튀어나올 수 있게 된다. 이것이 Karnaugh map을 쓰는 이유가 된다.

1을 묶는 것 뿐 아니라 0끼리 묶는 것도 가능한데,
이 경우에는 F 대신 F'를 묶는 것이라고 봐야 하며,
이 때는 sum-of-products가 아니라 product-of-sums로 나타내야 하는데,
이 부분에 대해서는 이후에 자세히 설명하도록 하겠다.

어쩐지 별로 유용해 보이지 않는것 같은 느낌이 드는 것은
사실 2-variable의 Karnaugh map은 가능한 looping의 방법이 매우 한정적이고,
또 Karnaugh map을 쓸 만큼 식이 복잡해 질 수도 없기 때문이다.
여기서는 대략 '이런 방법을 통해서 simplification이 가능하다'는 정도만 알고 넘어가면 될 것 같다.
Looping의 자세한 내용은 다음 포스트에서 다루기로 하겠다.