조합회로 Combinational circuit의 최적 축약형에 대한 깨달음

이전 글에서 카르노 맵을 활용 해서 조합회로의 불 표현식을 simplify 간소화하는 방법을 배웠다.

https://mharry345.tistory.com/7

카르노 맵 Karnaugh Map 에 대한 깨달음

 

그런데 갑자기 그런 생각이 들었다. "최적 축약형은 유일한가?"

그런 고민이 드는 것도 이상하지는 않은 것이, 우리가 카르노 맵에서 한 블럭에 대해 가장 큰 영역을 지정하고 그 영역을 기준으로 식을 간소화 한다.

그렇다면 최적 축약형은 유일하지 않을까?

 

생각을 해보니 반례가 있었다.

빨간색 영역은 축약 과정에서 clear하게 결정되는데, 보라색은 두 가지 방법으로 그룹화할 수 있다.

따라서 최적 축약형이 유일하지는 않다.

 

그러나 최적 축약형의 모습이 조금 다를지언정 구성하는 리터럴의 개수와 term의 개수는 동일하게 유지된다.

그 모습이 최소라면 더 적은 term, 더 적은 리터럴의 개수가 존재하는 것은 최소의 정의에 위배되기 때문이다.

 

정리하면(Gemini)

 

마지막으로 조합회로의 효율을 증가시키는 방법과 최적 축약형을 찾는 과정 사이의 그 관계를 알아보고 마치자.

 

반론이나 질문은 환영입니다.