내가 공부한 논리회로 설계13. Minterm과 SOP 최적화

이전에

2.1    에서는 Binary logic이 무엇인지 그리고 로직 게이트를 공부했습니다. 

2.2    에서는 불대수와 불대수에서만 성립하는 몇 가지 항등식에 대해서 공부해보았습니다. 항등식을 이용해서 회로를 간단히 하는 방법을 공부해보았습니다. 

2.3   에서 공부할 내용은 회로를 최적화하기 위한 새로운 것들을 공부합니다. 

그중에서  Sumterm, Productterm, Maxterm, Minterm을 공부합니다. 

(Term: 항)

 

 

 

25. 몇가지 기본개념을 공부해보겠습니다.  정확히 알고 넘어가길 바랍니다. 

Sumterm, Productterm, Maxterm, Minterm에 대한 기본개념이 정의되어있는데 정의를 정확히 숙지하고 있어야 합니다. 

product: 곱하기 기호로 표기하는 것>> AND로 게이트로 연결되는 회로

sum: 더하기기호로 표기하는 것 >> OR로 게이트로 연결되는 회로

 

ProducTerm은 AND연산으로 구성되어있는 항을 의미합니다. 

 

 

25-1. Minterm은 Product Term의 일종입니다.

Product Term의 조건중 일부를 만족하면 Minterm이라고 합니다.

 

 

그럼 그 조건이 뭐냐? 모든 입력 변수들이 하나씩은 다 포함되어 있어야 합니다. 

 

 

 

어떤 입력x,y,z가 있다고 합시다. 

입력 x,y,z를 사용해서 만들 수 있는 여러 가지 product Term이 있습니다. 

예를 들면 x/yz와 같은 productTerm 있고,

x/z도 하나의product Term입니다.

그중에서  x/yz라고 하는 것이 Minterm에 속합니다. 

 

모든 입력 변수가 포함되어있는 ProductTerm을 Minterm이라고 합니다.

x/z 같은 경우 Product Term이지만 y변수가 없기 때문에  Minterm이 될 수 없습니다. 

아래 그림과 같이 나타낼 수 있겠습니다. 

 

 

 

 

변수의 개수를 셀 때 y,/y을 다른 거라고 생각하고 count하지 않았나?

정리: ProducTerm 중에서 모든 변수가 한 번씩 포함되어있다면 Minterm이라고 한다. 

 

 

25-2. Maxterm 은 sum Term의 일종입니다. 

 

x, y, z라는 입력 변수를 가질 때

Sumterm으로 만들어지는 여러 항이 있을 것입니다. 

예를 들면 x+y+z , x+/y 등등이 있겠습니다. 

그중 특별한 조건을 만족하는 경우에 Maxterm에 포함됩니다.

 

 

그 특별한 조건은 모든 변수가 한 번씩 포함되어있는 Term을 말합니다. 

예를 들어서  x+y+z,/x+y+z 와 같은 항을 말합니다. 

 

 

 

Q:

입력 변수가 x, y, z일 때 MinTerm의 개수는?

 

8개입니다.

Q2

입력 변수가 x, y, z일 때 MaxTerm의 개수는?

 

8개입니다. 

Q3

입력 변수가 w, x, y, z일 때 Maxterm의 개수는?

 

16개 가 되겠습니다. 

 

위의 기본개념들이 잘 이해되어야 다음 내용들을 이해할 수 있겠습니다. 

 

 

 

 

26. Sum of Producs를 알아보겠습니다. 

이는 Sum of Product terms와 같은 말입니다.

약어로 SOP라고 이야기할 것입니다. 

 

ProductTerm의 Sum꼴로 되어있는 경우를 말합니다. 

AB, CD, CE는 모두 Product Term입니다. 

이것들을 OR Gate로 연결한 아래와 같은 회로를 SOP라고 합니다. 

 

SOP와 같은 방식으로 식을 구현하려면 AND들이 필요합니다. 

1st STAGE는 AND게이트로 구성된다는 이야기입니다. 

2nd Stage는 OR게이트로 구성됩니다. 

그림

 

 

 

 

 

즉, 복수개의 ANDGate와 

단일의 OR게이트로 연결되는 회로를 말합니다. 

 

27. 이것과 상반되는 Product of Sum이라는 개념도 있습니다. 

Product of Sum Terms 이 되겠습니다. 

Sum Term들의 곱이라고 봅니다. 

줄여서 POS라고 부릅니다. 

앞으로 굉장히 많이 보게 될 것입니다. 

 

 

X라는 것도 하나의 SumTerm

/Y+Z 도 하나의 SumTerm

X+Y+/Z 도 하나의 SumTerm

각각 SumTerm들의 곱입니다. 

