La forma no adyacente ( NAF ) de un número es una representación única de dígitos con signo , en la que los valores distintos de cero no pueden ser adyacentes. 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 son representaciones válidas de dígitos con signo de 7, pero solo la representación final, (1 0 0 −1) 2 , está en forma no adyacente.
Propiedades
NAF asegura una representación única de un número entero , pero el principal beneficio es que el peso de Hamming del valor será mínimo. Para representaciones binarias regulares de valores, la mitad de todos los bits serán distintos de cero, en promedio, pero con NAF esto se reduce a solo un tercio de todos los dígitos.
Obviamente, como mucho la mitad de los dígitos son distintos de cero, razón por la cual fue introducido por GW Reitweisner [1] para acelerar los primeros algoritmos de multiplicación, al igual que la codificación de Booth .
Debido a que cada dígito distinto de cero tiene que ser adyacente a dos ceros, la representación NAF se puede implementar de manera que solo tome un máximo de m + 1 bits para un valor que normalmente se representaría en binario con m bits.
Las propiedades de NAF lo hacen útil en varios algoritmos, especialmente algunos en criptografía ; por ejemplo, para reducir el número de multiplicaciones necesarias para realizar una potenciación . En el algoritmo, exponenciación al cuadrado , el número de multiplicaciones depende del número de bits distintos de cero. Si el exponente aquí se da en forma NAF, un valor de dígito 1 implica una multiplicación por la base y un valor de dígito -1 por su recíproco.
Otras formas de codificar enteros que evitan unos consecutivos incluyen la codificación de Booth y la codificación de Fibonacci .
Conversión a NAF
Existen varios algoritmos para obtener la representación NAF de un valor dado en binario. Uno de ellos es el siguiente método que utiliza división repetida; funciona eligiendo coeficientes distintos de cero de modo que el cociente resultante sea divisible por 2 y, por tanto, el siguiente coeficiente sea cero. [2]
Entrada E = ( e m −1 e m −2 ··· e 1 e 0 ) 2 Salida Z = ( z m z m −1 ··· z 1 z 0 ) NAF i ← 0 mientras que E > 0 lo hace si E es impar, entonces z i ← 2 - ( E mod 4) E ← E - z i demás z i ← 0 E ← E / 2 i ← i + 1 volver z