Nesousedící forma - Non-adjacent form
| Číselné soustavy |
|---|
| Hindu-arabská číselná soustava |
| východní Asiat |
| evropský |
| americký |
| Abecední |
| Bývalý |
| Poziční systémy podle základna |
| Nestandardní poziční číselné systémy |
| Seznam číselných soustav |
The nesousedící forma (NAF) čísla je jedinečný podepsané číslice, ve kterém nenulové hodnoty nemohou sousedit. Například:
- (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
Všechna jsou platná reprezentace se znaménkem 7, ale pouze konečná reprezentace, (1 0 0 −1)2, je v nesousedící formě.
Vlastnosti
NAF zajišťuje jedinečné zastoupení celé číslo, ale hlavní výhodou je, že Hammingova hmotnost hodnoty bude minimální. Pro pravidelné binární reprezentace hodnot, polovina všech bity bude v průměru nenulová, ale u NAF to klesne pouze na jednu třetinu všech číslic.
Je zřejmé, že nanejvýš polovina číslic je nenulová, což byl důvod, proč ji zavedl G.W. Reitweisner [1] pro urychlení časných multiplikačních algoritmů, podobně Kódování stánku.
Protože každá nenulová číslice musí sousedit se dvěma 0 s, lze reprezentaci NAF implementovat tak, že trvá maximálně m + 1 bit pro hodnotu, která by normálně byla reprezentována v binárním formátu s m bity.
Díky vlastnostem NAF je užitečný v různých algoritmech, zejména v některých kryptografie; např. pro snížení počtu násobení potřebných pro provedení umocňování. V algoritmu umocňování druhou mocninou, počet násobení závisí na počtu nenulových bitů. Je-li zde exponent uveden ve formě NAF, znamená hodnota číslice 1 násobení základnou a hodnota číslice −1 jeho převrácenou hodnotou.
Mezi další způsoby kódování celých čísel, která se vyhýbají po sobě jdoucím 1 s, patří Kódování stánku a Fibonacciho kódování.
Převod na NAF
Existuje několik algoritmů pro získání NAF reprezentace hodnoty dané v binární podobě. Jednou takovou je následující metoda využívající opakované dělení; funguje to tak, že vybereme nenulové koeficienty tak, že výsledný kvocient je dělitelný 2 a tedy další koeficient nula.[2]
Vstup E = (Em−1 Em−2 ··· E1 E0)2 Výstup Z = (zm zm−1 ··· z1 z0)NAF i ← 0 zatímco E > 0 udělat, pokud E je potom zvláštní zi ← 2 − (E mod 4) E ← E − zi jiný zi ← 0 E ← E/2 i ← i + 1 návrat z