논리회로 - 부울함수와 카르노맵

참고 교재: Digital Design with RTL Design, VHDL, and Verilog (Frank Vahid)

 

논리회로 과목은 디지털 공학, 디지털시스템설계와 거의 동일한 과목으로, 부울 대수, 잘 알려진 회로 (Adder, Mux, Encoder와 같은 회로), Finite State Machine과 이의 Sequential Logic 구현 등을 학습하게 된다.

 

Q. 진리표란?

 

진리표를 다루기 전에, 부울대수, 부울 함수를 살펴보자.

 

부울 대수에는 참과 거짓(1과 0) 값을 사용하며, 이에 대한 논리적 연산이 존재한다.

부울 함수는 input과 output이 모두 부울 값인 함수이다.

 

예를 들어, F(Y, Z) = Y + Z와 같은 부울식(boolean expression)을 갖는 부울 함수가 존재하면,

(Y = 1, Z = 1), (Y = 1, Z = 0), (Y = 0, Z = 1) 이면 F = 1

(Y = 0, Z = 0) 이면 F = 0 인 것을 알 수 있다.

 

진리표는 이러한 부울함수에 대해, 모든 input combination에 대한 output을 명세한 표이다.

F = Y + Z의 truth table은 다음과 같을 것이다.

 

Y	Z	F
0	0	0
0	1	1
1	1	1
1	0	1

Q. 카르노 맵이란?

 

카르노 맵은 부울식이 적은 variable을 가지도록 단순화하는 방법(optimization)이다.

참고로 부울식에서는 variable은 참 또는 거짓 값을 가지는 symbol (e.g. Y, Z), literal은 variable 그리고 이의 complement(')를 나타내는 symbol (e.g. Y, Z, Y', Z')을 의미한다.

 

예를 들어 다음과 같은 식을 가지는 함수가 있다고 하자.

F = XY + XY'

이 식은 다음과 같이 최적화할 수 있다. (variable Y가 식에서 사라졌다)

F = X ( Y + Y' ) = X

 

이렇게 variable을 최적화하는 방법 중 visual 한 방법이 카르노 맵이다.

 

다음과 같은 Truth table 4개가 있을 때 카르노 맵에 의해 유도되는 부울 식은 다음과 같다:

X / YZ	00	01	11	10	X / YZ	00	01	11	10
0	1	1	0	0	0	0	1	1	0
1	0	0	1	1	1	0	1	1	0
X / YZ	00	01	11	10	X / YZ	00	01	11	10
0	0	1	0	0	0	0	0	0	0
1	1	1	1	1	1	0	1	1	1

왼쪽 상단: F = X'Y' + XY

(F = X'Y'Z' + X'Y'Z + XYZ + XYZ')

오른쪽 상단: F = Z

(F = X'Y'Z + X'YZ + XY'Z + XYZ)

왼쪽 하단: F = X + Y'Z

(F = X'Y'Z + XY'Z' + XY'Z + XYZ + XYZ')

오른쪽 하단: F = XZ + XY

(F = XY'Z + XYZ + XYZ')