ブール代数・等価変形・実装コスト

等価な式は全入力で同じ出力を返します

組合せ回路を簡単化する目標は、式を短く書くことだけではありません。機能を保ちながら、論理段数・ファンイン・ファンアウト・実際のライブラリセルを考慮します。まず、ブール代数^{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$ が、$A=1$ なら $AB$ が既に 1 なので、$BC$ は定常状態の機能では冗長です。ただし、この項を除くと遷移時のハザード特性が変わる場合があります。この違いは後の遅延の講義で扱います。

下の各列は時間経過ではなく、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 の入力八組すべてで mismatch が常に 0 でなければなりません。X/Z を含む 4 状態シミュレーションや順序回路の等価性には、追加の条件が必要です。証明した範囲を明示する習慣が、設計レビューの基本です。