wanna be dev 🧑‍💻

Cool 하고 Sick한 개발자가 되고 싶은 uzun입니다

A.K.A. Kick-snare, hyjhyj0901, h_uz99 solvedac-logo

Computer Science/Logic Circuit Design

논리회로설계 [3] Optimization Algorithm

Kick_snare 2022. 4. 10. 11:05
728x90

본 포스팅은 Logic and Computer Design Fundementals (Pearson, 2013)의 내용을 다루고 있습니다.

Oprimization Algorithm


Sum of Product

  1. 모든 prime implicant를 찾는다.
  2. 그들 중, 모든 essential prime implicant를 찾아 선택한다.
  3. 나머지 non essential prime implicant들 중 최소한을 선택한다.

Product of Sum

  1. 모든 prime sum을 찾는다.
  2. 그들 중, 모든 essential prime sum을 찾아 선택한다.
  3. 나머지 non essential prime sum들 중 최소한을 선택한다.


minterm 과 maxterm의 갯수로 비교하면 안된다!

Logic Optimization For Don't Cares


용어 정리

  • Don't Care
    : 출력으로 0 또는 1 모두 올 수 있다.
  • Incompletely Specified Function
    : dont care를 가진 boolean function
  • Completely Specified Function
    : dont care를 가지고 있지 않은 boolean function

Optimization For Don't Care

Sum of Product

  1. 모든 prime implicant를 찾는다.
    • dont care을 1로 취급한다
  2. 그들 중, 모든 essential prime implicant를 찾아 선택한다.
    • dont care은 무시하고 선택한다
  3. 나머지 non essential prime implicant들 중 최소한을 선택한다.
    • dont care은 무시한다

Product of Sum도 마찬가지이다.

example


위 그림의 sum of product의 k-map을 구해보자

STEP 1

dont care을 1로 취급하여 모든 prime implicant를 찾는다

STEP 2


그들 중, 모든 essential prime implicant를 찾아 선택한다.
essential prime implicant는 최소 한개 이상의 어느 implicant에도 속하지 않는 minterm을 가져야한다. (dont care 제외)

초록색으로 essential prime implicant을 표시하였다.

STEP 3


dont care는 무시하고 최소한의 갯수와 최소의 리터럴을 가지도록 박스를 친다.

GATE Delay


게이트 출력값의 변화는 원인이 되는 입력값의 변화의 결과이다.
그 원인(입력)과 결과(출력) 사이에는 반드시 시간차가 존재한다.

디지털 회로의 함수적 기능을 생각하는 경우에는 게이트 지연시간을 무시할 수 없다.
그러나 회로의 성능을 고려할 때에는 게이트 지연시간을 무시할 수 없다.

로직레벨이 높아질수록 지연시간은 증가한다.

[Logic Design - 4]에 계속↗

728x90