CHAPTER 5 KARNAUGH MAPS( 카노 맵 ) This chapter in the book includes: Objectives Study Guide 5.1Minimum Forms of Switching Functions 5.2Two- and Three-Variable Karnaugh Maps 5.3Four-Variable Karnaugh Maps 5.4Determination of Minimum Expressions 5.5Five-Variable Karnaugh Maps 5.6Other Uses of Karnaugh Maps 5.7Other Forms of Karnaugh Maps Programmed Exercises Problems

Objectives 1. 주어진 3 변수에서 5 변수까지의 함수 ( 완전, 비완전 멩세된 ) 의 카노맴을 작성 함수는 최소항이나 최대항, 혹은 대수식으로 주어진다. 2. 맵으로 부터 함수의 필수주항을 결정한다. 3. 맵으로 부터 함수의 최소 논리곱의 함 또는 최소 논리합의 곱 식을 구한다. 4. 맵으로 부터 함수의 모든 주항을 구한다. 5. 맵을 통한 연산과 그에 대응하는 대수적 연산과의 관계의 이해

5.1 스위칭 함수의 최소 형식 스위칭 함수는 일반적으로 대수학적 방법을 사용함으로 써 간략화 될 수 있다 그러나 대수학적인 방법은 다음과 같은 두가지 문제가 있다. 1. 체계적인 방법을 적용하기 어렵다. 2. 완전한 최소식을 얻기 못 할 수도 있다. AND 나 OR 게이트들을 사용하여 함수를 회로로 구현할 때, 그 구현 비용은 게이트 의 개수와 사용된 입력의 개수에 의존하기 마련이다. 카노 맵 방법은 AND 와 OR 게이트로 이루어진 2 단 회로를 최소 비용으로 구현 할 수 있게 해준다. 논리곱의 함 식의 2 단 회로는 한 그룹의 AND 게이트의 출력이 모두 하나의 OR 게이트의 입력으로 들어가도록 구성되어 있으며, 마찬 가지로 논리합의 곱 식은 한 그룬의 OR 게이트 의 출력이 하나의 AND 게이트의 입력으로 구성 되어 있다. 그러므로, 최소 비용으로 2 단 회로를 구현하기 위해서는 반드시 최소 논리합의 곱 식이나 최소 논리곱의 합 식을 찾아 내어야 한다.

5.1 스위칭 함수의 최소 형식 1. 를 이용하여 항들을 결합한다. 가능한 많은 문자들을 소거 할 수 있을 때 까지 반복해서 수행한다. 이기 때문에 주어진 항은 한번 이상 사용 될 수도 있다 2. 합의 정리 또는 다른 정리를 이용하여 여분의 중복항을 소거한다. 어떤 함수에 대한 최소 논리 곱의 합 (minimum sum of products) 식은 (a) 최소 수의 항들을 가지고, (b) 각 항은 각각 최소 개수의 문자를 가진다 라는 두 가지 조건을 만족하는 논리 곱의 합 식으로 정의 된다. 최소항 식이 주어 졌을 때 최소 논리곱의 합 식은 다음의 절차를 통해 구 할 수 있다.

5.1 스위칭 함수의 최소 형식 Example: 최소 논리 곱의 합 식을 구하라. 한 함수에 대한 최소 논리합의 곱 (minimum product of sums) 식은 (a) 인수의 수가 최소이고 (b) 각각의 인수는 최소 개수의 문자수를 가진다 ” 라는 두가지 조건을 만족하는 논리합 곱 식으로 정의 된다.

5.1 스위칭 함수의 최소 형식 Eliminate by consensus 최대항 전개식과는 달리, 함수의 최소 논리합의 곱 식이 반드시 하나 밖에 없는 것은 아니다. 주어진 최대항 전개식에서 최소 논리합의 곱 식은 일반적으로 항의 결합을 위해 사용 되는 정리 를 제외하고는 최소 논리곱의 합 식을 경우에 사용된 절차와 유사한 절차를 통해 구 할 수있다.

5.22 변수와 3 변수 카노맵 A 2-variable Karnaugh Map 진리표와 마찬가지로, 어떤 함수의 카노맵은 독립 적인 변수 값들의 모든 가능한 조합을 각각의 사각형 내에 나타낼 수 있다.

