La rappresentazione NAF (dall'inglese non-adjacent form - rappresentazione non adiacente) di un numero è una rappresentazione binaria unica di cifre con segno, in cui i valori diversi da zero non possono essere adiacenti. Ad esempio:

(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

Tutte sono rappresentazioni valide di 7 in cifre con segno, ma solo l'ultima rappresentazione, (1 0 0 −1)2 è in forma non adiacente.

Proprietà NAF assicura una rappresentazione unica di un numero intero, ma il suo principale vantaggio è che il peso di Hamming del valore sarà minimo. Nella rappresentazione binaria dei numeri, in media la metà di tutti i bit sarà diversa da zero, ma con la rappresentazione NAF questo valore scende mediamente ad un terzo di tutte le cifre. Ciò porta a implementazioni efficienti di circuiti di addizione/sottrazione impiegati nell'elaborazione di segnali digitali.

Ovviamente, al massimo la metà delle cifre è diversa da zero, che è il motivo per cui è stata introdotta da G.W. Reitweisner per velocizzare i primi algoritmi di moltiplicazione, in modo simile all'algoritmo di Booth.

Poiché ogni cifra diversa da zero deve essere adiacente a due 0, la rappresentazione NAF può essere implementata in modo tale da richiedere al massimo m + 1 bit per un valore che normalmente sarebbe rappresentato in binario con m bit.

Le proprietà di NAF lo rendono utile in vari algoritmi, in particolare nell'ambito della crittografia; ad esempio, per ridurre il numero di moltiplicazioni necessarie per eseguire il calcolo di una potenza. Nell'algoritmo dell'elevamento a potenza per quadratura, il numero di moltiplicazioni dipende dal numero di bit diversi da zero. Se l'esponente viene dato in rappresentazione NAF, il valore 1 implica una moltiplicazione per la base, e il valore −1 per il suo reciproco.

Altre modalità di codifica degli interi che evitano sequenze consecutive di 1 includono l'algoritmo di Booth e la codifica di Fibonacci.

Note

Categoria:Teoria delle rappresentazioni