논리함수의 최적화된 구현(2)

다단 회로의 분석

윗단 AND → OR

$P_1 = x_2 x_3$
$P_3 = x_1 + P_1 = x_1 + x_2 x_3$

아랫단 OR → AND → OR

$P_2 = x_5 + x_6$
$P_4 = x_4 P_2 = x_4 (x_5 + x_6)$
$P_5 = P_4 + x_7 = x_4 (x_5 + x_6) + x_7$

최종단 AND

$f = P_3 P_5 = (x_1 + x_2 x_3) (x_4 (x_5 + x_6) + x_7)$

논리함수의 다른 표현(큐브 표현법: 2차원 큐브)

2차원 큐브

가로축에 $x_1$, 세로축에 $x_2$ 를 놓고
좌표(이진) 00, 01, 11, 10 순서로 꼭짓점을 매핑
1이 되는 경우(진리표에서 $f=1$인 행)인

세 곳(01, 10, 11)에 ●를 찍음

인접한 점 묶기

큐브(그룹)는 1개 점, 2개 점(2-큐브), 4개 점(4-큐브) 등으로 만들 수 있지만
예시에서는 2-큐브 두 개로 모든 ●를 커버하는 게 최적

• 세로 큐브 (10↔11): $x_1=1$ 고정 → 항 $x_1$
• 가로 큐브 (01↔11): $x_2=1$ 고정 → 항 $x_2$

최종 식 얻기

두 큐브에 대응하는 항을 OR로 합치면

논리함수의 다른 표현(큐브 표현법: 3차원 큐브)

3차원 격자(큐브)에 점 찍기

변수 $(x_1, x_2, x_3)$을 각각 x-축, y-축, z-축으로 배치한 2×2×2 큐브
진리표에서 $f=1$인 조합에 ● 표시

인접한 점 묶기(큐브 그룹핑)

• 4-큐브(면) 묶음
  $x_3=0$인 4개의 점을 한 덩어리로 묶음
  → 해당 항은 $\overline{x_3}$

• 2-큐브(간선) 묶음
  나머지 $x_1=1$이고 $x_2=0$ 인 두 점도 인접하므로 묶음
  → 해당 항은 $x_1 \overline{x_2}$

최종 식

논리함수의 다른 표현(큐브 표현법: 4차원 큐브)

4차원 큐브와 좌표 표시

정점 16개는 $(x_1 x_2 x_3 x_4)$ 4비트로 구분

묶음 찾기

• 4-큐브 묶음
  $x_2 = 0 , x_4 = 0$인 모든 정점
  → $\overline{x_2} \overline{x_4}$

• 4-큐브 묶음
  $x_1 = 0 , x_3 = 1$인 4개 정점
  → $\overline{x_1} x_3$

• 2-큐브 묶음
  $x_2 = 1 , x_3 = 1, x_4 = 1$인 2개 정점
  → $x_2 x_3 x_4$

최종 간소화 식