7 / 63 · 概念

布林代數、等價轉換與實作成本

以德摩根定律和因式分解轉換電路，區分邏輯等價與時序特性。

等價算式在所有輸入下都輸出相同值

簡化組合電路的目的不只是把算式寫短，還要在維持功能的同時，考慮邏輯層數、扇入、扇出與實際元件庫單元。先將布林代數^{布林代數處理 0、1 與 AND、OR、NOT 運算。此處的加號通常代表 OR，規則與整數加法不同。}中的 $+$ 與乘法符號解讀成 OR 與 AND。

A+AB=A,\qquad A+\overline A B=A+B

第二式可分情況確認： $A=1$ 時兩邊都為 1， $A=0$ 時兩邊都為 $B$ 。套用背熟的恆等式後，也應能說明其意義。

\overline{AB}=\overline A+\overline B,\qquad \overline{A+B}=\overline A\,\overline B

例如 $Y=AB+AC$ 等於 $A(B+C)$ 。前者可畫成兩個 AND 加一個 OR，後者則是一個 OR 加一個 AND。但若輸入到達時間或負載不同，閘數較少的一方不一定較快。

共識定理給出另一個等價關係：

AB+\overline A C+BC=AB+\overline A C

當 $BC=1$ ，若 $A=0$ ， $\overline A C$ 已為 1；若 $A=1$ ， $AB$ 已為 1，因此 $BC$ 對穩態功能是多餘的。不過移除這一項可能改變切換瞬間的冒險特性，差異會在後面的延遲單元說明。

下方每一欄是某一組 ABC 輸入，並非時間經過。請檢查兩個輸出是否每欄都相同。即使閘數與路徑不同，穩定 0/1 輸入下的功能仍相同。

AB + AC 與 A(B + C) 的等價性

查看波形資料

將轉換前後分別設為 y_ref 與 y_opt，輸入空間小時就逐一比較所有輸入。只通過一兩個範例，不能斷言等價。

SystemVerilog
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 的四態模擬或循序電路的等價性，需要額外條件。明確交代已證明的範圍，是設計審查的基本習慣。

化簡 $F=\overline A B+AB+A\overline B$ ，並寫出需要驗證的輸入組合數。

查看解說

前兩項為 $B(\overline A+A)=B$ ，所以 $F=B+A\overline B=A+B$ 。兩個變數共需檢查四組輸入。算式等價不表示兩種實作的傳播延遲也相同。