제 3 장 카르노 맵 (K-map : Karnaugh Map) 카르노 맵 소개 카르노 맵을 사용한 최소 곱의 합 식 무정의 (Don’t Care) 합의 곱 5변수와 6변수 맵 다중출력 문제

카르노 맵(K-map: Karnaugh map) 각 정사각형은 함수의 최소항들을 나타낸다.

Plotting Functions

3 변수 맵

예제 3.1 m0+m1: ABC + ABC =AB m4+m6: ABC + ABC =AC m0+m4: ABC + ABC =BC m1+m5: ABC + ABC =BC

수직 배열 맵(Vertical Map) 1 00 01 10 11 A BC AB 1 00 01 10 11 A BC 1 00 1 00 01 10 11 A BC AB 1 00 01 10 11 A BC 1 00 01 10 11 A BC AC

라벨이 붙여진 맵(Map with Columns labeled) 1 00 01 10 11 AB C 2 3 4 5 6 7 B A 1 00 01 10 11 AB C B A AB AC

4 변수 맵

2 개의 1로 이루어진 그룹

4 개로 이루어진 그룹

8 개로 이루어진 그룹 A D

예제 3.3 F = AB' + AC + A'BC' 곱의 합으로 표현되는 함수식을 맵에 나타내는 방법 F = AB'(C' + C) + AC(B' + B) + A'BC' = AB'C' + AB'C + AB'C + ABC + A'BC' = m4 + m5 + m5 + m7 + m2 = m2 + m4 + m5 + m7 (중복 제거 및 순서화)

내포항 (Implicant) 함수에 대한 곱의 합 식에서 사용되는 곱 항 임의의 곱의 합식은 내포항들의 합 내포항은 1, 2, 4, 8, ..(2의 지수승) 개의 1로 구성

내포항 예 최소항 2개로 구성된 그룹 4 개로 구성된 그룹 A'B'C'D' A'CD CD A'B'CD BCD A'BCD ACD 최소항 2개로 구성된 그룹 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 ------------------------------------------------------- 총 14개의 내포항

주 내포항 (Prime Implicant : PI) 다른 내포항에 완전히 포함되지 않는 하나의 내포항이다 F의 주내포항 : A'B'C'D', ABC', ABD, CD

주 내포항 (Prime Implicant : PI) 대수적 의미 임의의 문자 변수가 주 내포항에서 제거되면 더 이상 내포항이 아닌 내포항을 의미 A'B'C'D'는 B'C'D', A'C'D', A'B'D', A'B'C'가 내포항이 아니기 때문에 주 내포항

Cover F에 대한 임의의 곱의 합 식은 내포항들의 합 이런 곱의 합식을 F 의 커버(cover)라 한다. 내포항 ABD는 m13과 m15를 커버

예제 3.4 함수 G 3 개의 최소항 -> 적어도 2개의 항이 필요 G = ABD + ABC 함수 H 최소식 H = BC'D + ABC 내포항 ABD 는 다른 항에 의해 커버되는 1만을 커버

필수 주 내포항 (Essential Prime Implicant : EPI) 다른 주 내포항에 포함되지 않는 적어도 1개의 1을 포함하는 주 내포항이다. A'B'C'D', ABC', CD는 필수 주 내포항 A'B'C'D' ABC' CD 필수(Essential) : 주어진 함수에 대한 최소화된 곱의 합 형태의 어떤 수식에도 이 주 내포항은 포함되어야 한다는 뜻

카르노 맵을 사용한 최소 곱의 합 식 N-변수 맵에서, 각각의 사각형은 n 개의 인접한 사각형을 가짐 고립되었다는 것은 1을 갖는 인접한 정사각형들의 수가 적은 (또는 없는) 것을 의미한다. 3, 4변수 맵의 인접한 사각형

