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

标签：

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

Author

kainoj

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)

• OR($x, y$) = $majority(0, x, y)$
• AND($x, y$) = $majority(1, x, y)$
• XOR($x, y$) = AND( OR($x,y$), NOT( AND($x, y$) ) = $majority[1, majority(0,x,y) , not\:majority(1, x, y)]$

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.

$$\begin{aligned} S = a\veebar b \veebar c_{in} && C = (a\land b) \lor (c_{in} \land (a \lor b)) \end{aligned}$$

$S$ yields $4$-$\text{M}_3$ level (2x XOR). $C$ yields $3$-$\text{M}_3$ level (OR with 2-level AND). Thus, $\text{FA}_1$ has $4$-$\text{M}_3$ level.

Bonus: $C = majority(c_{in}, a,b)$. Thanks Igor!

(3)

Connect $4$ $\text{FA}_1$ in series. It's $\text{M}_3$ level is $4\cdot4 = 16$.

(4)

Classic $4$-bit multiplier (google for images). Connect three $4$-bit adders in series and try not to get messed with connections. $\text{M}_3$ level is: $3\cdot 16 + 8\cdot 1$: each of three $\text{FA}_4$ has level $16$ and there's one level of $8$ AND gates preceding $\text{FA}_4$'s.