6 논리식의 간략화 IT CookBook, 디지털 논리회로

학습목표 카르노 맵을 이용한 논리식의 간략화에 대해 알아본다. Quine-McCluskey 최소화 알고리즘에 대해 알아본다. 출력함수가 여러 개일 때 논리식을 공유하는 방법에 대해 알아본다. NAND와 NOR 게이트로 나타내는 방법을 알아본다. XOR 게이트와 XNOR 게이트의 특징에 대해 알아본다.

목 차 1. 2변수 카르노 맵 2. 3변수 카르노 맵 3. 4변수 카르노 맵 4. 선택적 카르노 맵 5. 논리식을 카르노 맵으로 작성 6. 5변수, 6변수 카르노 맵 7. Quine-McCluskey 최소화 알고리즘 8. 여러 개의 출력함수 9. NAND와 NOR 게이트로의 변환 10. XOR와 XNOR 게이트

(Simplified Boolean expression) Section 01 2변수 카르노 맵 진리식(부울대수식) 간소화 정규논리식 (Canonical Boolean Expression) 간소화된 논리식 (Simplified Boolean expression) 1. 부울대수법칙을 이용한 간소화 2. 카르노 맵 간소화 3. QM(퀸-맥클러스키) 간소화

Section 01 2변수 카르노 맵 2변수 카르노 맵 표현 방법 일반항과 무관항 표현 무관항(don't care) : 입력이 결과에 영향을 미치지 않는 최소항(Minterm). X로 표시하거나 d로 표시한다.

Section 01 2변수 카르노 맵 카르노맵을 이용한 간략화 방법 간략화 예 중복하여 묶어도 된다. ① 1, 2, 4, 8, 16개로 그룹을 지어 묶는다. ② 바로 이웃해 있는 항들끼리 묶는다. ③ 반드시 직사각형이나, 정사각형의 형태로 묶어야만 한다. 간략화 예 1 중복하여 묶어도 된다. a b f 0 0 0 1 1 0 1 1 1 1

Section 02 3변수 카르노 맵 3변수 카르노 맵 표현 방법

Section 02 3변수 카르노 맵 간략화 예 양쪽 끝은 연결되어 있다. 양쪽 끝은 연결되어 있다.

Section 02 3변수 카르노 맵 간략화 예(Cont’d) 가능한 크게 묶는다.

Section 02 3변수 카르노 맵 간략화 예(Cont’d) 세 번 중복하여 묶었다. a b c f 0 0 0 0 0 1 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 세 번 중복하여 묶었다.

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

Section 03 4변수 카르노 맵 예제 6-1 여러 가지 4변수 카르노 맵의 예제.

Section 03 4변수 카르노 맵

Section 03 4변수 카르노 맵

Section 03 4변수 카르노 맵 예제 6-2 다음 식과 같이 무관항이 있을 경우 카르노 맵을 이용하여 간략화

Section 03 4변수 카르노 맵 예제 6-3 다음 진리표로부터 카르노 맵을 작성하고 간략화하여라. A B C D F 예제 6-3 다음 진리표로부터 카르노 맵을 작성하고 간략화하여라. A B C D F 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 x 1

Section 04 선택적 카르노 맵 cf) 무관항이 있는 경우 - pp.208, 그림 6-21 참조

Section 05 논리식의 카르노 맵 작성 논리식에서 생략된 부분을 찾아서 Minterm으로 변경

Section 05 논리식의 카르노 맵 작성

최소항으로 바꾸지 않고 간략화의 반대방법으로 카르노 맵 작성 Section 05 논리식의 카르노 맵 작성 예제 6-4 다음 논리식을 카르노 맵으로 작성하고 간략화. 최소항으로 바꾸지 않고 간략화의 반대방법으로 카르노 맵 작성

Section 05 논리식의 카르노 맵 작성 예제 6-5 다음 논리식을 카르노 맵으로 작성하고 간략화.

Section 06 5변수, 6변수 카르노 맵 5변수인 경우 5변수 카르노 맵

Section 06 5변수, 6변수 카르노 맵 예제 6-6 다음 5변수 논리함수를 카르노 맵을 이용하여 간략화

Section 06 5변수, 6변수 카르노 맵 6변수인 경우 6변수 카르노 맵

Section 06 5변수, 6변수 카르노 맵 예제 6-7

Section 07 Quine-McCluskey 최소화 알고리즘 Implicant: 간략화되거나 최소화될 항. PI(Prime Implicant) : 카르노 맵에서 최대 크기로 묶어서 만들어진 곱의 항. EPI(Essential Prime Implicant) : PI중에서 유일한 PI PI와 EPI는 카르노 맵을 조사하여 결정. PI의 집합은 함수를 구성하는 각 최소항을 모두 포함하며, 각 최소항은 PI집합 중에 최소한 한 개의 PI에는 포함된다. Prime Implicant Essential Prime Implicant

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

