Microsoft PowerPoint - dc_ch3 [호환 모드]

Chapter 3 Karnaugh Maps

명제 진리표디지털시스템논리회로 Logic map K-map 부울함수

: Switching Expressions and Logic Maps 논리적인접 * 오직 1비트만이다른입력변수의두조합을논리적으로인접하다고함 * [ 예 ](x 와 x ) x), (xy 와 x y) xy), (xyz 와 xy z) z), (abcd 와 abcd ) (111과 011 혹은 101 혹은 110) (0101과 1101 혹은 0001 혹은 0111 혹은 0100) 기하학적인접 * 각행과열에있어서인접한 2 셀 (cells) 을기하학적으로인접하다고함 논리지도 (logical (or logic) map) * 기하학적으로인접한 2 셀이논리적으로인접하도록변수가나열된지도 * Each minterm of the function represented by this map corresponds to one cell of the map that carries a 1.

논리인접성이론 AB + AB = A ( A + B )( A + B ) = A [ 예 ] 식 AB + AB C + ABC 을최소화하시오. AB + AB C + = ABC + ABC ABC + AB C ABC = ( ABC + ABC ) + ( ABC + AB C ) = BC + AC + 논리인접최소항의쌍및쌍의그룹 * 논리적으로인접한 ( 즉, 이항들을부울식으로표현하였을경우두항사이에오직한문자만이서로다른경우 ) 한쌍의최소항

논리인접성이론에근거하여작성한표. (a) One-variable map. (b) Two-variable map. (c) Three-variable map. (d) Four-variable map. x x x y x y x y x y

미러이미지변환 5 변수카노맵 ABC DE 000 001 011 010 00 0 4 12 8 110 111 101 100 24 28 20 16 01 11 1 5 13 9 3 7 15 11 25 29 21 17 27 31 23 19 4-Variable K-Map 4-Variable K-Map 10 2 6 14 10 26 20 22 18 4-Variable K-Map 4-Variable K-Map Hinge

5 변수카노맵의누적된수 Adjacent Columns ABC DE 000 001 011 010 00 0 4 12 8 16 100 101 111 110 16 24 20 28 24 4-Variable K-Map 01 1 5 13 9 17 21 29 25 0 4 11 3 7 15 11 19 23 31 27 10 2 6 14 10 18 22 20 26 4-Variable K-Map 4-Variable K-Map 4-Variable K-Map

Six-variable Karnaugh maps. (a) Reflective structure. (b) Layer structure.

임플리컨트 (Implicant) * 어떤함수의임플리컨트는 임플리컨트가 1일때는언제든지함수가 1이되는곱항 를말함. * [ 예 ] 다음쪽의최소항 * 지도 (Map) 적관점에서설명하면, 4각형형태를지니면서내부에 1 만을포함하는 2 k 개 (1, 2, 4, 8,...) 의최소항으로구성된곱항 프라임임플리컨트 (Prime implicant of a function) * 임플리컨트중에서어느하나의다른임플리컨트에완전히포함되지않는것을말함 * [ 예 ] 지도 32 3,2 에타원으로표시된모든곱항 에센셜프라임임플리컨트 (Essential prime implicant) * 다른프라임임플리컨트에포함되지않는적어도하나의 1 을갖는프라임임플리컨트를말함. * [ 예 ] 지도 3,2에검은색타원으로표시된모든곱항

The implicants of F are Minterms Groups of 2 Groups of 4 A B C D A CD CD A B CD BCD A BCD ACD ABC D B CD ABC D ABC ABCD ABD AB CD

: Switching Expressions and Logic Maps Cubes of order k 또는 k-cube (k = 0, 1, 2, 3, ) * 진리값으로 1 을갖는 2 k (=1, 2, 4, 8, 16, ) 개의셀로구성된입방체 * 입방체내의각셀은다른 k 개의셀과인접함. * [ 예 ] k-cubes 0-cube, 1-cube, 2-cube 더이상줄여지지않는 SOP(Irreducible SOP) 같은논리값을가지면서더이상항의수나문자의수를줄일수없는 SOP. * 프라임임플리컨트로표현된 SOP 최소 SOP(Minimal SOP) * 가장적은수의항을갖는 SOP. * 항의수가같은경우에는문자의수가가장적은 SOP. f = wz + x y z + wyz + wxy + wxyz