맵 방법 1 모든 필수 주 내포항들을 찾음. 맵 상에서 필수 주 내포항들을 묶음 필수 주 내포항으로 만드는 최소항들에 * 표시를 한다. 일반적으로 가장 고립된 1들로부터 시작하는 것이 빠르다. 2. 함수를 커버하는 '충분한' 다른 주 내포항들을 찾음.(2 가지 기준) 선택된 주 내포항에 의해 될수록 많은 새로운(아직 커버되지 않은) 1을 커버하는 주 내포항을 선택. 고립되고 커버되지 않은 1을 남겨놓지 않도록 함.

예제 3.5 필수 주 내포항에 의해서만 커버 F = A'B'C'D' + ABC' + … F = A'B'C'D' + ABC' + CD

예제 3.6 필수 주 내포항과 주 내포항에 의해 커버 필수 주 내포항 가장 고립된 m11 -> wyz m0, m12, m8 -> y'z' 주 내포항 남은 2개의 1은 w'xz 에 의해 커버 주 내포항 w'xy', xyz 는 새로운 1 을 커버하지 않기 때문에 중복 최소곱의 합 식 f = y'z' + w y z + w'xz

예제 3.8 f(a, b, c, d) = m(0, 2, 4, 6, 7, 8, 9, 11, 12, 14) 필수 주 내포항: a'd' + bd' + a'bc + ab'd 1개의 1(m8)이 남음 4개로 이루어진 그룹(c'd')과 2개로 이루어진 그룹(ab'c')에 커버 최소 식 f = a'd' + bd' + a'bc + ab'd + c'd'

예제 3.10 특이한 경우 최소 해 G = A'BC' + A'CD + ABC + AC'D

예제 3.11 여러 개의 최소 해 g(w, x, y, z) = m(2, 5, 6, 7, 9, 10, 11, 13, 15) 예제 3.11 여러 개의 최소 해 g(w, x, y, z) = m(2, 5, 6, 7, 9, 10, 11, 13, 15) g = xz + wz + … g = xz + wz + w'yz' + wx'y g = xz + wz + w'yz' + x'yz' g = xz + wz + x'yz' + w'xy

예제 3.12 다소 복잡한 경우 F = A'C'D' + AC'D + A'CD + ACD' + …(가운데 맵) 예제 3.12 다소 복잡한 경우 F = A'C'D' + AC'D + A'CD + ACD' + …(가운데 맵) 커버되지 않은 3개의 1: B'D', AB', B'C 중 임의의 2개로 커버 최소 식 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 + A'CD + ACD' + AB' + B'C

예제 3.13 여러 개의 최소 해 m10 과 m15 f = b'd + bd + … 커버되지 않은 1: 3개 최소 해: 4가지

맵 방법 2 모든 주 내포항들을 원으로 묶음 모든 필수 주 내포항들을 선택 단지 한 번 원으로 묶인 1을 찾음으로써 쉽게 선택이 가능 맵 방법 1 에 기술한 것처럼 충분한 다른 주 내포항들을 선택 이들 주 내포항들은 이미 단계 1에서 지정됨

예제 3.15 복잡한 경우 가운데 맵 : 모든 주 내포항 m3와 m5 -> A'B' 와 C'D 필수 주 내포항 예제 3.15 복잡한 경우 가운데 맵 : 모든 주 내포항 m3와 m5 -> A'B' 와 C'D 필수 주 내포항 남은 4개의 1을 커버: 적어도 2개 이상의 항이 필요 B'D'는 2개의 새로운 1을 포함 B'C' 는 단지 1개를 포함 남은 1을 커버하기 위하여 ABC가 필요 최소 해 F = A'B' + C'D + B'D' + ABC

예제 3.16 필수 주 내포항의 cover가 작은 경우 G(A, B, C, D) = m(0, 1, 3, 7, 8, 11, 12, 13, 15) 필수 주 내포항 : YZ 5개의 1이 남음 주 내포항: W'X'Z, X'Y'Z', WXY', W'X'Y', WY'Z' , WXZ 적어도 3개의 항이 더 필요

