お茶の水女子大学 人間文化創成科学研究科 理学専攻 情報科学コース 2018年8月実施 情報基礎 問題2

标签：

• Ochanomizu-University
• Half-and-Full-Adders
• Ripple-Carry-Adder

Author

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

Description

CPU 内部の 32 ビット加算回路を次の手順で設計する。

1. 入力を $X,Y$、和を $S$、桁上げを $C$ とする 1 ビット半加算器 $HA$ の真理値表を示し、$S,C$ を論理式で表せ。
2. 論理演算子の記号を用いて $HA$ の論理回路図を示せ。
3. 入力 $X_i,Y_i,C_{i-1}$、出力 $S_i,C_i$ をもつ 1 ビット全加算器 $FA_i$ の真理値表を示し、$S_i,C_i$ を論理式で表せ。
4. 式を簡単化し、$FA_i$ の論理回路図を示せ。回路内に $HA$ を含めてもよい。
5. 32 個の全加算器 $FA_1$ から $FA_{32}$ を接続した 32 ビット加算回路の概略を描け。
6. この加算回路を含む CPU の部分の英語名と略称を答えよ。

题目描述

从半加器的真值表与逻辑电路出发，构造全加器，再把 32 个全加器连接成 32 位串行进位加法器，并写出该电路所属 CPU 部件的英文名称与缩写。

Kai

(1)

$X$	$Y$	$S$	$C$
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

したがって

$$\boxed{S=X\oplus Y,\qquad C=X\land Y}.$$

(2)

         ┌─────┐                  ┌─────┐
X ──────►│     │         X ──────►│     │
         │  ⊕  │────► S           │  ∧  │────► C
Y ──────►│     │         Y ──────►│     │
         └─────┘                  └─────┘
           XOR                      AND

(3)

$C_{i-1}$ を下位ビットからの桁上げとする。

$X_i$	$Y_i$	$C_{i-1}$	$S_i$	$C_i$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

よって

$$\boxed{ S_i=X_i\oplus Y_i\oplus C_{i-1}, \qquad C_i=(X_i\land Y_i)\lor(Y_i\land C_{i-1})\lor(C_{i-1}\land X_i)}.$$

(4)

二つの半加算器を用いる。まず

$$p=X_i\oplus Y_i,\qquad c_1=X_i\land Y_i,$$

次に

$$S_i=p\oplus C_{i-1},\qquad c_2=p\land C_{i-1}$$

とし、$C_i=c_1\lor c_2$ とすればよい。

Xi ───────►┌─────┐ p ───────►┌─────┐──────► Si
Yi ───────►│ HA1 │            │ HA2 │
           └──┬──┘      Ci-1 ►└──┬──┘
              │ c1               │ c2
              └──────►[ OR ]◄────┘
                         │
                         └──────────────► Ci

(5)

最下位ビットから最上位ビットへ桁上げを順に接続する。

          X1,Y1          X2,Y2                         X32,Y32
            ││             ││                             ││
C0=0 ───► [FA1] ──C1──► [FA2] ──C2──► ... ──C31──► [FA32] ──► C32
             │              │                              │
             S1             S2                            S32

これは 32 ビットのリップルキャリー加算器である。

(6)

CPU の Arithmetic Logic Unit（ALU、算術論理演算装置） に含まれる。