東京大学 情報理工学系研究科 創造情報学専攻 2016年8月実施 筆記試験 第2問

标签：

• Tokyo-University
• Combinatorial-Circuit
• Half-and-Full-Adders

Author

tomfluff

Description

(1) Show the truth table of a half-adder HA (Fig. 1) which outputs 1-bit sum $S$ and 1-bit carry $C$ from two 1-bit binary inputs $A$ and $B$.

(2) Draw a diagram of the half-adder circuit HA with devices of AND, OR, and NOT.

(3) Show the truth table of a full-adder FA (Fig. 2) which outputs 1-bit sum $S$ and 1-bit carry $C$ from two 1-bit binary inputs $A$, $B$, and 1-bit carry input $X$.

(4) Draw a diagram of the full-adder circuit FA using two half-adder HA devices. If necessary, you can use AND, OR, and NOT devices.

(5) Explain a method to build an n-bit adder for unsigned integers using full-adder FA devices.

(6) Explain a method to build a faster n-bit adder.

(7) Explain a method to execute a subtract operation with an n-bit adder through generating negative number in two's complement, and draw its circuit.

(8) Explain a method to build an n-bit adder-subtractor for unsigned integers with a single n-bit adder and an input signal $F$ to select addition or subtraction, and draw its circuit.

(9) Explain how to build a multiplier to generate a 2n-bit product $M$ from two n-bit unsigned integers $A$ and $B$.

题目描述

1. 写出半加器 HA 的真值表：输入为两个 1 位二进制数 (A,B)，输出为 1 位和 (S) 与 1 位进位 (C)（见图 1）。
2. 仅用 AND、OR、NOT 元件画出 HA 电路。
3. 写出全加器 FA 的真值表：输入为 (A,B) 和 1 位输入进位 (X)，输出为和 (S) 与进位 (C)（见图 2）。
4. 用两个 HA 构成 FA；必要时可增加 AND、OR、NOT 元件，画出电路。
5. 说明如何用 FA 构造无符号整数的 (n) 位加法器。
6. 说明如何构造速度更快的 (n) 位加法器。
7. 说明如何用二进制补码生成负数，并借助 (n) 位加法器执行减法；画出电路。
8. 只使用一个 (n) 位加法器，再增加选择加、减的输入信号 (F)，构造无符号整数 (n) 位加减器；说明方法并画图。
9. 说明如何构造乘法器，把两个 (n) 位无符号整数 (A,B) 相乘并输出 (2n) 位乘积 (M)。

考点

• 半加器与全加器：从真值表化简和位、进位逻辑，并用两个半加器组合全加器。
• 多位加法与快速进位：级联全加器实现行波进位，并用超前进位等结构缩短关键路径。
• 补码加减器：用控制信号选择性取反第二操作数并设置最低位进位，实现同一加法器完成加、减法。
• 无符号乘法器：由部分积生成和移位加法网络得到 (2n) 位乘积。

Kai

(1)

A	B	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

(2)

(3)

A	B	X	S	C
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

(4)

(5)

A method would be to do a bitwise addition for $A=a_0a_1a_2a_3...a_n$ and $B=b_0b_1b_2b_3...b_n$ two unsigned $n$ bit integers. And the carry of each addition would be connected to the X input of the following FA. Thus $FA_0$ has a0,b0,_ as inputs, $FA_1$ has a1,b1,c0 as inputs and so on.

(6)

A faster method would be to build a look-ahead carry adder. This adder basically computes the values with consideration to the carries without calculating the carry and waiting for the result of each pair to calculate the next result. Since each calculation can be expanded to use parameterization without the carry, it is possible to remove internal carries.

(7)

Subtraction would be an addition with the negative value. So let's assume we would like to calculate A-B, it is the same as computing A+(-B). This means that for subtraction all we need to do is compute the 2's-complement of B and add the two numbers together. This can be acomplished by inverting B and adding 1 to the X (carry) input of the n-bit adder.

Note: Example uses 4-bit but same drawing is for n-bit.

(8)

A method could be to use F as the input to the carry of the n-bit adder. As well as XOR F and every bit of B. This way, If F=1 meaning subtraction, B will be inverted and 2's complement will be implemented with the adder carry. Otherwise B will stay the same and addition will be implemented.

(9)

A method to compute multiplication would be using full adders and half adders in the following way:

Notice that the Truth Table of bits a*b is the same as a&b. Avery bi is multiplied by the whole of A and the solution is added between two consecutive bi and bi+1.

This method is very similar to the multiplication algorithm that is being tought in schools.