15 / 63 · 概念

從真值表到 MUX 與夏農展開

推導選擇邏輯的公式，並以 MUX 分解任意邏輯函數。

推導選擇規則

要在 sel=0 時輸出 a、sel=1 時輸出 b，就將各輸入乘上選擇條件，再用 OR 合併。

y=\overline s a+s b

代入 $s=0$ 只剩 a，代入 $s=1$ 只剩 b。a、b 相同時，改變 sel 仍有相同輸出，因此要找出選擇線錯誤，必須包含兩筆資料不同的情況。

藍色路徑代表選定輸入。將 a、b 設成不同值，再切換 sel；兩者相同時，即使選擇線接錯，也難以只靠輸出辨認。

選擇線改變的資料路徑

y = sel ? b : a

MUX 是分解邏輯函數的一般方法

任意布林函數 F 中，將 s 固定為 0 或 1 得到的子函數分別記為 $F_0,F_1$ 。

F=\overline s F_0+sF_1

這就是夏農展開。可用 s ? F1 : F0 將任意函數分成兩部分。例如 $F=a\oplus b$ 以 a 作選擇線時， $F_0=b$ 、 $F_1=\overline b$ ，因此可用 MUX^{多工器是依選擇訊號，將多個輸入之一連至輸出的組合電路。必須明確定義選擇位元與輸入編號的對應關係。}與反相^{反相是將 0 變為 1、1 變為 0 的 NOT 運算。公式上方的橫線表示對線下的整個運算式套用 NOT。詳細內容}組成 XOR。

4-to-1 選擇與優先權

以兩個選擇位元從四個輸入選一個，可用兩層 2-to-1 MUX 組成。另一方面，if (req0) ... else if (req1) ... 在多個請求同時為 1 時，優先選較前面的請求。位址選擇與優先權選擇是不同問題，不能混為一談。

SystemVerilog
assign y = sel[1] ? (sel[0] ? d3 : d2)
                 : (sel[0] ? d1 : d0);

理想平衡樹有 $2^m$ 個輸入時，選擇路徑為 m 層。實體延遲不只受層數影響，也取決於輸入到達時間、負載與配線。函數分解用來建立實作候選方案，並非保證最佳延遲的證明。

自己試試看

將 $F=a b+\overline a c$ 表示為以 a 為選擇線的 MUX。兩個資料輸入各是什麼？

查看解說

$a=0$ 時 $F_0=c$ ， $a=1$ 時 $F_1=b$ ，因此為 assign f = a ? b : c;。先算出兩個餘因子函數，避免把選擇線 0 與 1 的輸入對調。