불 대수, 등가 변환과 구현 비용

등가식은 모든 입력에서 같은 출력을 냅니다

조합회로를 단순화할 때 목표는 식을 짧게 쓰는 것만이 아닙니다. 기능을 유지하면서 논리 단계, 팬인, 팬아웃, 실제 라이브러리 셀을 고려해야 합니다. 먼저 불 대수^{i불 대수 0과 1, AND·OR·NOT을 다루는 대수입니다. 여기서 더하기 기호는 보통 OR이므로 정수 덧셈의 규칙과 다릅니다.}의 $+$와 곱셈 표기를 OR와 AND로 해석합니다.

두 번째 식은 $A=1$이면 양쪽이 1이고, $A=0$이면 양쪽이 $B$인 두 경우로 나누어 확인할 수 있습니다. 외운 항등식을 적용한 뒤에도 의미를 설명할 수 있어야 합니다.

드모르간 법칙으로 NAND·NOR 구조 읽기

예를 들어 $Y=AB+AC$는 $A(B+C)$와 같습니다. 전자는 AND 두 개와 OR 한 개, 후자는 OR 한 개와 AND 한 개로 그릴 수 있습니다. 그러나 입력 도착 시각이나 부하가 다르면 게이트 개수가 적은 쪽이 항상 더 빠르지는 않습니다.

합의 정리를 적용하면 다음과 같습니다.

$BC=1$인 경우 $A$가 0이면 $\overline A C$, 1이면 $AB$가 이미 1이므로 $BC$는 안정 상태의 출력에 영향을 주지 않는 중복 항입니다. 다만 이 항을 없애면 전환 순간의 hazard 특성이 달라질 수 있습니다. 그 차이는 뒤의 지연 강의에서 다룹니다.

아래 그림의 각 열은 시간의 흐름이 아니라 ABC 입력 조합 하나를 나타냅니다. 두 출력이 모든 열에서 같은지 보세요. 게이트 수와 경로가 달라도 입력이 안정된 0/1일 때 출력은 같습니다.

등가성 검증의 기준

변환 전후를 y_ref와 y_opt로 두고 작은 입력 공간에서는 모든 입력을 비교합니다. 테스트가 한두 예제만 통과했다고 등가라고 결론 내리면 안 됩니다.

assign y_ref = (a & b) | (a & c);
assign y_opt = a & (b | c);
assign mismatch = y_ref ^ y_opt;

0/1 입력 8개 조합에서 mismatch가 항상 0이어야 합니다. X/Z가 있는 4상태 시뮬레이션이나 순차회로의 등가성은 추가 조건이 필요합니다. 설계를 검토할 때는 어떤 입력과 조건에서 등가성을 확인했는지 함께 기록하세요.