Section 07 Quine-McCluskey 최소화 알고리즘 QM 방법은 간단하게 2단계로 이루어진다. 단계 1 : 을 적용하여 가능한 한 많은 변수들을 제거한다. 결과 항들은 PI가 된다. 단계 2 : PI 차트를 이용하여 함수를 PI의 최소 집합들로 표현한다. QM 방법을 이용한 간략화 과정

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

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

Section 07 Quine-McCluskey 최소화 알고리즘 QM 방법에서의 인덱스 A B C D 10진 표기 index 0 index 1 1 2 4 8 index 2 3 5 6 9 10 12 index 3 7 11 13 14 index 4 15

Section 07 Quine-McCluskey 최소화 알고리즘 예 인덱스 0의 000과 인덱스 1의 010은 가운데 비트 하나만 다르므로 결합될 수 있으며, 0-0이 된다. 인덱스 1의 010과 인덱스 2의 101은 서로 인접한 인덱스이지만 두 개 이상의 비트가 다르므로 결합할 수 없다. A B C 10진 표기 index 0 index 1 1 2 4 index 2 5 index 3 7

Section 07 Quine-McCluskey 최소화 알고리즘 3. QM 방법을 이용한 간략화 첫 번째 과정 minterm 10진 2진 index 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

Section 07 Quine-McCluskey 최소화 알고리즘 두 번째 과정 세 번째 과정 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 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 - (0,4,1,5)

Section 07 Quine-McCluskey 최소화 알고리즘 예제 6-8 다음 식을 QM방법을 이용하여 간략화 하여라. Column 1 index decimal A B C D (0) 0 0 0 0  1 (1) (2) (8) 0 0 0 1 0 0 1 0 1 0 0 0 2 (3) (5) (10) (12) 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 3 (7) (13) 0 1 1 1 1 1 0 1 4 (15) 1 1 1 1 Column 2 index decimal A B C D (0,1) (0,2) (0,8) 0 0 0 - 0 0 - 0 - 0 0 0  1 (1,3) (1,5) (2,3) (2,10) (8,10) (8,12) 0 0 - 1 0 - 0 1 0 0 1 - - 0 1 0 1 0 - 0 1 - 0 0 2 (3,7) (5,7) (5,13) (12,13) 0 - 1 1 0 1 - 1 - 1 0 1 1 1 0 - 3 (7,15) (13,15) - 1 1 1 1 1 - 1 Column 3 decimal A B C D (0,1,2,3) (0,2,1,3) (0,2,8,10) (0,8,2,10) 0 0 - - - 0 - 0 (1,3,5,7) (1,5,3,7) 0 - - 1 (5,7,13,15) (5,13,7,15) - 1 - 1

Section 07 Quine-McCluskey 최소화 알고리즘 IMPLICANTS 1 2 3 5 7 8 10 12 13 15 0 0 - - X - 0 - 0 (X) 0 - - 1 - 1 - 1 1 – 0 0 1 1 0 - Essential

Section 07 Quine-McCluskey 최소화 알고리즘 예제 6-9 다음 식을 QM방법을 이용하여 간략화 하여라. Column 1 index decimal a b c d (0) 0 0 0 0 1 (1) (2) (8) 0 0 0 1 0 0 1 0 1 0 0 0 2 (3) (6) (9) 0 0 1 1 0 1 1 0 1 0 0 1 3 (7) (14) 0 1 1 1 1 1 1 0 4 (15) 1 1 1 1

Section 07 Quine-McCluskey 최소화 알고리즘 Column 1 index decimal a b c d (0) 0 0 0 0  1 (1) (2) (8) 0 0 0 1 0 0 1 0 1 0 0 0 2 (3) (6) (9) 0 0 1 1 0 1 1 0 1 0 0 1 3 (7) (14) 0 1 1 1 1 1 1 0 4 (15) 1 1 1 1 Column 2 index decimal a b c d (0,1) (0,2) (0,8) 0 0 0 - 0 0 - 0 - 0 0 0  1 (1,3) (1,9) (2,3) (2,6) (8,9) 0 0 - 1 - 0 0 1 0 0 1 - 0 - 1 0 1 0 0 - 2 (3,7) (6,7) (6,14) 0 - 1 1 0 1 1 - - 1 1 0 3 (7,15) (14,15) - 1 1 1 1 1 1 - Column 3 index decimal a b c d (0,1,2,3) (0,1,8,9) 0 0 - - - 0 0 - 1 (2,3,6,7) 0 - 1 - 2 (6,7,14,15) - 1 1 -

Section 07 Quine-McCluskey 최소화 알고리즘 IMPLICANTS 1 2 3 6 7 8 9 14 15 0 0 - - X - 0 0 - (X) 0 - 1 - - 1 1 - Essential

