5. 불 대수, 카르노 맵

5. 불 대수, 카르노 맵

불 대수(Boolean algebra)는 논리회로를 설계하고 분석하는데 필요한 수학이다.  

불 대수의 덧셈(Boolean addition)은 OR 게이트를 이용하고 연산자는 +이다.

불 대수의 곱셈(Boolean product)은 AND 게이트를 이용하고 연산자는 ·(곱셈, 또는 기호생략)이다.

다음은 불 대수의 교환법칙, 결합법칙, 분배법칙을 논리게이트로 나타낸 것이다.

합(OR 게이트)과 곱(AND 게이트)의 교환법칙: \(A+B=B+A,\,A\cdot B=B\cdot A\)

합(OR 게이트)과 곱(AND 게이트)의 결합법칙: \(A+(B+C)=(A+B)+C,\,A\cdot(B\cdot C)=(A\cdot B)\cdot C\)

분배법칙: \(A\cdot(B+C)=A\cdot B+A\cdot C\)

다음은 불 대수의 성질들이다.

*드 모르간(DeMorgan) 법칙

드 모르간 법칙을 다음과 같이 변수가 3개 이상일 때도 적용할 수 있다.$$\begin{align*}\overline{X+Y+Z}&=\overline{X}\cdot\overline{Y}\cdot\overline{Z},\,\overline{X\cdot Y\cdot Z}=\overline{X}+\overline{Y}+\overline{Z}\\ \overline{X+Y+Z+W}&=\overline{X}\cdot\overline{Y}\cdot\overline{Z}\cdot\overline{W},\,\overline{X\cdot Y\cdot Z\cdot W}=\overline{X}+\overline{Y}+\overline{Z}+\overline{W}\end{align*}$$

논리회로에서 주입력(primary input)으로부터 주출력(primary output)방향으로 논리식을 단계적으로 유도한다.

다음의 논리회로에서 \(F=A(B+CD)\)이다(오른쪽은 논리표).

불 대수를 이용하여 다음의 논리식을 간략하게 나타낼 수 있다.$$\begin{align*}AB+A(B+C)+B(B+C)&=AB+AB+AC+BB+BC\\&=AB+AC+B+BC\,(AB+AB=AB,\,BB=B)\\&=AB+AC+B\,(B+BC=B(1+C)=B)\\&=B+AC\,(AB+B=(A+1)B=B)\end{align*}$$

왼쪽은 간략화 하기 전의 논리식에 대한 논리회로이고, 오른쪽은 간략화 한 후의 논리식에 대한 논리회로이다. 이 두 회로는 등가이다.

불 식은 곱항의 합(Sum-Of-Product, SOP)의 형태 또는 합항의 곱(Product-Of-Sum, POS)의 형태로 나타낼 수 있다.

SOP(AND-OR): \(AB+ABC,\,ABC+CD\overline{E}+\overline{B}C\overline{D},\,A+\overline{A}B\overline{C}+AC\)

POS(OR-AND): \((\overline{A}+B)(A+\overline{B}+C),\,(A+B)(A+\overline{B}+C)(\overline{A}+C)\)

*참고:$$\begin{align*}F&=\overline{AB}C+A\overline{BC}+ABC\\ \overline{F}&=(A+B+\overline{C})(\overline{A}+B+C)(\overline{A}+\overline{B}+\overline{C})\end{align*}$$

(위 논리식에 대한 진리표)    

다음과 같이 최소항(minterm), 최대항(maxterm) 표현법을 이용하여 나타낼 수 있다.

위 표에서 \(m_{i}=\overline{M_{i}}(M_{j}=\overline{m_{j}})\,(i,\,j=0,\,1,\,\cdots,\,7)\)이 성립한다. 예를들어$$\begin{align*}F_{1}&=\overline{xy}z+x\overline{yz}+xyz\\&=m_{1}+m_{4}+m_{7}=\sum(1,\,4,\,7)\\F_{2}&=\overline{x}yz+x\overline{y}z+xy\overline{z}+xyz\\&=m_{3}+m_{5}+m_{6}+m_{7}=\sum(3,\,5,\,6,\,7)\\F_{3}&=\overline{xyz}+\overline{x}y\overline{z}+\overline{x}yz+x\overline{y}z+xy\overline{z}\\&=m_{0}+m_{2}+m_{3}+m_{5}+m_{6}=\sum(0,\,2,\,3,\,5,\,6)\\ \overline{F_{3}}&=\overline{(\overline{xyz}+\overline{x}y\overline{z}+\overline{x}yz+x\overline{y}z+xy\overline{z})}\\&=(x+y+z)(x+\overline{y}+z)(x+\overline{y}+\overline{z})(\overline{x}+y+\overline{z})(\overline{x}+\overline{y}+z)\\&=M_{0}M_{2}M_{3}M_{5}M_{6}=\prod(0,\,2,\,3,\,5,\,6)\end{align*}$$이다. 위의 예에서 드 모르간 법칙에 의해 \(F_{3}=\sum(0,\,2,\,3,\,5,\,6)=\prod(1,\,4,\,7)\)이 성립함을 알 수 있다. 

