[논리 회로] 논리 회로와 부울 대수, 카르노 맵을 이용한 논리 회로 최적화

논리 회로

논리 회로(Logic Gate)는 디지털 회로에서 입력값들(0또는 1)을 받아서 논리 연산을 수행한 결과(0또는 1)를 출력하는 기초적인 전자 회로이다. 모든 컴퓨터, 스마트폰, 게임기 같은 디지털 장치의 작동은 이 논리 게이트를 조합해서 만든 회로로 이루어져있다.

 

주요 논리 게이트 설명

논리	논리식	설명	출력 조건
AND	A ⋅ B	모두 1일 때만 출력 1	A=1, B=1 : 출력=1
OR	A + B	하나라도 1일 때 출력 1	A=1, B=0 : 출력=1
NOT	A'	입력의 반대 출력	A=1 : 출력=0
NAND	(A ⋅ B)'	AND의 반대 결과	A=1, B=1 : 출력=0
NOR	​(A + B)'	OR의 반대 결과	A=0, B=0 : 출력=1
XOR	A ⊕ B	입력이 다르면 출력 1	A=1, B=0 : 출력=1
XNOR	(A ⊕ B)'	입력이 같으면 출력 1	A=1, B=0 : 출력=0

 

 

부울 대수

부울 대수는 0과 1을 사용해 두 개의 값으로만 표현하고 연산하는 대수학으로, 2진 변수와 논리 동작을 취급하는 함수이다. 논리 회로를 설계할 때 입출력의 관계를 부울 대수 형태로 표현할 수 있다. 부울 대수를 사용하면 논리식을 간략화함에 있어 유리하여 논리 회로 설계 시 부울 대수를 사용한다.

 

부울 대수를 이용해 복잡한 논리식을 간단한 회로로 만드는 예시

예시 1)
F = A · B + A · B'
   = A · (B + B')  // 분배법칙
   = A · 1 // 보완법칙
   = A  // 항등법칙

예시 2)
F = A + A·B
   = A  // 흡수법칙

예시 3)
F = A · (A + B)
   = A  // 흡수법칙

예시 4)
F = A · B + A · B′ + A′ · B
앞 두항
   = A · (B + B')  // 보완법칙
   = A · 1  // 항등법칙
   = A
나머지
   = A + A'·B
   = (A + A′)·(A + B)  // 분배법칙
   = 1·(A + B)   // 보완법칙
   = A + B  // 항등법칙

---

카르노 맵

카르노 맵(Karnaugh Map)은 논리식을 시각적으로 표현하고 간단하게 줄이는 도구이다. 진리표의 값을 2차원 격자 형태로 배열한 뒤, 인접한 1들을 묶어서 논리식을 더 단순하게 만들 수 있다. 특히, 논리식이 minterm(Σm) 형태나 truth table로 주어졌을 때 사용하기 적합하고, 부울 대수를 사용할 때보다 간단하고 직관적으로 논리식을 간략화할 수 있다는 장점이 있다.

 

논리식을 카르노 맵으로 표현하는 방법

1) 문제 파악

F(A, B, C) = Σm(1, 2, 3, 5, 7)

A, B, C라는 3개의 입력 변수가 있을 때,
F의 출력이 1이 되는 경우가 진리표의 1, 2, 3, 5, 7번 행이다.

 

 

2) 카르노 맵 틀 그리기 (3 변수용)

• B, C의 4가지 조합은 Gray 코드 순서로 배치한다. (00 -> 01 -> 11 -> 10)

	00	01	11	10
0
1

 

 

3) 카르노 맵에 1 채우기 (이진수 변환)

• 문제에 주어진 minterm 번호들을 이진수로 변환해 해당 위치에 1을 채워 넣는다.
• 입력 변수의 개수 = 이진수로 표현할 때 필요한 비트의 수

	00	01	11	10
0		1	1	1
1		1	1

 

minterm 번호 1을 이진수로 나타냈을 때 001,
minterm 번호 2를 이진수로 나타냈을 때 010,
minterm 번호 3을 이진수로 나타냈을 때 011,
minterm 번호 5를 이진수로 나타냈을 때 101,
minterm 번호 7을 이진수로 나타냈을 때 111.

 

카르노 맵에서 최종 논리식을 만드는 방법

인접한 1들을 가능한 크게 묶고, 그 묶음마다 간단한 식을 만들어서 OR(+)로 연결

 

1) 인접한 1 묶기 (Grouping)

• 반드시 2의 제곱 수만큼 묶어야 함 (1, 2, 4, 8 ...)
• 상하좌우 인접한 1끼리만 묶을 수 있음 (대각선 X)
• 카르노 맵은 도넛처럼 연결됨 (양 끝도 연결 가능)
• 가능하면 큰 개수로 그룹화하는 것이 간략화의 효과가 큼
• 1이 여러 그룹에 겹쳐서 포함돼도 괜찮음

01

 

2) 각 그룹을 간략화 하고, 간략화된 부울식들 끼리 OR(+) 연산

• 묶은 그룹 안에서 변하지 않는 고정된 변수만 사용
• 나머지는 변하므로 소거됨 (식에 안들어감)
• 변수가 0으로 고정되어 있다면 그 변수의 NOT
• 변수가 1로 고정되어 있다면 그 변수 그대로

예제 1)

a값은 두 칸 모두 0으로 고정되어 있어 사용
b값은 변하므로 소거
최종 논리식 F = a

 

위 예시를 식으로 생각하면

F = a'b' + a'b

   = a'(b' + b)

   = a'1

   = a'

 

예제2)

첫번째 초록색 묶음
a값은 네 칸 모두 0으로 고정되어 있어 사용
b와 c 값은 변하므로 소거

두번째 파란색 묶음
a값과 b값은 변하므로 소거
c값은 모두 0으로 고정되어 있어 사용

최종 논리식 F = a' + c'