6 장부울함수의간소화
개요 모든입력과출력조건이동일한경우에는가능한한논리회로를간단하게구성 논리회로간소화혹은최적화 부울식의간소화 : term 을감소하거나 literal 를감소한다. term 은게이트의수, literal 은게이트의입력수를나타낸다. 논리회로의동작속도향상, 소비전력감소등효율적인논리회로구성가능 논리회로를간소화하는방법 논리회로자체를간소화하는방법 논리회로를부울함수로표현한후부울함수를간소화 부울대수의기본정리를이용하는방법 연속적인부울정리사용으로 trial and error () 드모르강의정리와합의곱을반복적으로수행 -> SOP 형식을유도 (2) SOP에서공통인수를찾고이를소거 카르노맵 (karnaugh map) 방법 도식적인방법으로 6 개정도의입력변수까지사용 2
6. 부울대수식의기본정리이용 예 ) 부울함수 = w'('+z) + w'(+'z) 를간소화한후논리회로비교 = w'('+z) + w'(+'z)= w'' + w'z + w' + w''z = w'' + w''z = w''(+z) = w'' Z(a,b,c) = m(2,3,7) = m 2 + m 3 + m 7 = a'bc' abc +a'bc + abc sum of minterms 3 input AND 3 개, 3inputOR 개 = a'bc' + a'bc + a'bc + abc = a'b(c'+c) + bc(a'+a) =a'b +bc <- sum of products, 2 input AND 2 개, 2inputOR 개 3
6.2 카르노맵 진리표를그림모양으로나타낸것이며벤다이어그램 (venn diagram) 을확장한것 여러형태의사각형으로된그림으로진리표의각항 ( 최소항또는최대항 ) 들은카르노맵의각한칸의사각형에나타냄 카르노맵의각칸에서수평또는수직방향으로인접한칸 (adjacent term) 은한변수의논리상태만서로다르다. 카르노맵에서인접항을 2,4,8,6 의단위로묶음으로써부울변수를,2,3,4, 개씩감소한다. 카르노맵에서의간소화과정. 논리회로를부울함수로표시- 기본적으로 SOM(POM) 으로표현 2. 진리표로나타낸다. 3. 카르노맵에진리표의각값을적합한칸에기입 4. SOP로최소화할때는 '' 로구성되는최대인접항으로묶고 POS로최소화할때는 '0' 으로구성되는최대인접항으로묶는다. 5. 각항들은중복되어묶일수있다. 6. 모든최소항은한번이상은묶여야한다. 7. 큰항의묶음에서남아있는변수들로간소화된부울식을구한다. 정규 () 및반전 (') 인변수가묶음내에존재하면그변수는식으로부터소거모든칸에나타나는같은변수는최종식에남는다보다큰 (0) 의묶음은더많은수의변수를소거시킨다. '' 로묶은함수는정규형이므로 SOP로바로구하여진다. '0' 으로묶은함수는보수형이므로그결과를반전하여 POS 형의정규함수를구한다. 4
2 변수의카르노맵 카르노맵 2 개의 2 진변수에대한 4 개의최소항구성 각최소항은하나씩 4 개의사각형에배치 3변수의카르노맵 '+ 3 개의 2 진변수에대한 8 개의최소항구성 =('+)= '+ =('+) = 'z+z =z('+) =z 2개항의묶음 (looping) -인접한 (0) 의쌍을묶어정규입력과반전입력형태의 개변수소거 ''z'+'z'+'z'+z' ='z'(+')+z'('+)=z'('+) = z' 5
3 변수카르노맵 예 ) = ''z + 'z' + 'z + 'z 을카르노맵을이용하여간소화하여라. SOP - '' 묶음 = ' + 'z POS형 - '0' 묶음 ' = 'z' + = ('z' + )' = (+z)('+') 예 ) 다음진리표에대한논리식의최소화된논리도를그려라. z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 카르노맵 'z' 'z z z' ' 0 0 0 간소화된부울식 = z' +' 논리도 6
3 변수카르노맵예 A BC A BC (ABC) (A,B,C)= (,2,3,5,7) (2357) = C+A'B = A C 양쪽끝은연결되어있다. = C 7
간소화예 f = m(3,5,6,7) = ab + bc + ac A BC a b c f 0 0 0 0 = AC + C 0 0 0 0 0 0 0 A BC 0 0 0 0 0 = A + 가능한크게묶는다. C a bc 00 0 0 0 세번중복하여묶었다. 8
4 변수카르노맵 4 변수의카르노맵 4 개의변수에대한 2 4 =6 개의최소항구성 z' z w'' 9
4 변수카르노맵최소화예 = C = B = A + C = AB + AB + CD + CD B + D = = AB + AD + AC + BC 0
CD AB 00 0 0 00 0 0 CD AB 00 0 0 00 0 0 = ABC + ABC + BCD + BCD = ABC + ABC + BD + CD CD AB 00 0 0 00 0 0 4변수맵에서 term의변수감소는 single = 4변수 (minterm) two s = 3변수 four s = 2 변수 eight s = 변수 = AC + AC + D siteen it s = 0 변수 ( 상수 )
예제다음진리표로부터카르노맵을작성하고간소화하여라. A B C D 0000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 CD AB 00 0 0 00 0 0 = A + BCD + BCD 2
다중해를가지는카르노맵 f = + + z f = + + z = AB + ABD + ACD = AB + ABD + BCD 3
논리식의카르노맵작성 논리식에서생략된부분을찾아서 Minterm 으로변경 f ( w,,, z) = w + w + wz + wz + wz = w( + )( z + z) + w( z + z) + w( + = m(, 3, 5, 6, 7,2,3,4,5) ) z + w( + ) z + wz z w 00 0 0 00 0 0 f ( w,,, z ) = w + wz + 4
예제다음논리식을카르노맵으로작성하고간소화. = AB + BC + ACD + ABD + ACD 최소항으로바꾸지않고간소화의반대방법으로카르노맵작성 AB BC ACD CD AB 00 0 0 00 0 ABD ACD 0 = AB + BC 5
5 변수카르노맵 w 0 3 2 4 5 7 6 2 3 5 4 8 9 0 w v 6 7 9 8 20 2 23 22 28 29 3 30 24 25 27 26 5 변수 K-map 32 개의 minterms z z v = w' + z w w + v'z + v'z' z z 6
예제 다음 5 변수논리함수를카르노맵을이용하여간소화 ( A, B, C, D, E) = m(4, 5, 6, 7, 9,,3,5,6,8, 27, 28,3) A=0 DE BC 00 0 0 00 A= 00 0 0 0 0 ( A, B, C, D, E) = ABC + ABE + ABCE + ABCDE + BDE 7
6 변수카르노맵 v 0 3 2 6 7 9 8 4 5 7 6 20 2 23 22 2 3 5 4 28 29 3 30 w 8 9 0 24 25 27 26 32 33 35 34 48 49 5 50 6 변수 K-map 64 개의 minterms = v'z vz+ u'v + vw + uvw''z + uv'w'z' u w 36 37 39 38 44 45 47 46 40 4 43 42 52 53 55 54 60 6 63 62 56 57 59 58 z z 8
6.3 Don't Care 출력이완전히정의되지않는경우의함수에대하여사용한다. 입력변수의조합들에대한출력값은어떠한입력값이라도무관 (don't care) 하게된다. ( 예 ) BCD 코드에서 00 ~ 은정의되지않는값 부울함수를더간단하게하는데사용한다. don't care 항은 d 로표시하고 K-map에서도이를사용한다. don't care가있는논리함수의표현 ( 예 ) 함수 를 SOM과 don't care 혹은 POM과 don't care로표현하고최소화 (w,,, z) = (0,7,8,0,5) 5)+ d(,2,9,,3) 3) = (3,4,5,6,2,4) d(,2,9,,3) d(2) 는 로포함, 나머지는 0 로포함 < 곱의합형 > = 'z' + z 모든 은한번씩은포함 (cover) 되어져야함 d(,9,,3) 은 0로포함, d(2) 는 로포함 중첩항 (redundant term) < 합의곱형 > '=' +z' +'z =('+)('+z)(+z') 모든 0 은한번씩은포함 (cover) 되어져야함 9
예제 무관항을포함한경우카르노맵을이용하여간소화 = m( 0,2,3,4,5,) + d(,7,9,5) = m(,2,3,4,6,8,0) + d(0,2,4) 0,2,3,4,8,9,) + = m( d(,5,6,7,0,2) CD AB 00 0 0 00 0 0 = AB + CD + AC = D + AB = A + B 20
6.4 Quine-McClusk 논리간소화 테이블방법 (tabulation method, Q-M 방법 ) 입력변수가많을경우표를이용하여논리간소화 Tabulation 방법의단계 () ind PI(Prime Implicant)s - candidate (2) Select PI - include minimum number of terms Pi Prime Implicant : 2 의맥급수로묶을수있는최대인접항으로결합된 product term Essential Prime Implicant (EPI) : 한개혹은그이상의 minterms을포함 (cover) 하는유일한 PI 가있다면그 PI를 EPI라한다. K-map논리화 : EPI 는반드시포함하고나머지 minterm를 cover 하는최소수의 PI 를포함한다. 2
Quine-McClusk 과정 ind PI. Step : Grouping - 최소항을 의개수로분류 2. Step 2 : matching - 모든상하그룹에서모든최소항들을각각비교하여 개의변수만이다르다면그 2개의최소항을결합하고이때 개의변수가 삭제된다. 결합된항은 로표시. 3. Step 3 : step 2 의결과에서모든상하그룹에서같은자리에소거된변수 가있는항끼리비교하여 개의변수만이다르다면그 2개항을결합하고 개의변수가소거된다. 결합된항은 로표시. 4. step 3 의과정을변수항의결합이발생하지않을때까지한다. 5. 위과정에서남은항과매칭되지않은모든항들은 PI가된다. 22
Tabulation 방법예 PI 찾기 = m(0,,2,8,0,,4,5) 를 QM 으로최소화 0 w z grouping matching * PI's w''',, 'z', w * All PI's are EPI. 23
Q-M 방법예 (w,,,z)= m(,4,6,7,8,9,0,,5) 를 QM 으로최소화 ind PI's 매칭시 0 진수값으로실행 두값을비교하여,2,4,8,6 의차이가있을때결합 단, 아래그룹의값이더커야한다. 24
Select PI's Tabulation 방법예 () 행에찾아진모든 PI 를기입 ( 포함하는최소항을같이기입 ) (2) 열에모든최소항기입 (3) 각 PI 가 cover 하는최소항을각해당란에 X 로표시 (4) 단한개의 X 로표시된최소항을가지는 PI 를한다. EPI (5) (4) 의 EPI 가 cover 하는모든최소항을마지막행에표시 (6) (5) 의되지않는최소항을포함하는 PI 를최소개가되도록선택 (7) (4) 와 (6) 을포함하여논리식을작성 = ''z z + w'z' wz +w' + z 25
Don't care 를포함한 Q-M 방법 (w,,, z) = (2,3,7,9,,3) + d(,0,5) PI 찾기 d 를포함하여 PI 를찾는다 PI selection 포함되어져야할최소항에는 d를불포함 = ' +z +wz all EPIs 26
예제 다음식을 QM방법을이용하여간략히하라. PI 찾기 f ( a, b, c, d) = m( 0,, 2, 5, 6, 7, 8, 9,0,4) Column Column 2 Column 3 inde decimal a b c d 0 (0) 0 0 0 0 0 2 3 () (2) (8) (5) (6) (9) (0) (7) (4) 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 inde decimal a b c d 2 (0,) 000-0 0 (0,2) 0 0-0 (0,8) - 0 0 0 (,5) 0-0 (,9) (2,6) (2,0) (8,9) - 00 0 0-0 - 0 0 0 0 - (8,0) 0-0 (5,7) (6,7) (6,4) (0,4) 0-0 - - 0-0 inde decimal a b c d 0 (0,,8,9) (0,2,8,0) (0,8,,9) (0820) - 0 0 - -0-0 - 0 0-0 0 (0,8,2,0) - 0-0 (2,6,0,4) --0 (2,0,6,4) --0 27
PI 선택 IMPLICANTS 0 2 5 6 7 8 9 0 4 acd 0-0 X X abd 0 - X X abc 0 - X X bc - 00 0 - X X X (X) bd -0-0 X X X X cd --0 X X X (X) Essential X X X X X X X (X) X (X) f = abd + bc + cd cd ab 00 00 0 0 0 0 28
무관항조건을가진다음식을 QM 방법을이용하여간략히하라. m( 0,, 4, 6, 8,4,5) + f ( a, b, c, d) = d( 2, 3, 9) Column Column 2 Column 3 inde decimal a b c d 0 (0) 0000 0 0 0 2 () (2*) (4) (8) (3*) (6) (9*) 0 0 0 000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 (4) 0 4 (5) inde decimal a b c d 0 (0,) 000-0 0 (0,2*) 0 0-0 (0,4) 0-0 0 (0,8) - 0 0 0 (,3*) 00 0 - (,9*) - 0 0 (2*,3*) 0 0 - (2*,6) 0-0 (4,6) (8,9*) 0-0 0 0-2 (6,4) - 0 3 (4,5) - inde decimal a b c d 0 (02*3*) (0,,2*,3*) 00 0 - - (0,2*,4,6) 0 --0 (0,8,,9*) - 0 0 - 없음 2 없음 29
IMPLICANTS 0 4 6 8 4 5 ab ad bc bcd abc 0 0 - - X X X 0 --0 X (X) X - 0 0 - X X (X) b - 0 X X - X (X) Essential X X (X) X (X) X (X) cd = ad + bc abc ab 00 0 0 00 X X f + 0 0 X 30
6.5 다출력함수의설계 논리회로에서함수의출력이 2개이상인다출력을가지는논리회로 다변수함수예 (w,,,z)= m(,2,3,4,5) 2(w,,,z)= m(37235) m(3,7,,2,3,5) 3(w,,,z)= m(3,7,2,3,4,5) 각출력에대하여간소화를한다. 입력을동시에사용하는형태로논리도를작성한다. 3
6.6 논리회로의간소화 간소화 : 부울식의간소화와논리게이트의간소화 NOR 게이트와 NAND 게이트 만능 (universal ) 게이트 NAND 게이트 부울함수 AND-NOT(AND 게이트의출력을반전 ), NOT-OR(OR OR(OR 게이트의모든입력을반전 ) 의두가지로표현 NOR 게이트 부울함수 OR-NOT(OR 게이트의출력을반전 ), NOT-AND(AND 게이트의모든입력을반전 ) 의두가지로표현 32
Universal 게이트 NOT : NAND 혹은 NOR 만으로 NOT 구현 AND : NAND 혹은 NOR 만으로 AND 구현 OR : NAND 혹은 NOR 만으로 OR 구현 33
NAND 게이트의논리회로구성 Two stage logic SOP(SOM) 혹은 POS(POM) 으로표현 모든디지털회로는이단논리로표현가능 부울함수를 SOP 로표시하는방법 첫번째방법은함수값이 인최소항을 SOP 로표시 두번째방법은함수값이 0인최소항을 SOP로표시한후 를보수화 함수를 2 단계 NAND 게이트로표시하는방법. 함수값이 인최소항을구해 SOP 형식을직접적으로 NAND 게이트로변환 ( 동일한 2 단논리 ) 함수값이0인최소항을구해보수를한후SOP의 NAND게이트로표시, 마지막단에 NOT로사용되는 NAND 사용 (3단논리 ) 함수를 2 단계 NOR 게이트로표시하는방법. 함수값이 0인최대항을구해 POS 형식을직접적으로 NOR 게이트로변환.( 동일한 2단논리 ) 함수값이 인최대항을구해보수를한후 POS 의 NOR 게이트로표시, 마지막단에 NOT로사용되는 NOR 사용 (3단논리 ) 34
SOP : NAND-NAND 논리 2단 AND-OR 회로는 2단 NAND-NAND 논리로변환예 ) 부울함수 =w+'+z를곱의합형인논리회로로표시하고, NAND 게이트로구현하라. w w z z w w z z 35
POS : NOR-NOR 논리 2단 OR - AND 회로는 2단 NOR-NOR 논리로변환예 ) 부울함수를 POS 논리회로를구성하고 NOR 게이트로만구현하라. = (w+)('+)(+z) +)(+z) w z w w z z 36
게이트간소화 가능한한 IC 개수를줄여서 = AB + CD 로표현되는식의회로를구현하려고한다. TTL IC 를가지고회로를구성하여라. 2 개논리게이트사용 개논리게이트사용 37
사용별게이트의표현선택 회로설계에있어대치논리게이트를적절히사용하여회로해석을쉽게한다. - 동작시킬회로의최종출력이 Active High이냐 Active Low에따라선택 - 그림 (b) : 출력 Z는 A=B= 또는 C=D=인경우에 High - 그림 (c) : 출력 Z 는 A 또는 B 가 Low 이고, C 또는 D 가 Low 일때만 Low 출력 Bubble 위치반전을나타내는버블은출력에버블이있으면그다음입력에버블이있도록연결버블이없는출력에는없는입력을연결 38
6.7 XOR 게이트와 XNOR 게이트 비교연산을수행하는게이트 교환법칙과결합법칙성립 XOR 게이트 A B 이면 출력, A=B 이면 0 출력 부울함수 : = = ' + ' XNOR 게이트 A B 이면 0 출력, A=B 이면 출력 부울함수 : = = ' ' + XOR 과 XNOR는서로보수함수 ' =( ' + ')' = (+')('+) = '++''+' = +'' XNOR 39
XOR 사용예 ( 예 ) 0 와 0 는각각 2 비트 2 진수이다. 이두수가서로같은값을가질때출력이 HIGH 가되는논리회로를설계하라. 진리표작성하면각입력의같은자리수가같을때출력이 ( 예 ) 간소화시 XOR나 XNOR를이용한예 z = ABCD + AB'C'D + A'D' = AD(BC + B'C') C) +A'D' = AD(B C) + A'D' 3변수 XOR 부울식 (,,z)= z = m(,2,4,7) K-map = ''z +'z' +'z' + z 의개수가홀수개 3 변수 XNOR 부울식? 40