東京工業大学 情報理工学院 情報工学系 2017年8月実施 午前 4.

标签：

• TITech
• Majority-Gate-Logic-Synthesis
• Half-and-Full-Adders
• Signed-Addition-Subtraction-and-Overflow-Detection

Author

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

Description

変数はすべて $\{0,1\}$ の値をとる。$(X_{n-1},\ldots,X_0)$ は $X_{n-1}$ を MSB、$X_0$ を LSB とする $n$ 桁の二進数であり、負数には $2$ の補数表現を用いる。中間結果を新しい変数に代入してよい。

(1) $X,Y,Z$ のうち $2$ 個以上が $1$ のときだけ $1$ を返す $\operatorname{maj}(X,Y,Z)$ を積和標準形で表せ。

(2) $\operatorname{nor}(X,Y)=\overline{X\vee Y}$ とし、$NX=\bar X,NY=\bar Y,NZ=\bar Z$ とする。$X,Y,Z$ のうち $2$ 個以上が $1$ のときだけ $0$、それ以外は $1$ を返す関数 $\operatorname{nmaj}(NX,NY,NZ)$ を、実引数 $NX,NY,NZ$ と $2$ 入力 nor のみで表せ。関数の個数を最少にせよ。

(3) $X,Y,Z$ のうち奇数個が $1$ のときだけ $1$ を返す $3$ 入力 $\operatorname{xor}(X,Y,Z)$ を、$2$ 入力 nor のみで表せ。関数の個数を最少にせよ。

(4) $3$ ビットの $X,Y$ の $1$ の補数をそれぞれ $(CX_2,CX_1,CX_0)$、$(CY_2,CY_1,CY_0)$ とする。和 $X+Y$ の $4$ ビット表現を $(A_3,A_2,A_1,A_0)$ とする。$CX_i,CY_i$ と $3$ 入力 xor、$3$ 入力 nmaj、$2$ 入力 nor だけを用い、各 $A_i$ を最少個数の関数で表せ。

(5) 差 $X-Y$ の $4$ ビット表現を $(S_3,S_2,S_1,S_0)$ とする。$X_i,Y_i,CX_i,CY_i$ と上記の $3$ 種類の関数だけを用い、各 $S_i$ を最少個数の関数で表せ。

(6) $n$ ビットの $X,Y$ の積を $(M_{2n-1},\ldots,M_0)$ とする。$2n$ ビットのレジスタ $R,P$ および $P_{-1}$ を用意し、初期値を

$$R=(X_{n-1},\ldots,X_0,0,\ldots,0),\quad P=(0,\ldots,0,Y_{n-1},\ldots,Y_0),\quad P_{-1}=0$$

とする。原文では $0\leq k\leq n-1$ の各回で、現在の $(P_0,P_{-1})$ により次の処理を指定している。加減算には桁上げを伴い、処理後に各ビットを $i$ から $i-1$ へ送る。

$(P_0,P_{-1})$	原文の処理
$(0,0)$	$P$ を右シフト
$(1,0)$	$P+R$ を右シフト
$(0,1)$	$P-R$ を右シフト
$(1,1)$	$\boxed A$

(a) 原文の「$k=n-1$ で $P$ が積になる」という条件に対して、空欄 $A$ の動作を答えよ。 (b) 加減算により積が求まる理由を式で説明せよ。 (c) $P_{-1}$ を参照せず、$P_0=0$ ならシフト、$P_0=1$ なら加算後シフトとする方式と比較して長所・短所を述べよ。

题目描述

1. 写出三输入多数决函数的最小项之和。
2. 已知三个反相输入，用最少的二输入 NOR 构造原输入多数决的反相输出。
3. 用最少的二输入 NOR 构造三输入异或。
4. 仅给定两个三位数的逐位反相输入，用 xor、nmaj、nor 构造四位有符号和，并尽量减少函数调用。
5. 同时给定正反相输入，用相同函数构造四位有符号差，并减少函数调用。
6. 按给定寄存器初值和相邻两位控制表，填写乘法过程的第四种动作、证明原理并比较普通加移法。题面的加减符号及结束轮次按扫描原文保留在上表中。

Kai

以下、$N=\operatorname{nor}$、$P=\operatorname{xor}$、$M=\operatorname{nmaj}$ と略記する。定義から $M(u,v,w)=uv\vee uw\vee vw$ である。定数入力 $0$ を利用する。

