[논회설] 논리회로설계 강의 요약해보기 06-1

카르노 맵 최적화를 체계적으로 배우기

용어부터 정리하자

• Literal: 변수가 나타나는 형태
• Implicant
  • 리터럴의 곱의 형태
  • 카르노맵에서는 써클로 표현된다.
• Prime Implicant
  • 더 이상 확장할 수 없는 Implicant
  • 더 이상 확장할 수 없는 Circle(카르노 맵에서!)
• Essential Prime Implicant
  • 해당 함수를 만족시키기 위해 필요한 Prime Implicant
  • 모든 EPI는 꼭 포함된다.
  • Non-EPI는 포함될 수도, 안 될 수도 있다.
  • 근본은 The Fewst, The Largest
  • 카르노맵에서는, 단 하나의 써클에만 포함되는 1이 있는 PI가 EPI이다.
• Cover
  • F = 1을 만족시키는 모든 써클의 집합
  • 해당 함수를 구현할 수 있는 방법
  • Cover는 여러개 있을 수도 있음!!! → 그러니까 The Fewest, The Largest 한 Cover를 찾는 거임.
• Cost
  • 게이트의 수 + 입력의 수
  • Ignore complement (NOT)

카르노 맵을 최적화하는 순서

1. 모든 Prime Implicant를 생성한다.
2. EPI를 모두 찾는다.
3. EPI만으로 F = 1을 만족하나요?
   1. Yes → 끝!
   2. No →  Non-EPI 중 Complete Cover를 만들 수 있는 PI들을 찾아내야함!

 

카르노맵과 SOP vs POS

카르노 맵의 표현방법은 SOP(sum of products)와 직접적으로 연관되어 있다!

→ Why? 1인 것을 것을 골라서 Circle을 구성하고나서, 이를 더해줬기 때문에!

 

그러면, POS는?

→ 0인 것을 골라서 Circle을 구성하고나서, 이를 곱해주면 된다!