Forma no adyacente
La forma no adyacente (FNA -NAF en inglés-) de un número es una representación de dígito signado única. Como el nombre sugiere, el criterio consiste en que dentro de la expresión del número, no se admiten valores no nulos consecutivos. Por ejemplo:
(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
Todas estas expresiones son representaciones válidas de dígito signado de 7 en base 2, pero solo la representación final, (1 0 0 −1)2, cumple el criterio FNA.
Propiedades
La FNA asegura la representación única de un entero dado, pero el beneficio principal que se deriva de esta expresión es que el peso de Hamming (número de cifras distintas de cero en la expresión) será mínimo. Para representaciones binarias regulares de valores, en promedio la mitad de todos los bits serán no nulos, pero con FNA este promedio se reduce a un tercio de todos los dígitos.
Evidentemente, al menos la mitad de los dígitos no suelen ser cero, razón por la cual G.W. Reitweisner[1] utilizó este concepto en los primeros diseños de algoritmos de multiplicación binarios, como el algoritmo de Booth.
Debido a que cada dígito tiene que ser adyacente a dos ceros, la representación del FNA puede ser implementada de forma que solo ocupe un máximo adicional de m + 1 bits para un valor que normalmente sería representado en binario con m bits.
Las propiedades de la FNA la hacen útil en varios algoritmos, especialmente en criptografía. Por ejemplo, para reducir el número de multiplicaciones necesarios para desarrollar una exponenciación. En el algoritmo "exponenciación binaria", el número de multiplicaciones depende del número de bits no nulos. Si el exponente aquí está dado en forma FNA, un valor de dígito 1 implica una multiplicación por la base, y un valor de dígito −1 por su recíproco.
Otros métodos de codificar enteros que evitan unos consecutivos incluyen el codificado de Booth y el codificado de Fibonacci.
Convirtiendo a FNA
Hay varios algoritmos para obtener el FNA de un valor dado en binario. El método siguiente utiliza la división repetida. Trabaja escogiendo coeficientes no nulos, de forma que el cociente resultante es divisible por 2 y por lo tanto el coeficiente siguiente es un cero.[2]
Input E = (em − 1 em − 2 ··· e1 e0)2 Output Z = (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
Véase también
Referencias
- George W. Reitwiesner, Binary Arithmetic, Advances in Computers, 1960.
- D. Hankerson, A. Menezes, and S.A. Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004. p. 98.