乐正

Actions speak louder than words.

Sicp-ex3-30

问题

图3-27展示的是通过串接起$n$个全加器组成的一个级联进位加法器。这是用于求$n$位二进制数之和的并行加法器的最简单形式。输入$A_1, A_2, A_3 \dots A_n$与$B_1, B_2, B_3 \dots B_n$是需要求和的两个二进制数(每个$A_k$和$B_k$都是$0$或者$1$)。这一电路产生出与之对应的和的$n$个二进制数$S_1, S_2, S_3 \dots S_n$,以及这一求和的最终进位值$C$。请写出一个过程ripple-carry-adder生成这种电路,该过程应以各包含着$n$条线路的三个表——$A_k,B_k和S_k$——作为输入,还有另一线路$C$。级联进位加法器的主要缺点是需要等待进位信号器向前传播。请设法确定,为了得到$n$位级联进位加法器的完整输出,我们将需要怎样的延时。请用与门、或门和反门的时延来表示这一时延。

一个对n位二进制数的逐位进位加法器

解答

用$D_{and}$、$D_{or}$和$D_{not}$分别表示与门、或门和反门的时延。那么一个半加器所需要的时延是:

$$ D_{HA} = max(D_{or}, \; D_{not} + D_{and}) + D_{and} $$

所以一个全加器的时延是:

$$ \begin{align} D_{FA} &= 2 \times D_{HA} + D_{or} \\ &= 2 \times (max(D_{or}, \; D_{not} + D_{and}) + D_{and}) + D_{or} \end{align} $$

所以一个$n$级联进位加法器的时延是:

$$ \begin{align} D_{nFA} &= n \times D_{FA} \\ &= 2n \times (max(D_{or}, \; D_{not} + D_{and}) + D_{and}) + nD_{or} \end{align} $$

draft

« sicp-ex3-29 sicp-ex3-31 »

Comments