컴퓨터구성 (2)

> 2주차 1강

1.4 Map Simplication (맵의 간소화)
진리표에서 얻은 논리식을 간소화하는 방법

Karnaugh Map(K-Map)
• 부울 함수를 곧바로 간소화 가능
• K-Map이란, 어떤 함수를 가장 최소화된 폼으로 표현할 수 있도록 Truth Table(진리표)를 재배치 시킨 것
Minterm(민텀)
• 진리표에서 변수의 각 조합
• n개의 변수가 존재 → 2^n개의 민텀이 존재

Boolean Equation
F(x,y,z) = x + y’z
= $\sum$(1,4,5,6,7) = x’y’z + xy’z’ + xy’z + xy’z + xyz’ + xyz
밑 그림에서 진리표는 8개의 민텀을 가짐. 출력 F가 ‘1’이 되는 민텀을 선택.

compliment, AND, OR
x가 1이면 무조건 1이 나오고, 0, 0, 1 일 경우엔 1이 나옴
진리표(Truth Table)를 재배치하여 K-Map을 만들 수 있음.

최우측 하단 1은 진리표 7번째와 같은 정보를 나타냄. 110 → 1
위의 진리표, K-Map, Boolean Equation은 모두 같은 정보를 나타냄

K-Map 이용 절차
1. 변수의 개수에 따라 해당되는 Map을 선택, 출력값 1을 갖는 민텀 자리를 1로 표시함

• 교과서 방식에선 10진수로 수를 표현해주고 1의 값을 갖는 자리에 1로도 표시를 해줌. X, Y, Z는 1의 값을 갖는 영역을 나타내줌.

• 교수님이 사용하는 방식에선, 사용하는 변수를 확실하게 표기해줌. (ex : A/B, x/yz)
• 변수 별 경우의 수를 자리에 나타내주고(0,1, 00, 01, 11, 10), 출력값이 1이 되는 것들의 위치에 바로 1이라고 표기해줌.

2. 출력값이 1인 인접한 민텀들을 묶어서 가능한 큰 직/정 사각형이 되도록 그룹핑.민텀의 개수는 2^n에 속하는 숫자여야 함.

빨강 : AB’ / 초록 : B’C / 검정 : AC
최대한 크게 그루핑을 해줘야 함
3. 인접한 민텀 / 인접한 사각형
• 하나의 민텀을 구성하는 변수들과 다른 민텀을 구성하는 변수들의 값이 하나만 틀릴 경우 ‘인접한 민텀’이라 함

Ex) F = x + y’z
y가 0, z가 1이면 출력값 1이 나온다고 생각하면 됨.

(1) 진리표(Truth Table)

(2) F(x,y,z) = $\sum$(1,4,5,6,7)
(3) K-Map

• 위 그림들처럼 인접한 사각형을 묶는 요령, 규칙이 존재함. 하나의 K-Map에서도 여러 개의 그루핑을 할 수가 있는데, 가장 효율적으로 하는 게 중요함.
ex)
F(A,B,C) = $\sum$(0,2,4,5,6)
F = C’ + AB’

4가 중복이 되겠지만 5번을 해결하기 위해 같이 묶어줬음 (가능하면 크게)

Product-of-Sums Simplication
F(A,B,C,D) = $\sum$(0,1,2,5,8,9,10)
F = B’D’ + B’C’ + A’C’D —> Sum of Product from
(AND 부터 취하고, 그걸 OR로 묶어놓는 것)
F’= AB + CD + BD’ (group minterms marked 0)
F’’ = (F) = (A’ + B’)(C’ + D’)(B’ + D)
(OR게이트로 다 묶고 그 출력값을 AND로 묶음) —> Product of Sum form

(12, 8 행은 A, 9,11 열은 라인 C)

교수님이 K-Map 그릴 때 즐겨 쓰시는 방법은,
1. 사용하는 변수 위치를 포함해서 표시
2. 각 변수들의 위치 표시
(순서가 대개 00, 01, 11, 10임. 3, 4가 바뀌는 것)
3. 최대한 큰 그룹 만들고, 어느 변수에 의해 결정 되는지 찾기
4. 논리합으로 각 그룹을 묶어서 최대한 간소화된 표현식을 구함

• NAND Implementation
Sum of Product : F = B’D’ + B’C’ + A’C’D

X’ + Y’ + Z’ = (X’ + Y’ + Z’)’’ = (X’’Y’’Z’’)’ = (XYZ)’
‘의 ‘는 안 한 거랑 같음 (첫 강의에서 배운 드모르간 법칙 적용)
• NOR Implementation
Product of Sum : F = (A’ + B’)(C’ + D’)(B’ + D)

X’Y’Z’ = (X’Y’Z)’’ = (X’’ + Y’’ + Z’’)’ = (X + Y + Z)’

Don’t care conditions
• F(A,B,C) = $\sum$(0,2,6), d(A,B,C) = $\sum$(1,3,5) —> 이렇게 표시함
• F=A’ + BC’ = $\sum$(0,1,2,3,6)

1,3을 1로 간주하면 0,1,3,2 4개를 묶을 수 있음. 5를 버린다면 4개 묶은 것과 2,6 두개를 묶은 것 두개의 그룹으로 묶을 수 있게 됨.

(즐겨 사용하시는 방법-)

F(A,B,C,D) = AB + CD
Don’t care 조건은 유리하면 1로 간주, 필요 없으면 0으로 생각하고 버리면 됨.
(최우측 하단의 x는 0으로 간주하고 버린 것임.)
ex)