카노맵 (Karnaugh map) *M M. Karnaugh 는 1953 년 조합논리회로의합성에관한맵방법 이란논문에서앞에서설명한인접이웃, 논리인접최소항의배열이라는아이디어를사용하여부울함수를최소화시키는도표방법을개발. * 각각의사각형이부울식으로부터최대항과최소항을표현하는사각행렬. * 논리적으로인접하는 2 n 개의셀은하나로묶여보다적은변수로표현됨. 2변수의경우 : AB A B AB, AB,. 3변수의경우: A B C A BC ABC ABC A B C A B C A BC A BC * 카노맵최소화. 일반적으로맵에있는모든엔트리들을포함할필요가있는그룹의수는최소화, 그룹의크기는최대화하는논리인접그룹을선택.

* 인접사각형 :. 2 정사각형이인접하였다 2 정사각형에대응되는각최소항의구성문자중단하나의문자만보수관계에있고나머지문자는모두같은경우. [ 예 ]( 변수 3개 ): m = X Y Z m = X Y m + m = X Z ( Y + Y ) = * 묶는방법. 2 n 개의정사각형을묶음. 한묶음은크게. 묶음의수는적게 * 진리표 카노도표. 2 정사각형이인접하도록표를구성 F b 0 1 a 0 1 0 1 1 0. F = a b + ab = ( a + a ) b = 1 b = b Z 4 6 4 6 X Z. 출력값이 1 이되는입력값들의조합을살펴보면a는 0 이든 1 이든상관없고, b가 0 이기만하면되므로 F=b 라할수있다.

- 3 변수도표 : 정사각형묶음과문자수. 정사각형 1=2 0 개 3 개의문자. 정사각형 2=2 1 개 2 개의문자. 정사각형 4=2 2 개 1 개의문자. 정사각형 8=2 3 개 0 개의문자 ( 부울함수 =1) - n 변수도표 : 정사각형묶음과문자수. 정사각형 1=2 0 개 n 개의문자. 정사각형 2=2 1 개 (n-1) 개의문자. 정사각형 4=2 2 개 (n-2) 개의문자. 정사각형 2 n-1 개 1 개의문자. 정사각형 2 n 개 0 개의문자 ( 부울함수 =1) (c) 테이블방법 (Quine-Mcluskey method)

Map Method 1 1. Find all essential prime implicants. Circle them on the map and mark the minterm(s) that make them essential with an asterisk (*). Do this by examining each 1 on the map that has not already been circled. It is usually quickest to start with the most isolated 1 s, that is, those that have the fewest adjacent squares with 1 s in them. 2. Find enough other prime implicants to cover the function. Do this using two criteria: a. Choose a prime implicant that covers as many new 1 s (that is, those not already covered by a chosen prime implicant). b. Avoid leaving isolated uncovered 1 s.

minimum all prime implicants

Map 2.12 x yz + x yz + xy z + xy z + xyz. Map 2.13 A better solution. Map 2.14 The minimum solutions.

g = xz+ wz+ w yz + wx y g=xz+ wz+w yz + x yz g = xz+ wz+ x yz + w xy

not used minimum G = A BC + A CD + ABC + AC D

F = A C D + AC D + A CD + ACD + B D + AB F = A C D + AC D + A CD + ACD + B D + B C F = A C D +AC D AC D + A CD + ACD + AB + B C

f=a c d +bc d +acd+b cd + f = a b d + a bc + abd + ab c

minimum other p.i.s F = BD + A C D + AB C

Map Method 3 1. Find all essential prime implicants (using either Map Method 1 or 2). 2. Replace all 1 s covered by the essential prime implicants with X s Xs. This highlights the 1 s that remain to be covered. 3. Then choose enough of the other prime implicants (as in Mthd Methods 1 and d2) 2).

Finding a minimum product of sums expression requires no new theory. The following approach is the simplest: 1. Map the complement of the function. (If there is already a map for the function, replace all 0 s by 1 s, all 1 s by 0 s and leave X s unchanged.) 2. Find the minimum sum of products expression ess for the complement of the function (using the techniques of the last two sections). 3. Use DeMorgan s theorem (P11) to complement that expression, producing a product of sums expression.

f = a c + ab c + acd f = ac + a c + abd f = ac + a c + bcd f = (a + c)(a + c )(a + b + d ) f = (a + c)(a +c )(b + c + d )

