Analysis of Delays in Converting from a
Redundant Representation.

byColin D. Walter
Computation Department, U.M.I.S.T.,
PO Box 88, Sackville Street, Manchester M60 1QD, U.K.
cdw@sna.co.umist.ac.uk
http://www.co.umist.ac.uk/

Key Words: Computer arithmetic, on-line algorithms, most significant digit
first algorithms, binary conversion, redundant number representations, realtime systems.

Abstract
The use of a redundant 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. We analyse and report on the
delays encountered when this is done by an on-line algorithm, giving a good upper boundon the expected delay.
representation with base r.

The delay is approximately logrk for the kth digit in a

IEE Computers & Digital Techniques, 144 No 4, (July 1997), pp. 219-221.

1. Introduction.
High speed arithmetic employs several standard techniques to avoid the delay caused
by carries which may propagate the whole length of a number. These include the use of aredundant number system to enable digit operations to be performed in parallel, andreorganising algorithms to operate digit serially from the least significant digit. However,for many applications, such as image compression and real time systems [1], on-line
methods [2] are preferable. Such algorithms consume and generate data digit serially but
most significant digit first.
On-line output is generally in redundant form since carries cannot be propagated up.
However, on-line input may have to be in a standard non-redundant form. For example, if
redundancy is given by including negative digits, then exponentiating by an on-line
exponent which contains negative bits in a ring which contains no inverse (or for which
the inverse is expensive to compute) is a problem. Another example might be supplying
input to pre-existing components which expected non-redundant input. Hence there is aneed for an on-line converter from redundant to standard representations.

On-linealgorithms tend to produce and consume data at a constant speed, say one digit per clock
cycle. Such a converter cannot do this without occasional delays as it awaits sufficient
information to propagate the carries. Generally, such delays may accumulate because
subsequent on-line processes cannot catch up; they can only process a single digit at onceor wait if an input digit is not available. This article looks at the average delay expected,
as this may be of interest in real time systems.
Ercegovac and Lang [4] have already shown how to convert back to non-redundant
form in such cases. Although their method converts as fast as possible, they do not
attempt to measure the average expected delay. The complexity of the delay turns out tobe logarithmic, and thus coincides with the complexity of carry propagation and of
performing a parallel digit conversion (see [5]). The results are applicable also when online output is to be rounded (see [3]).

2Converting Redundant Representations

C. D. Walter

2. Examples.
We begin with some illustrative decimal examples which use the usual digits together
with a digit X of value 10 and, for the first, also a digit 1 of value –1. The redundant
numbers 0.1999...9X... and 0.2000...0 1 ... may convert to 0.2000... and 0.1999...
respectively. In both cases we can allow for any eventuality by maintaining a lower
bound L = 0.1999... and an upper bound U = 0.2000... which are in standard nonredundant form and are updated as each input digit in received. Eventually an input digit
will determine which of these to choose. The common prefix of such bounds will belong
to the standard representation of the input and so can be sent to output. If, as here, thelargest carry up from the unread part of the redundant input is ±1, then only sequences of
9s or 0s in the converted output could lead to lead to carry propagation affecting morethan one digit..

With the same notation, consider the input 0.29993954...

Only when the ‘3’ isreceived is it clear that the ‘2’ is correct and can be output. A delay of three cycles builds
up as a result of the three ‘9’s. This holds up the output of all subsequent digits.
However, the next ‘9’ does not further delay the output of its preceding ‘3’ because, by
the time the ‘3’ can be output, the ‘5’ has already been read. Thus the delay of a given
output digit depends not on the total number of preceding digits ‘9’, but on the length ofthe maximal substring of consecutive ‘9’s which precede it.

Clearly the relative distribution of digits affects the average delay. If only digits ‘0’ to‘9’ occur, then the number is already in standard form and the delay is clearly 0. If thedigit set includes X but not 1 , then a process may require to generate an ambiguous
sequence of ‘9’s which can be upgraded by ‘X’ rather than a sequence of ‘0’s which it
could not decrease. Thus ‘9’s would be more frequent, increasing the average delay.
Complexity also arises because consecutive digits are not usually independent. This isreadily verified for a carry save adder in base 10, if the carry and save are added to give a
digit between 0 and X: a digit position with output ‘9’ is unlikely to generate a non-zerocarry, so that it is unlikely to be followed by an X.

