3. 게이트레벨 최소화

Karnaugh Map을 이용한 논리함수 간소화 방법 논리함수식을 간소화하기 위해 체게화된 방법 K-map 을 이용하여 함수 간소화 방법 수평, 수직으로 인접한것들끼리 묶는다 겸치는부분이 있더라도 가능하면 크게 묶는다 1, 2, 4, 8, … , 2ⁿ 개씩 묶으면 각각 0, 1, 2, 3, … n 개의 literal수를 줄일수 있다 “1” 을 묶으면 f 에대한 표현식, “0” 을 묶으면 f′에 대한 표현식을 얻을수 있다 Sum of Product : “1”을 묶어 f 에 대하여 표현한 식 입력수가 7 개 이상이면 다루기 어렵다

게이트-레벨 최소화 – 2-입력 맵 y y y 1 1 1 x x x y 1 x y y y 1 1 1 x x x 1 1 1 x x x y 1 x′y′ (m0) x′y (m1) xy′ (m2) Xy (m3) x xy’ + xy = x(y+y’) = x x’y + xy = y(x+x’) = y x’y’ + x’y = x’(y’+y) = x’ y y y 1 1 1 x x x x’y’ + xy’ = (x’+x)y’ = y’ x + x’ = 1 or y + y’ = 1

게이트-레벨 최소화 – 2-입력 맵 x y f 1 1 1. Bool 대수 이용 2. map 이용 y 1 1. Bool 대수 이용 2. map 이용 y 1 f = x’y + xy’ + xy = x’y + x(y’+y) = x’y + x = (x’+x)(y+x) = x+y x f = x + y

게이트-레벨 최소화 – 3-입력 맵 y’ y x’ x z 00 01 11 10 1 yz x x′y′z’ (m0) x′y′z x′y′z’ (m0) x′y′z (m1) x′yz (m3) x′yz’ (m2) 1 xy′z’ (m4) xy′z (m5) xyz (m7) xyz’ (m6) yz x x’ x z

게이트-레벨 최소화 – 3-입력 맵 yz yz yz x x x yz yz yz x x x 00 01 11 10 1 00 01 1 00 01 11 10 1 00 01 11 10 1 x x x yz yz yz 00 01 11 10 1 00 01 11 10 1 x 00 01 11 10 1 x x

게이트-레벨 최소화 – 3-입력 맵 f = ∑(3 ,5 ,6 ,7) x y z f 1 1 f = xy + yz + xz yz 1 yz 00 01 11 10 1 x f = xy + yz + xz

게이트-레벨 최소화 – 3-입력 맵 f = ∑(2, 3, 4 ,6 ,7) x y z f 1 1 f = y + xz’ yz x 1 yz 00 01 11 10 1 x f = y + xz’

게이트-레벨 최소화 – 3-입력 맵 f = ∑(1, 2, 4, 7) (ex) f = A’C+A’B+AB’C+BC 1 BC A 00 01 11 10 1 A F = A’B’C+A’BC’+AB’C’+ABC = A’(B’C+BC’)+A(B’C’+BC) = A’(B C)+A(B ᆞ C) = A’(B C)+A(B C)’ = A (B C) = A B C + + + + + + +

게이트-레벨 최소화 – 4변수 맵 y’ y yz 00 01 11 10 wx w’ x’ w z (m0) (m1) (m3) w’x’y’z’ (m0) w’x’y’z (m1) w’x’yz (m3) w’x’yz’ (m2) w’xy’z’ (m4) w’xy’z (m5) w’xyz (m7) w’xyz’ (m6) wxy’z’ (m12) wxy’z (m13) wxyz (m15) Wxyz’ (m14) wx’y’z’ (m8) wx’y’z (m9) wx’yz (m11) (m10) wx w’ x’ w z

게이트-레벨 최소화 – 4변수 맵 yz yz yz wx wx wx yz yz yz wx wx wx 00 01 11 10 00

