[Karnaugh Map] 3-variable
2012. 2. 16. 23:50
모양
2-variable 에서 확장하여 이번엔 3-variable Karnaugh map을 살펴보자.
아래쪽으로 길쭉한 형태인데, 이번엔 A, B 두개가 아니라 A, BC로 표현되어 있기 때문이다.
(AB, C라면 가로로 길쭉한 모양이 될 것이다. 어느쪽으로 긴지 짧은지는 큰 상관이 없다.)
BC로 표현되면서 0, 1이 아닌 00, 01, 11, 10이 각 행별로 쓰여져 있다.
각 행은 BC가 00, 01, 11, 10에 해당하는 숫자가 된다.
그림에서도 볼 수 있듯이 ABC = 001을 가리키고 있는 화살표를 살펴보면 BC = 01, A = 0 임을 볼 수 있다.
이러한 방식으로 truth table의 각 숫자들이 배치된다.
주의할 점은 00, 01, 11, 10이라는 숫자의 배치가 서로 뒤섞여서는 안된다는 것이다.
Karnaugh map의 가장 중요한 역할은 인접한 complement끼리 looping을 하는 것이다.
예를 들면 ABC, ABC'는 looping 되어 AB가 될 수 있는데,
그러기 위해서는 A, B는 같아야 하고, C만 다른 것이어야 한다.
따라서 00, 01, 11, 10의 순서를 잘 살펴보면 알 수 있듯이,
각 숫자의 사이사이는 B, C 둘 중 하나만 바뀌며, 두 숫자가 동시에 바뀌는 일이 없다.
다시 말해서 11 → 00 또는 00 → 11 또는 01 → 10 또는 10 → 01로 가는 경우는 없다.
만약 11과 00이 인접해 있도록 Karnaugh map을 만든 다음 그것들을 looping하게 되면,
그 looping은 별다른 의미가 없다. BC + B'C'는 더 이상 simplify 할 수 없기 때문이다.
물론 11, 10, 00, 01의 순서라든지 10, 00, 01, 11의 순서로 하는 것은 가능하다.
헷갈리지 않을 자신이 있다면 그렇게 써도 상관 없다.
다만 만약 대학교에서 시험을 치르게 된다면,
숫자를 바꾸는 것으로 불이익을 당하지 않을거라고는 장담 못한다.
Location of Minterms
Karnaugh map의 형태에 대한 이야기를 좀 더 확장시키기 위해서,
각 칸마다 minterm의 binary, decimal 값을 할당해 보았다.
먼저 (a)를 살펴보면, abc = 000, 001, ... 등으로 표시한 것이며, 화살표는 adjacency를 표현한 것이다.
앞서 2-variable Karnaugh map에서도 이야기 했듯이 인접한 0 또는 1은 looping이 가능하다.
(하나의 Karnaugh map에서 어떤 looping이 1에 대한 것이었다면 다른 looping도 전부 1에 대한 것이어야 한다.)
화살표로 연결되어있는 것들 끼리는 looping이 가능하다는 이야기이다.
특히 위 그림에서 100과 110의 경우도 looping이 된다.
어떠한 모양으로 looping이 되는지는 아래에서 보여주도록 하겠다.
결론적으로 이야기해서, 위에서도 언급이 되었지만
3개의 variable 중 2개는 같고 1개만 다른 minterm들 끼리는 looping이 된다.
위 Karnaugh map에서는 시각적으로 멀리 떨어져 있는 minterm들도 사실은 인접해 있는 것으로 보면 된다.
쉽게 생각해서, 지구 전체를 그려놓은 평면지도를 떠올리면 된다.
오른쪽 끝이 아메리카 대륙이고 그 끝을 벗어나면
세상의 끝을 벗어나게 되는 것이 아니라 다시 유럽 대륙이 나올 뿐이다.
(b) 그림의 decimal notation은 000 = 0, 111 = 7과 같이
단순히 3-variable을 그냥 2진수의 3자리 숫자라고 생각했을 때의 값을 적어둔 것이다.
이는 곧바로 minterm의 각 번호와 연결된다.
다시 말해서 m_0, m_1, ... 과 같은 minterm 표현 방식에서의 아래첨자들과 직접적인 연관을 갖는다.
1이 어디 있는지 찾는 것 만으로 곧바로 minterm expansion이 가능하게 되는 셈이다.
Product Terms on a Karnaugh Map
각각의 product term들이 어떻게 Karnaugh map에 배치되는지 봄으로써
Karnaugh map과 product term 사이의 괴리감을 줄여보도록 하자.
(a)
먼저 왼쪽부터 보면 'b' 라는 term은 Karnaugh map에서 아래쪽의 네개의 1로 표시된다.
우리는 이 1을 큰 둥근 사각형으로 looping할 수 있다.
각 term들은 각각 c, c', a, a' 를 내포하고 있으며, 공통적으로 b를 갖는다.
위아래의 1을 먼저 묶는다면 c와 c'를 먼저 묶게 될 것이고,
왼쪽과 오른쪽의 1을 먼저 묶는 다면 a와 a'를 먼저 묶게 된다.
이렇게 묶인 두개의 작은 looping은 다시 묶이는 것이 가능하다.
예를 들어 a'b와 ab로 묶였다면, 각각의 looping은 다시 b'와 b를 갖게 되므로, 다시 looping이 되는 것이다.
(b)
bc'는 우리가 전에 보아왔던 형태가 된다.
a'bc'와 abc'에 해당하는 minterm 두 개가 묶여있는 형태다.
이걸 보면, 만약 반대로 (b)와 같이 looping이 되어있을 때
그게 bc'인지 어떻게 바로 알 수 있는가 하는 의문이 들 것이다.
분석은 두가지로 가능하다. 하나는 각각의 minterm을 뽑아서 직접 expression을 simplify 하는 것이고
다른 하나는 그냥 looping을 보고 곧바로 답을 얻는 방법이다.
첫 번째 방법은 사실 Karnaugh map을 쓰는 의미가 없다. 그래서 두 번째 방법에 대해서만 설명한다.
두번째 방법은 looping의 위치를 잘 보면 된다. a, b, c의 3가지 variable을 차례로 살펴보면,
looping은 a와 a'와 같이 complement가 동시에 걸쳐있는것을 볼 수 있다.
이는 곧, looping의 product term에는 a가 포함되지 않음을 의미한다.
한편 b, c에 대해서는 동시에 걸쳐있는 complement가 없으므로,
옆의 bc = 10 을 통해서 최종적으로 bc' 라는 product term을 얻게 되는 것이다.
이러한 looping은 나중에는 한개가 아닌 여러개가 겹쳐 나오기 때문에,
looping을 보고 곧바로 product term과 연결짓는 연습을 할 필요가 있다.
(c)
이번엔 looping이 잘려있는 형태를 보이고 있다.
앞서 언급했듯이 인접해있는것 처럼 보이지 않지만 사실 인접한 minterm들이 있다.
그러한 minterm은 위 그림처럼 연결이 가능하다.
a=1, c=0인데 b, b' 의 complement를 동시에 포함하고 있다.
따라서 ac'의 그림임을 알 수 있다.
Simplification Example
f를 다음과 같이 정의했다고 하자.
f(a,b,c) = abc' + b'c + a'
위 식이 minimum solution인지 아닌지 살펴보려면,
이전에 배웠던 simplification skill을 이용할 수도 있겠지만, 여기서는 Karnaugh map을 이용해 보도록 하자.
먼저 abc', b'c, a'를 Karnaugh map위에 표시한다.
abc'는 곧 한개의 minterm이므로 looping을 할 수 없다.
하지만, Karnaugh map을 잘 보면,
abc' 역시 looping이 될 수 있는 위치에 있는데 looping되지 않고 있음을 알 수 있다.
이를 바로 왼쪽의 1과 looping하게 되면 bc'로 줄일 수 있게 된다.
결론적으로 f(a,b,c) = bc' + b'c + a' 로 줄이는 것이 가능하다.
Illustrating the Consensus Theorem
위 그림은 the consensus theorem이 어떻게 가능한지를 Karnaugh map을 통해 보여주고 있다.
간단히 이야기 해서 다른 loop을 통해서 이미 묶여진 minterm들은 또 다시 looping할 필요가 없다.
즉, yz라는 consensus term은 굳이 다시 looping할 필요가 없다
Function with Two Minimum Forms
위 그림은 두 가지의 looping을 보여주고 있는데, 결론적으로 두 식에는 별 차이가 없다.
어떤것이 맞고 틀리다의 문제가 아니라, 둘 다 맞는 표현이다.