1.4 Map Simplification (맵의 간소화)
- 진리표로 부터 얻은 논리식을 간소화 하는 방법
◎ Karnaugh Map 방식
- 부울 함수를 곧바로 간소화 할 수 있다.
- K-Map이란 어떤 함수를 가장 최소화된 폼으로 표현할 수 있도록 Truth Table을 재배치 시킨 것
-> 진리표 Truth Table을 재배치 시킨 것이 K-map : 갖고 있는 정보는 같다
◎ 민텀(Minterm)
- 진리표에서 변수의 각 조합
- N개의 변수가 있다면 2^N개의 민텀이 존재
민텀 x, y, z 3개의 변수를 사용하는 민텀은 1,1,0일 때 출력값이 1이 된다,
x'y'z가 하나의 민텀이 되고 2진수로 표시한 것 : 2진수로 1이 001이므로 -> x'y'z
4는 100 -> xy'z' ; 이것이 하나의 민텀
전체적으로는 8개의 민텀이 존재, 사용하는 변수가 3개이므로 그리고 출력값이 1이 되는 민텀들이 위에
1,4,5,6,7이고 그것들의 합을 나타낸다.
간소화 시키는 방법
1. boolean 대수식 - 저번 게시글
2. K-Map 적용 - 장점 : 하라는대로 하면 가장 간소화 된 식을 보장
▷ K-Map 이용 절차
1. 사용되는 변수의 개수에 따라 밑에서 해당되는 K-Map을 선택하고 ‘1’ 이란 출력 값을 갖는 민텀 자리를
1로 표시한다.
K-map을 이용하는 방법 2가지를 설명해주시는데 하나는 교과서 방식, 하나는 교수님의 방식
의아할 수도 있는 점이 교수님 방식의 yz칸 수가 00, 01, 11, 10이라고 되어있는데 한 비트씩 변환이 가능하기 때문이다.
2. 1 이란 출력값을 갖는 인접한 민텀들을 묶어서 가능한 한 큰 직/정 사각형이 되도록 그룹핑 한다. 이때 그룹에 속하는 민텀의 개수는 1, 2, 4, 8, . . 등 2n 에 속하는 숫자이어야 한다
먼저, 초록색 사각형의 조건을 살펴보면 A하고는 아무 상관이 없다. A가 1이든 0이든 1을 출력값이 1로 같지만,
B는 0이어야하고 C는 1이어야하는 조건이 존재한다.
검은색은 A가 1이어야하고, B하고는 아무런 상관이 없음 B가 0이든 1이든 출력값은 1이기 때문에 하지만 C는 1만 가능하다.
분석해보면
빨간색 그룹은 변수 A와 B가 각각 1과 0이어야 하며 (AB’),
초록색 그룹은 변수 B와 C가 각각 0과 1이어야 하며 (B’C),
검은색 그룹은 변수 A와 C가 각각 1과 1이어야 한다 (AC).
-> 최종적으로 간소화된 출력 함수는 F(A,B,C) = AB’ + B’C + AC 이 된다.
회로로 그리면 And 게이트 3개 + Not 게이트 2개 그리고 And 게이트 3개를 Or 게이트 1개로 묶어주어 출력해주면 된다
▷ K-Map 이용 절차 (계속)
인접한 민텀(adjacent minterm) 또는 인접한 사각형(adjacent square)이란 ?
하나의 민텀을 구성하는 변수들과 다른 민텀을 구성하는 변수들의 값이 하나만 틀릴 경우 “인접한 민텀”이라 한다.
e.g., 아래의 K-Map에서 민텀 8과 10은 변수 ABCD의 값이 각각 1000과 1010으로 변수 C의 값 하나만이 틀리므로 인접한 민텀이라 한다. 마찬가지로 2(0010)와 10(1010) 또한 인접한 민텀이고, 5(0101)과 13(1101) 또한 인접한 민텀이다.
하지만 3(0011)과 15(1111), 또는 5(0101)와 6(0110)은 서로 2개의 변수가 틀리기 때문에 인접한 민텀이 아니다.
문제를 보고 이해한 후 가장 먼저 해야할 것이 진리표를 만들기
진리표를 만든 다음 거기에서 불린대수식을 찾으면 민텀들을 확인한 후 민텀들의 합으로 나타낼 수 있다.
그것을 간소화 시키는 것 -> F = x + y'z로 만들어야함 , 이것이 위에서 말한 2가지 방법을 이용
위에서 그룹핑으로 2개의 사각형으로 나타낼 수 있다. (2개의 1로 만들어진 사각형, 4개의 1로 만들어진 사각형)
작은 사각형을 보면 y값이 0이어야하고 그 다음에 z값이 1이어야한다.
반면에 밑에 있는 그룹은 x값이 1이어야한다.
따라서 결과가 F = x + y'z로 나오는 것이다.
인접한 사각형으로 나타낼 수 있는 것
B/C는 1이여야만 하고, A는 1, C는 0이어야만한다. F = AC' + BC
F(A,B,C, D) = Σ(0,1,2,6,8,9,10)
-> F= A’CD’ + B’D’ + B’C’
▷Product-of-Sums Simplification : Product는 And 게이트로 묶이는 것을 의미
-> 위 그림은 먼저 And게이트로 연결시켜준 후 종합적으로 Or게이트를 사용해 전체를 취합해준다. 이 방식을
Sum of Product form이라고 하고
-> 먼저 Or게이트로 먼저 다 묶고 그 출력값들을 하나의 And게이트로 묶은 것이 될 것(회로가) 이 방식을
Product of Sum form이라고 한다.
교수님 방식으로 K-Map을 만드는 게 더 실수가 적은것같다.
Then apply 1,0,0,1 to see 2 forms have same output !!
-> 이거에 대한 아래 그림
위에 NAND와 NOR는 그림과 교수님 설명으로 이해할 수 있는데 밑에 Don't Care를 한 번 보자
d(A, B, C) 이 민텀은 Don't care 민텀이다. 우리가 우리의 이득이 될 수 있도록 1로 간주할 수도 있고, 0으로 간주할 수도 있는 민텀들이다. 오른쪽 그림의 x표시가 이 민텀들이다.
-> 1번과 3번 민텀을 1로 간주하게 된다면 0132 - 4개의 더 큰 그룹으로 만들 수 있으므로 회로가 더 간단해질 수 있다.
-> 5번 민텀을 1로 간주한다면 그룹이 하나 더 생기는 것이므로 회로가 복잡해진다. 그래서 1로 간주하지 않는다.
위 개념이 Don't care conditions이다.
오늘 수업 중 가장 중요한 것은 K-Map을 이용해 논리식을 가장 간소화된 방법으로 표현하는 과정이다.
교과서 식의 방법과 교수님이 설명해주신 방법 2가지 방법으로 K-Map을 진행할 수 있는데 난 개인적으로
교수님의 방식이 더 이해가 잘 된 것 같다. 아래의 그림이 오늘 수업의 가장 중요한 내용이다.
마지막 예제는 복습할 겸 내일 해봐야겠다.