[컴퓨터 구조] Karnaugh-map

*[Mano의 컴퓨터 시스템 구조 3판]의 공부할겸 요약한 내용입니다.

---

Karnaugh-Map(K-Map)

- K-map을 이용하여 Boolean expressions를 좀 더 간단히 하면 최적의 Logic Diagram(회로)를 얻을 수 있다.

 

- 진리표에서 변수의 각 조합을 민텀(Minterm)이라고 한다. n개의 변수가 있으면 2^n개의 민텀이 있게 된다. 아래 사진은 변수가 3개이기 때문에 민텀은 2^3 = 8개이다.

 

- 진리표에서 출력 f가 1이 되는 민텀만 뽑으면 f(A,B,C) = Σ(1, 2, 3, 5)으로 표현이 된다.

- 맵은 여러 개의 사각형의 구역으로 이루어지고 각 사각형의 구역은 각각의 민텀을 표시하게 그려진다. 함수가 1이 될 때, 즉 논리 표현식의 출력이 1이 될 때 해당 민텀의 구역에 1을 넣고 출력이 0이 될 때에는 해당 민텀 구역에 0을 넣거나 아무것도 넣지 않는다. 

*위의 사진은 몇 번째의 민텀인가를 보이는 숫자가 구역 안에 위치해 있는 모습이다. 3변수 이상의 카노 맵에서는 위의 사진처럼 순서를 주의해야 한다.

 

- 진리표에 의해 표시되는 부울 함수는 그 함수의 값이 1이 되는 민텀을 해당되는 구역에 1로 집어 넣는다. 위의 사진이의  진리표에서 출력 F가 1인 민텀들을 뽑으면 Σ(1,2,3)으로 나타낼 수 있다. 이 뽑힌 민텀들을 알맞는 구역에 작성한다. 그 후 인접 구역의 1을 가능한 크게 묶는데 2의 승수로 묶는다(중복된 1이 있어도 상관없다).묶어낸 각각의 그룹은 대수항을 표시하고 이들의 논리합(OR)을 취하면 된다.

 

- 얻은 식을 바탕으로 회로를 작성하면 된다.

 

Don't Care 조건

- 맵의 민텀 구역에는 1이나 0이 들어간다. 민텀이 1이 되거나 0이 되거나에 관계없이 같은 함수의 값을 갖는 경우가 있다. 이러한 don't care를 맵에서는 X로 집어넣고 간소화시키기 위하여 묶는데 편리하도록 이를 1로 보거나 0으로 본다.

(묶는데 유리한 방향으로 생각한다.)

 

*예) 다음 부울 함수를 간소화하라.

F(A, B, C) = Σ(0, 2, 6)

don't care 조건은

d(A, B, C) = Σ(1, 3, 5)

이를 맵으로 표시하면 아래 그림처럼 된다.

여기서 묶음 안에 들어간 don' care X를 1로 유리하게 본다. 즉 X를 1로 봄으로써 네 개의 민텀을 크게 묶을 수 있게 된다. 간소화 된 결과 표현식은

F = A' + BC'

만약 don't care X를 전부 0으로 생각하고 묶으면

F = A'C' + BC'

가 되므로 표현식이 더 복잡해져서 좋지 않다.