SIGNED-DIGIT REPRESENTATIONS OF MINIMAL HAMMING WEIGHT

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.