지난 시간에 최소항, 최대항을 살펴보고 카노맵과 연관 관계를 설명하였다.
최소항, 최대항에 대한 자세한 이해보다 카노맵과 연관지어 카노맵을 푸는 전략적인 방법 중심으로 설명하겠다.
2015/05/22 - [컴퓨터구조] - 최소항과 최대항, 카르노맵(카노맵)
다시 간단하게 최소항은 입력단의 논리곱의 조합을, 최대항은 입력단의 논리합의 조합을 나타낸다고 설명했다.
이 최소항, 최대항의 가지 수는 부울 함수의 변수의 가지 수에 따라서 정해져 있고, 이 항들을 맵으로 만든 것이 카노맵이다.
각각의 최소항 또는 최대항(최소항의 보수)은 카노맵에서 항이라고 부른다.(이부분은 필수주항 파트에서 다룰 것이다.)
2개의 변수 X,Y를 갖는 카노맵의 기본개념을 나타낸다. m은최소항을 뜻하고 첨자의 숫자는 최소항 비트조합의 10진수에 대응되는 값을 나타낸다. (부연설명 : 최소항 XY는 11 이므로 m3임)
예> X'Y + XY' + XY 를 위 카노맵을 이용하여 구해보자.
위 처럼 표현된다.
이는 아래와 같이 묶을 수 있다.
묶여진 항은 각각 X, Y로 표현될 수 있고 이는 합으로 연결된다. (곱의 합 꼴)
X + Y
부연설명 하면 위 함수는 m1+m2+m3 Y=1인경우 m1+m2는 1이되고 X=1인경우 m2+m3는 1이된다.
또, Y=0인경우 m1+m2는 0이되고 X=0인경우 m2+m3는 0이 된다.
이처럼 m1+m2는 Y로 나타낼 수 있고, m2+m3는 X로 나타낼 수 있다.
이 둘의 합은 m1+m2+m2+m3가 되고, m2+m2는 m2 로 표현될 수 있다.(부울 함수기 때문)
결국 카노맵에 의해서 곱의 합 꼴로 바꿀 수 있다.
묶는 방법은 저번 시간에도 간략히 설명햇지만, 최대한 많이 묶어야 한다.
묶는 방법에는 1,2,4,8....개로 사각형 형태로 묶을 수 있다.
즉, 이웃한 항끼리 묶을 수 있고, 이웃한 항은 대각선이 아니고 아래위, 좌우가 된다.
다음 예를 보자.
또 위 맵은 1의 값을 갖는 최소항들이 연결되지 않은 것 같지만 연결된 것으로 볼 수 있다. 정 사각형 형태다.(X'Z')
최소항 0000 의 위쪽에 있는 값이 1000으로 간주된다. 왼편에 있는 값은 0010이 된다.
위 맵을 원통모양으로 구부려 모양을 맞춘다 생각하면 쉽다.
위 맵의 부울 함수로의 표현식은 F(W,X,Y,X) = ∑m(0,2,8,10) 이다. 이는 논리곱의 합 형태가 된다.
논리합의 곱형태를 만드는 방법
최소항과 최대항은 보수관계다.(이에 대한 자세한 설명은 실용적이지 못하다 생각하여 다루지 않았다.)
위 맵에서 1이 아닌 부분(빈부분)은 사실 0의 값을 갖는다. 이 0의 값을 최소항으로 생각하여
F' = m1 + m3 + m4+ m5 + m6 + m7 + m9 + m11 + m12 + m13 + m14 + m15
보수를 취하면
F = m1' × m3' × m4' m5' × m6' × m7' × m9' × m11' × m12' × m13' × m14' × m15'
각 최소항의 보수(최대항)를 구하여 위 식에 대입하면 합의 곱으로 바꿀 수 있다.
(예> WXYZ의 최대항은 W'+X'+Y'+Z', W'XYZ'의 최대항은 W+X'+Y'+Z다.)