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:
Todas son representaciones válidas de dígitos con signo de 7, pero sólo la representación final, (1 0 0 −1) 2 , está en forma no adyacente.
La forma no adyacente también se conoce como representación de "dígito canónico con signo".
NAF asegura una representación única de un número entero , pero el principal beneficio es que el peso Hamming del valor será mínimo. Para las 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. Esto conduce a implementaciones eficientes de redes de suma/resta (por ejemplo, multiplicación por una constante) en el procesamiento de señales digitales cableadas . [1]
Obviamente, como máximo la mitad de los dígitos son distintos de cero, razón por la cual fue introducido por GW Reitweisner [2] para acelerar los primeros algoritmos de multiplicación, muy parecido a la codificación 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 modo que solo se necesite 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 exponenciación . En el algoritmo de 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 números enteros que evitan unos consecutivos incluyen la codificación Booth y la codificación Fibonacci .
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. [3]
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 E > 0 hacer si E es impar entonces z i ← 2 − ( E mod 4) E ← E − z i demás z yo ← 0 mi ← mi /2 yo ← yo + 1 regresar z
Prodinger [4] proporciona una forma más rápida donde x es la entrada, np la cadena de bits positivos y nm la cadena de bits negativos:
Entrada x Salida np , nm xh = x >> 1; x3 = x + xh ; c = xh ^ x3 ; np = x3 & c ; nm = xh & c ;
que se utiliza, por ejemplo, en A184616.