Lecture 9(Logic simplication & SOP & POS)

Boolean Analysis of Logic Circuits (Boolean을 이용한 간결한 표현) 

Boolean algebara는 Logic circuit을 표현하는데 간결함을 줄 수 있습니다.

따라서 복잡한 Logic circuit도 인풋의 정보를 통해 손쉽게 아웃풋을 결정할 수 있습니다.

예를 들어 X = A(B + CD) 같은 논리회로가 있다고 가정합니다.

변수가 A, B, C, D이므로 2^4 = 16 가지의 조합이 생길 수 있습니다.

먼저 A(B + CD)가 HIGH(1)를 출력하기 위해서는 

1) A가 1이고 (B + CD) 가 1이면 됩니다.

2) 더 깊숙히 들어가서 (B + CD)가 1이 되려면 B = 1 or CD = 1  이 되거나 B와 CD가 둘다 1이 되야합니다.

3) 더 깊숙히 들어가서 CD가 1이 되려면 C와 D 모두 1이 되어야 합니다.

이러한 과정을 모두 종합하면 A(B + CD)가 1이 되기 위해서는 

1) A와 B가 모두 1이면 C 와 D는 상관없이 1이 됩니다.

2) A와 C와 D가 1이면 B는 상관없이 1이 됩니다.

 

Logic Simplication Using Boolean Algebra 

저번 Lecture에서 배운 Boolean Algebra를 이용하여 Logic 수식을 간편화 합니다.

ex) AB + A(B + C) + B(B + C)

 = AB + AB + AC + BB + BC (분배 법칙)

 = AB + AB + AC + B + BC (B = BB)

 = AB + AC + B + BC (AB + AB = AB)

 = AB + AC + B (B + BC = B)

 = B + AC (B + AB = B)

 

ex) [AB'(C + BD) + A'B']C

  = (AB'C + AB'BD + A'B')C      (분배 법칙)

  = (AB'C + A·0·D + A'B')C       (BB' = 0)

  = (AB'C + 0 + A'B')C            

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

  = AB'CC + A'B'C                  (분배 법칙)

  = AB'C + A'B'C                    (CC = C)

  = B'C(A + A')                      (결합 법칙)

  = B'C · 1                            (A + A' = 1)

  = B'C

 

ex) AB'C(BD + CDE) + AC'

  = AB'CBD + AB'CCDE + AC'       (분배 법칙)

  = AB'CDE + AC'                      (A 0 = 0) (CC = C)

  = AB'CDE + AC'(1 + B'DE)         (1 + A = 1) 이므로 임의로 (1 + B'DE)를 만들어 줍니다.

  = AB'CDE + AC' + AB'C'DE        (분배 법칙)

  = AB'DE(C + C') + AC'              (결합 법칙)

  = AB'DE + AC'                        (C + C' = 1)

  = A(B'DE + C')                       (결합 법칙)

---

Standard Forms of Boolean Expressions (Boolean 표현 방식)

모든 Boolean 표현은 2가지 방식으로 변환 할 수 있습니다.

1) The sum-of-produces form (SOP)

2) The product-of-sums form (POS)

 

Domain 이란 개념이 나오는데 쉽게 말해 변수의 집합이라 이해하면 편합니다.

변수의 보수가 다 취해졌거나 기본 변수 둘중 하나가 들어갑니다.

ex) A'B +A'BC' 의 도메인은 {A, B, C} 입니다.

    ABC' + CD'E + B'CD 의 도메인은 (A, B, C, D, E} 입니다.

---

The Sum-of-Products (SOP) Form

두개 이상의 변수가 Boolean addition에 의해 합쳐진 형태입니다.

오직 1개로 된 변수만 존재가능합니다 (AB(O) , (A + B)(X)) 

보수를 표현할때, 변수 2개를 묶는 보수는 존재하지 못합니다. ((AB)'(X)  , A'B'(O))

 

AND / OR Implementation of an SOP Expression

각 변수는 AND 로 만들고 변수의 합은 OR 로 만듭니다.

ex) AB + BCD + AC

 

Conversion of a General Expression to SOP Form (SOP Form으로 변환)

항상 완성된 변수는 1개이고 덧셈 형식이어야 합니다.

ex) A(B + CD) = AB + ACD

ex) AB + B(CD + EF) = AB + BCD + BEF

 

The Standard SOP Form

Domain에 모든 변수가 하나의 product로 존재하는 것입니다.

ex) Domain = {A, B, C, D}  

AB'CD + ABC'D' + A'BCD는 각 product 마다 Domain에 있는 모든 변수가 표함되 있습니다.

반면에 AB + ABC + ABCD는 각 product마다 모든 변수가 포함되어 있지 않으므로 Standard sop form 이 아닙니다.

 

Converting Product Terms to Standard SOP (Non-standard SOP를 Standard SOP로 바꾸기)