게이트-레벨 최소화 – 4변수 맵 f = A’B’C’+B’CD’+A’BCD’+AB’C’ yz yz yz 00 01 11 10 00 01 11 10 00 01 11 10 wx wx wx f = A’B’C’+B’CD’+A’BCD’+AB’C’ f = ∑(0,1,2,4,5,6,8,9,12,13,14) yz yz 00 01 11 10 wx 00 01 11 10 wx

게이트-레벨 최소화 – 4변수 맵(ex) f = ∏(3,4,6,7,11,12,13,14,15) yz yz 00 01 11 10 wx wx 00 01 11 10

게이트-레벨 최소화 – 5변수 맵 000 001 011 010 110 111 101 100 00 A’B’C’D’E’ (m0) A’B’C’D’E (m1) A’B’C’DE (m3) A’B’C’DE’ (m2) A’B’CDE’ (m6) A’B’CDE (m7) A’B’CD’E (m5) A’B’CD’E’ (m4) 01 A’BC’D’E’ (m8) A’BCDE’ (m9) A’BC’DE (m11) A’BC’DE’ (m10) (m14) A’BCDE (m15) A’BCD’E (m13) A’BCD’E’ (m12) 11 ABC’D’E’ (m24) ABC’D’E (m25) ABC’DE (m27) ABC’DE’ (m26) ABCDE’ (m30) ABCDE (m31) ABCD’E (m29) ABCD’E’ (m28) 10 AB’C’D’E’ (m16) AB’C’D’E (m17) AB’C’DE (m19) AB’C’DE’ (m18) AB’CDE’ (m22) (m23) AB’CD’E (m21) AB’CD’E’ (m20) CDE AB

게이트-레벨 최소화 – 5변수 맵 CDE 000 001 011 010 110 111 101 100 00 01 11 10 CDE 000 001 011 010 110 111 101 100 00 01 11 10 AB AB CDE CDE 000 001 011 010 110 111 101 100 00 01 11 10 000 001 011 010 110 111 101 100 00 01 11 10 AB AB

게이트-레벨 최소화 – 5변수 맵 CDE 000 001 011 010 110 111 101 100 00 01 11 10 000 001 011 010 110 111 101 100 00 01 11 10 CDE AB AB CDE CDE 000 001 011 010 110 111 101 100 00 01 11 10 000 001 011 010 110 111 101 100 00 01 11 10 AB AB

게이트-레벨 최소화 – 5변수 맵 f = ∑(0,2,4,6,9,13,21,23,25,29,31) CDE 000 001 011 010 110 111 101 100 00 1 3 2 6 7 5 4 01 8 9 11 10 14 15 13 12 24 25 27 26 30 31 29 28 16 17 19 18 22 23 21 20 000 001 011 010 110 111 101 100 00 1 01 11 10 CDE AB AB f = A’B’E’ + BD’E+ACE

게이트-레벨 최소화 – 5변수 맵 f = ∑(0,2,4,6,9,11,13,15,17,21,25,27,29,31) 000 001 011 010 110 111 101 100 00 1 3 2 6 7 5 4 01 8 9 11 10 14 15 13 12 24 25 27 26 30 31 29 28 16 17 19 18 22 23 21 20 CDE CDE 000 001 011 010 110 111 101 100 00 1 01 11 10 AB AB f = A’B’E’ + BD’E+ACE

게이트-레벨 최소화 – 5변수 맵 Ex 3-7) 다음 Boole 함수를 간략화하라. F(A,B,C,D,E)=Σ(0,2,4,6,9,13,21,23,25,29,31) F = A'B'E' + BD'E + ACE

합의 곱(Product of Sum) 간략화 (1) “0” 을 묶어 f’ 의 Sum of Product 를 구한 후 (2) f’ 의 보수를 취하여 f 를 구한다 yz f = ∑(0,1,2,5,8,9,10) wx 00 01 11 10 yz wx 00 01 11 10 1 Product of Sum f’ = AB + CD + BD’ f = (f’)’ f = (A’+B’)(C’+D’)(B’+D) Sum of Product f = B’C’ + B’C’ + A’C’D

