Representations found by the greedy algorithm

[Edwin Clark]

There is also something similiar called the non-adjacent form
(NAF) of an integer--which is a representation of an integer
to base 2, with "bits" 1,-1 and 0. Such a representation
is unique if no two adjacent "bits" are nonzero. Years ago Joe
Liang and I wrote some papers on error-correcting codes
for arithmetic in which this idea appears. The number
of non-zero "bits" in a NAF is an analogue of the Hamming
weight of a binary number.  There are also generalizations
to bases r > 2, but not quite as simple. Some of our work
was covered in van Lint's hardback Springer yellow book on
coding theory. 

So long ago I can barely recall what it was about. 

A google search on "non-adjacent form" will
no doubt lead to better references. 

We also got a similar form for some bases for the Gaussian
integers and other Euclidean rings. But I doubt if any of
that is related to the current discussion.



--Edwin