|
|
|
|
|
Non-adjacent FormThe 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 = (em − 1 em − 2 ··· e1 e0)2
- Output: E = (zm zm − 1 ··· z1 z0)NAF
- em ← 0
- e−1 ← 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 ei + 1 · ei ≠ 0 then
-
-
- zi ← 2 · ei + 1 + ei
-
-
- zi + 1 ← 0
-
-
- i ← i + 2
-
- else
-
-
- zi ← ei
-
-
- 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 em − 1 em − 2 ··· e1 e0)2
- Output: E = (zm zm − 1 ··· z1 z0)NAF
- i ← 0
- while E > 0 do
-
- if E is odd then
-
-
- zi ← 2 − (E mod 4)
-
- else
-
-
- zi ← 0
-
- E ← (E − zi)/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.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|