6 논리식의 간략화

학습목표 01. 2변수 카르노 맵 02. 3변수 카르노 맵 03. 4변수 카르노 맵 04. 선택적 카르노 맵 05. 논리식을 카르노 맵으로 작성 06. 5변수, 6변수 카르노 맵 07. Quine-McCluskey 최소화 알고리즘 08. 여러 개의 출력함수 09. NAND와 NOR 게이트로의 변환 10. XOR와 XNOR 게이트

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

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

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

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

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

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

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

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

03 4변수 카르노 맵

03 4변수 카르노 맵

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

03 4변수 카르노 맵 예제 6-3 다음 진리표로부터 카르노 맵을 작성하고 간략화하여라. A B C D F 0 0 0 0 예제 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

04 선택적 카르노 맵

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

05 논리식의 카르노 맵 작성

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

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

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

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

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

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

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

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

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

07 Quine-McCluskey 최소화 알고리즘 2. 기본 규칙 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)

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 ? 변수가 결합되는 경우 변수가 결합되지 못하는 경우

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

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

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

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)

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

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

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

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 -

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

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

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 없음

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

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

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

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 없음

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

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

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

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

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

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

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

08 여러 개의 출력함수

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

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

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

09 NAND와 NOR 게이트로의 변환 기본 게이트의 NAND, NOR 식 NOT AND OR NAND NOR XOR

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

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

09 NAND와 NOR 게이트로의 변환 예제 6-18 다음 카르노 맵을 NAND 게이트만으로 표현하여라. 이 논리식을 이중 부정을 하여 드모르간의 정리를 적용하여 변형.

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

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

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

09 NAND와 NOR 게이트로의 변환 예제 6-19 다음 논리식을 2입력 NAND 게이트만으로 표현하여라. AND 게이트 뒤에 NOT을 두개씩 붙이면,

09 NAND와 NOR 게이트로의 변환

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

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

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

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

09 NAND와 NOR 게이트로의 변환 예제 6-21 NOR 게이트만으로 표현하여라. A B C D F 1

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

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

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

10 XOR와 XNOR 게이트 4변수 XOR

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

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

10 XOR와 XNOR 게이트 ⊙

10 XOR와 XNOR 게이트 ⊙ ⊙ ⊙

10 XOR와 XNOR 게이트 XOR 게이트의 다른 표현 XOR : 입력된 신호가 서로 다를 때 출력이 1이 되는 게이트 77

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