3

IEE Computers & Digital Techniques, 144 No 4, (July 1997), pp. 219-221.

3. Determination of the Output Digits.
We will consider converting the redundant representation A = Si³1air-i of a fractional
real number into a standard, non-redundant representation A' = Si³1a'ir-i. Here r is theradix of the representations. We assume the redundant digits ai are in the range 0..2(r−1)
whereas those of A' are to be in the standard range 0..r−1. In the representation A weassume consecutive digits occur independently and r−1 occurs with probability 1/r.
(Since no other digit has the same residue mod r as r–1, it is reasonable to assume it
occurs with probability 1/r.) We will use B[k] to denote a number representation of kdigits, i.e. one of the form S1≤i≤kbir-i. Then B[k] = C[k] will mean the values of B[k] and C[k]are equal, whereas B[k] ≡ C[k] will mean their representations are identical.

The “on-the-fly” conversion method in [4] defines two non-redundant k-digit numbers
L[k] and U[k] such that either L[k] ≡ A'[k] or U[k] ≡ A'[k].

Thus, any common prefixof L[k] and U[k] is part of the output we desire. The properties A[k] ≤ A < A[k]+2r-k,
A'[k] ≤ A' < A' [k]+r-k, A = A' and A'[k] = A[k]+nr-k for some integer n, entail that n = 0 or
1.

Hence L[k] = A[k] and U[k] = A[k]+r-k.

These values can be constructed

incrementally. By equating values, if ak+1 < r then L[k+1] ≡ L[k]+ak+1r-k-1, whereas if
ak+1 ≥ r then L[k+1] ≡ U[k]+(ak+1–r)r-k-1.

Similarly, U[k+1] ≡ L[k]+(ak+1+1)r-k-1 if

ak+1 < r–1 whereas U[k+1] ≡ U[k]+(ak+1+1–r)r-k-1 if ak+1 ≥ r–1. Thus L[k+1] and U[k+1]agree on their first k digits when ak+1 ≠ r–1, as we expected from the decimal examples
above. (We have actually chosen the largest range of redundant digits for which this is
the case.) So, for ak+1 ≠ r–1 the delay to outputting the kth digit is the same as for the k–
1th digit. Moreover, L[k+t] and U[k+t] will agree on only their first k digits precisely
when ak+1 ≠ r–1 but ak+i = r–1 for 1 < i ≤ t. This happens with probability (1−r-1)r1-t.
Then, if ak+t+1 ≠ r–1, the next t digits are all determined together.

4

Converting Redundant Representations

C. D. Walter

4. The Average Delay − An Upper Bound.
When output digits are determined they are added to an output buffer, from which any
available digits are output at the rate of one per cycle, the same rate as digits are input. If
the kth output digit is determined by the k+1st input digit and the output buffer is empty,
then it will be output immediately, i.e. one cycle after the corresponding input digit. Thisis the minimal conversion time for a digit, and so its delay will be defined to be 0. So, if
after queueing in the output buffer the kth digit is output on the (k+1+d)th cycle, it isdefined to have a delay of d. We wish to determine the average value of d as a function ofk.
An initial, crude upper bound on the average delay is easy to obtain. On average, an
input of k digits will contain r-1k digits r−1, each of which contributes up to 1 to thedelay. However, there may be a further delay if the k+1st digit is r−1. The average∞

number of consecutive digits r−1 starting at the k+1st is ∑i = 0 ir −i (1−r-–1) = (r−1)-–1.
(The sum is over sequences of length i terminated by a digit other than r−1.) So, overall,
the average delay is at most r-1k + (r−1)-–1. Numerical work soon shows that this is arather poor estimate.