[ 예제 ] 다음식을 4변수카노맵을사용하여간략화하라. L = f(a, b, c, d) = (0, 2, 5, 7, 8, 10, 13, 15) cd ab 00 01 11 10 0 4 12 8 00 1 1 01 1 5 13 9 1 1 b ' d ' 3 7 15 11 11 1 1 2 6 14 10 10 1 1 bd L=b d +bd =(b + d) L = f(a, b, c, d) = (0, 2, 5, 7, 8, 10, 13, 15) 에대한 4변수카노맵

[ 예제 ] 다음식을간략화하라. P = f(r, s, t, u) = (1, 3, 4, 6, 9, 11, 12, 14) tu rs 00 su' 00 01 11 10 0 4 12 8 1 1 1 5 13 9 01 1 1 3 7 15 11 11 1 1 P=s u+su 2 6 14 10 10 1 1 s' u

[ 예제 ] 다음을간략화하라. P = f(a, b, c, d) = (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) ab cd 00 01 11 10 0 4 12 8 00 1 1 1 1 c' 01 1 1 5 13 1 1 1 9 P=c +bd +a d +a d 11 3 7 15 11 P = c' +bd' +a ' d ' a ' d ' 10 P = f(a, b, c, d) = (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) 에대한 4 변수카노맵 2 6 14 10 1 1 1 bd'

Typical subcubes on a five-variable map.

Map for f(v,w,x,y,z) = Σm(0,1,2,3,6,7,11,15,16,17,19,23,27,31). (a) Subcubes for the minimal sum. (b) Subcubes for the minimal product.

두개의 5 변수카노맵에대한수직정렬 00 000 101 111 110 16 20 28 24 1 1 01 17 21 29 25 11 19 23 31 27 10 18 22 30 26 1 1 000 101 111 110 0 4 12 8 00 1 1 01 1 5 13 9 11 3 7 15 11 2 6 14 10 10 1 1

W = f(a, b, c, d, e) = (1, 3, 4, 6, 9, 11, 12, 14, 17, 19, 20, 22, 25, 27, 28, 30) 을위한카노맵 de abc 00 01 000 001 011 010 0 4 12 8 16 100 101 111 110 1 1 1 1 1 5 13 9 1 1 1 1 17 20 21 28 29 24 25 ce' c' e 11 3 7 15 11 19 1 1 1 23 31 27 1 2 6 14 10 18 22 20 10 1 1 1 1 26 W = ce' +c' e or W = c +e

J = f(v, w, x, y, z) = (4, 5, 6, 7, 9, 11, 13, 15, 25, 27, 29, 31) 을위한 5 변수카노맵

F = A B C + A BE + AB C E + ABCD E + BDE

F = A C E + ABCD + CD E + BCE + B C DE + A CD F = A C E + ABCD + CD E + BCE + B C DE + A D E

Six-variable Karnaugh maps. (a) Reflective structure. (b) Layer structure.

Typical subcubes on a six-variable map.

abc def 000 001 011 010 000 0 8 24 16 100 101 111 110 32 40 56 48 001 1 9 25 17 33 1 1 1 1 cf 41 57 49 011 3 11 27 19 35 43 59 1 1 1 1 51 010 2 10 26 18 34 42 58 50 100 4 12 28 20 36 44 60 52 K = f(a, b, c, d, e, f) = (9, 11, 13, 15, 25, 27, 29, 31, 41, 43, 45, 47, 57, 59, 61, 63) 을위한 6변수카노맵 101 111 110 5 13 29 21 1 1 7 15 31 23 1 1 6 14 30 22 37 39 45 47 61 1 1 63 1 1 38 46 62 53 55 54 K = cf

abc 000 001 011 010 100 101 111 110 def 0 8 24 16 32 40 56 48 000 1 1 1 1 1 1 1 1 d ' e' f' 001 1 9 25 17 33 41 57 49 011 3 11 27 19 35 43 59 51 a ' c' f' 010 2 10 1 1 26 18 1 34 42 58 50 100 4 12 28 20 1 1 1 36 44 60 52 101 5 13 29 21 37 45 61 53 a ' b ' f' 111 110 7 15 31 23 6 14 30 22 1 1 1 39 47 63 38 46 62 55 54 I = f(a, b, c, d, e, f) = (0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 32, 40, 48, 56) 을위한 6 변수카노맵 I = d ' e' f' +a ' c' f' +a ' b ' f'

