15 / 63 · 概念

真理値表から MUX とシャノン展開へ

選択論理を式で導き、任意の論理関数を MUX で分解します。

選択規則を式で導く

sel が 0 なら a、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 の 2 段で構成できます。一方、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 の入力を逆にしないよう、先に部分関数を求めます。