The Determination of Carry Propagation Length for Binary Addition
George W. Reitwiesner · IEEE Transactions on Electronic Computers · 1960
It is well known that the expected maximum length of nonzero carry propagation in the addition of two uniformly distributed binary numbers of n-digits each is less than log2 n. The propagation of both zero and nonzero carry is required in the employment of asynchronous self-timing addition. For the addition of two n-digit binary numbers which are uniformly distributed, a simple recursive algorithm is readily derived for the exact determination of the expected maximum length of zero or nonzero carry propagation.