A Simple Left-to-Right Algorithm for Minimal Weight Signed Radix-r Representations

Author

Muir, James A.

Author_Institution

Sch. of Comput. Sci., Carleton Univ., Ottawa, Ont.

Volume

53

Issue

3

fYear

2007

fDate

3/1/2007 12:00:00 AM

Firstpage

1234

Lastpage

1241

Abstract

We present a simple algorithm for computing the arithmetic weight of an integer with respect to a given radix rges2. The arithmetic weight of n is the minimum number of nonzero digits in any signed radix-r representation of n. This algorithm leads to a new family of minimal weight signed radix-r representations which can be constructed using a left-to-right on-line algorithm. These representations are different from the ones previously discovered by Joye and Yen. The idea behind our algorithm is that of choosing closest elements which was introduced by Muir and Stinson. Our results have applications in coding theory and in the efficient implementation of public-key cryptography

Keywords

digital arithmetic; coding theory; left-to-right on-line algorithm; minimal weight signed radix-r representation; public-key cryptography; Arithmetic; Codes; Elliptic curve cryptography; Galois fields; Gaussian processes; Lattices; Mathematics; Polynomials; Public key cryptography; Computer arithmetic; elliptic curve cryptography; left-to-right recoding; minimal weight representations; redundant representations; signed radix-$r$ representations;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2006.890775

Filename

4106133