Analysis of delays in converting from a redundant representation

The use of a redundant number system allows many arithmetic operations to process digits sequentially, most significant digit first. Final conversion back to a standard binary representation can require time to propagate any carries. This paper analyses and reports on the delays encountered when this is done by an online algorithm, giving a good upper bound on the expected delay. The delay is approximately log,k for the kth digit in a representation with base r