東京工業大学 工学院 情報通信系 2018年8月実施 S4 二進・BCD加減算器

标签：

• institute-of-science-tokyo
• Boolean-Function-Minimization
• Combinatorial-Circuit

Author

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

Description

S4. 否定を $\overline x$，論理積を $x\cdot y$，論理和を $x\vee y$ と表す。$N$ ビット整数変数を $X=x_{N-1}\cdots x_1x_0$ とし，整数定数の10進・2進表記を $(\cdots)_{10}$，$(\cdots)_2$ とする。論理式は最小数の AND 項からなる NOT–AND–OR 形式（積項の和形式）で答えよ。

1. 二つの $N$ ビット入力 $A=a_{N-1}\cdots a_0$，$B=b_{N-1}\cdots b_0$ の和 $A+B$ を出力する加算器は，図 S4.1 のように $N$ 個の全加算器（FA）を桁上げで接続して構成され，$c_{\rm in}=c_0=0$ である。第 $k$ 桁（$k=0,\ldots,N-1$）の全加算器の真理値表 S4.1 を用い，$s_k,c_{k+1}$ を $a_k,b_k,c_k$ の論理式で表せ。

   $a_k$	$b_k$	$c_k$	$c_{k+1}$	$s_k$
   0	0	0	0	0
   0	0	1	0	1
   0	1	0	0	1
   0	1	1	1	0
   1	0	0	0	1
   1	0	1	1	0
   1	1	0	1	0
   1	1	1	1	1

   各 FA は $a_k,b_k,c_k$ を入力し，$s_k,c_{k+1}$ を出力する。最終キャリーは $c_{\rm out}=c_N$，和の下位 $N$ ビットは $s_{N-1}\cdots s_0$ である。

2. 図 S4.2 の減算器は，$B$ の各ビットを反転して $B'=b'_{N-1}\cdots b'_0=\overline b_{N-1}\cdots\overline b_0$ とし，加算器に $A,B',c_{\rm in}=1$ を入力する。$A,B,B'$ は符号なし非負整数である。次の（ア）～（ウ）を埋めよ。

   $N$ ビット加算器の $N+1$ ビット出力は $S'=c_Ns_{N-1}\cdots s_0=A+B'+c_{\rm in}$ である。$B'$ は $B$ の（ア）の補数であり，

   $$B'+B=\boxed{\text{イ}}-1.$$

   $c_{\rm in}=1$ より

   $$S'=A+B'+1=A-B+\boxed{\text{イ}}.$$

   さらに

   $$d=\begin{cases}0&(A\ge B),\\1&(A<B)\end{cases}$$

   とすると，$c_{\rm out}=c_N$ との関係は $d=\boxed{\text{ウ}}$ となる。

3. 図 S4.3 は4ビットで1桁の10進数を表す BCD（Binary-Coded Decimal）用加算器である。BCD 入力 $A=a_3a_2a_1a_0$，$B=b_3b_2b_1b_0$ は $(0000)_2$～$(1001)_2$，すなわち0～9を取る。$c_{\rm in}$ は下位桁からの BCD 桁上げである。二進加算器の5ビット出力

   $$S'=c_4s_3s_2s_1s_0=A+B+c_{\rm in}$$

   は0～19であり，$S'\ge10$ のとき BCD 桁上げ $c_{\rm out}=1$ とする。BCD 加算補正器により下位4ビットを BCD 出力 $T=t_3t_2t_1t_0$（0～9）へ補正する。

   a) $c_{\rm out}=f_1(c_4,s_3,s_2,s_1,s_0)$ の論理式を示せ。
   b) $c_{\rm out}=1$ のとき補正器が $s_3s_2s_1s_0$ に加える4ビット定数 $M$ を2進数で示せ。

4. 図 S4.4 の BCD 減算器では，$B$ をビット反転して二進加算器に入力する。$c_{\rm in}$ には下位桁からの BCD 減算キャリーを入力し，$c_{\rm in}=0$（$\overline c_{\rm in}=1$）は下位桁でボローが発生したことを表す。

   $$D'=A-B-\overline c_{\rm in},\qquad -10\le D'\le9.$$

   $D'<0$ のときボローが生じ，$c_{\rm out}=c_4=0$ となる。そのとき BCD 減算補正器は下位4ビットに $(10)_{10}=(1010)_2$ を加えて BCD 出力 $t_3t_2t_1t_0$ を得る。

   図 S4.5 の共通加減算器には制御信号 $g$ があり，$g=0$ で BCD 加算 $A+B$，$g=1$ で BCD 減算 $A-B$ を行う。入力補正器は $B,g$ から $B''$ を作り，二進加算器は $A,B'',c_{\rm in}$ を加える。出力キャリーは $c_{\rm out}=f_2(g,c_4,s_3,s_2,s_1,s_0)$ とし，共通補正器は $g,c_{\rm out}$ に応じて下位4ビットを補正する。

   a) 入力補正器の各出力 $b''_k$（$k=0,1,2,3$）を $g,b_k$ で表せ。
   b) $c_{\rm out}=f_2(g,c_4,s_3,s_2,s_1,s_0)$ の論理式を示せ。
   c) 共通補正器が $s_3s_2s_1s_0$ に加える4ビット変数 $h_3h_2h_1h_0$ の各ビットを，$g,c_{\rm out}$ の論理式で表せ。

