Digital Circuits(디지털 회로)(3) - Combinational Logic Circuits(2) Circuit Optimization

 

Chapter 2-2의 흐름

• 최적화의 목적
• cost 기준(L, G, GN)
• Karnaygh Map(K-map)
• Adjacency
• Prime Implicant / Essential Prime Implicant
• Don't Care 조건
• SOP/POS 최소화
• Espresso 알고리즘
• Multi-level Optimization

---

왜 최적화가 필요한가

논리식이 복잡하면 회로 비용이 커진다.

영향 :

1. 게이트 수 증가
2. 게이트 입력 수 증가
3. literal 수 증가
4. 전파 지연 증가
5. 면적 증가
6. 전력 증가

그렇기에 같은 기능을 하는 회로라면 더 간단한 식으로 바꾸는 것이 중요하다.

---

Cost 기준

1. Literal Cost (L) : 전체 literal 개수
2. Gate Input Cost(G) : 모든 게이트 입력 수 종합, 인버터 제외 (입력의 갯수를 세면 쉽다)
3. Gate Input Cost with NOTs(GN) : 게이트 입력 수 + 인버터 수

최적화 목표는 이 비용들을 줄이는 것이다.

---

Two-Level Optimization

1. SOP는 AND-OR 2단 구조
2. POS는 OR-AND 2단 구조

이번 챕터에서는 이러한 2 level 회로를 최소화하는 방법을 다룬다.

---

Karnaugh Map의 목적

K-map은 진리표를 시각적으로 배열해서 인접한 minterm/maxterm을 묶고 변수를 제거하는 도구다.

핵심은 진리표는 그냥 숫자 나열, K-map은 인접 칸이 1비트만 다르게 배치되어 묶기 쉬워진다는것이다.

2변수 카르노 맵

3변수 카르노 맵

4변수 카르노 맵

---

Gray Code 배열

K-map은 행과 열을 일반 이진순서가 아니라 Gray code 순서로 놓는다

예 : 00 01 11 10

이렇게 해야 인전 칸끼리 1비트만 다르게 된다.

---

Adjacency(인접성)

K-map에서 인접한다는 것은 입력값이 한 비트만 다른 경우다.

중요한 점은 좌우 끝도 인접하며 위 아래 끝도 인접하다는 것이다.

실제로는 wrap-around된다.

그렇기에 끝과 끝이 붙는 걸 놓치면 최소식을 못 구한다.

---

Minimization Theorem의 의미

K-map이 가능한 이유는 인접 항을 합치면 변수 하나가 사라지기 때문이다.

즉, 한 비트만 다른 두 항을 묶으면 그 변수는 없어 질 수 있다. K-map은 이 원리를 그림으로 적용한 것이다.

---

그룹핑 규칙

K-map에서 1또는 0을 묶을 때 규칙은 다음과 같다.

1. 그룹 크기는 반드시 2의 거듭 제곱
2. 반드시 직사각형
3. 대각선 묶기 불가(만약 대각선이면 exclusive or nor등을 고려는 해보면 좋다)
4. 가능한 한 크게 묶기
5. 중복 묶기 가능

---

왜 큰 그룹이 좋은가

큰 그룹일수록 더 많은 변수가 제거된다.

1. 2칸 그룹 -> 변수 1개 제거
2. 4칸 그룹 -> 변수 2개 제거
3. 8칸 그룹 -> 변수 3개 제거

즉 큰 그룹인 literal cost를 줄여준다.

---

그룹에서 항 읽는 법

그룹 안에서 값이 바뀌지 않는 변수만 남기고, 바뀌는 변수는 제거한다.

어떤 4칸 그룹에서 A = 1, B = 0만 고정이고 C, D는 변한다면 그 그룹은 다음과 같다.

---

SOP 최소화와 POS 최소화

1. SOP 최소화 : 1을 묶는다.
2. POS 최소화 : 0을 묶는다.

---

Prime Implicant(PI)

더 이상 확장할 수없는 가장 큰 implicant를 prime implicant라 한다. 즉, K-map에서 가능한 최대 크기로 묶은 후보들이다.

PI는 후보 그룹이라 생각하면 된다

---

Essential Prime Implicant(EPI)

어떤 1을 오직 하나의 PI만 덮고 있다면 그 PI는 반드시 필요하다. 이것이 바로 필수 주항이다.

 

즉, EPI는 무조건 선택 PI는 남은 1을 덮기 위해 선택하면 된다.

---

최소화 절차

문제를 풀 때 다음 순서가 가장 안전하다.

1. K-map 에서 진리표를 보고 1또는 0 채우기
2. 가능한 큰 그룹 찾기
3. PI 찾기
4. EPI 먼저 선택
5. 남은 칸을 최소 개수 그룹으로 덮기
6. 최종 최소식 작성

---

Don't Care 조건

Don't care는 특정 입력 조합이 발생하지 않거나 발생해도 출력이 중요하지 않은 경우다.

보통 K-map에 x로 표시한다.

사용법 :

1. 필요하면 1처럼 써서

2. 필요 없으면 무시

즉, 무조건 포함이 아니라 필요할 때만 사용한다.

---

Don't Care의 효과

don't care를 이용하면

1. 더 큰 그룹 가능
2. literal 수 감소
3. gate input cost 감소

즉 회로를 더 싸게 만들 수 있다.

---

Espresso Algorithm

K-map은 사람이 직접 하는 방법이고, 변수가 많아지면 비효율적이다.

그래서 자동화된 최적화 알고리즘이 필요하다.

Espresso는 대표적인 subopimum heuristic minimization(부분 최적 휴리스틱 최소 알고리즘이다.

핵심 단계:

1. Expand
2. Irredundant Cover 불필요한 보장
3. Reduce

간단히 변수가 많을 때 K-map 대신 자동화된 근사 최소화 방법 정도로만 알자.

---

Multi-Level Optimization의 의미

단순 하나를 짧게 만드는 게 아니라 전체 네트워크 구조를 더 효율적으로 만드는거다.

---

Chapter 2 총정리

• Binary variable은 0과 1만 가진다.
• 기본 연산은 AND, OR, NOT이다.
• Boolean algebra는 논리식 변환과 단순화에 사용된다.
• DeMorgan 법칙은 보수식 변환의 핵심이다.
• minterm은 한 행에서만 1인 product term이다.
• maxterm은 한 행에서만 0인 sum term이다.
• canonical SOP는 1인 행의 minterm 합이다.
• canonical POS는 0인 행의 maxterm 곱이다.
• standard form은 모든 변수를 포함할 필요가 없다.
• 최적화의 목적은 literal, gate, delay 비용 감소다.
• K-map은 인접 항을 묶어 변수 수를 줄이는 도구다.
• K-map은 Gray code 순서와 wrap-around adjacency를 사용한다.
• 그룹 크기는 반드시 2의 거듭제곱이다.
• 가능한 한 크게 묶어야 한다.
• prime implicant는 최대 크기 묶음 후보이다.
• essential prime implicant는 반드시 선택해야 한다.
• don’t care는 유리할 때만 사용한다.
• SOP 최소화는 1 묶기, POS 최소화는 0 묶기다.
• 큰 함수는 Espresso나 multi-level optimization으로 다룬다.