카르노 맵

카르노 맵(Karnaugh map)은 입력변수의 가능한 모든 값과 각 값에 대한 결과 출력을 나타내서 진리표와 유사하다.

참고: 여기서 편의상 \(\overline{x}=x',\,\overline{y}=y',\,\overline{z}=z',\,\overline{w}=w'\)로 나타내겠다.  

위의 그림에서 왼쪽은 2변수 카르노 맵, 오른쪽은 3변수 카르노 맵이고 3변수 카르노 맵에서 \(m_{0}\)와 \(m_{2}\), \(m_{4}\)와 \(m_{6}\)은 서로 떨어져 있지만 인접한 것으로 간주한다.

(4변수 카르노 맵)

위의 그림은 셀의 인접성을 나타낸 것이다. 이 셀의 인접성으로부터 서로 떨어져 있는 셀도 인접한 것으로 간주한다.

카르노 맵을 이용하여 SOP 간략화를 할 수 있다. 우선 SOP식의 각 곱항에 대해 카르노 맵에 1을 넣는다. 그 다음으로 인접한 1이 포함된 셀을 그룹으로 묶되 가능한 크게 묶고 \(1,\,2,\,4,\,8,\,\cdots,\,2^{n}\)개수 단위로 묶는다.

\(F=\overline{x}y+x\overline{y}+xy\)식을 다음과 같이 카르노 맵에 표시하여 간략화하면 \(F=x+y\)이다.

SOP식을 카르노 맵에 위의 그림처럼 각 곱항에 1을 넣는다. 그다음으로 그룹핑을 하여 간략화한다.

(앞의 경우와 같은 방법을 이용한다.)

\(F=\sum(0,\,2,\,3,\,5,\,7,\,8,\,9,\,10,\,11,\,13,\,15)\)를 다음과 같이 카르노 맵에 나타낼 수 있다.

여기서 인접한 항들을 묶을 수 있는 모든 경우(PI, Prime Implicant)는 \(CD,\,B'C,\,AD,\,AB',\,BD,\,B'D'\)이고, 이들 중 반드시 포함되어야 할 항(EPI, Essential Prime Implicant)은 \(BD,\,B'D'\)이다. 따라서$$\begin{align*}F&=BD+B'D'+CD+AD\\&=BD+B'D'+CD+AB'\\&=BD+B'D'+B'C+AD\\&=BD+B'D'+B'C+AB'\end{align*}$$이다. 

*2개의 곱항이 1개의 변수만 값의 차이가 있으면 값의 차이가 나는 변수가 제거되어 문자 개수가 하나 적은 하나의 곱항으로 간략화 될 수 있다. 

무정의 조건(don't care condition)은 입력 변수의 조합 중 사용하지 않는 곱항을 무정의 조건으로 사용하여 간략화 과정에 사용한다. 이때 필요한 경우 유리한 방향(크게 묶기)으로 사용할 수 있고, 더 이상 크게 묶을 것이 없으면 사용하지 않아도 된다.

예를들어 \(F=\sum(1,\,3,\,7,\,11,\,15)\)를 원래대로 간략화하면 \(F=yz+x'zw'\)이나 무정의 조건을 사용하면

위의 왼쪽 그림의 경우 \(F=yz+x'w'\)이고, 오른쪽 그림의 경우 \(F=yz+zw'\)이다.

카르노 맵을 이용하여 POS형을 간략화 할 수 있다.

위의 그림처럼 직접 대입해서 그룹핑을 한 다음 간략화 하여 구하거나 또는 보수를 취해서 SOP형태로 나타내어 해석한 후, 다시 보수를 취하여 구한다.         

다음은 7-세그먼트 디스플레이 이다.

이것 역시 카르노 맵을 이용하여 설계할 수 있다.(설계는 독자의 몫으로 남긴다)

참고자료:

Digital Fundamentals 11th edition, Floyd, Pearson

Digital Design 5th edition, Mano, Ciletti, Pearson

Introduction to Logic Design 3th edition, Marcovitz, McGraw-Hill