東京大学 情報理工学系研究科 コンピュータ科学専攻 2016年2月実施 問題4

标签：

• Tokyo-University
• Majority-Gate-Logic-Synthesis
• Full-Adder-and-Critical-Path
• Combinational-Binary-Multiplier

Author

kainoj, 祭音Myyura

Description

The majority gate $\text{M}_3$ is a binary logic gate defined as follows: $\text{M}_3$ has $3$ inputs and $1$ output. The output is $1$ if two or three of the inputs are 1; and 0 otherwise.

When you answer circuit designs in the questions below, you can use NOT gates and constants $0$ and $1$ in addition to $\text{M}_3$ gates, but other gates such as AND or OR cannot be used. You should draw an $\text{M}_3$ gate as a rectangle labeled with $\text{M}_3$, and a NOT gate as a circle, as shown in the following example:

Answer the following questions. Try to make $\text{M}_3$-levels (i.e. the maximum number of serially connected $\text{M}_3$ gates) as small as possible in your answers.

(1) Design and depict the following logic circuits:

• (a) AND of $2$ inputs,
• (b) OR of $2$ inputs,
• ($c$) XOR of $2$ inputs.

(2) A 1-bit full adder $\text{FA}_1$ is defined as follows: $\text{FA}_1$ has $3$ inputs and $2$ outputs called $\text{S}$ (sum) and $\text{C}$ (carry), respectively. $\text{S}$ and $\text{C}$ are defined so that $2\text{C} + \text{S}$ is equal to the sum of the $3$ input bits.
Design and depict a $1$-bit full adder $\text{FA}_1$. Answer its $\text{M}_3$-level, too. You can use the circuits you have designed in Question (1).

(3) Design and depict a $4$-bit full adder $\text{FA}_4$. Answer its $\text{M}_3$-level, too.

Here $\text{FA}_4$ takes, as inputs: (i) two unsigned $4$-bit integers, and (ii) a carry bit.
It outputs the $5$-bit sum. You can use the circuits you have designed in Questions (1) and (2).

(4) Design and depict a $4$-bit multiplier $\text{MUL}_4$. Answer its $\text{M}_3$-level, too.

Here $\text{MUL}_4$ takes two unsigned $4$-bit integers as inputs. It outputs the $8$-bit product of the inputs. You can use the circuits you have designed in Questions (1), (2), and (3).

题目描述

三输入多数门 $\mathrm{M}_3$ 有三个输入和一个输出：三个输入中至少有两个为 $1$ 时输出 $1$，否则输出 $0$。

以下各题设计电路时，除 $\mathrm{M}_3$ 外只可使用非门和常量 $0,1$，不得使用与门、或门等其他门。绘图时按题中示例，用标有 $\mathrm{M}_3$ 的矩形表示多数门，用圆形表示非门。回答时应尽量减小 $\mathrm{M}_3$ 层数，即任一通路上串联的 $\mathrm{M}_3$ 门的最大数量。

（1）设计并画出以下逻辑电路：

• 两输入与；
• 两输入或；
• 两输入异或。

（2）一位全加器 $\mathrm{FA}_1$ 有三个输入以及和位 $\mathrm{S}$、进位 $\mathrm{C}$ 两个输出，且要求 $2\mathrm{C}+\mathrm{S}$ 等于三个输入位之和。设计并画出 $\mathrm{FA}_1$，同时给出其 $\mathrm{M}_3$ 层数。可以使用第（1）问设计的电路。

（3）设计并画出四位全加器 $\mathrm{FA}_4$，并给出其 $\mathrm{M}_3$ 层数。该电路输入两个无符号四位整数和一个进位位，输出五位和；可以使用第（1）、（2）问的电路。

（4）设计并画出四位乘法器 $\mathrm{MUL}_4$，并给出其 $\mathrm{M}_3$ 层数。该电路输入两个无符号四位整数，输出八位乘积；可以使用前面各问设计的电路。

Kai

(1)

• $\operatorname{AND}(x,y)=\operatorname{M}_3(0,x,y)$
• $\operatorname{OR}(x,y)=\operatorname{M}_3(1,x,y)$
• $\operatorname{XOR}(x,y)=\operatorname{M}_3\!\left(0,\operatorname{M}_3(1,x,y),\neg\operatorname{M}_3(0,x,y)\right)$

XOR is "$2$-$\text{M}_3$-level".

(2)

Classic $1$-bit full adder. Just draw a table and then depict the circuit. Let $a,b,c_{in}$ be inputs.

The direct construction from (1),

$$S=(a\mathbin{\mathrm{XOR}}b)\mathbin{\mathrm{XOR}}c_{in}, \qquad C=(a\land b)\lor\{c_{in}\land(a\lor b)\},$$

is valid and has four $\mathrm M_3$ levels. A smaller equivalent construction is

$$\begin{aligned} C&=\operatorname M_3(a,b,c_{in}),\\ T&=\operatorname M_3(b,c_{in},\neg a),\\ S&=\operatorname M_3(\neg C,a,T). \end{aligned}$$

Its truth table gives $2C+S=a+b+c_{in}$, and $\mathrm{FA}_1$ has two $\mathrm M_3$ levels.

(3)

Connect four $\mathrm{FA}_1$ cells as a ripple-carry adder, with $C_{i+1}=\operatorname M_3(a_i,b_i,C_i)$. Carry $C_i$ has depth $i$, and $S_i$ needs two further majority levels; therefore the $4$-bit adder has $\mathrm M_3$-level $5$ (at $S_3$).

(4)

Use the shift-and-add circuit shown: generate all partial products $p_{ij}=\operatorname M_3(0,a_i,b_j)$ in parallel, and combine the four shifted rows with three ripple-carry adders. Including the one partial-product level, the maximum depths after the first, second, and third adder rows are respectively $6$, $9$, and $12$. Thus this $\mathrm{MUL}_4$ has $\mathrm M_3$-level $12$.