Section 07 Quine-McCluskey 최소화 알고리즘 예제 6-10 다음 식을 QM방법을 이용하여 간략화 하여라. Column 1 index decimal a b c d 없음 1 (1) (2) (4) 0 0 0 1 0 0 1 0 0 1 0 0 2 (3) (5) (9) 0 0 1 1 0 1 0 1 1 0 0 1 3 (7) 0 1 1 1 4 (15) 1 1 1 1

Section 07 Quine-McCluskey 최소화 알고리즘 Column 1 index decimal a b c d 1 (1) (2) (4) 0 0 0 1 0 0 1 0 0 1 0 0  2 (3) (5) (9) 0 0 1 1 0 1 0 1 1 0 0 1 3 (7) 0 1 1 1 4 (15) 1 1 1 1 Column 2 index decimal a b c d 1 (1,3) (1,5) (1,9) (2,3) (4,5) 0 0 - 1 0 - 0 1 - 0 0 1 0 0 1 - 0 1 0 -  2 (3,7) (5,7) 0 - 1 1 0 1 - 1 3 (7,15) - 1 1 1 Column 3 index decimal a b c d 1 (1,3,5,7) (1,5,3,7) 0 - - 1 2 없음

Section 07 Quine-McCluskey 최소화 알고리즘 IMPLICANTS 1 2 3 4 5 7 9 15 0 - - 1 X - 0 0 1 (X) 0 0 1 - 0 1 0 - - 1 1 1 Essential

Section 07 Quine-McCluskey 최소화 알고리즘 예제 6-11 무관항 조건을 가진 다음 식을 QM방법을 이용하여 간략화 하여라. Column 1 index decimal a b c d (0) 0 0 0 0  1 (1) (2*) (4) (8) 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 2 (3*) (6) (9*) 0 0 1 1 0 1 1 0 1 0 0 1 3 (14) 1 1 1 0 4 (15) 1 1 1 1 Column 2 index decimal a b c d (0,1) (0,2*) (0,4) (0,8) 0 0 0 - 0 0 - 0 0 - 0 0 - 0 0 0  1 (1,3*) (1,9*) (2*,3*) (2*,6) (4,6) (8,9*) 0 0 - 1 - 0 0 1 0 0 1 - 0 - 1 0 0 1 - 0 1 0 0 - 2 (6,14) - 1 1 0 3 (14,15) 1 1 1 - Column 3 index decimal a b c d (0,1,2*,3*) (0,2*,4,6) (0,8,1,9*) 0 0 - - 0 - - 0 - 0 0 - 1 없음 2

Section 07 Quine-McCluskey 최소화 알고리즘 IMPLICANTS 1 4 6 8 14 15 0 0 - - X 0 - - 0 (X) - 0 0 - - 1 1 0 1 1 1 - Essential

Section 07 Quine-McCluskey 최소화 알고리즘 예제 6-12 QM방법을 이용하여 POS 형태로 간략화 하여라. Column 1 index decimal a b c d 1 (2*) 0 0 1 0  2 (3*) (5) (9*) (10) (12) 0 0 1 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 0 0 3 (7) (11) (13) 0 1 1 1 1 0 1 1 1 1 0 1 Column 2 index decimal a b c d 1 (2*,3*) (2*,10) 0 0 1 - - 0 1 0  2 (3*,7) (3*,11) (5,7) (5,13) (9*,11) (9*,13) (10,11) (12,13) 0 - 1 1 - 0 1 1 0 1 - 1 - 1 0 1 1 0 - 1 1 - 0 1 1 0 1 - 1 1 0 - Column 3 index decimal a b c d 1 (2*,10,3*,11) - 0 1 - 2 없음

Section 07 Quine-McCluskey 최소화 알고리즘 IMPLICANTS 5 7 10 11 12 13 - 0 1 - (X) X 0 - 1 1 0 1 - 1 - 1 0 1 1 0 - 1 1 1 1 - Essential

Section 07 Quine-McCluskey 최소화 알고리즘 예제 6-13 다음 식을 QM방법을 이용하여 SOP 형태로 간략화 하여라. Column 1 index decimal a b c d (0) 0 0 0 0  1 (1) (2) (8) 0 0 0 1 0 0 1 0 1 0 0 0 2 (5) (6) (9) (10) 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 3 (7) (14) 0 1 1 1 1 1 1 0 Column 2 index decimal a b c d (0,1) (0,2) (0,8) 0 0 0 - 0 0 - 0 - 0 0 0  1 (1,5) (1,9) (2,6) (2,10) (8,9) (8,10) 0 - 0 1 - 0 0 1 - 0 1 0 1 0 0 - 1 0 - 0 2 (5,7) (6,7) (6,14) (10,14) 0 1 - 1 0 1 1 - - 1 1 0 1 - 1 0 Column 3 index decimal a b c d (0,1,8,9) (0,2,8,10) (0,8,1,9) (0,8,2,10) - 0 0 - - 0 - 0 1 (2,6,10,14) (2,10,6,14) - - 1 0

