부울함수를 맵에 배치하고 사각형을 조합할 때 항, 주항, 필수주항이 생겨나는데 이 관계를 통해서 맵의 간략화를 깊게 이해할 수 있다.
항
교보문고 '디지털 논리와 컴퓨터 설계'라는 책에 다음과 같이 정의되어있다.
함수가 논리곱의 모든 최소항에 대해 1값을 가지면 논리곱은 함수의 항(implicant)다. 맵에서 1을 포함한 정사각형들로만 구성된 사각형은 항이 된다. 항P에서 어떤 문자를 제거할 때 항이 아닌 논리곱항을 얻게 되면, P는 주항(prime implicant)이다. n변수 함수에 대한 맵에서 주항은 1을 포함한 정사각형들을 최대한 2m (m=0,1,2,3,4,…,n)개씩 조합하여 만든 사각형들의 집합이다.
멍…. 뭔 소리냐? ㅋㅋ 멘탈이 나가기 시작한다. 하지만 절대 포기하지 맙시다.
솔직히 항,주항,필수주항의 정의에 대한 이해를 못해도 맵 간략화는 충분히 직관적으로 할 수 있다. 그런데 이 정의는 카르노맵 알고리즘을 설계한다면 중요한 단서가 된다고 생각한다. 아무튼..
붉은색 글씨를 비교하면 항과 주항의 관계를 알 수 있다. 1을 포함한 정사각형은 아래 카르노맵(4X4인경우)에서 16개의 작은 정사각형 각각을 말한다. 1을 포함한 정사각형 한개는 4변수 맵에서는 4개의 변수로 나타낸다. (예:abcd) 어떤 문자를 또 제거하게 되면 3개의 변수로 나타내지고(예:abc), 맵에서는 2칸이되고, 또 제거하면 2개의 변수로 나타내지면서 맵에서는 4칸을 차지하게 된다. 또 제거하면 1개의 변수(예 : a)로 맵에선 8칸을 차지하게 된다.
항이란 어떤 부울 함수를 위와 같이 맵에 배치했을 때 1을 포함하여 만들 수 있는 모든 사각형을 말한다.
주항이란 이런 항들 중에 최대한 으로 크게 만들되 (1,2,4,8….)의 칸수를 갖는 사각형들을 말한다.
우리는 간략화를 위해 주항이라는 개념을 이미 써오면서 사각형을 묶어왔다.
그러면 주항을 묶어보자.
3개의 주항이 나온다. 4개로 묶는 경우가 최대로 큰 사각형이 나오고 이런 사각형은 위와 같이 단 3개만 존재한다. 더 찾으면 노벨상?
이젠 여기서 필수 주항이라는 개념이 필요하다.
필수 주항
다시 위 책에서 인용하면
"함수의 최소항이 오직 하나의 주항에만 포함된다면, 그 주항은 필수적(essential)이라고 한다."
이건 그나마 이해하기 쉽다. 그래도 풀어쓰면 어떤 1을 포함하는 정사각형이(아무거나) 하나의 주항에만 포함된다면 그 주항은 필수주항.
그래서 위에서 필수주항은 두개가 된다.
파란색 주항은 위 조건을 만족하는 1을 포함하는 정사각형을 가지고 있지 않다. 나머지 두 개의 주항은 0001, 0003 그리고 1100, 1110 이렇게 1을 포함하는 정사각형(최소항)을 가지고 있다. 그래서 필수 주항이 된다.
파란 부분은 겹치는 부분으로 맵 간략화의 목적상 생략된다.
필수가 아닌 주항
예>
위 맵을 간략화 하기 위한 선택지는 꽤 많아보인다.
0000, 0001, 0100, 0101 의 4개의 최소항을 갖는 정사각형이 보이고 나머지는 2개의 사각형들이 보이는데..
여러 개의 주항들이 있지만, 여기서 선택을 해야한다. 물론 아무렇게나 선택을 해도 상관은 없지만, 간략화를 위해 일정한 규칙에 따라야한다.
위 맵은 붉은색 부분만 필수주항이다.(필수주항의 정의 참고)
나머지 부분들은 필수주항이 아니다. 그렇다고 버릴 수는 없다. 선택을 해야하는데, 파란 테두리들을 필수가 아닌 주항이라고 한다.
규칙 – 중복없이 최소항을 포함해라
또는
무정의 조건
무정의 조건은 간단하다. 빌려 쓰기라고 표현하고 싶다.
좀 더 간단하게 간략하기 위해서 무정의 항을 빌려 쓰는 것이다. 주의할 점은 무정의 조건이 있어야 한다.
무정의 조건이란 기술되지 않은 최소항을 말한다. 정의되지 않은 입력값은 정의된 출력값에 영향을 미치지 않기 때문에 위에서 말한 빌려쓰기가 가능하다.
예를들어 BCD-to-7 세그먼트 디코더의 경우 무정의 조건을 사용할 수 있다.
BCD-to-7 세그먼트 디코더는 전자시계를 만드는 데 사용한다.
각 숫자를 표현하는 8 모양은 7개의 세그먼트로 구성되어있다. 이 세그먼트의 조합에 따라 숫자가 구성되고 각 세그먼트들은 디지털 회로에서 하나의 출력이 된다. 이에 대한 설명은 차차 하기로 하고,
이런 디지털 회로를 구성할 때 모든 최소항이 다 쓰이는 것은 아니다. 이렇게 쓰이지 않는 최소항은 무정의 조건이 되어 빌려 쓸 수가 있다.
앞으로 계속 나오는 이야기이므로 여기서는 간단한 예만 들고 마무리 하겠다.
x로 표시된 곳이 무정의 조건이다.
예>
위와 같이 필요에 따라서 최소항으로 생각하여 묶을 수 있다.