Forma no adjacent

La forma no adjacent (FNA ; en anglès, Non-adjacent form, NAF) d'un nombre és una representació de dígit signat única. Com el nom suggereix, el criteri consisteix en el fet que dins de l'expressió del nombre no s'admeten valors no nuls consecutius. Per exemple:

(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

Totes aquestes expressions són representacions vàlides de dígit signat de 7 en base 2, però només la representació final, (1 0 0 −1)₂, compleix el criteri FNA.

Propietats

La FNA assegura la representació única d'un nombre enter donat, però el benefici principal que es deriva d'aquesta expressió és que el pes de Hamming (nombre de xifres diferents de zero en l'expressió) serà mínim. Per representacions binàries regulars de valors, de mitjana la meitat de tots els bits seran no nuls, però amb la FNA aquesta mitjana es redueix a un terç de tots els dígits.

Evidentment, almenys la meitat dels dígits no solen ser zero, raó per la qual G.W. Reitweisner va utilitzar aquest concepte en els primers dissenys d'algorismes de multiplicació de nombres binaris, com l'algorisme de Booth.^[1]

Com que cada dígit ha de ser adjacent a dos zeros, la representació de la FNA pot ser implementada de manera que només ocupi un màxim addicional de m + 1 bits per a un valor que normalment seria representat en binari amb m bits.

Les propietats de la FNA la fan útil en diversos algorismes, especialment en criptografia; per exemple, per reduir el nombre de multiplicacions necessàries per desenvolupar una potenciació. En l'algorisme d'exponenciació binària, el nombre de multiplicacions depèn del nombre de bits no nuls. Si l'exponent aquí està donat en forma FNA, un valor de dígit 1 implica una multiplicació per la base, i un valor de dígit -1 pel seu recíproc.

Altres mètodes de codificar nombres enters que eviten uns consecutius inclouen el codificat de Booth i el codificat de Fibonacci.

Conversió a la FNA

Hi ha diversos algoritmes per obtenir la FNA d'un valor donat en binari. El mètode següent utilitza la divisió repetida. Treballa escollint coeficients no nuls, de manera que el quocient resultant és divisible per 2 i per tant el coeficient següent és un zero.^[2]

Input E = (e_{m − 1} e_{m − 2} ··· e₁ e₀)₂
Output Z = (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

Referències

↑ Reitwiesner, George W. Binary Arithmetic (en anglès). Advances in Computers, 1960.
↑ Hankerson, D.; Menezes, A.; Vanstone, S.A.. Guide to Elliptic Curve Cryptography (en anglès). Springer-Verlag, 2004, p. 98.

[Reitweisner-1] Reitwiesner, George W. Binary Arithmetic (en anglès). Advances in Computers, 1960.

[gecc-2] Hankerson, D.; Menezes, A.; Vanstone, S.A.. Guide to Elliptic Curve Cryptography (en anglès). Springer-Verlag, 2004, p. 98.

[1]

[2]