题目描述

以下用上方完整真值表及电路连接定义作答。$\overline x$、相乘、$\vee$ 分别表示非、与、或；$N$ 位整数为 $X=x_{N-1}\cdots x_0$，常数用下标10、2区分十进制和二进制。所有逻辑式要求 AND 项数最少的积之和形式。

1. $N$ 位加法器由 $N$ 个全加器串接，输入为 $A,B$，初始进位 $c_{\rm in}=c_0=0$。由表 S4.1，用 $a_k,b_k,c_k$ 表示第 $k$ 位的和 $s_k$、进位 $c_{k+1}$；最终进位为 $c_N$。
2. 对无符号非负整数 $A,B$，逐位取反 $B$ 得 $B'$，用 $A+B'+1$ 实现减法。填写（ア）至（ウ）：$B'$ 是 $B$ 的哪一种补数；$B+B'=$（イ）$-1$，$A+B'+1=A-B+$（イ）；定义 $A\ge B$ 时 $d=0$，否则 $d=1$，用加法器进位 $c_{\rm out}$ 表示 $d=$（ウ）。
3. 一位 BCD 输入 $A,B$ 都在0～9之间，$c_{\rm in}$ 为低位十进制进位。二进制和 $S'=c_4s_3s_2s_1s_0=A+B+c_{\rm in}$ 在0～19之间，十进制进位在 $S'\ge10$ 时为1。
   a) 写出 $c_{\rm out}=f_1(c_4,s_3,s_2,s_1,s_0)$。
   b) 在 $c_{\rm out}=1$ 时，下四位需加哪个4位二进制常数 $M$，才能使输出 $T$ 成为0～9的 BCD 数？
4. BCD 减法中，$B$ 取反后送入加法器；$c_{\rm in}=0$ 表示低位发生借位，因此实际差为 $D'=A-B-\overline c_{\rm in}$，范围为 $-10$～9。负差对应 $c_{\rm out}=c_4=0$；此时给下四位加 $(1010)_2$ 作 BCD 校正。共用电路的控制信号为 $g$：$g=0$ 加法、$g=1$ 减法。
   a) 用 $g,b_k$ 写出输入校正器的各位 $b''_k$。
   b) 写出统一进位函数 $f_2(g,c_4,s_3,s_2,s_1,s_0)$。
   c) 用 $g,c_{\rm out}$ 分别写出要加到下四位的校正量 $h_3h_2h_1h_0$。

Kai

1)

和は奇数個の入力が1のときに1，桁上げは2個以上が1のときに1となる。

$$\boxed{s_k=\bar a_k\bar b_kc_k\vee\bar a_kb_k\bar c_k\vee a_k\bar b_k\bar c_k\vee a_kb_kc_k},$$

$$\boxed{c_{k+1}=a_kb_k\vee b_kc_k\vee c_ka_k}.$$

2)

$B'=2^N-1-B$ なので

$$\boxed{(\text{ア})=1,\quad(\text{イ})=2^N,\quad(\text{ウ})=\bar c_{\rm out}}.$$

$A\ge B$ のときだけ $A-B+2^N\ge2^N$ となり，キャリーが1となる。

3)

$S'\in[0,19]$ より

$$\boxed{c_{\rm out}=c_4\vee s_3s_2\vee s_3s_1}.$$

十進の基数10と二進4ビットの基数16の差を補うので，加える定数は $\boxed{(0110)_2}$。

4)a)

$g=0$ でそのまま，$g=1$ で反転するため

$$\boxed{b''_k=\bar g b_k\vee g\bar b_k}.$$

4)b)

加算時の式と減算時の $c_4$ を選択すると

$$\boxed{c_{\rm out}=c_4\vee\bar g s_3s_2\vee\bar g s_3s_1}.$$

4)c)

$c=c_{\rm out}$ と略記する。必要な補正は $(g,c)=(0,1)$ で $0110$，$(1,0)$ で $1010$，それ以外は $0000$。よって

$$\boxed{h_3=g\bar c,\quad h_2=\bar gc,\quad h_1=g\bar c\vee\bar gc,\quad h_0=0}.$$