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

标签：

• institute-of-science-tokyo
• Boolean-Function-Minimization
• Finite-State-Machine-Minimization
• Computer-Architecture

Author

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

Description

S4. 以下の問に答えよ。$x\vee y$ は論理和，$xy$ は論理積，$\neg x$ は否定を表す。

1. 次の論理式と等価な論理式を，OR を用いず，AND と NOT のみを用いてできるだけ簡単に表せ。
   a) $a\vee b$
   b) $\neg(a\vee\neg b)\vee(b\vee\neg c)$

2. 表 S4.1 の入力 $a,b,c$，出力 $x$ の論理関数を図 S4.1 の回路で実現する。ただし内部信号 $f_1$ は恒偽（0）ではない。

   $a$	$b$	$c$	$x$
   0	0	0	0
   0	0	1	1
   0	1	0	1
   0	1	1	1
   1	0	0	1
   1	0	1	0
   1	1	0	1
   1	1	1	1

   図 S4.1 の接続は $x=((a\vee b)\land f_1)\vee f_2$ であり，$f_1,f_2$ を生成する回路には $a,b,c$ を入力できる。

   a) 内部信号 $f_1$ の論理式を $a,b,c$ を用いてできるだけ簡単に表せ。
   b) 内部信号 $f_2$ の論理式を同様に表せ。

3. 図 S4.2 の入力を $(a,b,c)$，出力を $y$ とする。信号線の論理値が1に固定され，その影響が出力側に伝搬する故障を1縮退故障という。例えば出力線 $\ell_9$ の1縮退故障は，他に故障がない前提で入力 $(0,0,0)$ によって検出できる。

   図 S4.2 の信号線は，入力 $a,b,c$ がそれぞれ $\ell_1,\ell_2,\ell_3$。$a$ は $\ell_4$ を経て NOT へ入り，その出力 $\ell_6$ と $b$ の AND が $\ell_7$ となる。$a$ の別の分岐 $\ell_5$ と $c$ の AND が $\ell_8$ となる。$\ell_7,\ell_8$ の OR が $\ell_9=y$ である。

   a) 正常時の $y$ を $a,b,c$ を用いてできるだけ簡単に表せ。
   b) $\ell_5$ が1縮退故障したときの $y$ を同様に表せ。
   c) 他に故障がない前提で，$\ell_5$ の1縮退故障を検出できる入力ベクトルをすべて示せ。

4. 表 S4.2 の状態遷移表について答えよ。

   状態	入力0の次状態/出力	入力1の次状態/出力
   $Q_0$	$Q_2/0$	$Q_1/0$
   $Q_1$	$Q_3/1$	$Q_0/0$
   $Q_2$	$Q_0/0$	$Q_1/0$
   $Q_3$	$Q_1/1$	$Q_4/0$
   $Q_4$	$Q_2/0$	$Q_0/0$

   a) 初期状態が $Q_0$，入力列が $00101$ のときの出力列を示せ。
   b) 同じ入力列を与えたとき出力列が異なれば，二つの状態を区別できる。例えば入力列 $0$ で $Q_0$ と $Q_1$ は区別できる。$Q_0$ と $Q_4$ を区別する入力列を一つ，できるだけ短く示せ。
   c) 出力列によって区別できる入力列が存在しない二つの状態を等価という。$Q_0$ と等価な他の状態をすべて示せ。

