0
\$\begingroup\$

In section 5.3. of the following book an analysis of carry propagation in the ripple carry adder is performed. However the statistical analysis doesn't particularly convince me. Specifically at the beginning of page 81 it is stated that "The probability that a carry generated at position i will propagate up to and including position (j - 1) and sto at position \$j(j > i)\$ is \$2^{-(j-1-i)}*1/2 = 2^{-(j-i)}\$ ".

However, assuming j > i, my modeling gives me instead of a factor 1/2, a factor \$(1/2^4)\$. I would like to understand how the result of the book is derived, does anybody have a clue?

Update, based on the comments:

Basically "assuming at position \$i\$ a carry has been generated (let's call this event \$g_i\$) then this would propagate through the position \$i+1,i+2,...j-1\$, let's call such events \$p_{i+1},\ldots,p_{j-1}\$, such propagation will stop at position \$j\$ if the propagated bit is both "annihilated" (event \$a_{j}\$) or there's a further carry generation in position \$j\$, \$g_j\$. So the whole probability can be expressed as $$Pr(g_j \vee a_j,p_{j-1},\ldots p_{i+1} \;|\; g_i) = Pr(g_j \vee a_j,p_{j-1},\ldots p_{i+1})= \prod_{k=i+1}^{j-1} Pr(p_k) \left( Pr(g_j) + Pr(a_j)\right) = 2^{j-i-1}\times \left( \frac{1}{4} + \frac{1}{4}\right) = 2^{j-i-1} \times \frac{1}{2} = 2^{j-i}.$$

In the equation I wrote I'm considering that all the events $$g_j,a_j,p_{j-1} \ldots p_{i+1} , g_i $$ are all disjointed.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

I just took a quick look. I didn't read the book leading up to the part you referenced. It's quite possible that I'm misinterpreting terms and that's important because the question is all about the terms the author is defining. That said, I think I agree with you that there is a problem of interpretation in the quantitative statement you referenced. But I'm not sure I agree with your conclusion about it.

Just to be clear about my interpretation, I believe the author is stating that there exist four logical states to consider for a full adder that divide down into three important effects on the carry input, from the point of view of the carry output. The resulting three conditions are:

  1. \$A_j=B_j=0\$. In this case, the carry input (if any) will be ignored and is, in effect, stopped. Since this accounts for one of the four cases it is assigned a probability of \$0.25\$.
  2. \$A_j\ne B_j\$. In this case, the carry input will be propagated. Since this accounts for two of the four cases it is assigned a probability of \$0.50\$.
  3. \$A_j=B_j=1\$. In this case, the carry input (if any) is ignored and a new carry generated. Since this accounts for one of the four cases it is assigned a probability of \$0.25\$.

But take notice of the way I've inserted some commentary about each of these. I'll get back to this, shortly.

Now, given those definitions, the author goes on to make the statement: "The probability that a carry generated at position \$i\$ will propagate up to and including position \$j-1\$ and stop at position \$j\$ ([ed:where] \$j > i\$) is \$2^{-\left(j-1-i\right)}\times\frac{1}{2}=2^{-\left(j-i\right)}\$."

How is that supposed to be interpreted, though? What does the phrase "stop at position \$j\$" mean? If you go back and look at the three conditions I lay out above, you will see that there are actually two cases where the carry input is stopped. It is stopped when \$A_j=B_j=0\$ and it is also stopped when \$A_j=B_j=1\$, because either way the carry input doesn't matter and is ignored.

So let's take a look at the simplest case where \$j=i+1\$. (Since the author allows all cases where \$j > i\$, I think this is a valid case.) In this case, the probability of a carry being generated in position \$i\$ is exactly 1, since it is assumed by the author's statement that a carry is, in fact, generated at position \$i\$ by definition. There will be no position \$j-1\$ in this case (or there are zero such positions), so the carry will by definition propagate through all of the zero such positions with a probability of 1, as well. Now we come to position \$j\$. And in this case, an input carry will be stopped at this stage in either (1) or (3) mentioned above, or with probability 0.5. The author's computation says that this should be \$2^{-\left(j-i\right)}=2^{-1}=\frac{1}{2}=0.5\$ and so this matches up ... if you are using one possible interpretation of the idea of stopping the input carry. On the other hand, if you are only focused on the meaning shown in (1) above, then you'd get a different result. But I think this isn't the author's intended meaning. I think the author is quite aware that an input carry will be stopped by either (1) or by (3) and has formulated the equation, accordingly.

So I'm betting, ignorant of further reading that I'm unwilling to do at this time, that you are merely mis-interpreting the author's intended meaning because the listed three cases lead you in that direction. You think only case (1) causes the input carry to be stopped when, in fact, it is both cases (1) and (3) that do so.

EDIT: Thanks for asking me to formalize things:

  • For the case under consideration, the probability of position \$i\$ emitting a carry out (of \$1\$) is exactly \$1\$ by definition, because the case presumes that position \$i\$ is carrying out. Probability here is \$P_i = 1=2^0\$
  • The probability of each intervening positions, those which are neither position \$i\$ nor are position \$j\$ but are instead positions \$k\$ where \$i < k < j\$, propagating a carry happen only in (2) and with probability 0.5 for each such position. If \$i\$ represents the position emitting a carry and if \$j\$ represents the final position stopping that carry from propagating, then there are \$n=j-i-1\$ such intervening positions. So the total probability of propagation through all \$n\$ intervening positions will be \$P_{\left({i+1}\right)\,...\,\left({j-1}\right)} = 2^{-n}=2^{-\left(j-i-1\right)}\$.
  • The probability of the final position \$j\$ stopping a carry is due to either (1) or (3). So the probability is \$P_j= 0.25 + 0.25 = 0.50 = 2^{-1}\$.

Now, combining all three:

\$P_{total} = \left[P_i\right] \cdot \left[P_{\left({i+1}\right)\,...\,\left({j-1}\right)}\right]\cdot \left[P_j\right] = 2^0 \cdot 2^{-\left(j-i-1\right)} \cdot 2^{-1} = 2^{0-\left(j-i-1\right)-1}=2^{-\left(j-i\right)}\$

So, here I get the same result as the author shows.

\$\endgroup\$
8
  • \$\begingroup\$ Can you please formalize the probability how would expressed? would it be something similar to what I wrote here? math.stackexchange.com/questions/1904219/… \$\endgroup\$ Aug 26, 2016 at 18:43
  • \$\begingroup\$ I'm just realizing there's some problem in the formula I forwarded to you... sorry xD, but anyway if you could formalize your explanation with a formula like the one i showed you it would be very useful. \$\endgroup\$ Aug 26, 2016 at 18:49
  • \$\begingroup\$ @user8469759: I've added an EDIT section for you to examine. Perhaps it helps. Perhaps it doesn't because I'm still not understanding things. \$\endgroup\$
    – jonk
    Aug 26, 2016 at 19:22
  • \$\begingroup\$ I'm having a look, and I'll try to formalize as well. Thanks again \$\endgroup\$ Aug 26, 2016 at 20:01
  • \$\begingroup\$ @user8469759: okay. I'll wait. \$\endgroup\$
    – jonk
    Aug 26, 2016 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.