Section 07 Quine-McCluskey 최소화 알고리즘 IMPLICANTS 1 2 5 6 7 8 9 10 14 0 - 0 1 X 0 1 - 1 0 1 1 - - 0 0 - (X) - 0 - 0 - - 1 0 Essential

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

Section 08 여러 개의 출력함수 예제 6-14 다음과 같은 2개의 논리함수를 하나의 시스템으로 통합

Section 08 여러 개의 출력함수 예제 6-15

Section 08 여러 개의 출력함수 예제 6-16

Section 08 여러 개의 출력함수

Section 08 여러 개의 출력함수 예제 6-17 세 함수끼리 서로 독립된 부분과 두 개의 함수에서 같은 영역 중 크게 묶을 수 있는 영역을 먼저 찾는다.

Section 08 여러 개의 출력함수 나머지 중에서 공통된 부분과 독립된 부분을 찾는다.

Section 08 여러 개의 출력함수 무관항을 갖는 경우 서로 독립된 영역을 찾은 후, 선택되지 않는 부분을 찾아서 나머지를 묶는다.

Section 09 NAND와 NOR 게이트로의 변환 회로를 설계할 때에 MAND와 NOR 게이트만으로 모든 회로를 만들 수 있다. 기본 게이트의 NAND, NOR 식 NOT AND OR NAND NOR XOR

Section 09 NAND와 NOR 게이트로의 변환 기본 게이트 NAND 게이트로 표현 NOR 게이트로 표현 NOT AND OR XOR

Section 09 NAND와 NOR 게이트로의 변환 기본 게이트의 NAND, NOR 회로(Cont’d) 기본 게이트 NAND 게이트로 표현 NOR 게이트로 표현 NAND NOR

Section 09 NAND와 NOR 게이트로의 변환 이 논리식을 이중 부정을 하여 드모르간의 정리를 적용하여 변형.

Section 09 NAND와 NOR 게이트로의 변환 Another Method 1

Section 09 NAND와 NOR 게이트로의 변환 Another Method 2 2입력 NAND 게이트만으로 나타내기 위해 이 논리식을 변형.

Section 09 NAND와 NOR 게이트로의 변환 모든 AND 게이트의 뒤에 NOT을 두 개 붙인다.

Section 09 NAND와 NOR 게이트로의 변환 AND 게이트 뒤에 NOT을 두개씩 붙이면,

Section 09 NAND와 NOR 게이트로의 변환

Section 09 NAND와 NOR 게이트로의 변환 예제 6-20 SOP로 나타낸 논리식을 NOR 게이트만으로 표현하여라. 0을 묶어서 SOP 식으로 표현하면, 이것을 부정하게 되면 f 가 되며, 드모르간의 정리를 적용하면 다음과 같은 POS식이 만들어진다.

Section 09 NAND와 NOR 게이트로의 변환 논리식을 이중 부정을 하여 드모르간의 정리를 적용하여 변형. 또는 OR 게이트의 출력에 이중 부정을 하여 다음과 같이 할 수 있다.

Section 09 NAND와 NOR 게이트로의 변환

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

Section 09 NAND와 NOR 게이트로의 변환 B C D F 1

Section 09 NAND와 NOR 게이트로의 변환

Section 09 NAND와 NOR 게이트로의 변환 OR의 출력에 NOT을 2개 붙이면, 나머지 OR와 AND를 NOR로 바꾸기 위해서 OR의 출력에 NOT을 두 개 붙이고, AND의 입력 쪽에 NOT을 두 개 붙인다.

Section 10 XOR와 XNOR 게이트 XOR : 홀수개의 입력이 1인 경우, 출력이 1이 되는 게이트 3변수 XOR

Section 10 XOR와 XNOR 게이트 4변수 XOR

Section 10 XOR와 XNOR 게이트 XNOR : 짝수개의 입력이 1인 경우 출력이 1이 되는 게이트 ⊙ ⊙

Section 10 XOR와 XNOR 게이트 4변수 XNOR ⊙ ⊙ ⊙

Section 10 XOR와 XNOR 게이트 ⊙

Section 10 XOR와 XNOR 게이트 ⊙ ⊙ ⊙

Section 10 XOR와 XNOR 게이트 XOR 게이트의 다른 표현 79

Section 10 XOR와 XNOR 게이트 XOR 게이트의 다른 표현 (Cont’d) XOR를 NAND 만으로 표현하기 위하여 이중부정을 취하고 드모르간의 정리를 적용하여 정리 80

6장 논리식의 간략화 끝