Non-adjacent form

The non-adjacent form (NAF) of a number is a unique signed-digit representation. Like the name suggests, adjacent values cannot be non-zero. For example:

(0 1 1 1) = 4 + 2 + 1 = 7

(1 0 −1 1) = 8 − 2 + 1 = 7

(1 −1 1 1) = 8 − 4 + 2 + 1 = 7

(1 0 0 −1) = 8 − 1 = 7

All are valid signed-digit representations of 7, but only the final representation (1 0 0 −1) is in NAF.

Obtaining NAF

There are several algorithms for obtaining the NAF representation of a value given in binary. One such is the modified Booth scheme:

Input: E = (e_{m − 1} e_{m − 2} ··· e₁ e₀)₂

Output: E = (z_m z_{m − 1} ··· z₁ z₀)_NAF

e_m ← 0

e₋₁ ← 0

Find and replace all sequences of 0 1 ··· 1 0 (with k repeated 1's) with 1 0 ··· 0 −1 0 (with k − 1 repeated 0's)

i ← 0

while i < m do

if e_{i + 1} · e_i ≠ 0 then

z_i ← 2 &middot e_{i + 1} + e_i

z_{i + 1} ← 0

i ← i + 2

else

z_i ← e_i

i ← i + 1

return z

Another way, one that doesn't have to search for and count strings of 1's, is a method using repeated division:

Input: E = (0 e_{m − 1} e_{m − 2} ··· e₁ e₀)₂

Output: E = (z_m z_{m − 1} ··· z₁ z₀)_NAF

i ← 0

while E > 0 do

if E is odd then

z_i ← 2 − (E mod 4)

else

z_i ← 0

E ← (E − z_i)/2

i ← i + 1

return z

Properties

NAF assures a unique representation of an integer, but the main benefit of it is that the Hamming weight of the value will be minimal. For regular binary representations of values, half of all bits will be non-zero, on average, but with NAF this drops to only one-third of all bits.

Because every non-zero value has to be adjacent to two 0's, the NAF representation can be implemented such that it only takes a maximum of m + 1 bits for a value that would normally be represented in binary with m bits.

The non-zero bits in NAF will toggle between 1 and −1 when examined from left-to-right or right-to-left — that is, if a bit of 1 is encountered, the next non-zero bits on the left and right will be −1 and vice versa.

The properties of NAF make it useful in hardware implementations, especially those in cryptography.