SumTerm들의 AND로 표기되어있으므로 Product of Sum Term(Product of Sums)라고 부릅니다. 

 

 

 

1st stage에 OR 게이트가 여러 개

2nd Stage에 AND게이트가  한 개 나옵니다. 

 

 

 

28. 말로만 듣던 민텀

ProductTerm 중에서 어떤 조건을 만족하면 Minterm이라고 하였습니다. 

모든 입력 변수가 반드시 한번 나타나야 합니다. 

(not 이 있어도 되고 없어도 됩니다.>> X와 /X 중 하나만 등장해도 X가 등장했다고 생각.)

 

두 번째 줄의 설명은 초반에 퀴즈로 무슨 말인지 알 수 있을 것입니다. 

 

 

 

 

 

8개의 Minterm이 있습니다. 

 

입력 변수가 X, Y, Z인 경우에 대해 가능한 입력을 작성해보았습니다. 

각 입력에 대해서  Minterm을 입력 변수로 매핑해보겠습니다. 

근데 어떤 매핑 룰을 적용할 거라면

값이 0이면 Xnot을 붙이고, 1이면 not을 붙이지 않습니다. 

 

아래와 같이 작성할 수 있습니다. 

 

그리고 Minterm을 m0부터 m7까지 맵핑시킬 수 있습니다. 

 

 

 Minterm이 /X /Y/Z이면 m0에서 m7은 다음과 같은 값을 가집니다. 

m0일 때만 1이 출력됩니다. 

반대로 생각해보면  재밌는 성질이 생기는데

/X,/Y,/Z은 특정한 영역에서만 1이 되는 것입니다.

 

특정한 입력이 뭐냐면 잘 생각해보면 x가 0이고 y가 0이고 z가 0일 때만 1이 됩니다.

AND로 연결되어있기 때문에 입니다. 

 

 

하나 더 해보겠습니다.

/X/YZ의 출력 값을 알아보겠습니다. 

X가 0이고, Y가 0이고 Z가 1일 때만 1이 됩니다. 나머지는 0이 됩니다. 

세 개가 AND게이트로 연결되어있기 때문입니다. 

 

위와 같이 생각해서 나머지 Minterm도 채워보면 아래와 같은 표가 완성됩니다. 

 

 

대각선에서만 해당 값이 1인 것을 알 수 있습니다. 

 

 

 

29. 이러한 PROPERTY를 이용해서 재밌는 것을 해보려고 합니다. 

 

 

왼쪽에 진리표가 있습니다.

입력이 X, Y, Z이고 출력은 F인 진리표입니다. 

위와 같이 진리표가 주어졌을 때 이를 만족시키는 회로를 구하는 것이 문제입니다. 

 

 

불대수가 있으면 그것을 가지고 회로를 그리는 방법, 진리표 채우기를 공부했습니다. 

그때 진리표가 있을 때 회로를 그리거나, 수식을 찾는 방법을 나중에 공부해본다고 했는데

그것을 지금 해보려고 합니다. 

 

 

그렇게 하기 위해서 Minterm을 알아야 합니다. 

출력 F는 어떻게 작성하냐면 진리표가 있을 때 출력 F를 입력의 함수로 적을 수 있습니다. 

값이 1인 녀석을 Minterm의 Sum으로 작성할 수 있습니다. 

조금  헷갈리니까 바로 예시를 들어서 설명해보도록 하겠습니다. 

진리표에서 출력 값이 1인 행들을 작성해줍니다. (행의 숫자는 0부터 시작합니다.)

 

왼쪽 수식

입력값이 X, Y, Z로 3개인 논리함수를

F 또는 F(X, Y, Z)로 작성할 수 있습니다. 

앞에서 배운 심벌을 맵핑하는 것을 이용하면

 

 

오른쪽과 같은 수식으로도 나타낼 수 있습니다. 

의미: Minterm값이 1인 것들의 Sum으로 나타내겠다

기호로는 다음과 같이 작성할 수 있습니다. 

F=m2+m3+m5+m7로 작성할 수 있습니다. 

 

 

 

진리표에서 다음행을 예로 들어 설명해보겠습니다. 

m2에 대응하는 입력값들을 작성해주면 됩니다. 

(진리표에서 3번째 행의 출력을 구성하는 입력값을 작성)

3,5,7번째 출력 값을 이루는 입력값들을 작성해주면 됩니다.

그런뒤에 OR게이트로 연결하면 됩니다. 

 

 

 

수식을 불대수항등식을 이용하여 간단하게 나타내면 됩니다. 

 

아래사진에서

두번째줄의 항이 가장많은 논리함수를 Sum of Minterm이라고 합니다.

