非隣接形式

非隣接形式( NAF )の数値は、ゼロ以外の値が隣接できない一意の符号付き数字表現です。例:

(0 1 1 1) ₂ = 4 + 2 + 1 = 7

(1 0 −1 1) ₂ = 8 − 2 + 1 = 7

(1 −1 1 1) ₂ = 8 − 4 + 2 + 1 = 7

（１００ −１）_２＝８−１＝７

これらはすべて7の有効な符号付き数字表現ですが、最後の表現(1 0 0 −1) ₂のみが非隣接形式です。

非隣接形式は、「標準符号付き数字」表現とも呼ばれます。

プロパティ

NAFは整数の一意な表現を保証しますが、その主な利点は値のハミング重みが最小限になることです。通常の値の2進表現では、平均して全ビットの半分が非ゼロになりますが、NAFを使用すると、これは全桁の3分の1にまで減少します。これにより、ハードワイヤードデジタル信号処理における加算/減算ネットワーク（定数による乗算など）の効率的な実装が可能になります。^[1]

明らかに、桁の最大半分はゼロ以外であり、これがブース符号化と同様に初期の乗算アルゴリズムを高速化するためにGW Reitweisner ^[2]によって導入された理由です。

すべての非ゼロの数字は 2 つの 0 に隣接している必要があるため、NAF 表現は、通常はmビットのバイナリで表現される値に対して最大m + 1 ビットのみを使用するように実装できます。

NAF の特性により、さまざまなアルゴリズム、特に暗号化アルゴリズムで役立ちます。たとえば、指数計算を実行するために必要な乗算回数を減らすことができます。の二乗による指数計算アルゴリズムでは、乗算回数は非ゼロビットの数によって決まります。ここで指数が NAF 形式で指定されている場合、数字の値 1 は底による乗算を意味し、数字の値 -1 はその逆数による乗算を意味します。

連続する 1 を避ける整数をエンコードする他の方法には、ブースエンコードとフィボナッチエンコードがあります。

NAFへの変換

2進数で与えられた値のNAF表現を得るためのアルゴリズムはいくつかあります。その1つは、繰り返し除算を使用する次の方法です。これは、結果の商が2で割り切れるように非ゼロの係数を選択し、次の係数がゼロになるようにすることで機能します。^[3]

   入力     E = ( e _{m −1} e _{m −2} ··· e ₁ e ₀ ) ₂
   出力     Z = ( z _m  z _{m −1} ··· z ₁ z ₀ ) _NAF
   i ← 0E > 0
   の場合Eが奇数の
           
       場合、 z _i ← 2 − ( E mod 4)
            E ← E − z _i
       それ以外
           z _i ← 0
        E ← E /2
        i ← i + 1zを
   返す

より高速な方法はProdinger ^[4]によって提案されており、xは入力、npは正のビットの文字列、nmは負のビットの文字列である。

   入力   x
   出力  np , nm 
   xh = x >> 1;
    x3 = x + xh ;
    c = xh ^ x3 ;
    np = x3 & c ;
    nm = xh & c ;

これは、たとえば A184616 で使用されます。

外部リンク

標準符号付き数字表現の紹介
Coleman, JO; Yurdakul, A. (2001 年 3 月 21 ～ 23 日) 。標準符号付き数字システムにおける分数。情報科学とシステムに関する会議。ジョンズホプキンス大学。OCLC 48052559。

参考文献

^ Hewlitt, RM (2000). FIR デジタルフィルタの標準符号付き数字表現. 信号処理システム, 2000. SiPS 2000. 2000 IEEE ワークショップ. pp. 416–426. doi :10.1109/SIPS.2000.886740. ISBN 978-0-7803-6488-2. S2CID 122082511。
^ Reitwiesner, George W. (1960). 「バイナリ演算」.コンピュータの進歩. 1 : 231–308. doi :10.1016/S0065-2458(08)60610-5. ISBN 9780120121014。
^ Hankerson, D.; Menezes, A.; Vanstone, SA (2004).楕円曲線暗号ガイド. Springer. p. 98. ISBN 978-0-387-21846-5。
^ Prodinger, Helmut. 「数字が -1、0、1 の整数のバイナリ表現について」(PDF)。整数。2021 年6 月 25 日閲覧。

[1] Hewlitt, RM (2000). FIR デジタルフィルタの標準符号付き数字表現. 信号処理システム, 2000. SiPS 2000. 2000 IEEE ワークショップ. pp. 416–426. doi :10.1109/SIPS.2000.886740. ISBN 978-0-7803-6488-2. S2CID 122082511。

[Reitweisner-2] Reitwiesner, George W. (1960). 「バイナリ演算」.コンピュータの進歩. 1 : 231–308. doi :10.1016/S0065-2458(08)60610-5. ISBN 9780120121014。

[gecc-3] Hankerson, D.; Menezes, A.; Vanstone, SA (2004).楕円曲線暗号ガイド. Springer. p. 98. ISBN 978-0-387-21846-5。

[4] Prodinger, Helmut. 「数字が -1、0、1 の整数のバイナリ表現について」(PDF)。整数。2021 年6 月 25 日閲覧。