0

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)}\times1/2$".

However my modeling gives me a different result, to be honest the result given by the book is not explained very well, IMHO.

Here is my derivation,

I call $g_i$ the event that a carry is generated at position $i$, $p_i$ the event that a carry is propagated through the position $i$ and $a_i$ the event that it is annihileted. All of these events depend only from $x_i, y_i$ (bits of the input). I have to compute the probability

$$ Pr\left(g_i,p_{i+1},...,p_{j-1},a_{j}\right) = Pr(g_i) \prod_{k=i}^{j-1}Pr(p_{k}) Pr(a_j) $$

However when I substitute the probabilities given by the book at the beginning of page 81 the result that comes out from my expression is not the same, so probably both I'm missing something or the book's result is wrong.

Can you help to understand where is the problem?

user8469759
  • 5,285
  • Based on the example given in the book, it seems to me a chain can stop either when the carry is annihilated or when a new carry is generated. If you only count annihilation you will get half the correct probability. What probability did your modeling give you? – David K Aug 26 '16 at 19:11
  • basically the same, but instead of the factor 1/2 it gives me 1/2^4 – user8469759 Aug 26 '16 at 19:16
  • I think that should be $\prod_{k=i+1}^{j-1}Pr(p_{k})$ rather than $\prod_{k=i}^{j-1}Pr(p_{k})$, because you cannot have both $g_i$ and $p_i$ occur simultaneously. – David K Aug 26 '16 at 20:24

1 Answers1

1

I think this comes down to the interpretation of the phrase,

The probability that a carry generated at position $i$ will propagate up to and including position $j - 1$ and stop at position $j$ $(j > i)$

You seem to have interpreted this as "the probability that a carry is generated at position $i$ and propagates up to and including position $j - 1$ and is annihilated at position $j$". The only way for a chain to be "annihilated" is if it reaches a position where both addends have bit value $0$.

The book is interpreting this phrase to mean "the probability that a carry propagates up to and including position $j - 1$ and the chain stops for any reason at position $j$, given that a carry is generated at position $i$". Reasons for the chain to stop are because position $j$ annihilates the carry, or because position $j$ generates a new carry (which stops the previous chain), or because "position $j$" is actually the "carry out" bit (which by assumption no chain can continue beyond).

That is, the probability that the book computes as $2^{-(j-i)}$ is meant to be $$ \left(\prod_{k=i+1}^{j-1}Pr(p_{k})\right) Pr(a_j \lor g_j) $$ which is a factor of $8$ greater than the result you reported.

David K
  • 98,388