A signed digit representation of an integer n in radix r is a sequence
of digits a = (..., a2, a1, a0) with a(i) is-an-element-of {0, +/- 1,
..., +/-(r - 1)} such that n = SIGMA(i=0)infinity a(i)r(i). Redundant
representations of this form have been used successfully in many arit
hmetic applications, including the exponentiation problem in a group.
Increased efficiency is usually derived from the possibility of having
fewer nonzero digits than the standard radix r representation. Let K(
r) (n) denote the minimal Hamming weight over all signed digit represe
ntations of n in radix r. In this correspondence, we give an on-line a
lgorithm for computing a canonical signed digit representation of mini
mal Hamming weight for any integer n. Using combinatorial techniques,
we compute the probability distribution Pr [K(r) = h], where K(r) is t
aken to be a random variable on the uniform probability space of k-dig
it integers. Also, using a Markov chain analysis we show that E(K(r))
approximately (r - 1)k/(r + 1) as k --> infinity.