5.22 변수와 3 변수 카노맵 A BF Truth Table for a function F (a) 맵에서 각 1 은 F 의 최소항에 해당한다. 맵에서 인접한 칸의 최소항들은 단지 하나의 변수만 다르므로 결합 시킬수 있다 A ’ B ’ 와 A ’ B 는 아래 위로 서로 입접하고 있는데. 두 최소항은 변수 A ’ 는 같고 변수 B 와 B ’ 가 다르므로 서로 결합할 수 있어 1 을 루프 (loop) 로 묶으면 A ’ 가 남음

5.22 변수와 3 변수 카노맵 A B CF 변수의 진리표와 카노맵 (a)

5.22 변수와 3 변수 카노맵 3 변수 카노 맵에서 최소항의 위치

5.22 변수와 3 변수 카노맵 Karnaugh Map of F(a, b, c) = m(1, 3, 5) = ∏(0, 2, 4, 6, 7)

5.22 변수와 3 변수 카노맵 곱항들을 어떻게 카노 맵에 표시 할 수 있는가를 설명

카노맵에 의한 간단화 1. 카노맵 상에서 인접한 “ １ ” 을 찾아, 이것을 Loop( 루프 ) 로 둘러싼다. 단 루프는 종횡 ( 縦横 ) 에서 2 의 승수의 크기를 갖는 것으로 한다. 2. 루프의 크기는 될 수 있는 한 크게 하고 루프 수는 될 수 있는 한 적 게 한다. † 3. 각각의 루프에 대응하는 ＡＮＤ소자를 만들고 이것들의 출력을 Ｏ Ｒ소자의 입력으로 하는 조합 회로를 작성 † 루프를 크게 하는 것은 ＡＮＤ의 입력 수를 감소시키는 것에 대응 하고, 루프 수를 감소시키는 것은 ＡＮＤ의 수를 감소시키는 것에 대 응한다. 더 이상 크게 할 수 없는 루프을 나타내는 논리식을 “ 주항 (prime implicant) 이라 한다.

