필요성

여러개의 함수를 동일한 variable을 이용해서 나타내고자 하는 경우,
circuit은 제각각 구현하더라도, gate를 중복해서 사용하면 좀 더 효율적일 것이다. 

4개의 input과 3개의 output이 있는 다음 함수를 circuit으로 구현해 보자.


먼저 각 함수를 구현하기 위해서 Karnaugh map을 그린다.


각 함수는 위와 같이 looping할 수 있다. 이를 이용해서 circuit을 구현하면,


위와 같이 그릴 수 있다. 위와 같이 하면 9개의 gate와 21개의 input이 필요하다.
이제 이 circuit을 좀 더 간단히 하고자 한다.
먼저, circuit을 바로 바라봤을 때, 'AB'를 만드는 AND gate가 중복되어 있는 것을 볼 수 있다.
따라서 둘 중 하나를 없애고 없앤 쪽의 connection을 남은 하나의 'AB'와 연결하면
1개의 gate와 2개의 input이 줄어들게 된다.

한편, ACD와 A'CD의 gate를 통해서 CD = ACD + A'CD 를 구현할 수 있다. 따라서
CD 역시 제거가 가능하다.


최종적으로 위와 같이 circuit의 규모를 줄였다. 7개의 gate와 18개의 input이 사용되었다.
F_2는 ABC' + A'CD + ACD로 구현되어, minimum sum-of-products 라고 할 수 없다.
A'CD, ACD는 F_2에서 prime implicant라고 할 수 없다.
바꾸어 말하면, multiple-output circuit을 구현하는데 있어서
prime implicant를 구하고 minimum solution을 구하는 것은 큰 의미가 없다.
하지만, 위의 경우와 마찬가지로, gate의 숫자를 줄이는 것은 필요하다.



Directly Using Karnaugh Map

Karnaugh map이 아래와 같이 그려지는 함수 f_1, f_2, f_3이 있다고 하자.


먼저 각 Karnaugh map에 대해서 원래 하던대로 looping을 해 볼 수 있을 것이다.
하지만 map을 살펴보면 이것이 가장 좋은 solution이 아니라는 것을 알 수 있다.
먼저 f_2에 있는 a'bd, f_3에 있는 abd, ab'c'는 f_1에도 존재한다.
abd와 a'bd를 이용해서 우리는 f_1의 ad를 만들 수 있다. 
또한 f_1에서, 중복되는 ab'c'를 택하면, ab'를 제거해도 된다.
따라서 minimal solution는 다음과 같이 쓸 수 있다.


중복되는 gate는 밑줄로 표시했다.
Multiple-output circuit에 대해서는 Karnaugh map의 best solution이
항상 전체의 minimal solution이 되지는 않는다는 것을 다시 한 번 강조한다.



Determination of Essential Prime Implicants for Multiple-Output Realization

Minimum 2-level multiple-output circuit을 구현하기 위한 첫번째 단계로
essential prime implicant를 구하는 것이 요구된다. 
하지만 어떤 함수에서는 essential prime implicant인 것이 다른 함수에서는 그렇지 않을 수도 있다.
바로 이전 예제에서 f_1에 bd는 f_1에서는 essential prime implicant이지만, 다른 함수에서는 그렇지 않다.
그 이유는 f_1에서 essential prime implicant를 구성했던 minterm들 중 하나가
다른 함수의 일부에서 동시에 존재하기 때문이다.


위 그림을 살펴보자. (b)를 보면, f_1은 c'd + abd 로 이루어져 있다.
c'd는 f_1에 대해 essential 하다. f_2를 살펴보면 c'd에 해당하는 minterm들은 존재하지 않는다.
그러나 abd를 보면, 15번의 minterm이 f_2에, 다른 모양으로 looping되어있다.
따라서 abd는 essential하다고 할 수 없다.

다른 예제를 살펴보자.


f_1에서 2번과 5번의 minterm은 f_2에서 존재하지 않는다.
2번의 minterm을 cover할 수 있는 prime implicant는 a'd'이므로,
a'd'는 essential prime implicant가 된다. 
마찬가지 방법으로 5번의 minterm을 cover할 수 있는 prime implicant는 a'bc'이므로,
이 역시 essential prime implicant가 된다. 

이제 f_2를 기준으로 살펴보자. 1번과 12번의 minterm은 f_1에서 존재하지 않는다.
따라서, 이들을 포함하는 looping 역시 essential prime implicant가 되는 것이다.
결론적으로는 (b)와 같은 best solution을 얻게 되는 것이다.

정리하면, 어떤 함수에 있는 minterm이 다른 모든 함수에서 존재하지 않는 경우
이 minterm을 포함하는 prime implicant는 essential prime implicant라고 할 수 있다.
물론, 반드시 circuit으로 구현될 필요가 있다.
이러한 essential들을 먼저 구한 다음에 나머지에 대해서 정리하면 된다.

