Lecture 10 (SOP, POS, 카르노 맵 간소화)

Boolean Expressions and Truth Tables 

모든 standard Boolean Expression들은 truth table로 전환가능합니다.

또한 standard SOP 또는 POS expression들은 truth table로 결정될 수 있다.

 

Converting SOP Expressions to Truth Table Format (SOP 를 Truth Table로 바꾸기)

sop expression은 단 한개의 product라도 1이면 1이 됩니다.

ex) A'B'C + AB'C' + ABC 를 Truth Table로 바꾸기

먼저 sop expression을 2진법으로 바꾸어 줍니다.

따라서 A'B'C = 001, AB'C' = 100, ABC = 111이 됩니다.

그러므로 입력 변수 ABC가 001, 100, 111 만 출력이 1이 되고 나머지 경우에는 0이 됩니다.

ABC|  X

000 |  0

001 |  1

010 |  0

011 |  0

100 |  1

101 |  0

110 |  0

111 |  1

 

---

Converting POS Expressions to Truth Table Format (POS 를 Truth Table 로 바꾸기)

pos expression은 단 한개의 sum term이 1개라도 0이면 0입니다.

ex) (A + B + C)(A + B' + C)(A' + B + C') 를 Truth Table로 바꾸기

먼저 pos expression을 2진법으로 바꾸어 줍니다.

따라서 (A + B + C) = 000, (A +B' + C) = 010, (A' + B + C') = 101 이됩니다.

그러므로 입력변수 ABC가 000, 010, 101 만 출력이 0이되고 나머지 경우에는 1이 됩니다.

ABC| X

000 | 0 

001 | 1

010 | 0

011 | 1

100 | 1

101 | 0

110 | 1

111 | 1

---

Determining Standard Expressions from a Truth Table(Truth Table로 부터 standard expression 결정)

Truth Table로부터 standard SOP, POS expression을 결정할 수 있습니다.

ex)

    Inputs       Output

A    B     C        X

0    0     0         0

0    0     1         0

0    1     0         0

0    1     1         1

1    0     0         1

1    0     1         0

1    1     0         1

1    1     1         1

위의 표는 Domain(A, B, C)에 해당하는 Truth Table입니다.

여기서 Standard SOP 는 아웃풋이 1인 부분을 찾는 것입니다.

따라서 SOP는 011, 100, 110, 111 즉, (A'BC) + (AB'C') + (ABC') + (ABC) 가 됩니다.

Standard POS는 나머지 부분 즉, 아웃풋이 0인 부분을 찾는 것입니다.

따라서 POS는 000, 001, 010, 101 즉, (A + B + C)(A + B + C')(A + B' + C)(A' + B + C') 가 됩니다. 

---

The Karnagh Map (카르노 맵)

카르노 맵은 매우 쉽게 Boolean expression을 간단화 시키는 도구입니다.

카르노 맵은 각 cell이 2형식을 나타내는 2차원 배열의 모습입니다.

변수의 개수에 따라 cell의 수가 정해집니다. 

만약 변수가 3개라면 2^3 = 8 즉, 8개가 필요하고 변수가 4개라면 2^4 = 16개가 됩니다.

---

The 3-Variable Karnaugh Map (3개의 변수 카르노 맵)

3개의 변수 카로노 맵은 총 8개의 cell이 필요합니다.

그림에서 보다시피 변수 3개의 카르노 맵입니다.

카르노 맵에서 행은 변수 A, B가 차지하고 열 부분은 C가 차지합니다.

각 행과 열이 만나는 곳에서 표시를 해주면 됩니다.

 

 

 

 

 

 

 

 

The 4-Variable Karnaugh Map (4개의 변수 카르노 맵)

4개의 변수 카르노 맵은 총 16개의 cell이 필요합니다.

그림에서 보다시피 변수 4개의 카르노 맵입니다.

카르노 맵에서 행은 변수 A, B가 차지하고 열부분은 C, D가 차지합니다.

각 행과 열이 만나는 곳에서 표시를 해주면 됩니다.

 

 

 

 

 

---

Cell Adjacency (cell 접합)

 

나중에 카르노 맵을 계산할 때 cell를 사각형 모형으로 묶어야 하는데 필요한 개념입니다.

여기서 주의할점이 위에 있는 행과 아래있는 행은 붙어있는 사각형입니다.

따라서 이 그림은 원형으로 생각하는게 좋습니다.

 

 

 

 

---

Karnaugh Map SOP Minmization (카르노 맵 SOP 최소화)

Standard SOP expression이 주어지면 2진수로 바꾸어 그대로 카르노 맵에 표시해주면 됩니다.

주어진 Standard SOP expression은 아웃풋이 1이므로 카르노 맵에 표시해주고 

나머지는 0입니다. 여기서 0은 표시를 생략해줍니다.

예를 들어 A'B'C + A'B'C + ABC' + AB'C'는 2진수로 바꾸면

001 + 001 + 110 + 100 입니다. 따라서 해당하는 카르노 맵에

표시해주면 됩니다.

나머지는 0이므로 표시를 생략해 줍니다.

 

 

만약 Nonstandard-SOP expression으로 주어지면 Standard-SOP로 바꿔주어서 그대로 똑같이

표시해 줍니다.

예를들어 A' + AB' + ABC' 가 주어지면

= A' + AB' + ABC'

= A'B + A'B' + AB' + ABC'

= A'BC + A'BC' + A'B'C + A'B'C' + ABC' + AB'C + AB'C'

= 011 + 010 + 001 + 000 + 110 + 101 + 100

 

 

 

Karnaugh Map Simplication of SOP Expressions (SOP를 카르노 맵 Simplication)

카르노 맵에서 사각형 grouping으로 묶어서 계산합니다.

먼저 group은 2의 거듭제곱 꼴로 묶어서 계산합니다. 1, 2, 4, 8....

group은 서로 겹치게 묶을 수 있습니다.

먼저 가장 크게 묶고 차례로 작아지게 묶습니다.

오른쪽 그림처럼 빨간색, 초록색, 파랑색 부분으로 묶을 수 있습니다. 

빨간색 group은 공통적으로 각 cell마다 B가 포함되어 있습니다.

파란색 group은 공통적으로 각cell마다 A'C가 포함되어 있습니다.

초록색 group은 공통적으로 각cell마다 C'D가 포함되어 있습니다.

이것을 모두 더하면 simplication이 이루어진것입니다.

 

ex) Minimize the following standard SOP expression using a Karnaugh Map