5. （A）～（O）に最も適切な語句を下の選択肢から選び，番号で答えよ。同じ選択肢を何度選んでもよい。

   a) コンピュータで実行される論理関数で表現できる様々な処理は，出力が入力のみによって定まる（A）で実現できるが，多くの場合（B）で実現されている。（B）の出力は，その入力と状態によって定まる。
   b) 整数を2進数表現したとき，最上位ビットを（C），最下位ビットを（D）と呼ぶ。負の整数を考える場合，1の補数表現や2の補数表現では，整数が負であるかは（E）で判断できる。同じビット数の場合，1の補数表現で表現できる数は2の補数表現と比べ（F）。コンピュータ内部では多くの場合，1の補数表現を（G）。実数は（H）方式もしくは（I）方式で表現されるが，（J）誤差が生じる。
   c) コンピュータは一般に（K），（L），（M），入力装置，出力装置で構成される。（K）はレジスタや ALU などで構成され，（K）と（L）を合わせてプロセッサもしくは CPU と呼ぶ。一般的なコンピュータでは（M）は階層化され，プロセッサの近くに（N）であるメモリが，遠くに（O）であるメモリが配置される。

   番号	選択肢	番号	選択肢	番号	選択肢
   1	加算器	11	MSB	21	標準
   2	乗算器	12	USB	22	丸め
   3	算術演算	13	多い	23	演算装置
   4	アナログ回路	14	少ない	24	安全装置
   5	組合せ回路	15	等しい	25	制御装置
   6	順序回路	16	用いる	26	記憶装置
   7	BUS	17	用いない	27	検査装置
   8	FPGA	18	固定小数点	28	高速
   9	IoT	19	浮動小数点	29	高価
   10	LSB	20	最小二乗	30	大容量

题目描述

以下使用上面的完整真值表、电路连接、状态表及30个术语选项。$\vee$ 表示或，相乘表示与，$\neg$ 表示非。

1. 只用 AND 和 NOT，不用 OR，将下列等价逻辑式尽量化简：
   a) $a\vee b$；
   b) $\neg(a\vee\neg b)\vee(b\vee\neg c)$。
2. 用结构 $x=((a\vee b)\land f_1)\vee f_2$ 实现表 S4.1 的函数。内部函数 $f_1$ 不得恒为0；生成 $f_1,f_2$ 的部分可使用 $a,b,c$。
   a) 写出尽量简单的 $f_1$；
   b) 写出尽量简单的 $f_2$。
3. 电路连接如图 S4.2：$\neg a$ 与 $b$ 输入上方 AND，$a$ 的分支 $\ell_5$ 与 $c$ 输入下方 AND，两者再经过 OR 得到 $y$。信号线固定为1且影响传至输出的故障称为固定为1故障；例如输出线 $\ell_9$ 的该故障可用 $(0,0,0)$ 检出。假设没有其它故障：
   a) 化简正常输出 $y$；
   b) 化简仅 $\ell_5$ 固定为1时的输出 $y$；
   c) 列出能检测此故障的全部输入 $(a,b,c)$。
4. 对表 S4.2：
   a) 从 $Q_0$ 开始输入 $00101$，求输出序列。
   b) 相同输入导致不同输出时可区分两个状态；例如输入 $0$ 可区分 $Q_0,Q_1$。给出尽量短的一个输入序列以区分 $Q_0,Q_4$。
   c) 不存在任何输入序列能区分的状态称为等价状态，求与 $Q_0$ 等价的其它所有状态。
5. 从上面的30个选项中为（A）～（O）选择最合适的词语，回答其编号，选项可以重复使用。
   a) 可用逻辑函数表示的计算机处理能够由输出只取决于输入的（A）实现，但多数情况下使用（B）；（B）的输出取决于输入与状态。
   b) 二进制整数的最高、最低有效位分别称（C）、（D）。在反码与补码中，由（E）判断整数是否为负。相同位数的反码能表示的数比补码（F）。计算机内部多数情况下（G）反码。实数采用（H）或（I）方式表示，但会产生（J）误差。
   c) 计算机一般由（K）、（L）、（M）、输入设备和输出设备组成。（K）含寄存器与 ALU；（K）与（L）合称处理器或 CPU。（M）通常分层，靠近 CPU 的存储器具有（N）的特性，较远的具有（O）的特性。

Kai

1)

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)}.$$

2)

真理値表から $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$ となり，全入力で一致する。

3)

正常時は $\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)}$$

のみである。

4)a)

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

4)b)

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

4)c)

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{ のみ}}.$$

5)

空欄	語句（選択肢番号）
A	組合せ回路（5）
B	順序回路（6）
C	MSB（11）
D	LSB（10）
E	MSB（11）
F	少ない（14）
G	用いない（17）
H	固定小数点（18）
I	浮動小数点（19）
J	丸め（22）
K	演算装置（23）
L	制御装置（25）
M	記憶装置（26）
N	高速（28）
O	大容量（30）