Don’t-Care 조건 논리값이 규정(“0” or “1”) 되어있지 않은 Minterm의 집합 f = ∑(1,3,7,11,15) d = ∑(0,2,5) yz yz wx 00 01 11 10 x 1 X wx 00 01 11 10 x 1 X or f = yz + w’x’ f = yz + w’z

Don’t-Care 조건 f = ∑(1,3,6,7,11,15) d = ∑(4,5,14) f = w’x + yz + w’z 00 01 11 10 1 X wx 00 01 11 10 1 X f = w’x + yz + w’z f = yz + xy + w’z

Don’t-Care 조건(ex:7-Segment Display) B8 B4 B2 B1 1 Don’t-Care 조건

NAND와 NOR의 구현 AND 게이트의 구현 OR 게이트의 구현 ((xy)’)’ = xy ((x+y)’)’ = x+y Digital 회로는 대부분 NAND/NOR/NOT 게이트로 구성 NAND/NOR/NOT 게이트를 digital logic family 의 universal gate 라 함 AND 게이트의 구현 OR 게이트의 구현 ((xy)’)’ = xy ((x+y)’)’ = x+y (x’+y’)’ = xy (x’y’)’ = x+y

NAND와 NOR의 구현 = = (xyz)’ x’ + y’ + z’ = (xyz)’ (x + y + z)’

NAND회로의 구현 [방법 1] 게이트의 변환을 이용 (ex) [방법 1] f = AB + CD+ E

NAND회로의 구현 1 f = x’y’z’ + xyz’ = ((x’y’z’+xyz’)’)’ [방법 2] “1”를 묶어 f의 sum of product 를 구한후, f에 보수를 두번 취한다 (ex) f = ∑(0, 6) yz 00 01 11 10 1 x f = x’y’z’ + xyz’ = ((x’y’z’+xyz’)’)’ = ((x’y’z’)’(xyz’)’)’

NAND회로의 구현 f’ = x’y + xy’+z = ((x’y+xy’+z)’)’ = ((x’y)’(xy’)’(z)’)’ [방법 3] “0” 을 묶어 f’의 sum of product 를 구한후, 다시 보수를 두번 취하여 f’ 에 대한 NAND 회로로 구현한후, 출력에 NOT 게이트를 연결 yz 00 01 11 10 1 x f’ = x’y + xy’+z = ((x’y+xy’+z)’)’ = ((x’y)’(xy’)’(z)’)’

NAND회로의 구현 (ex) f = ∑(0, 2, 4) [방법 2] [방법 3] yz yz x x 00 01 11 10 1 [방법 2] [방법 3] yz yz 00 01 11 10 1 x 00 01 11 10 1 x

NAND회로의 구현 [방법 1] 게이트의 변환을 이용

NAND회로의 구현 f’ = x’y+xy’+z (f’)’ = (x’y+xy’+z)’ = (x+y’)(x’+y)z’ [방법 2] “0”를 묶어 f’의 sum of product 를 구한다 f’에 보수를 취하여 f를 구한후, f에 보수를 두번 취한다 (ex) f = ∑(0, 6) yz x 00 01 11 10 1 f’ = x’y+xy’+z (f’)’ = (x’y+xy’+z)’ = (x+y’)(x’+y)z’ ((f)’)’ = (((x+y’)(x’+y)z’)’)’ = ((x+y’)’+((x’+y)’+z)’

NAND회로의 구현 1 f = x’y’z’+xyz’ f’ = (x’y’z’+xyz’)’ = (x’y’z’)’(x+y+z’)’ [방법 3] “1”를 묶어 f의 sum of product 를 구한 후, f에 보수를 취하여 f’ 에 대한 NOR 회로로 구현 후 출력에 NOT 게이트를 연결한다 yz 00 01 11 10 1 x f = x’y’z’+xyz’ f’ = (x’y’z’+xyz’)’ = (x’y’z’)’(x+y+z’)’ = (x+y+z)(x’+y’+z) = ((x+y+z)’+(x’+y’+z)’)’

Exclusive-OR 함수 패리티의 생성과 검사 P = x y z

Exclusive-OR 함수 C = x y z P