応用情報技術者 2020年秋期午前2 問23

問題文

次の表に示す値が格納されたLUT (Lookup Table) と等価な回路はどれか。ここで、LUTのアドレス信号

A_{2} \sim A_{0}

は

A_{0}

がLSBで、ア〜エの回路の入力信号

a

が

A_{2}

、

b

が

A_{1}

、

c

が

A_{0}

に対応する。

🖊️ 解答を隠して解いてみる

選択肢

ア：

イ：（正解）

ウ：

エ：

🔒 解説は解答すると表示されます

LUT論理式導出【午前2解説】

正解の理由

LUTの出力が1となるアドレスは1, 3, 5, 6です。これを総和形で表すと

f = Σ (1, 3, 5, 6)

すなわち

f = a^{'} b^{'} c + a^{'} b c + a b^{'} c + ab c^{'}

です。代数的に整理すると

f = ab c^{'} + (a^{'} + b^{'}) c = (ab) c^{'} + (ab)^{'} c = (ab) \oplus c

となります。つまり出力は「aとbのAND」と「c」の排他的論理和（XOR）です。選択肢の中でaとbをANDし、その結果をcとXORしている回路が対応するため、イが等価になります。

（回路対応の説明）イはaとbをANDして得た信号とcを二入力の排他的論理和（XOR）で結んだ構成と読めます。ANDの出力が

ab

、XORの出力が

(ab) \oplus c

であり、これが上の

f

と一致します。

解法ステップ

LUTの出力が1となるアドレス（10進）を拾う：1, 3, 5, 6。
各アドレスを対応するミンターン（ $a, b, c$ の組）に変換し、和（OR）で結ぶ： $f = Σ (1, 3, 5, 6)$ 。
和積形（sum-of-products）を代数的に整理する／Karnaughマップで最小化する。
- 代数操作で $f = a^{'} b^{'} c + a^{'} b c + a b^{'} c + ab c^{'}$ から $f = ab c^{'} + (a^{'} + b^{'}) c$ を導き、さらに $f = (ab) \oplus c$ とする。
回路図を読み、どの選択肢が $(ab) \oplus c$ を実現するかを確認する。ANDで $ab$ を作り、それと $c$ をXORする回路が一致するためイを選ぶ。

選択肢別の誤答解説

ア：回路は $ab + c$ （ANDの出力と $c$ のOR）を表す。 $ab + c$ はアドレス7（ $a = 1, b = 1, c = 1$ ）で1となるが、LUTは0なので不一致。
イ：ANDで $ab$ を作り、右側ゲートが排他的論理和（XOR）なら出力は $(ab) \oplus c$ 。上で示した簡約式と一致するため正しい。
ウ：左で $a$ と $b$ をORしてからその結果を $c$ とANDするので $f_{ウ} = c (a + b) = a c + b c$ 。例えばアドレス6（ $110$ ）では $c = 0$ なので0となり、LUTの値1と合わない。
エ：左で $a$ と $b$ をORし、さらに右でそれと $c$ をORするため $f_{エ} = a + b + c$ 。アドレス2（ $010$ ）では $a + b + c = 1$ となるがLUTは0なので不一致。

（要点）各回路から対応する論理式を明示してからLUTの式

f

と比較することが重要です。

よくある誤解

XORと OR の記号を取り違える：XORは OR に似た記号だが、入力側にもう一つ弧（追加の曲線）がある点で区別します。見落とすとイを OR と読み誤り、誤答につながります。
アドレスのビット順（MSB/LSB）の誤認識：問題文の指定（A2がMSB，A0がLSB、a=A2,b=A1,c=A0）を逆に読むとミンターンが狂います。
最小化を省略して「各1出力にANDを用いてORする」実装を前提に考える：最小化により単純なAND＋XORで済む場合があるため、まず式を簡約するクセをつけると良いです。

補足コラム

(論理式の別表現) $f = (ab) \oplus c$ は展開すると $f = ab c^{'} + (ab)^{'} c = ab c^{'} + (a^{'} + b^{'}) c$ となり、AND＋OR＋NOTで実装する場合の構成も読み取れます。
LUTは任意の真理値表を直に格納できるため、得られた式をそのままハードウェアで実装するか、簡約して低コスト回路に置き換えるかは設計目標（遅延、面積、消費電力）によって選びます。

FAQ

Q1: XORの図記号が分かりにくいときはどう確認すればよいですか？
A1: 入力側に「もう一つ小さな弧（補助弧）」が付いているのがXORです。疑わしい場合は、図のゲートの説明（凡例）や問題文中の用語（排他的和等）を探してください。

Q2: この関数を AND/OR/NOT だけで表すとどうなりますか？
A2: 先に示した通り、

f = ab c^{'} + (a^{'} + b^{'}) c

や

f = ab c^{'} + a^{'} c + b^{'} c

のように展開できます。これをAND/OR/NOTゲートで構成可能です。

Q3: 手早く式を最小化するコツは？
A3: 小さめの変数数（3〜4）ならKarnaughマップが速く確実です。代数的には共通因子でまとめてみる（cでくくる等）とXOR形が見つかることがあります。

コードで真理値表を確認（例）

# a,b,cの順で0..7を評価してLUTの値と (a&b) XOR cを比較
lut = [0,1,0,1,0,1,1,0]
def f_from_expr(a,b,c):
    return (a & b) ^ c
for i in range(8):
    a = (i>>2)&1
    b = (i>>1)&1
    c = i&1
    print(i, lut[i], f_from_expr(a,b,c))