Non-standard SOP를 Standard SOP로 바꿀러면 이전에 배운 Boolean Algebra의 법칙을 사용합니다.

그중 rule 6(A + A' = 1)를 사용하면 됩니다.

예를 들어 Domain{A, B, C, D} 가 있다고 하면 

ABC는 Non-standard SOP입니다. 이를 Standard SOP로 바꾸려면 ABC에 1을 곱해줍니다.

ABC = ABC(D + D') = ABCD + ABCD' 입니다.

 

ex) AB'C + A'B' + ABC'D 

ABC'D 는 이미 Standard form이므로 가만히 둡니다.

1) AB'C = AB'C(D + D')

          = AB'CD + AB'CD'

2) A'B' = A'B'(C + C')

         = A'B'C + A'B'C'

         = A'B'C'(D + D') + A'B'C'(D + D')

         = A'B'CD + A'B'CD' + A'B'C'D + A'B'C'D'

따라서 AB'C + A'B' + ABC'D = AB'CD + AB'CD' + A'B'CD + A'B'CD' + A'B'C'D + A'B'C'D' + ABC'D

 

Binary Representation of a Standard Product Term (Standard Product를 2진법으로 표현)

Standard product는 각각 1을 의미합니다.

따라서 AB'CD' 가 1이 되려면 A = 1, B' = 1, C = 1, D' = 1 이 되어야합니다.

이를 이진수로 표현하면 A = 1, B = 0, C = 1, D = 0 입니다.

ex) Determine the binary values for the following sop expression (ABCD + AB'C'D + A'B'C'D')

1) ABCD가 1이 되려면 A = 1, B = 1, C = 1, D = 1 입니다.

2) AB'C'D 가 1이 되려면 A = 1, B = 0, C = 0, D = 1 입니다.

3) AB'C'D' 가 1이 되려면 A = 0, B = 0, C = 0, D = 0 입니다.

---

The Product-of-Sums (POS) Form

두개 이상의 변수가 Boolean addition에 의해 곱해진 것입니다.

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

POS Form에서 마찬가지로 두개 이상의 보수를 묶지 못합니다.

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

 

The Standard POS Form

Domain에 모든 변수가 하나의 product로 존재하는 것입니다.

ex) Domain = {A, B, C, D}  

(A' + B' + C)(A + B + C)(A' + B' + C)는 각 product 마다 Domain에 있는 모든 변수가 표함되 있습니다.

각 Product에 Domain안에 있는 변수가 모두 들어가 있으면 Standard POS Form 입니다.

 

Converting a SUM Term to Standard POS (Non-standard POS를 Standard POS로 바꾸기)

Booleand Algebra 법칙 중에서 rule 8(A · A' = 0) 과 rule 12(A + BC = (A + B)(A + C)) 를 사용합니다.

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

(A' + B' + C' + D)는 이미 Standard POS form 이므로 가만히 둡니다.

1) (A + B' + C) = A + B' + C + DD'(0) 

                    = (A + B' + C + D)(A + B' + C + D')

2) (B' + C + D') = AA'(0) + B' + C + D'

                     = (A + B' + C + D')(A' + B' + C + D)

따라서 (A + B' + C)(B' + C + D')(A + B' + C' + D) 

= (A + B' + C + D')(A' + B' + C + D) + (A + B' + C + D')(A' + B' + C + D) +(A + B' + C' + D) 입니다.

  

Binary Representation of a Standard Sum Term (Standard Sum term을 2진수로 표현)

Standard Sum term은 각각 0을 의미합니다.

따라서 A + B' + C + D'가 0이 되려면 A = 0, B' = 0, C = 0, D' = 0 이 되어야합니다.

이를 2진수로 표현하면 A = 0, B = 1, C = 0, D = 1이 됩니다.

ex) Determine the binary value ((A + B + C + D)(A + B' + C' + D)(A' + B' + C' + D'))

1) (A + B + C + D)가 0이되려면 A = 0, B = 0, C = 0, D = 0 이 되어야 합니다.

2) (A + B' + C' + D)가 0이 되려면 A = 0, B = 1, C = 1, D = 0 이 되어야 합니다.

3) (A' + B' + C' + D') 가 0이되려면 A = 1, B = 1, C = 1, D = 1이 되어야 합니다.

---

Converting Standard SOP to Standard POS (SOP를 POS로 바꾸기)

1) 먼저 SOP형식으로 주어진 수식을 2진수로 표현해줍니다.

2) 1)에서 나온 2진수들을 제외한 2진수들을 써줍니다.

3) 2)에서 나온 2진수를 POS로 바꿔줍니다.

 

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

1) 000, 010, 011, 101, 111 (각 SOP형식을 2진수로 표현해줍니다.)

2) 001, 100, 110 ( 1)에서 나온 2진수 중에서 안나온 수를 써줍니다.

3) (A + B + C')(A' + B + C)(A' + B' + C)   (  2)에서 나온 수를 POS형식으로 만들어 줍니다)