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

2진 결정도(binary decision diagram, BDD)

결정 트리(Decision Tree)

진리표의 값을 그대로 결정 트리로 변환

노드 줄이기(Reducing Nodes)

트리에 중복이 많음

• 동일 노드 병합
  " $x_2$ 검사 → 0이면 $f=1$ " 이 동일하게 $x_1=0$ 쪽과 $x_1=1$쪽에 있음
  → 하나로 합침

• 무의미한 노드 제거
  $x_1=1$ 인 경우, $x_2$ 검사는 해봤자
  둘 다 $f=1$로 가는 구간은 노드가 불필요

AND와 OR 함수의 BDD

AND

• x₁=1 분기에서 내려온 x₂ 노드는
  x₂=0 → 0
  x₂=1 → 1
  두 값이 서로 다르므로 노드를 유지

• x₁=0 분기의 x₂ 노드는
  x₂=0 → 0
  x₂=1 → 0
  두 경우 모두 0 으로 가기 때문에 불필요

OR

• x₁=1 분기로 가면 항상 결과가 1 이므로 x₂ 노드를 제거

XOR함수의 BDD

엣지가 교차된 형태