(AB'C + A'BC + A'B'C + A'B'C' + AB'C')

먼저 주어진 변수를 2진수로 바꿔줍니다. => 101, 011, 001, 000, 100 

이것으로 카르노 맵에 표시해줍니다.

그 다음 grouping으로 묶어 줍니다.

빨간색 group은 B' 한개만 공통적으로 각 cell마다 포함되어 있습니다.

파란색 group은 A'C 만 공통적으로 각 cell  마다 포함되어 있습니다.

따라서 B' + A'C 가 최종 답이 됩니다.

 

 

 

 

 

"Don't Care" Conditions

말 그대로 있어도 되고 없어도 되는 조건입니다.

예를 들어 BCD 코드에서는 1010, 1011, 1100, 1101, 1110, 1111 총 6개의 invalid 가 있습니다.

따라서 Don't care 도 똑같습니다. 오른쪽 진리표에서 보듯이

101, 110, 111은 X가 표시되어 있습니다. 

X가 Don't condition입니다. 

X는 1로 될수도 있고 0이 될 수 도 있습니다.

Grouping 하는거에 따라 달리질 수 있습니다.

따라서 맨 왼쪽에 카르노 맵처럼 할 수 있습니다.

 

 

 

ex) 1) Derive on SOP expression     2) Minmize the SOP expression

segment : 0, 2, 3, 5, 6, 7, 8, 9

진리표는 다음과 같습니다. 9위로는 Don't care condition 입니다.

카르노 맵은 오른쪽 그림과 같습니다.

최종 결과는 BD + B'D' + A + C 입니다.

 

 

 

 

 

 

 

 

Karnaugh Map POS Minimization (카르노 맵 POS 간소화)

방금전에 배운 SOP는 1을 카르노 맵에 표시해주었습니다.

반대로 POS는 0을 표시해줍니다.

ex) (A + B + C)(A + B' + C)(A' + B' + C)(A' + B + C')

이 sum term들을 2진수로 바꿔주면 000, 010, 110, 101 입니다.

 

 

 

 

 

 

 

Karnaugh Map Simplication of POS Expressions (카르노 맵에서의 POS 간소화)

ex) (A+B+C)(A+B+C')(A+B'+C)(A+B'+C')(A'+B'+C)

이것을 2진수로 나타내면 000, 001, 010, 011, 110

카르노 맵에서 Grouping을 해주어서 간소화 해주면

최종답은 A(B'+C) 가 됩니다.

=>AB' + AC

 

 

 

 

 

 

 

 

 

Converting Between POS and SOP (POS를 SOP로 SOP를 POS 바꾸기)

매우 쉽습니다.

설명보다 예시로 공부하는게 더 이해하기 쉽습니다.

먼저 (A'+B'+C+D)(A+B'C+D)(A+B+C+D')(A+B+C'+D')(A'+B+C+D')(A+B+C'+D) 가 POS 형식으로 주어졌을떄,

이것을 2진수로 바꾸면 1100, 0100, 0001, 0011, 1001, 0010이 됩니다.

이를 통해 먼저 POS로 바꿔줍니다. 

따라서 POS에서는 최종 답이 (B'+C+D)(B+C+D')(A+B+C') 이 됩니다.

그 다음 카르노 맵을 통해 처음 POS자리에 있던 0을 제외하고 빈칸에 1로 채워줍니다.

이것을 다시 Grouping 해주고 SOP로 바꿔줍니다.

최종답은 B'C'D' + AC + BC + BD 입니다