카노프맵을 이용한 부울 함수의 간략화

회로 구현의 효율성을 위해 부울함수의 간략화가 필요한데, 부울 대수의 규칙과 법칙만을 이용해선 완전한 최소화가 용이하지 않다. 따라서 카노프 맵을 이용하여 간략화 하는 방법을 알아야 한다.



* 카노프 맵이란?
-입력변수들에 대한 조합 수 만큼의 셀들로 구성된 2차원 배열
- 인접해 있는 1들을(0들을) 2^n개 단위의 그룹으로 묶고, 정해진 규칙에 따라 변수를 제거
- 3 - 변수, 4-변수 및 5-변수 부울 함수들에 대하여 적용가능
- 그 이상의 변수 함수들에 대해선
방법은 있으나 프로그래밍으로 대부분 해결

(1) 3- 변수 sop형 부울 함수에 대한 카노프맵

3-변수 카노프 맵이란
2^3개(8개)의 셀들로 이루어진 2차원 배열이다.(변수가 만들 수있는 최소항의 수와 같다)

 

 

각 셀에는 대응되는 2진수들이 있다. 2진수들을 각 셀에 기록해준다.

또한 각 셀에는 대응되는 최소항들을 작성한다.

 

 

-Sop 형 부울함수에 대한 카노프맵

(1)정규형 sop 표현으로 변형 후
(2)함수를  구성하는 각항에 대응되는 셀을 ‘1’ 로 채움

 

주로 작성하게 될 카노프 맵이다.

(2) 셀의 인접성을 이용하여 간략화하기

카노프 맵에서 바로 옆, 혹은 위 아래 등 인접한 셀들은 단 한개의 변수값만 서로 다르기 때문에 이 인접성을 이용하여 간략화를 할 수 있다. 앞뒤양옆 돌려감기 가능하므로 열심히 눈으로 찾아보자.

1을 가진 셀들 중에서 인접한 것들을 하나의 그룹으로 묶는다. (2의 승수 단위로) 00-10 돌려감기 가능

 

-방법

1.1을 가진 셀들 중에서 인접한 것들을 하나의 그룹으로 묶는다. (단 그룹 내 '1'의 개수는 2^n개 단위)

2.변수의 제거 : 묶음 그룹에 해당하는 변수들 중에서 비트 값이 서로 다른 변수는 제거한다.

ex)

그룹 중 A는 세 셀 모두 000이다->제거하지 않음

그룹 중 B는 세 셀이 011이다. -> B 제거 

3.간략화된 항 표현 : 값이 0이면 A' 1이면 그냥 A. 다른 변수도 마찬가지. 이 때 한 변수는 그룹당 하나.

변수의 값이 0이면 보수형, 1이면 정상형으로 표현한 최소항을 각 그룹당 하나씩 구한다.

2^1 개의 셀을 묶으면 1개 변수 제거 가능

2^2 개의 셀을 묶으면 2개 변수 제거 가능

2^3 개의 셀을 묶으면 3개 변수 제거 가능

(3) Prime imlicants

-Prime Implicant :카노프 맵에서 나오는 최대한 많은 묶음.(단, 최대한 크게 묶었을 때)

-Essential Prime Implicant : 카노프 맵에서 이 묶음 아니면 이 셀을 못 묶어요 하는 묶음.

셀을 묶는 방법이 하나밖에 없는 셀을 하나라도 포함하면 Essential Prime Implicant

 

PI=A'D',CD'                          EPI=A'C',AC

-PI 주의.얘는 묶는 방법이 두개다, 하나는 없어도 모든 셀을 묶어줄 수 있다. 싶으면 하나만 함수에 포함시켜야 한다. 둘 중 어느 것을 포함시켜도 정답이 된다.

간략화 결과 : F=A'C'+AC+A'D' or F=A'C'+AC+CD'

 

(4)POS 표현의 간략화

 

1.SOP 표현의 카노프 맵을 그린다.

2.1이 쓰여있지 않은 0의 영역에서 셀을 묶는다.(F')

3.셀들을 POS꼴로 나타낸다. (F')'

 

=>드모르간 법칙에 의해 성립

 

혹은 SOP 간략화 방법을 0으로 그대로 따라해도 된다.

 

풀어보자!

1.아래 부울 대수를 간략화해서 AND-OR 구조로 구현해 SOP 꼴로 나타내어라.

가로세로 3,4번째 줄을 바꿔주지 않으면 망한다. 과거의나처럼... 부호 하나 차이가 나면서 인접하기 위해 바꾼다고 한다.

2.OR-AND 구조로 구현하여 POS 꼴로 나타내어라.

나처럼 SOP형태와 헷갈려서 POS형태로 변환시 빼먹은 것 없게 주의하자.

 

 

(5)Don't Care 조건을 가진 경우의 간략화

-사용되지 않는 입력변수의 조합

특정 비트 조합이 사용되지 않을 경우, 안 쓰는 그대로 낭비하지 말고, 간략화에 도움이 되도록 어떤 것이든 쓸 수 있게 하자는 취지.

 

카노프 맵에서는 해당 셀을 X로 표시한다.=>X는 0이든 1이든 될 수 있다는 뜻이다.

보통 문제에서 Don'tCare가 되는 셀이 주어지므로, 맵에 잘 표시하고 간략화에 도움이 되도록 선택해서 사용하자.

POS꼴에 사용할 땐 0이라고 해석하는 것 잊지 않기(SOP와 반대로 사용하기)

 

(6)5-변수 카노프 맵

4-변수 카노프 맵을 포개어 구성->3차원 형태.

(7)간략화 불가능 카노프 맵

XOR함수

XNOR함수

카노프 맵이 바둑판 형태. 변수가 몇 개든 간략화 불가능