5. An Improved Upper Bound.
Each occurrence of an input digit r−1 leads to an extra delay of up to 1 time unit. The
delay may actually be less, as noted in one of the previous examples. The delay is, in fact,
determined by the maximum string of input digits r−1 from the beginning up to the next
one different from r−1. To see this, it suffices to establish that if the input digit is not r−1
then the output buffer contains d digits where d is the maximum length of any input
sequence of digits r−1. The output buffer length does not change if another digit different
from r−1 is received. Otherwise, if d' consecutive digits r−1 occur and d' ≤ d then thebuffer temporarily decreases in size by d', but is eventually restored to size d. However, if
a new maximal sequence of d' consecutive digits r−1 occurs, so d' > d, then the buffer
empties and is restored with d' digits, all of which then experience a delay of d'.

5

IEE Computers & Digital Techniques, 144 No 4, (July 1997), pp. 219-221.

The main problem with the estimate of the average delay in the last section is that
there are probably many submaximal sequences of consecutive digits r−1 for each ofwhich 1 was unnecessarily added to the estimate.

One way to avoid most of thisunwanted contribution is to force a minimum delay of t, say, on all output. This makes anallowance once for all the subsequences of length t or less, rather than for every
occurrence. In effect the buffer starts with t elements.
So, suppose there is a built-in delay of t between input and output. The kth digit will
be processed at or before a time which is k+t plus the delay caused by digits r−1 lying insubsequences of length greater than t. A subsequence of length l > t will add at most l−t
to the delay. So a single digit in such a sequence will add on average at most (l−t)l-1 tothe delay. The formula for the average delay therefore needs to be re-expressed with asummation over sequences of length l for each digit position.
Consider the probability that the κth input digit lies in a sequence of l consecutive(r−1)s, of which exactly p occur at or before position κ. We assume p ≤ κ and p ≤ l sinceotherwise the parameters are impossible. For l = 0 and p = 0 the probability is just 1−r-1.
For l > 0 and fixed p < κ the probability is (1−r-1)2r-l since both ends of the subsequencemust have a digit other than r−1. Otherwise, i.e. for l > 0 and p = κ, all the first l digits
are r−1, but the l+1st is not, so the probability is (1−r-1)r-l. Summing over the possible
values of p, namely 0 ≤ p ≤ min{κ,l}, we find that the probability of the κth digit lying ina string of exactly l consecutive digits r−1 is 1−r-1 for l = 0, l(1−r-1)2r-l for 0 < l < κ and(κ−1)(1−r-1)2r-l + (1−r-1)r-l for κ ≤ l. As a check, summing these over all l ≥ 0 gives
probability 1.
The contribution to the average delay given by the first k digits is the sum overappropriate κ and l of the product of the probability of the case (κ,l) and the bound on the
delay which it might cause. This yields:∑κ =1 (∑l =t +1
kmax{κ −1,t }

∞

(

)

(l − t )(1 − r − 1 ) 2 r − l + ∑l = max{κ ,t +1} ( l −l t ) (κ − 1)(1 − r − 1 ) 2 + (1 − r − 1 ) r − l6)Converting Redundant Representations

C. D. Walter

For the contribution of the k+1st and subsequent digits, we sum over the lengths l of thesubsequences of digits r–1 to which the k+1st digit might belong and the possible sizes pof the part which starts at position k+1. The delay to add for each case is probability of
the case times the length of the sequence starting there times the delay per sequence digit.
This yields:kl∑l = t +1 ∑ p = 0 p(l − t )l − 1 (1 − r − 1 ) 2 r −l+∑l = k +1 ((l − k )(1 − r − 1 ) + ∑ p=l − k +1 p(1 − r − 1 ) 2 )(l − t )l − 1r −ll∞When k = t = 0 the sum of the two expressions is easily (r−1)−1. Using induction we
obtain {kr−1 + (r−1)−1}r−t for the sum when k = t. Then, with this as the base case,induction over k will establish the sum as {kr−1 + (r−1)−1}r−t whenever 0 ≤ t ≤ k. So,

