The non-adjacent form (NAF) of a number is a unique
signed-digit representation
In mathematical notation for numbers, a signed-digit representation is a positional numeral system with a set of signed digits used to encode the integers.
Signed-digit representation can be used to accomplish fast addition of integers because ...
, in which non-zero values cannot be adjacent. For example:
:(0 1 1 1)
2 = 4 + 2 + 1 = 7
:(1 0 −1 1)
2 = 8 − 2 + 1 = 7
:(1 −1 1 1)
2 = 8 − 4 + 2 + 1 = 7
:(1 0 0 −1)
2 = 8 − 1 = 7
All are valid signed-digit representations of 7, but only the final representation, (1 0 0 −1), is in non-adjacent form.
The non-adjacent form is also known as "canonical signed digit" representation.
Properties
NAF assures a unique representation of an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
, but the main benefit of it is that the
Hamming weight
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string o ...
of the value will be minimal. For regular
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
representations of values, half of all
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented a ...
s will be non-zero, on average, but with NAF this drops to only one-third of all digits. This leads to efficient implementations of add/subtract networks (e.g. multiplication by a constant) in hardwired
digital signal processing
Digital signal processing (DSP) is the use of digital processing, such as by computers or more specialized digital signal processors, to perform a wide variety of signal processing operations. The digital signals processed in this manner ar ...
.
Obviously, at most half of the digits are non-zero, which was the reason it was introduced by G.W. Reitweisner
for speeding up early multiplication algorithms, much like