예제 3.16 계속 최소해 F = YZ + W'X'Z (dotted circle) + X'Y'Z' + WXY' 예제 3.16 계속 최소해 F = YZ + W'X'Z (dotted circle) + X'Y'Z' + WXY' F = YZ + W'X'Y' + X'Y'Z' + WXY' F = YZ + W'X'Y' + WY'Z' + WXY' F = YZ + W'X'Y' + WY'Z' + WXZ

예제 3.17 필수 주 내포항이 없는 경우 a'c'd' 로 시작하는 경우의 해 예제 3.17 필수 주 내포항이 없는 경우 a'c'd' 로 시작하는 경우의 해 f = a'c'd' + bc'd + acd + b'cd'

예제 3.17 (계속) a'c'd' 와 abd를 선택하는 경우 (가운데 맵)  5개의 항 예제 3.17 (계속) a'c'd' 와 abd를 선택하는 경우 (가운데 맵)  5개의 항 a'c'd' 와 a'b'd'를 선택하는 경우 (가운데 맵)->5개의 항 a'b'd' 로 시작 (세번째 맵) f = a'b'd' + a'bc' + abd + ab'c

예제 3.18 필수 주 내포항이 없고 복잡한 경우 G(A, B, C, D) = m(0, 1, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15) m0를 커버하는 C'D' 로 시작, 그리고 B'D, BC m13을 커버하는 3가지(AB 또는 AC' 또는 AD ) F = C'D' + B'D + BC + { AB 또는 AC' 또는 AD }

