제3장 부울식의 간략화 내용 3.1 부울식의 대수적 간략화

Presentation on theme: "제3장 부울식의 간략화 내용 3.1 부울식의 대수적 간략화"— Presentation transcript:

1 제3장 부울식의 간략화 내용 3.1 부울식의 대수적 간략화
3.1 부울식의 대수적 간략화 그룹화 후의 부울정리 적용/ 제거에 의한 표준형으로 확장/ 드모르강 정리 사용 3.2 배치도 3.3 카르노맵 간략화 기법/ 4변수 맵/ 필수주항을 이용한 최상의 간략화 / 비표준형 부울식의 카르노맵/ 무시항을 갖는 부울식의 카르노맵/ 카르노맵에서 0을 사용한 간략화 / 다중출력 간략화/ 대규모 카르노맵 3.4 테이블 방법 : 간략화 원리와 방법 / 무시항 조건이 있는 경우

2 제 3장 부울식의 간략화 3.1 부울식의 대수적 간략화 3.1.1 그룹화(grouping) 후의 부울정리 적용

3 제 3장 부울식의 간략화 3.1 부울식의 대수적 간략화 3.1.1 그룹화(grouping) 후의 부울정리 적용
(1) 콘센서스 정리

4 제 3장 부울식의 간략화 3.1 부울식의 대수적 간략화 3.1.1 그룹화(grouping) 후의 부울정리 적용
(1) 콘센서스 정리 부울식 AB+A’C 한 항(AB)에 있는 변수(A)가 또 다른 항(A'C)에 그 변수의 보수가 존재하는 쌍의 항들(AB, A'C)이 주어지면, 두 개의 항에서 선택된 변수(A)와 그 변수의 보수(A')를 제외하고 남은 변수들(B와 C)을 곱하여 만들어진 항(BC)을 콘센서스 항(consensus term)이라 하고 생략이 가능하다. 즉 다음의 부울식이 성립 AB+A’B = AB+A’C+BC 또 다른 형태 : (A+B)(A’+C) = (A+B)(A’+C)(B+C)

5 제 3장 부울식의 간략화 3.1 부울식의 대수적 간략화 3.1.2 제거에 의한 표준형으로 확장

6 제 3장 부울식의 간략화 3.1 부울식의 대수적 간략화 3.1.3 드모르강 정리 사용

7 제 3장 부울식의 간략화 3.2 배치도 1952년 배치(E.W. Veitch)에 의해서 제안된 배치도는 벤도(Venn diagram)를 개량한 것으로 벤도의 원을 사각형 모양의 셀(cell)로 바꾸고, 사각형 셀을 매트릭스 형태로 구성한 것이다. 2변수 및 3변수 배치도 부울식

8 제 3장 부울식의 간략화 3.2 배치도 1952년 배치(E.W. Veitch)에 의해서 제안된 배치도는 벤도(Venn diagram)를 개량한 것으로 벤도의 원을 사각형 모양의 셀(cell)로 바꾸고, 사각형 셀을 매트릭스 형태로 구성한 것이다. 2변수 및 3변수 배치도

9 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 묶여질 수 있는 항을 간단히 시각적으로 확인하는 방법을 제공
각 셀에 표기한 문자변수 대신에 1과 0을 기입 사각형의 2차원적인 배열로 구성 사각형은 하나의 최소항(minterm)과 연관 어떤 최소항에서 하나의 변수가 사실이고 다른 최소항에서 동일한 변수가 보수인 것 외에는 수직이든 수평이든 인접한 사각형의 최소항은 동일한 변수를 가지고 있다.

10 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 2변수와 3변수 카르노맵 (1) 2변수 카르노맵
2변수에는 4개의 변수 결합 정사각형 형태를 그리고 4개의 작은 정사각형으로 모양을 만들다. 각 결합은 카르노맵의 각 셀에 하나씩 할당한다. 셀은 맵의 양 가장자리를 따라 2개 변수에 의해서 분류된다. 이 경우 세로에 1개 변수(A) 그리고 가로에 1개 변수(B)를 할당한다. 인접한 셀은 변수 하나 차이로 항에 할당되는데 가로 방향으로 0, 1 그리고 세로 방향으로 0, 1이 된다. 0은 변수가 보수이고 1은 변수가 보수가 아니라는 것을 나타낸다. 가로 방향 또는 세로 방향으로 인접한 셀은 변수 하나 차이로 항에 할당되므로 하나의 셀로부터 다음 셀로 옮김에 따라 하나의 변수가 변한다. 왼쪽 제일 위 셀은 A'B'(즉, 00)이고 이를 기준하여 오른쪽 인접셀은 A'B(즉, 01) 그리고 아랫 방향 인접셀은 AB'(즉, 10)가 된다. 나머지 하나 아래 오른쪽은 AB(즉, 11)가 된다. 큰 정사각형 왼쪽에 1을 감싸고 있는 A 변수와 위쪽 B 변수 라벨 표시는 뒤에 간략화 과정에 유용하게 이용된다. 변수 라벨 표시는 변수값이 1인 곳에 하므로 표시 안된 곳은 변수값이 0이 된다.

11 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 2변수와 3변수 카르노맵 (2) 3변수 카르노맵

12 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 2변수와 3변수 카르노맵 (2) 3변수 카르노맵 함수 맵핑

13 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 간략화 기법

14 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 간략화 기법 함수 맵핑 간략화 결과

15 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.1 간략화 기법 (1) 가장자리(edge)간의 간략화
함수 맵핑

16 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.1 간략화 기법 (2) 대규모 그룹화

17 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.1 간략화 기법 (3) 진리표와 카르노맵
(4) 카르노맵에서 최소항 번호를 부여 그림

18 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.2 4변수 카르노맵
변수 카르노맵 4변수 부울식은 16개의 사각형을 가진 카르노맵을 요구 간략화 과정은 인접 1은 함께 그룹화하고 가능한 커다란 그룹을 형성한다. 16개의 사각형을 가진 네 변수 맵에서 1이 2개인 그룹, 1이 4개인 그룹, 1이 8개인 그룹, 또는 16개 모두가 1인 그룹을 예측할 수 있다.

19 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 변수 카르노맵

20 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 변수 카르노맵 함수 맵핑 간략화 결과

21 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 변수 카르노맵 최소항 번호 부여

22 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.3 필수 주항을 이용한 최상의 간략화
임플리컨트 (Implicant) 카르노맵상의 그룹(한 개의 1을 포함하여) 주어진 부울식이 1이 될 수 있는 입력값을 나타내는 곱항을 부울식의 임플리컨트라함. 가장 기본적인 임플리컨트는 최소항 AC'D', AB'D', A'CD, A'CD', A'C. 그룹화되지 않은 A'B'C'D'도 임플리컨트

23 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.3 필수주항을 이용한 최상의 간략화
주항(Prime Implicant, PI) 임플리컨트가 변수를 줄이기 위해서 다른 항들과 결합될 수 없는 즉, 더 큰 그룹들 내에 포함된 그룹에 속하지 않는 그룹 AC'D', AB'D', 그리고 A'C

24 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.3 필수주항을 이용한 최상의 간략화
필수주항(Essential Prime Implicant, EPI) 다른 PI에 속해있지 않은 최소항을 최소한 한 개 포함하는 PI 즉 최소항이 단지 하나의 PI에 의해서 그룹화되는 PI

25 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.3 필수주항을 이용한 최상의 간략화
필수주항을 이용한 최상의 간략화 두가지 형태의 카르노맵

26 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 필수주항을 이용한 최상의 간략화 두가지 해답

27 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.4 비표준형 부울식의 카르노맵 비표준형 부울식
간략화 부울식

28 제 3장 부울함수의 간략화 3.3 카르노맵(Karnaugh map) 3.3.5 무시항을 갖는 부울식의 카르노맵
(1) 무시항(don’t care) 0 또는 1로 취급 간략화된 부울식

29 제 3장 부울함수의 간략화 3.3 카르노맵(Karnaugh map) 3.3.5 무시항을 갖는 부울식의 카르노맵
(2) 입력변수의 조합이 발생하지 않는 예

30 제 3장 부울함수의 간략화 3.3 카르노맵(Karnaugh map) 3.3.5 무시항을 갖는 부울식의 카르노맵
(3) BCD 1000과 1001을 검출하는 부울식 구현 부울식 간략화된 부울식

31 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.6 카르노맵에서 0을 사용한 간략화 부울식
간략화 결과

32 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.7 다중출력 간략화 다중 출력 부울식
간략화된 다중 출력 부울식

33 제 3장 부울식의 간략화 3.3 카르노맵(Karnaugh map) 3.3.8 대규모 카르노맵 : 5변수 카르노맵

34 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.1 간략화 원리와 방법
① 간략화된 함수를 얻기 위해 묶음으로 존재할 수 있는 주항(prime implicant, PI)을 찾는다. ② 주항 중에서 간략화 부울식에 반드시 포함되는 필수주항(essential prime implicant, EPI)을 테이블을 사용하여 구하고, 구해진 필수주항과 최소 개수의 항과 최소 개수의 변수가 될 수 있도록 적절한 주항들을 선정하여 간략화된 부울식을 구하는 것이다.

35 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.1 간략화 원리와 방법 (1) 주항 결정 최소항의 2진 표현과 1의 개수

36 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.1 간략화 원리와 방법 주항 결정 최소항의 그룹화

37 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.1 간략화 원리와 방법 (1) 주항 결정 주항 결정

38 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.1 간략화 원리와 방법 (1) 주항 결정 주항 결정

39 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.1 간략화 원리와 방법 (1) 주항 결정 주항 결정

40 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.1 간략화 원리와 방법 (1) 주항 결정 주항 결정

41 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.1 간략화 원리와 방법 주항 결정 간략화된 부울식

42 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.1 간략화 원리와 방법 (2) 필수주항 결정 필수주항 결정

43 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.1 간략화 원리와 방법 (2) 필수주항 결정 (3) 간략화된 부울식
필수주항에 의해 제거되지 않는 최소항

44 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.2 무시항 조건이 있는 경우 부울식 (1) 주항 결정

45 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.2 무시항 조건이 있는 경우 부울식 (1) 주항 결정

46 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.2 무시항 조건이 있는 경우 부울식 (2) 필수주항 선택

47 제 3장 부울식의 간략화 3.4 테이블 방법 3.4.2 무시항 조건이 있는 경우 부울식 (3) 간략화된 부울식