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

6-3차시

Tabular Method

아무튼, 요걸 배우는 이유? 

카르노 맵은 scalability 문제가 발생하고, 이를 해결할 방법이 필요함.

→ Tabular Method: Quine-McCluskey!!

 

Tabular Method: Quine-McCluskey

• 50년대 중반에 발표됨.
• K-map의 Scalability 문제를 해결한 논리식의 최적화 기법
• K-map의 최적화 원리를 이용한 Algorithmic한 체계적 방법
• 주로 적용하는 핵심 규칙 
  • Uniting theorem ab + ab' = a(b+b') = a*1 = a
  • "참과 거짓이 둘다 포함되어있는 변수를 지운다"라고 생각하면 편하다.

• Algorithm 단계
  1. 모든 prime implicants를 찾는다.
     
     1. 출력이 1인 minterm과 don't care인 minterm을 모두 나열한다.
     2. minterm 내의 1의 개수에 따라 묶어서 그룹을 만든다.
     3. i번째 그룹 Gi와 i+1번째 그룹 G(i+1) 내의 모든 항목을 서로 비교한다.
        1. 1 비트 차이가나는 항목끼리 uniting theorem을 적용한다. 
           왜 비트 차이이냐? 1비트만 차이가 나야 Uniting theorem을 적용할 수 있기 때문이다.
           예를 들어, E1*a + E2*a' 가 있을 때, a를 지우기 위해서는 E1과 E2가 같아야 한다.
           사실 이건 이 tabular method 뿐만 아니라, 카르노 맵에서도 활용한 것이다. 단지 눈에 띄지 않았을뿐... 
        2. 다른 항목과 묶어서 더 큰 implicant를 만들 수 있는지 확인한다.
  2. 모든 Essential Prime Implicants를 찾는다.
     1. PI chart를 그릴것이다!(주의, PI chart의 맨 위 열 index에는 minterm만 표시한다.)
     2. 서로 연관 있는 minterm과 PI의 만나는 Cell에 'X' 표시
     3. minterm을 기준으로 'X' 표시가 하나만 있는 PI가 표시되어 있는 PI가 EPI이다.
     4. 모든 EPI를 찾는다!
  3. 남아있는 1을 Cover하는 Prime Implicants를 찾는다.

 

Tabular Method 심화

Tabular Method 연습문제 풀이 영상에서 나온 더 심화적인 방법

Column Dominance Rule: 어떤 Column 하나가 다른 Column을 포함할 경우 지울 수 있다. (체크 표시가 더 많은 것을 지우면 된다.)

Row Dominance Rule: 어떤 Row 하나가 다른 Row에 포함될 경우 지울 수 있다. (체크 표시가 더 적은 것을 지우면 된다.)

 

→ PI reduction이 가능하다..!

→ EPI를 구하는 것이 더 편하다!