2 진수를 EX-3 BCD code 로 2 진수 EX-3 BCD 변환을위한진리표 A=f(W,X,Y,Z)= (5,6,7,8,9)+ d(10,11,12,13,14,15) B=f(W,X,Y,Z)= (1,2,3,4,9)+ d(10,11,12,13,14,15) C=f(W,X,Y,Z)= (0,3,4,7,8)+ d(10,11,12,13,14,15) W X Y Z A B C D 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 무관항... D=f(W,X,Y,Z)= (0,2,4,6,8)+ d(10,11,12,13,14,15) 1 0 1 1 무관항... 1 1 0 0 무관항... 1 1 0 1 무관항... 1 1 1 0 무관항... 1 1 1 1 무관항...

진수 EX-3 BCD 카노맵 WX YZ 00 01 11 10 0 4 12 8 00 d 1 WX YZ 00 01 11 10 0 4 12 8 00 1 d XY' Z ' 01 1 5 13 1 d 1 9 W 01 1 5 13 9 1 d 1 X ' Z 3 7 15 11 11 1 d d XZ 3 7 15 11 11 1 d d 2 6 14 10 10 1 d d XY 2 6 14 10 10 1 d d X ' Y (a) 출력 A 의카노맵 (b) 출력 B 의카노맵

YZ 2진수 EX-3 BCD 카노맵 WX 00 01 11 10 00 0 4 12 8 1 1 d 1 Y ' Z ' YZ WX 00 00 01 11 10 0 4 12 8 1 1 d 1 Z ' 1 5 13 9 1 5 13 9 01 d 01 d 3 7 15 11 11 1 1 d d YZ 3 7 15 11 11 d d 2 6 14 10 2 6 14 10 10 d d 10 1 1 d d (c) 출력 C 의카노맵 (d) 출력 D 의카노맵

W W U3A 1 2 W ' X Y 74LS04 X U3B 3 4 X ' 74LS04 U3C 5 6 74LS04 Y Y ' Z X Y X Z X ' Y U1A 1 2 74LS00 U1B 4 5 74LS00 U1C 9 10 3 6 8 (X Y)' (X Z)' (X' Y)' U2B 3 4 6 5 74LS10 A A = W +X Y +X Z Z U3D 9 8 Z ' 74LS04 X ' Z 12 13 74LS00 U1D 11 (X' Z)' U2C 9 10 8 11 B 2 진수 3 초과코드변환기 X Y ' Z ' 74LS00 1 U2A 2 12 13 74LS10 (X Y' Z ' )' 74LS10 B = X ' Y +X ' Z +X Y' Z ' A=W+XZ+XY B=X Y+X Z+XY Z Z C=Y Z+YZ Z=Z Y Z Y ' Z ' U4A 1 2 74LS00 U4B 4 5 3 6 (Y Z)' (Y' Z ' )' 9 10 U4C 74LS00 8 C C = Y ' Z ' +Y Z 74LS00 D D = Z '

최대항을사용한세변수맵 z xy 00 01 11 10 0 2 6 4 0 0 0 y +z 1 3 7 5 1 0 0 y' +z' J = (y +z)(y' +z' )

[Ex] 다음그림의함수를간략화하라. G = f(a, b, c, d) = π(0, 4, 5, 7, 8, 9,11, 12, 13, 15) cd ab 0 00 01 11 10 4 12 00 0 0 0 0 8 c +d b ' +d ' 01 1 5 13 9 0 0 0 3 7 15 11 11 0 0 0 a ' +d ' 4변수맵간략화 G = f(a, b, c, d) = π(0, 4, 5, 7, 8, 9,11, 12, 13, 15) 10 2 6 14 10 G = (c +d)(a' +d ' )(b' +d ' )

L = f(a, b, c, d, e) = π ( 0, 2, 4, 6, 8, 9, 10, 11, 12, 14, 16, 17, 18, 19, 24, 25, 26, 27) 의맵 de abc a ' +c 00 000 001 011 010 0 4 12 8 16 100 101 111 110 0 0 0 0 0 0 20 28 24 a +e 01 1 5 13 9 17 21 0 0 0 29 25 11 3 7 15 11 0 19 0 23 31 27 0 2 6 14 10 18 22 20 10 0 0 0 0 0 0 26 b ' +c L = (a +e)(a' +c)(b' +c)

A multiple-output combinational network.

Realization of Table 4.13. (a) Karnaugh maps for minimal sums. (b) Realization of individual minimal sums. (c) Realization based on shared term.