부울 방정식 최소화
저번 포스트의 내용처럼 일단 여기의 몇 가지 내용을 최소화 시켜보자.
방정식 풀고 있으니 중2 정도로 돌아간 기억이 나서 재미있었다.
앞서 나온 드모르간으로 활용할 수 있는 방안은 Bubble Pushing 이라는게 있다.
드모르간에 의하여 둘은 스왑가능하다.
그래서 아래와 같이 단순화도 가능하다.
1. K-Map 개요
• 부울식(Boolean Expression)을 시각적으로 간단하게 줄이는 도구
• 1953년 Maurice Karnaugh가 고안
• 최대 4개 변수까지 효율적으로 사용 가능
• 진리표(Truth Table)의 1을 묶어서 단순한 논리식으로 표현
2. K-Map의 기본 구성
• 행과 열로 이루어진 격자(grid)
• 각 칸은 **입력 변수의 조합(Minterm)**을 나타냄
• **이웃 칸(adjacent squares)**은 단 하나의 변수만 다른 조합
예:
| a | b | y |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
➡ K-Map에선 1이 연속되는 위치들을 묶어 간단한 식으로 줄일 수 있음.
3. K-Map 표현 예시 (2-input)
• 변수: A, B
• 진리표에서 Y가 1인 항들을 묶어서 간단화
| a | b | y |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
• Y = A’B’ + A’B = A’
즉, 두 개의 Minterm을 묶어서 A’로 간단화
4. K-Map 작성 규칙
1. 인접한 1들은 묶는다 (1, 2, 4, 8칸 등 2의 제곱수만 가능)
2. 묶을 수 있는 한 크게 묶는다
3. 동일한 1은 여러 번 묶을 수 있음
4. 테두리 wrap-around 가능
5. Don’t care(X) 항은 필요한 경우에만 포함
5. K-Map 구성 요소 용어
용어설명
| Literal | 변수 또는 그 보수 (ex: A, A̅) |
| Implicant | 리터럴의 곱 (ex: AB, A̅C) |
| Prime Implicant | 더 이상 확장할 수 없는 묶음 |
| Essential Prime Implicant | 반드시 포함해야 하는 핵심 묶음 |
6. K-Map 활용 예시 (3입력)
입력: A, B, C
진리표:
| a | b | c | y |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
→ Y가 1인 위치만 K-Map에 표시 → 인접한 칸 묶음 → 최적화된 부울식 도출
예를 들어)
7. 4변수 K-Map (A, B, C, D)
• 16칸의 격자
• 행: AB, 열: CD
• 묶음은 항상 인접 1, 2, 4, 8칸만 가능
• Wrap-around(양 끝 묶기) 허용
예시:
• Y = A’C’ + B’D
📌 8. 정리: K-Map 사용 이유
이유설명
| 시각화 | 부울식을 시각적으로 줄이기 쉬움 |
| 간단화 | 최소한의 논리 게이트 사용 |
| 회로 최적화 | 비용/전력/복잡도 감소 |
| 분석 속도 | 2~4변수 함수의 빠른 단순화 가능 |
앞에서 했던 Dont Cares의 개념과도 추가를 할 수 있다.
K-maps with Don't cares
이렇게 묶어내서 표현할 수 있다.
'프로그래밍 > 디지털회로' 카테고리의 다른 글
| [디지털 회로] 조합 논리 회로 (Combinational Logic Circuits) 와 불 방정식 (0) | 2025.03.25 |
|---|
