Prof. Seewhy Lee Presents Ch. 6 논리식의 간소화 정적 평형 Prof. Seewhy Lee Presents

카르노 맵을 이용하여 논리식을 간소화할 수 있다. NAND와 NOR 게이트로 나타내는 방법을 이해하고 이를 응용할 수 있다. 퀸-맥클러스키 최소화 알고리즘을 이용하여 논리식을 간소화할 수 있다. 출력함수가 여러 개일 때 논리식을 공유하는 방법을 이해할 수 있다. XOR 게이트와 XNOR 게이트의 특징을 이해하고 이를 활용할 수 있다.

Contents 1. 2변수 카르노 맵 2. 3변수 카르노 맵 3. 4변수 카르노 맵 4. 선택적 카르노 맵 5. 논리식의 카르노 맵 작성 6. 5변수, 6변수 카르노 맵 7. 퀸-맥클러스키 간소화 알고리즘 8. 여러 개의 출력함수 9. NAND와 NOR 게이트로의 변환 10. XOR와 XNOR 게이트

1. 2변수 카르노 맵

불 대수를 이용한 간소화하는 방법은 복잡하고 검증도 어렵다. 체계적으로 논리식을 간소화하기 위해 카르노 맵(1953년 Maurice Karnaugh가 소개)과 퀸-맥클러스키 방법(1956년 Willard Van Orman Quine과 Edward J. McCluskey 개발)이 필요 퀸-맥클러스키 방법은 많은 변수에 대해서도 쉽게 간소화할 수 있다.

2변수 카르노 맵 표현 방법

일반항과 무관항 표현 출력이 1이거나 무관항만 표시한다.

카르노 맵을 이용한 간소화 방법 ① 출력이 같은 항을 1, 2, 4, 8, 16개로 그룹을 지어 묶을 수 있고, ② 바로 이웃한 항들끼리 묶을 수 있으며, ③ 반드시 직사각형이나 정사각형의 형태로 묶어야 하고, ④ 최대한 크게 묶는다. ⑤ 중복하여 묶어서 간소화된다면 중복하여 묶는다. ⑥ 무관항의 경우 간소화될 수 있으면 묶어 주고, 그렇지 않으면 묶지 않는다. 불 대수의 법칙으로 풀면 A=0이므로 A B=0 and 1이므로 제거 즉, 한 변수에서 서로 다른 값이 묶여지면 제거한다.

간소화 예 중복하여도 되므로 크게 묶는다. A B F 0 0 0 1 1 0 1 1 1 불 대수의 법칙으로 풀면

2. 3변수 카르노 맵

3변수 카르노 맵 표현 방법 행과 열을 바꾸어도 상관없다. 설계자가 선호하는 방법을 선택하면 된다.

간소화 예 1

간소화 예 2 양쪽 끝은 연결되어 있다. 동일한 카르노 맵 이웃하는 비트들이 한 비트만 다르면 순서는 관계없다.

간소화 예 3

다른 묶음에 모두 포함되어 있으므로 중복하여 묶지 않는다. 간소화 예 4 양쪽 끝은 연결되어 있다. 다른 묶음에 모두 포함되어 있으므로 중복하여 묶지 않는다.

간소화 예 5 가능한 크게 묶는다. 크게 묶지 않아 간소화가 덜 된 식

간소화 예 6 A B C F 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 세 번 중복하여 묶인 경우

간소화 예 7 모두 0이면 논리식은 F=0이다. 모두 1이면 논리식은 F=1이다.

3. 4변수 카르노 맵

4변수 카르노 맵 표현 방법 상하 좌우는 연결되어 있다.

4. 선택적 카르노 맵

카르노 맵에서 선택적으로 묶을 수 있는 경우 <2가지 답이 가능한 경우>

<5가지 답이 가능한 경우>

5. 논리식의 카르노 맵

논리식에서 생략된 부분을 찾아서 최소항(Minterm)으로 변경

6. 5변수와 6변수의 카르노 맵

5변수인 경우 <5변수 카르노 맵>

6변수인 경우 <6변수 카르노 맵>

7. 퀸-맥클러스키 간소화 알고리즘

퀸-맥클러스키(Quine-McCluskey) 간소화 알고리즘 1. QM 알고리즘 퀸-맥클러스키(Quine-McCluskey) 간소화 알고리즘 퀸(Willard Van Orman Quine)과 맥클러스키(Edward J. McCluskey)가 1956년에 개발 컴퓨터 알고리즘으로 개발하기에 적합 입력변수가 4개 이하이면 카르노 맵을 이용하는 것이 편리함 입력변수가 5개 이상인 경우에는 퀸-맥클러스키(이하 QM) 알고리즘이 유용 용어 정리 Implicant: 간소화되거나 최소화될 항 PI(Prime Implicant) : 최종적으로 남아있는 곱의 항 EPI(Essential Prime Implicant) : PI중에서 유일한 PI

Quine-McCluskey 방법 QM 과정 QM 방법은 최소 SOP 식으로 만들어 진다. 진리표에서 최소항을 모두 찾는다. 최소항 중에서 입력변수에 1이 나타나는 개수에 따라서 인덱스(index)를 매겨 그룹을 만든다. 각 그룹내의 항들을 모두 비교하여 한 비트만 다른 항들을 찾아서 간소화하고, 간소화 에 사용된 항들을 표시한다. 위 ③의 과정을 반복하여 더 이상 간소화되지 않을 때까지 계속한다. 간소화 과정이 끝나고 표시되지 않은 항들이 PI(prime implicants, 주항)가 된다. 중복된 PI를 찾기 위하여 차트를 만들고, EPI(essential prime implicants, 필수주항)를 찾 는다. EPI에 포함되는 PI들을 제거한다. EPI에 포함되지 않은 항들에 대해서 최소 개수의 SOP 식을 찾는다.