예제 3.18 (계속) m0를 커버하는 B'C' 로 시작하는 경우, BD', CD 예제 3.18 (계속) m0를 커버하는 B'C' 로 시작하는 경우, BD', CD 앞에서 처럼 m13을 커버하는 3가지(AB 또는 AC' 또는 AD ) 총 6 개의 최소 해가 존재

예제 3.19 주 내포항들을 2개씩 그룹핑함 7 개의 항 이내로 간소화가 불가능하고, 32개의 다른 해가 존재 1개의 필수 주 내포항과 10개의 1이 남음 모든 주 내포항 : 가운데 맵 주 내포항들을 2개씩 그룹핑함 7 개의 항 이내로 간소화가 불가능하고, 32개의 다른 해가 존재 f = a'b'c'd' + a'cd + bc'd + a b'd + a bc' + a'bc + a cd' = a'b'c'd' + a'cd + bc'd + ab'd + abd' + bcd' + ab'c = …

Don’t Care (무정의) 무정의를 가진 함수에 대한 최소 해를 구하는 방법 정의 변경 주 내포항 : 다른 더 큰 사각형에 포함되지 않은 1, 2, 4, 8, .. 개의 1 또는 ×의 사각형이다. - ×(무정의)도 1과 같이 동등하게 다룬다. 필수 주 내포항 : 다른 주 내포항에 의해 커버되지 않는 1을 적어도 한 개를 커버하는 주 내포항이다. 무정의(×)는 주 내포항을 필수로 만들지는 않는다. 최소 해를 구할 때 무정의 중에 어떤 것은 포함되고 어떤 것은 포함되지 않음

예제 3.20 F(A, B, C, D) = m(1, 7, 10, 11, 13) + d(5, 8, 15) 최소해 (가운데 맵) F = BD + A'C'D + AB'C 모든 무정의를 1로 고려하는 경우 (오른쪽 맵) F = BD + A'C'D + AB'C + AB'D' F = BD + A'C'D + ACD + AB'D' 모든 무정의를 ‘0’으로 고려한 경우 F = A'B'C'D + A'BCD + ABC'D + AB'C

예제 3.21 모든 해의 대수적 표현이 동일하지 않은 경우 예제 3.21 모든 해의 대수적 표현이 동일하지 않은 경우 2 개의 필수 주 내포항 x'z 와 w'yz (가운데 맵) 4 개의 무정의로 이루어진 w'x'는 주 내포항이지만, 필수는 아님 모두 무정의로만 이루어진 주 내포항은 사용할 수 없음 최소화 해 g1 = x'z + w'yz + w'y'z' + wxy' (m0 = 1) g2 = x'z + w'yz + xy'z' + wxy' (m0 = 0) g3 = x'z + w'yz + xy'z' + wy'z (m0 = 0) g2 와 g3 는 대수학적으로 같은 함수이지만 g1 과는 다르다.

예제 3.22 g1 = c'd' + ab + b'd' + a'cd g2 = c'd' + ab + b'd' + a'b'c 세번째 맵 : ad'를 이용한 해 g1 = c'd' + ab + b'd' + a'cd g2 = c'd' + ab + b'd' + a'b'c g3 = c'd' + ab + ad' + a'b'c 동일성을 검증 : 무정의들이 처리된 값을 표로 구현 g1 ≠ g2 = g3

맵 방법 3 1. 맵 방법 1 또는 2를 사용하여 모든 필수 주 내포항을 찾음 2. 필수 주 내포항에 포함되는 모든 1들을 X 로 대치 포함되지 않고 남아있는 1 을 구별하기 위함 3. 맵 방법 1과 2 에서 처럼 다른 주 내포항들을 충분히 선택

예제 3.23 F(A, B, C, D) = m(0, 3, 4, 5, 6, 7, 8, 10, 11, 14, 15) 처음에 필수 주 내포항 A'B와 CD를 찾음 두번째 맵 : 포함된 모든 1을 무정의로 변환 나머지 1들은 AC와 B'C'D' 에 의해 커버 최소화 해 F = A'B + CD + AC + B'C'D'

합의 곱 합의 곱 형태의 최소화 함수의 보수를 맵에 표현 함수에 대한 맵이 이미 존재하는 경우, 모든 0을 1로, 모든 1을 0으로 대치. X 는 변환하지 않음 앞에서 사용한 방법을 이용하여 함수의 보수에 대한 최소화 곱의 합 식을 찾음 합의 곱 식을 만들기 위하여, 2 에서 구한 곱의 합 수식에 보수를 취함 (드모르강의 정리 (대수적 속성 P11)을 이용)

예제 3.25 합의 곱 f (a, b, c, d) = m(0, 1, 4, 5, 10, 11, 14)  f '(a, b, c, d) = m(2, 3, 6, 7, 8, 9, 12, 13, 15) f 에 대한 최소 곱의 합 식 f = a'c' + ab'c + acd' f 에 대한 최소 합의 곱 식 f' = ac' + a'c + abd  f = (a'+c)(a+c')(a'+b'+d') f' = ac' + a'c + bcd  f = (a'+c)(a+c')(b'+c'+d')

5, 6 변수 맵 5변수 맵은 25 = 32개로 구성 16개의 정사각형을 2개층(layer)구조로 나타냄 5변수 맵은 25 = 32개로 구성 16개의 정사각형을 2개층(layer)구조로 나타냄 5변수 맵(2-layer)

6변수 맵의 경우도 16개의 정사각형의 맵이 4개층 구조로 그려짐 4변수 맵과 동일

5 변수 함수에 대한 맵핑 F(A, B, C, D, E) = m(4, 5, 6, 7, 9, 11, 13, 15, 16, 18, 27, 28, 31)

1들 중에서 인접한 층에서 대응하는 정사각형에 1이 없는 것 이러한 1을 포함한 주 내포항은 그 층에만 속하게 된다(따라서, 4변수 맵 문제가 된다.). 이와 같은 예로, m4, m9, m16, m28의 경우가 있다 F = A'B'C + A'BE + AB'C'E' + ABCD'E' + …

F = ABC + ABE + ABCE + ABCDE + BDE 양쪽의 레이어 상에 1을 커버하는 필수 주 내포항 최종 해 (계속) F = ABC + ABE + ABCE + ABCDE + BDE

다중 출력 문제 다중 출력을 가진 시스템을 설계하는 경우가 많음 3개의 입력 A, B, C와 2개의 출력 F, G 2개의 문제로 나누어서 취급 하나의 시스템: 게이트들의 공유가능 -> 비용 줄임.

예제 3.32 F(A, B, C) = m(0, 2, 6, 7) G(A, B, C) = m(1, 3, 6, 7) 각 함수에 대해 아래와 같은 식을 얻을 수 있음 F = AC + AB G = AC + AB

(예제 3.32 계속) 우측: 두개의 독립된 문제 좌측: 항(AB) 공유함으로써 게이트 수가 줄어듬.

예제 3.33 F(A, B, C) = m(0, 1, 6) G(A, B, C) = m(2, 3, 6) 독립된 문제(위쪽 맵) : F = AB + ABC G = AB + BC 공유(아래쪽 맵) : F = AB + ABC G = AB + ABC

(예제 3.33 계속) 독립된 문제: F = AB + ABC G = AB + BC (6 게이트: 4 AND, 2 OR, 13 inputs) 공유: F = AB + ABC G = AB + ABC (5 게이트: 3 AND, 2 OR, 11 inputs)

예제 3.34 F(A, B, C) = m(2, 3, 7) G(A, B, C) = m(4, 5, 7) 독립된 문제 해 f = ab + bc g = ab + ac 공유항 이용 f = ab + abc g = ab + abc

예제 3.35 F(A, B, C, D) = m(4, 5, 6, 8, 12, 13) G(A, B, C, D) = m(0, 2, 5, 6, 7, 13, 14, 15) 하나의 함수에서만 1인 것(적색)들에서 필수 주 내포항 찾음

(예제 3.35 계속) 공유항 이용 F = ACD + ABD + BCD G = ABD + BC + BCD (20 inputs, 7 게이트)

(예제 3.35 계속) 독립함수로 풀면 F = ACD + ABD + BC G = ABD + BC + BD (21 inputs, 8 게이트)

예제 3.36 F(A, B, C, D) = m(0, 2, 3, 4, 6, 7, 10, 11) G(A, B, C, D) = m(0, 4, 8, 9, 10, 11, 12, 13) 각 함수(F, G)의 독립 해 (분리하여 풀음) F = AC + AD + BC G = AC + CD + AB (18 inputs, 8 게이트) 먼저 공유되지 않는 1들에서 필수 주 내포항 묶음

(예제 3.36 계속) ACD 와 ABC 를 공유 (16 inputs, 6 게이트) F = AC + ACD + ABC G = AC + ACD + ABC

예제 3.37 F(W, X, Y, Z) = m(2, 3, 7, 9, 10, 11, 13) G(W, X, Y, Z) = m(1, 5, 7, 9, 13, 14, 15) * mark : 공유안되는 필 수 주내포항

(예제 3.37 계속) F = XY + WYZ + W XYZ G = YZ + WXY + WXYZ (7 게이트,20 inputs) F, G를 분리하여 구한 해 F = XY + WYZ + WYZ G = YZ + WXY + XZ (8 게이트, 21 inputs)

예제 3.38 분리된 문제로 해를 구하는 경우 F = AB + BD + BC G = C + ABD H = BC + ABC + ( ABD or ACD) (10 게이트, 25 inputs)

(예제 3.38 계속) 공유하여 구한 해 F = BC + ABC + ABD + ABD G = C + ABD H = BC + ABC + ABD (8 게이트, 22 inputs)

예제 3.40 : 무정의를 가진 시스템의 예 F(A, B, C, D) = m(2, 3, 4, 6, 9, 11, 12) + d(0, 1, 14, 15) G(A, B, C, D) = m(2, 6, 10, 11, 12) + d(0, 1, 14, 15) BD: 공유안되는 필수 주 내포항

(예제 3.40 계속) ABD 을 공유 F = BD + ABD + AD G = AC + ABD + CD (17 inputs, 7 게이트)

(예제 3.40 계속) ACD 를 공유 F = BD + ACD + BD G = AC + ABD + ACD (18 inputs, 7 게이트)