5.22 변수와 3 변수 카노맵 Given Function 1. 항 abc ’ 는 a=1 과 bc=10 일 때 1 이어서 맵의 a= 1 열과 bc=10 행에 대응하는 칸에 1 을 기입 한다. 2. 항 b ’ c 는 bc=01 일 때 1 이어서 맵의 bc=01 인 행 의 두칸에 1 을 기입한다. 3. 항 a ’ 는 a=0 일 때 1 이어서 맵의 a=0 인 열의 모든 칸에 1 을 기입한다. ( 주의 abc=001 인 칸에 이미 1 이 있으므로, 그 칸에 두 번째로 또 1 을 넣을 필요는 없다. : x+x=x

5.22 변수와 3 변수 카노맵 3 변수 함수의 간소화

5.22 변수와 3 변수 카노맵 그림 5-6(a) 맵의 보수

5.22 변수와 3 변수 카노맵 합의 정리를 보여주는 카노 맵 Consensus term is redundant

5.22 변수와 3 변수 카노맵 2 개의 최소식을 갖는 함수

5.3 4 변수 카노맵 Location of Minterms on Four-Variable Karnaugh Map

5.3 4 변수 카노맵 Plot of acd + a’b + d’

5.3 4 변수 카노맵 4 변수의 간략화

5.3 4 변수 카노맵 불완전 (dont’ care) 하게 쓰여진 함수의 간략화 Don’t care term don ’ t care( 무관항 ) 은 필요할 때만 사용

5.3 4 변수 카노맵 Figure 5-14 최소 논리합의 곱식에서도 카노 맵을 사용가능 0 에 관해서 루프를 묶어면 됨 논리곱의 합식을 논리합의 곱식으로 바꿈

5.4 필수 주항을 이용한 간략화 Prime implicants 다른 항과 루프로 결합할 수 있기 때문에 주항이 될 수 없다. 주항 - F 의 관련항 (Implicants) : 함수 F 의 맵에서 1 이 하나 있거나 루프로 묶여진 1 들은 F 의 관련항이라고 부르는 곱항을 나타낸다.( 관련항과 주항은 다음장에서 설명 ) - F 의 주항 ( prime Implicants) : 관련항중 변수를 소거하기 위해서 더 이상 다른 항과 결합될 수 없는 관련항을 주항 (prime implicants) 라고 한다. 맵상에서 다른 1 들과 전혀 입접하지 않는 단 하나만의 1 항은 주항이 된다.

모든 주항의 결 정 5.4 필수 주항을 이용한 간략화 맵에서 모든 주항을 찾았을 때, 몇몇 주항은 최소 논리 곱의 합 식에 포함 되지 않는다는 것을 명심 하나의 관련항의 모든 1 들이 주항들 속에 전부 포함되더라도, 그 항은 어떤 특정한 한 개의 주항에 항 전체가 포함 되지 않 을 수도 있으므로 역시 주항이 될 수 있다. 주항을 찾는 과정에서 무관함 (don ’ t care) 는 1 처럼 취급한다. 그러나 어떤 주항이 모두 무관항들로 구성되어 다면 최소식의 부분이 될 수 없다. 함수의 모든 주항은 카노맵으로 부터 구해진다. abd 는 다른 1 의 그룹과 묶혀 간략화 가능하므로 주항이 아니다.

함수의 모든 주항이 일반적으로 최소 논리곱의 합식을 만들기 위해 필요한 것은 아니기 때문에, 주항을 선택하는 체계적인 과정이 필요하다. 맵에서 잘못된 순서로 주항을 선택하면, 결과적으로 최소식을 얻지 못한다. 5.4 필수 주항을 이용한 간략화 - CD is 모든 1 들이 포함 되어 있어서 필요하지 않다. B’C, AC, BD 는 필수 주항이다. - CD 는 CD 안에 각각의 1 이 다른 주항에 포함 되기 때문에 필수 주항이 아니 다. 하나의 최소항이 단 하나의 주항에만 포함되다면, 이 주항을 필수주항이라 한다.

1. 먼저 필수 주항을 찾아라 2. 만약에 필수 주항에 의해서 최소항을 표현 할 수 없을 때, 더 많은 주항을 최 소항 표현에 추가 해야 한다. 5.4 필수 주항을 이용한 간략화 일반적으로 맵으로 부터 최소 논리곱의 합 식을 찾기 위해 먼저 모든 필수 주항을 루프 로 묶어야 한다. 주 : 1 이 회색으로된 부분은 단 하나의 주항이다. 다른 모든 1 은 2 개에 주항에 포함된다. 주어진 최소항과 인접한 모든 1 이 단 하나의 항에 포함 된다면 그 항은 필수 주항이다. 필수주항을 찾는 방법 : 단순히 아직 포함되지 않는 1 을 보고 얼마나 많은 주항이 그 1 을 포함하는 지 확인

카노맵을 사용하여 최소 논리곱의 합 식을 구하는 순서도 5.4 필수 주항을 이용한 간략화

1)I 6 과 이에 인접하는 1 들과 X 들 ( I 4 와 X 7 ) 는 A’B 에 포함 되므로 A’B  essential PI 2)I 13 을 살펴보면, 이에 인접하는 1 과 X 들 ( I 5, I 9,, X 15 ) 는 하나의 단항에 포함되지 않으므로 필수 주항이 아니다 3) 마찬가지로 I 8 과 I 9 에 인접한 항을 검사해 보면 필수 주항이 나타나지 않는다. 4)I 10 은 I 8 만 인접하고 있으므로 AB’D’ 는 I 10 과 I 8 양쪽 모두 포함 하고 있기 때 문에 AB’D’  essential PI 5) 필수 주항 을 선택한 후에 맵에서 나머지 1 을 포함하는 AC’D is not an essential PI 5.4 필수 주항을 이용한 간략화 1 4 로 시작해 보면, 인접한 1 들과 X(X 0, ) 들이 단일 항에 포함 되지 않으므로, 필수 주항 이 분명히 아니다라는 것을 알게 됨,

5.5 5 변수 카노맵 5 변수 카노 맵 5 변수 카노 맵은 4 변수 맵 위에 하나를 더 위치시켜 3 차원으로 만듬 하층의 항은 0 에서 15 까지, 상층은 16 에서 31 까지 있으며, 하층의 항은 A ’ 를 포함하고 상층의 항들은 A 를 포함 2 차원으로 맵을 나타내기 위해 4 변수 맵의 각각의 사각형을 대각선으로 나누고, 대각선 아래에는 하층의 항을 놓고 대학선 위에는 상층의 항을 둔다.