QM 방법은 크게 2단계로 이루어진다. QM 방법을 이용한 간소화 과정 단계 1 : 인덱스별로 구분하고 AB+A B =A B+ B =A를 적용하여 가능한 변수들을 제거한다. 결과 항들은 PI가 된다. 단계 2 : PI 차트를 이용하여 함수를 PI의 최소 집합들로 표현한다. QM 방법을 이용한 간소화 과정 민텀항의 합 규칙을 이용하여 PI 들을 구한다. PI 차트를 이용하여 PI 집합을 구한다. 입력

기본 규칙 QM 방법은 규칙 A+ A =1 을 반복 적용하여 최소화한다. 함수의 각 항들은 2진 형태(0과 1)로 표현하고, 변수가 제거된 곳은 대시(-)를 사 용한다. A B C : 101로 표현 (A=1, B=0, C=1) A B C : 010로 표현 (A=0, B=1, C=0) A B : 10-로 표현 (A=1, B=0, C= ) AC : 1-1로 표현 (A=1, B=, C=1)

<변수가 결합되지 못하는 경우> QM 방법을 이용한 간소화 과정 두 자리가 다르기 때문에 결합될 수 없다. A B C D 0 0 1 1 1 0 1 1 - 0 1 1 A B C D 0 1 1 1 1 0 1 1 ? <변수가 결합되는 경우> <변수가 결합되지 못하는 경우> 두 항을 결합하기 위한 QM 방법의 첫 번째 규칙은 오직 한 비트만 다를 때 제 거된다는 것이다. 첫 번째 규칙을 적용하기 위해서 minterm 항들을 서로 1의 개수에 따라서 재배 열한다. minterm 항을 2진 형태로 표현하여 1의 개수에 따라서 인덱스를 매기며, 인덱 스 0, 인덱스 1, 인덱스 2 등으로 나열한다.

QM 방법에서의 인덱스 분류 A B C D 10진 표기 index 0 index 1 1 2 4 8 index 2 3 5 6 9 index 1 1 2 4 8 index 2 3 5 6 9 10 12 index 3 7 11 13 14 index 4 15

다음 식을 인덱스로 분류하면 표와 같다. * 출력이 1인 항만 표시한다. A B C F  인덱스 10진수 0 0 0 1 0 0 1 0 1 0 2 0 1 1 4 1 0 0 3 1 0 1 6 1 1 0 * 출력이 1인 항만 표시한다. 1 1 1

2. QM 알고리즘을 이용한 간소화 인덱스 표 만들기 minterm 10진 2진 index 0 0 0 1 0 0 1 4 0 0 0 1 0 0 1 4 1 0 0 5 1 0 1 2 인덱스 표 만들기 Column 1 index decimal A B C (0) 0 0 0 1 (1) (4) 0 0 1 1 0 0 2 (5) 1 0 1

첫 번째 과정 두 번째 과정 Column 1 index decimal A B C (0) 0 0 0  1 (1) (4) (0) 0 0 0  1 (1) (4) 0 0 1 1 0 0 2 (5) 1 0 1 Column 2 index decimal A B C (0,1) (0,4) 0 0 - - 0 0 1 (1,5) (4,5) - 0 1 1 0 - 두 번째 과정 Column 1 index decimal A B C (0) 0 0 0  1 (1) (4) 0 0 1 1 0 0 2 (5) 1 0 1 Column 2 index decimal A B C (0,1) (0,4) 0 0 - - 0 0  1 (1,5) (4,5) - 0 1 1 0 - Column 3 decimal A B C (0,1, 4,5) - 0 - ●

8. 여러 개의 출력 함수

여러 개의 출력함수를 갖는 시스템의 통합 두 개의 시스템으로 분리되어 있는 것을 하나의 시스템으로 통합하는 것이 가 능하고, 공유 가능한 게이트가 있을 때 공유하여 시스템을 구성하면 경제적으 로 좋은 시스템이 될 수 있다. 2개로 분리된 시스템 하나로 통합된 시스템

무관항을 갖는 경우 서로 독립된 영역을 찾은 후, 선택되지 않는 부분을 찾아서 나머지를 묶는다.

선택되지 않은 부분을 찾아 묶는다.

9. NAND / NOR 게이트로의 변환

기본 게이트의 NAND, NOR 식 NOT AND OR NAND NOR XOR

기본 게이트의 NAND, NOR 회로 기본 게이트 NAND 게이트로 표현 NOR 게이트로 표현 NOT AND OR XOR

기본 게이트 NAND 게이트로 표현 NOR 게이트로 표현 NAND NOR

다른 방법 : AND 게이트 뒤에 OR 게이트가 있을 때 이중부정 적용

2입력 NAND 게이트만으로 나타내기

모든 AND 게이트의 뒤에 NOT을 두 개 붙인다.

2입력 NOR 게이트만으로 나타내기 OR와 AND 사이에 이중 부정

나머지 OR와 AND를 NOR로 바꾸기 위해서 OR의 출력에 NOT을 두 개 붙이고, AND의 입력 쪽에 NOT을 두 개 붙인다.

10. XOR / XNOR Gates

XOR : 홀수개의 입력이 1인 경우, 출력이 1이 되는 게이트

XNOR : 짝수개의 입력이 1인 경우 출력이 1이 되는 게이트

XOR : 두 입력이 모두 0이거나 1이면 출력이 0이 되는 게이트

XOR를 NAND 만으로 표현하기 위하여 이중부정을 취하고 드모르간의 정리를 적용하여 정리

Thanks for your attention~!! Prof. Seewhy Lee