Posted by Nicatio

댓글을 달아 주세요

  1. sang hoon 2012.04.21 04:15 신고  수정/삭제 댓글쓰기

    또 다시 도움을 받는 군요. 공부하는 데 큰 도움이 됩니다~ 너무 감사해요 ㅋ
    그런데 이제 디지털 논리회로 포스팅은 끝인가요? ㅜㅜ

  2. hong jjong 2012.05.05 23:26 신고  수정/삭제 댓글쓰기

    덕분에 많이 도움되었습니다!! 논리회로 배우는 전기과학생인데
    순차논리회로에 대한 포스팅은 없나요 ㅠ?
    아무리 들어도 이해가 안가서 미치겠네요..ㅠ_ㅠ

    • Nicatio 2012.05.09 18:09 신고  수정/삭제

      답변이 늦어 죄송합니다
      아마도 학기중에 포스팅하기가 쉽지 않을 것 같습니다. ㅜㅜ

    • Hong JJong 2012.05.16 22:57 신고  수정/삭제

      아닙니다.ㅎ 복잡한 전공 책보다가 막히면 늘 여기와서 참조하는데 간략하면서도 이해하기 쉽게 적어주셔서 많은 도움 받고 있어서 늘 감사합니다^^;;

    • Nicatio 2012.05.17 15:55 신고  수정/삭제

      도움이 되었다니 다행입니다 ^^

  3. jun 2012.05.26 00:11 신고  수정/삭제 댓글쓰기

    혹시 이 자료들 어디서 구하는지 알수있을까요?ㅠㅠ

  4. ^^ 2012.06.04 18:19 신고  수정/삭제 댓글쓰기

    이자료들 책에서 직접 스캔해서 올리신 거에요?
    뒷부분 더 보고싶은데 다른데서 못구하나요?

  5. 지우현 2013.04.17 18:20 신고  수정/삭제 댓글쓰기

    내용 너무나도 잘봤습니다

    곧 시험이라 요긴하게 쓰일것같습니다.

    감사합니다

  6. 1234 2013.04.18 18:15 신고  수정/삭제 댓글쓰기

    도움많이 되었어요 ㅎㅎ 뒷단원도 올려주실수있나요?

  7. 곽진우 2013.06.21 20:57 신고  수정/삭제 댓글쓰기

    원서라 읽기 힘들었는데 덕분에 도움 많이 받네요~감사합니다.

  8. dd 2013.10.27 17:59 신고  수정/삭제 댓글쓰기

    덕분에 많이 알아가고있는 미래자동차공학과 학생입니다.
    디지털 논리 설계를 배우고있는 중인데 멀티플렉서, 디코더, 프로그레머블 논리소자를 배우고 있는 과정입니다. 그런데 이부분이 잘 이해가 가지 않더군요.
    ROM, PLA, PAL에 관한 포스팅도 해주시면 감사하겠습니다.

  9. 전자공학학생 2014.10.22 03:35 신고  수정/삭제 댓글쓰기

    안녕하십니까. 논리회로 공부하다가 너무 궁금해서 질문올립니다. 교수님? 포스팅 하시는 글이 제가 보는 원서랑 같아서 더 이해하기가 좋습니다.

    다름이 아니고 제가 질문하는건 더 뒷단원인데 너무 궁금해서 올립니다.
    hazard 단원에서 sop형태는 static 1 hazard만 생기고, pos형태는 static zero hazard만 생긴다고 알고 있는데, 책을 보다 보니, sop 중 어떤 product가 xx'a(a=1 or null)의 형태를 가질 수가 있는데, 이를 가지면 static 1 hazard 말고도 다른 hazard가 생길수가 있다는데, 이해가 안갑니다.

    첫째로 xx'a가 sop에서 product의 한 형태로 가질 수가 있다는게 이해가 안갑니다.
    두번째로는 다른 hazard를 가질수 있다는게 이해가 안갑니다.
    셋쨰로는 dynamic hazard는 어떤 경우에 생기는지 잘 모르겠습니다 ㅠ

    • Nicatio 2014.10.22 14:09 신고  수정/삭제

      1. xx'a 의 형태를 가질 수 있다는 것은 그냥 그렇게 정의한것으로 생각하시면 됩니다.

      2. Delay없는 input일 경우에는 항상 0이겠지만, 그렇지 않는 경우가 생기죠. 즉,
      x = 1 인 경우에, x' = 0 인데 x'이 delayed 되면 xx'a = a 가 되는 static 1 hazard.
      x = 0 인 경우에, x' = 1 인데 x'이 delayed 되면 xx'a = 0 가 되는 static 0 hazard.

      3. dynamic hazard는 서로 다른 delay를 가지는 여러 input이 오게 되는 경우에 발생할 수 있습니다.

    • 전자공학학생 2014.10.22 20:15 신고  수정/삭제

      답변해주셔서 감사합니다^^