맨마지막줄에 있는 논리함수를  SOP(Sum of product,Sum of product terms)로 최적화했다고 말합니다.

요약하자면 

출력을 1로 만드는 입력 세트들을 Minterm으로 만들 수 있습니다. 

이 Minterm 들을 sum으로   연결하면 됩니다.

그러면 논리 함수 F가 완성됩니다. 

 

왜 그런지 생각해봅시다.

F는 Minterm의 Sum형태로 주어져 있습니다. 

 

F는 언제 1이 될 수 있을까요? (Hint: OR로 연결되어있다. )

>> F는 term 중 하나의 출력이 1일 때 1이 될 수 있습니다. 

 

 

조금 더 풀어서 이야기한다면 (위 사진의 두번째줄 Sum of Minterm에서)

(첫 번째 항이 1이 되려면)

X는 0, Y는 1, Z는 0 이 되어야 합니다. 

 

(두 번째 항이 1이 되려면)

X는 0, Y는 1, Z는 1 이 되어야 합니다.

 

(세 번째 항이 1이 되려면)

X는 1, Y는 0, Z는 1 이 되어야 합니다.

 

(네 번째 항이 1이 되려면)

X는 1, Y는 1, Z는 1 이 되어야 합니다.

 

F는 첫 번째, 두 번째, 세 번째, 네 번째 항이 1이면 1이다.라는 이야기입니다. 

다시 말해서 위의 4가지 조건들 중 하나를 만족하면 1이 된다는 것입니다. 

 

지금 한 이야기가 진리표 이야기입니다.

위의 4가지와 같은 입력값일때 출력값을 진리표에서 찾아보면 그 행의 출력 값이 1인 것을 알 수 있습니다.

 

! 진리표에서 담고 있는 정보와 수식의 의미가 같음을 알 수 있습니다. 

이해는 한번 하면 되고 기계적으로 연습해보면 됩니다. 

 

 

 

불대수를 이용해 최적화까지 한 논리 함수를 이용하여 회로를 그리면 다음과 같습니다.

 

 

※ 하나 기억해야 할 것

F 수식이 있는데 sum of Minterm에 해당하는 것은??

(불대수로 항등식으로 최적화하는 과정 중에 있는 수식 3가지 그림 첨부)

 

 

다음의 진리표를 주고 Sum of Minterm으로 표현하시오. 하는 문제가 있습니다. 

 

답은 1번만 답이 됩니다. 

문제가 Sum of Minterm으로 표현하라고 했으므로

Minterm의 의미를 생각하면 입력 변수가 각각 하나씩 있어야 합니다. 

 

2,3번의 경우에는 Minterm이 아닙니다.

 

EX. 또 다른 문제에서 SumofProduct로 표현하라고 했다면 정답은 3번이 되겠습니다. 

3번이 SOP로 나타내었으면서 가장 간단하기 때문입니다. 

 

보통 진리표를 주고 회로를 구현해야 한다면

먼저 Sum of Minterm으로 표현한 다음에,그 식을 불대수항등식을 이용해 최적화한뒤,

SOP를 얻고 회로를 구현하면 되겠습니다. 

 

 

30-1. 비슷한 문제를 하나 풀어보도록 하겠습니다. 

위와 같이 진리표가 주어져 있습니다. 

입력은 X, Y, Z이고 출력이 E인 진리표가 있습니다. 

 

1) Sum of Minterm으로 나타내어 보고,

2) SOP로 최적화하고 (곱들의 합.)

3) 회로를 그려보시오

 

 

Sum of Minterm

 

답을 작성할 때는 맨 마지막 줄만 작성해야 합니다. 

진리표를 보면서 m0 출력 값을 작성하면  헷갈리기 때문에 위쪽에 입력값들을 파란색으로 작성해두었습니다.

 

 

SOP

 

 

회로

 

 

 

30-2. 조금 더 심화해서 다음 문제를 풀어보겠습니다. 

입력 변수가 많아지면 조금 더 복잡해질 뿐입니다. 

 

출력은 F이고 입력 변수로 WXYZ가 있다고 알려주는 것입니다. 

 

 

Sum of Minterm으로 나타내고 Sum of product로 최적화해보라는 문제입니다. 

0000부터 1111까지

출력될 것입니다..

0가 0000이라면

,,, 0 ,2,4,6,13,15를 이진수로 나타내면 되겠구나.

그리고 그 이진수에 대응하는 게이트를 찾으면 된다. 

그것을 불대수 항등식을 이용해 최적화하면 SOP가 되고 

SOP를 이용해서 회로를 쉽게 그릴 수가 있겠습니다. 

 

 

다음 포스팅에서 풀이를 하도록 하겠습니다.