東京工業大学工学院情報通信系 2017年8月実施 S4 論理回路・状態等価・計算機構成

标签：

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

OR を使わず AND と NOT のみで $a\vee b$ ， $\neg(a\vee\neg b)\vee(b\vee\neg c)$ を簡単に表せ。
$(a,b,c)=000,001,010,011,100,101,110,111$ に対する出力 $x$ が順に $0,1,1,1,1,0,1,1$ である。 $x=(a\vee b)f_1\vee f_2$ を満たす簡単な $f_1,f_2$ を求めよ。ただし $f_1$ は恒偽でない。
回路の上段は $\neg a$ と $b$ の AND，下段は $a$ と $c$ の AND，出力 $y$ は両者の OR である。下段へ分岐する $a$ の信号線 $\ell_5$ のみを1に固定する故障について，正常時・故障時の出力と，故障を検出する全入力を求めよ。
次の Mealy 機械について，初期状態 $Q_0$ ，入力 $00101$ の出力， $Q_0$ と $Q_4$ を区別する入力列， $Q_0$ と等価な他の全状態を求めよ。

次の空欄（A）～（O）を補え：出力が入力のみで決まる回路（A），出力が入力と状態で決まる回路（B），最上位/最下位ビット（C）/（D），補数表現で負を判定するビット（E），同じビット数で1の補数表現が表せる数は2の補数表現より（F），通常の計算機は1の補数を（G），実数の表現方式（H）（I）と（J）誤差，基本構成の（K）（L）（M）と入出力装置，CPU近くのメモリ（N），遠くのメモリ（O）。ただし（K）はレジスタと ALU を含み，（K）と（L）が CPU を構成する。

化简布尔式，设计双输出组合逻辑，求固定为1故障的测试向量，分析 Mealy 状态等价，并填写补数、浮点数及计算机基本结构术语。术语空格按下方解答表的原题字母对应。

De Morgan の法則と吸収則より

\boxed{a\vee b=\neg(\neg a\land\neg b)},

\neg(a\vee\neg b)\vee(b\vee\neg c) =(\neg a\land b)\vee b\vee\neg c =b\vee\neg c=\boxed{\neg(\neg b\land c)}.

真理値表から $x=b\vee a\bar c\vee\bar ac$ 。例えば

\boxed{f_1=\bar c,\qquad f_2=b\vee\bar ac}

とすれば $(a\vee b)f_1\vee f_2=b\vee a\bar c\vee\bar ac$ となり，全入力で一致する。

正常時は $\boxed{y=\bar ab\vee ac}$ ，故障時は $\boxed{y_{\rm fault}=\bar ab\vee c}$ 。差が出る条件は $a=0,c=1,b=0$ であり，検出入力は

\boxed{(a,b,c)=(0,0,1)}

のみである。

状態列は $Q_0\to Q_2\to Q_0\to Q_1\to Q_3\to Q_4$ 。出力列は $\boxed{00010}$ 。

入力列 $\boxed{10}$ に対し， $Q_0$ からは $01$ ， $Q_4$ からは $00$ が出るため区別できる。1文字では両状態とも常に0を出すので，長さ2が最短である。

1文字の出力により $\{Q_0,Q_2,Q_4\}$ と $\{Q_1,Q_3\}$ に分割する。入力1の遷移先で $Q_4$ が前者から分離し，次に $Q_1,Q_3$ も分離する。残る $\{Q_0,Q_2\}$ は，入力0で同集合に，入力1でともに $Q_1$ に移る。よって

\boxed{Q_0\text{ と等価な他の状態は }Q_2\text{ のみ}}.