(1)

積和標準形は

$$\boxed{XY\bar Z\vee X\bar YZ\vee\bar XYZ\vee XYZ}.$$

(2)

$a=NX,b=NY,c=NZ$ とおく。次の $6$ 個で実現できる。

$$\begin{aligned} u_1&=N(a,a),&u_2&=N(b,b),&u_3&=N(a,b),\\ u_4&=N(u_1,u_2),&u_5&=N(c,u_4),&M(a,b,c)&=\boxed{N(u_3,u_5)}. \end{aligned}$$

実際、出力は $(a\vee b)(c\vee ab)=ab\vee ac\vee bc$ となる。最少個数は $\boxed6$。

(3)

次の $8$ 個でよい。

$$\begin{aligned} u_1&=N(X,Y),&u_2&=N(X,u_1),&u_3&=N(Y,u_1),\\ u_4&=N(u_2,u_3),&u_5&=N(Z,u_4),&u_6&=N(Z,u_5),\\ u_7&=N(u_4,u_5),&P(X,Y,Z)&=\boxed{N(u_6,u_7)}. \end{aligned}$$

$u_4=\overline{X\oplus Y}$ であり、後半も XNOR をとるから出力は $X\oplus Y\oplus Z$。最少個数は $\boxed8$。

(4)

最少個数は $\boxed7$ であり、次のように実現する。

$$\begin{aligned} A_0&=P(CX_0,CY_0,0),&c_1&=N(CX_0,CY_0),\\ A_1&=P(CX_1,CY_1,c_1),&q_2&=M(CX_1,CY_1,A_1),\\ x_2&=N(CX_2,CX_2),&A_2&=P(x_2,CY_2,q_2),\\ A_3&=M(A_2,x_2,q_2). \end{aligned}$$

$c_1$ は下位桁からの桁上げ、$q_2=\bar c_2$ は第 $1$ 桁からの桁上げの否定、$x_2=X_2$ である。$x_2=q_2$ なら $A_3=x_2$、異なるなら $A_2=Y_2$ なので、最後の式は符号拡張した和の符号ビットを与える。

(5)

借りを $b_1,b_2$ とすれば、次の $6$ 個で実現する。

$$\begin{aligned} S_0&=P(X_0,Y_0,0),&b_1&=N(X_0,CY_0),\\ S_1&=P(X_1,Y_1,b_1),&b_2&=M(CX_1,Y_1,b_1),\\ S_2&=P(X_2,Y_2,b_2),&S_3&=M(X_2,CY_2,b_2). \end{aligned}$$

$S_3$ は符号拡張した上位桁の差である。最少個数は $\boxed6$。

(6)

(a)

原文を文字どおり満たす $A$ は存在しない。空欄として意図される動作は $\boxed{\text{加減算せず算術右シフト}}$ である。ただし原文の加減方向では一般に積を得られない。例えば $n=2,X=Y=1$ では空欄を使う前に、状態 $k=1$ で $P=2$ となり、積 $1$ と一致しない。正しい Booth 法の更新は

$$\boxed{P\gets\operatorname{ASR}\bigl(P+(P_{-1}-P_0)R\bigr)}$$

であり、$(1,0)$ で減算、$(0,1)$ で加算する。旧 $P_0$ を $P_{-1}$ に保存し、$n$ 回後、すなわち状態 $k=n$ で積を読む。最小負数も扱う場合、上位部分に符号拡張用の $1$ ビットを追加し、最終結果の下位 $2n$ ビットを取る。

(b)

$y_{-1}=0$ とすると、$2$ の補数の値は

$$Y=-y_{n-1}2^{n-1}+\sum_{k=0}^{n-2}y_k2^k =\sum_{k=0}^{n-1}(y_{k-1}-y_k)2^k.$$

したがって

$$XY=\sum_{k=0}^{n-1}(y_{k-1}-y_k)X2^k.$$

各係数は $-1,0,1$ なので、上記の減算・シフトのみ・加算で計算できる。原文どおり符号を逆にするとこの和は $-XY$ になる。

(c)

連続する $1$ の列を、その両端の加減算に置き換えられるため、長い $1$ の列では演算回数を減らせる。また $2$ の補数を直接扱える。一方、前のビットを保持するレジスタ、減算器および制御が必要で、交互に $0,1$ が現れる場合などは加減算回数が増える。反復回数自体は $n$ 回である。