카르노맵

카르노맵 문제 풀이 방식 

SOP expression으로 표현된 Function을 맵을 그려 그룹핑한 후, 식을 최소화한다. 

 

1. F(A,B,C) = ∑m(0,1,...~) + d(0,~) 으로 표현된 SOP Expression을 보고 Function의 변수 갯수를 확인하고 표를 작성한다.

2. 작성된 표에 ∑m(0,1,...~)에 있는 숫자의 위치에 1, 나머지는 0을 작성한다. 

2-2. d(0,..~) -> Don't care - 함수 구현에 중요한 부분이 아니며, 그룹핑을 늘릴 수 있다면 1, 그렇지 않다면 0을 작성한다.

3. 표를 다 그렸으면 1로 표기된 부분을 사각형 형태이며, 내부 1의 갯수가 2^n 이 되도록 그룹핑한다. 

3-2. 표의 가장자리에 있는 1도 반대편에 있는 1과 그룹핑 가능하다. 

4. 그룹핑된 사각형 내부에 변수를 최소화 할 수 있는 식을 확인한다. 

 

ex.  F(A,B,C,D) = ∑m(0,1,4,5,10,14) = A'C' + ACD'

K-map

1로 표기된 부분을 그룹핑한 후 2x2 사각형은 A = 0, C = 0을 공통으로 가지고 있으므로 A'C'로 최소화 가능

2x1 사각형은 A = 1, C = 1, D = 0을 공통으로 가지고 있으므로 ACD'로 최소화 가능 

 

-> 따라서 A'C' + ACD'로 최소화 가능