5.55 변수 카노맵 5 변수 카노 맵 이들 항들은 결합 되지 않는다. 왜냐하면 이 항들은 다른 ( 이강혁 ) 층과 다른 행에 있기 때문이다.( 두 변수가 다름 ) 이들 8 항들은 BD ’ 로 결합 ( 마지막두 행으 로 부터 B 와 위의 두 열로 부터 D ’ ; 상층 과 하층에 각각 4 개의 항들이 있으므로 A 는 소거된다 ) 이들 4 개 항들은 ( 상층으로 부터 4 개와 하층의 2 개 ) CDE( 중앙의 2 행으로 부터 C 와 열로 부터 DE) 로 되기 위해 결합 맨 윗층에 있 두 항들은 AB ’ DE ’ 로 합해진다.

5.55 변수 카노맵 Figure 5-22 상층 또는 하층의 항은 4 변수 맵의 항 처럼 결합된다. 그리고 같은 사각형 안에 대각선으로 나누어진 두 항들은 한 변수만 다르므로 서로 결합 할 수 있다. 예로 항 0 과 20 은 다른 행과 다른 층에 있기 때문에 인접한 것이 아니다. 인접한 항을 검사할 때 각 항은 5 개의 가능한 인접 사각형에 대한 검사해야 한다. ( 일반적으로 인접 사각형의 수 는 변수의 수와 같다 )

5.55 변수 카노맵 Figure 5-23 Resulting minimum solution 최소항 0 에 인접한 모든 1 은 P 1 에 포함 되기 때문에 주항 P 1 이 먼저 선택된다. 그 다음에 최소항 24 에 인접한 모든 1 을 포함 하는 P 2 가 선택 된다. “ 그 후에 남아 있는 모든 1 은 최소한 2 개의 다른 주항에 포함되므로 결과를 얻기 위해서는 시행 착오적으로 처리해야 한다. ”

5.55 변수 카노맵 Figure 5-24 Final solution 우선 m 16 에 인접한 모든 1 을 포함하는 p 1 을 먼저 선택한다. 다음에 m 3 에 인접한 모든 1 을 포함하는 P 2 를 선택한다. 그 다음 m 8 에 인접하는 모든 1 을 포함하는 p 3 을 선택한다. m 14 는 m 15 와 인접하기 때문에 P 4 또한 필수 주항이 된다. 더 이상 필수 주항이 없으므로 나머지 1 을 포 함하는 P 5 와 ( ) 또는 ( ) 을 선택한다.

5.6 카노맵의 다른 사용법 same 진리표를 이용하거나 대수적으로 수행한 많은 연산들을 카노맵을 이용 가능 맵은 진리표와는 형식이 다르나 같은 정보를 전달 F 에 대한 식을 맵에 작성하면 F 와 F ’ 에 대한 최소항과 최대항을 알아 낼 수 있다. 두 함수가 같은 카노맵을 가진다. AND(OR)  OR(AND) 가능

5.6 카노맵의 다른 사용법 Figure 5-25 카노맵은 식의 인수화를 쉽게 할 수 있음 맵을 검사하여 하나 이상의 변수를 공통으로 가지는 항을 나타낼 수 있다. 함수를 대수적으로 간략화 할 때, 어떤 단계를 거칠 것인가를 결정하는데 길잡이로 이용할 수 있다.

5.6Other Uses of Karnaugh Maps Figure 5-26 ACDE 최소항을 얻기 위해 ACDE 항을 더해야 한다는 것을 아래 맵으로 부터 알 수 있다. 이 항을 추가 이들 두 항들도 소거

5.7 다른 형태의 카노맵 Figure Veitch Diagrams 0 과 1 들고 카노맵의 위측과 측면을 표시하는 대신, 아래 그림과 같이 표시하는 경우도 있다 A 로 표시된 맵의 절반은 A=1 이고 나머지 절반은 A=0 이다. 다른 변수도 비슷하게 해석하면 됨 이와 같은 방식으로 표시된 맵을 바이치 다이아그램 (Veitch Diagram) 이라 한다. 이것은 최소항 이나 최대항 형식보다는 대수적 형식으로 주어진 함수를 작성하는데 유용

5.7Other Forms of Karnaugh Maps Figure Other Forms of Five-Variable Karnaugh Maps 5 변수 맵에 대해서는 2 개의 또 다른 형식을 사용한다. 한가지는 2 개의 4 변수 맵을 나란히 구성하는하는 것 또 다른 한가지는 이의 변형으로 아래 그림과 같이 미러 이미지.(mirror image) 맵을 이용 하는 것이다.