LEMMA Under the above hypotheses and a built-in delay of t < k, the average
delay for the kth digit is less thant + { kr−1 + (r−1)−1 }r−t .

Observe that for t = 0 this coincides with our initial, rough bound. Taking t = logrk now
gives our main conclusion, namely:

THEOREMWith the above assumptions about digit probabilities andindependence for the input, an on-line converter from redundant to standard baser representations produces an average delay of at most logrk + r−1 + (r−1)−1k−1
between inputting and outputting the kth digits.
A marginally better choice of t can be obtained for known values of r and k by putting
t = logrk − s in the lemma, and differentiating the formula for the delay with respect to s inorder to obtain the minimum. The theorem, with s = 0, provides a reasonable choice forsmall k, whilst taking s = 1 works well for medium sized k (as in Table 1). Letting k tend
to infinity, the best choice is s = 1 + logrlogre , and it yields the following corollary:

COROLLARY. With the above notation and hypotheses, for sufficiently large k
the average delay in establishing the kth non-redundant digit is less than logrk.

7

IEE Computers & Digital Techniques, 144 No 4, (July 1997), pp. 219-221.

6. Computational Results.
Despite the apparently reckless counting above of extra delays for digits which were
not in a maximal subsequence, computational results suggest that the above formulae are
fairly accurate. Indeed, from Table 1 the difference between the actual delays in adjacentcolumns tends to 1, as the formula suggests. So the most significant term does indeed
seem to be logrk with coefficient 1, and the relative error between the true delay and ourbound slowly decreases as k increases.

k
Actual
delay
Lemma
bound

20

21

22

23

24

25

26

27

28

29

210

1.500 1.875 2.383 3.014 3.759 4.592 5.485 6.420 7.382 8.360 9.348
1.500 2.000 2.500 3.250 4.125 5.062 6.031 7.015 8.008 9.004 10.002
Table 1. Delays for r = 2.

Exact computation of the true delay is not trivial because of the large number of
numbers involved. The most efficient manner found was the following. For each k, thenumber of representations of length k with a maximal subsequence of digits r−1 withlength l and an end subsequence of such digits with length l' were tabulated. The results
were used iteratively to compute the figures for k+1 from those of k, with a very careful
tabulation order to minimise disk accesses and make the accesses sequential. The table
was computed in this way and similar results were also obtained for some small r > 2.

7. Conclusion.
The aim of this paper has been to prove the theorem of section 5, which shows that inconverting numbers from a redundant representation to a non-redundant one in a mostsignificant digit first order, the average delay due to waiting for carries to propagate isbounded essentially by the logarithm of its length. This result depends on several realistic
suppositions about the way the digits are distributed. Computational results indicate thatthe bound is close to being the least upper bound.

8

Converting Redundant Representations

C. D. Walter

References.
[1]

A. Blum & P. Chalasani, An On-Line Algorithm for Improving Performance inNavigation, Proc. 34th Symp. on Foundations of Computer Science, 1993, pp. 2-11.

[2]

M. D. Ercegovac & T. Lang, On-Line Arithmetic: A Design Methodology andApplications in Digital Signal Processing, VLSI Signal Processing 3, R.W. Broderson &H.S. Moscovitz (Eds.), IEEE Press, N.Y. 1988, pp. 252-263.

[3]

M. D. Ercegovac & T. Lang, On-the-fly Rounding for Division and Square Root,

Proc 9th Symp. on Computer Arith., Santa Monica, Ca, USA, 6th-9th Sept 1989, IEEE
Press, 1989, pp. 169-173.

[4]

M. D. Ercegovac & T. Lang, On-the-fly Conversion of Redundant into

Conventional Representations, IEEE Trans on Computers, Vol. C-36, No. 7 (July 1987),
pp. 895-897.

[5]

T. Stouraitis & C. Chen, Fast digit-parallel conversion of signed digit into

conventional representations, Electronic Letters, Vol. 27, No. 11 (May 1991), pp. 964965.

23rd September 1996

9