Chapter 06. 논리식의 간소화.

Presentation on theme: "Chapter 06. 논리식의 간소화."— Presentation transcript:

1 Chapter 06. 논리식의 간소화

2 카르노 맵을 이용하여 논리식을 간소화할 수 있다. NAND와 NOR 게이트로 나타내는 방법을 이해하고 이를 응용할 수 있다.
퀸-맥클러스키 최소화 알고리즘을 이용하여 논리식을 간소화할 수 있다. 출력함수가 여러 개일 때 논리식을 공유하는 방법을 이해할 수 있다. XOR 게이트와 XNOR 게이트의 특징을 이해하고 이를 활용할 수 있다. 01. 2변수 카르노 맵 변수, 6변수 카르노 맵 02. 3변수 카르노 맵 퀸-맥클러스키 간소화 알고리즘 03. 4변수 카르노 맵 여러 개의 출력함수 04. 선택적 카르노 맵 09. NAND와 NOR 게이트로의 변환 05. 논리식의 카르노 맵 작성 10. XOR와 XNOR 게이트

3 01 2변수 카르노 맵 개요 2변수 카르노 맵 표현 방법 불 대수를 이용한 간소화하는 방법은 복잡하고 검증도 어렵다.
체계적으로 논리식을 간소화하기 위해 카르노 맵(1953년 Maurice Karnaugh가 소개)과 퀸-맥클러스키 방법(1956년 Willard Van Orman Quine과 Edward J. McCluskey 개발)이 필요 퀸-맥클러스키 방법은 많은 변수에 대해서도 쉽게 간소화할 수 있다. 2변수 카르노 맵 표현 방법 무관항(don't care) : 입력이 결과에 영향을 미치지 않는 최소항 ⅹ로 표시하거나 d로 표시한다.

4 01 2변수 카르노 맵 일반항과 무관항 표현 출력이 1이거나 무관항만 표시한다.
출력 0을 표시하여도 되지만 일반적으로 생략한다.

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

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

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

8 02 3변수 카르노 맵 간소화 예 1

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

10 02 3변수 카르노 맵 간소화 예 3

11 다른 묶음에 모두 포함되어 있으므로 중복하여 묶지 않는다.
02 3변수 카르노 맵 간소화 예 4 양쪽 끝은 연결되어 있다. 다른 묶음에 모두 포함되어 있으므로 중복하여 묶지 않는다.

12 02 3변수 카르노 맵 간소화 예 5 가능한 크게 묶는다. 크게 묶지 않아 간소화가 덜 된 식

13 02 3변수 카르노 맵 간소화 예 6 A B C F 1 세 번 중복하여 묶인 경우

14 02 3변수 카르노 맵 간소화 예 7 모두 0이면 논리식은 F=0이다. 모두 1이면 논리식은 F=1이다.

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

16 Section 변수 카르노 맵 예제 여러 가지 4변수 카르노 맵의 예제.

17 Section 변수 카르노 맵

18 Section 변수 카르노 맵

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

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

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

22 04 선택적 카르노 맵 <5가지 답이 가능한 경우>

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

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

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

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

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

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

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

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

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

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

33 Section 08 여러 개의 출력함수

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

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

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

37 08 여러 개의 출력함수 선택되지 않은 부분을 찾아 묶는다.

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

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

40 09 NAND와 NOR 게이트로의 변환 기본 게이트 NAND 게이트로 표현 NOR 게이트로 표현 NAND NOR

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

42 09 NAND와 NOR 게이트로의 변환 다른 방법 : AND 게이트 뒤에 OR 게이트가 있을 때 이중부정 적용

43 09 NAND와 NOR 게이트로의 변환 2입력 NAND 게이트만으로 나타내기

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

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

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

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

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

49 09 NAND와 NOR 게이트로의 변환 2입력 NOR 게이트만으로 나타내기 OR와 AND 사이에 이중 부정

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

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

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

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

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

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

56 10 XOR와 XNOR 게이트

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

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

59