非隣接形式

非隣接形式（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

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

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

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

プロパティ

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

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

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

NAFの特性は、様々なアルゴリズム、特に暗号アルゴリズムにおいて有用です。例えば、べき乗演算に必要な乗算回数を削減できます。平方乗法によるべき乗演算アルゴリズムでは、乗算回数は非ゼロビットの数に依存します。ここで指数がNAF形式で与えられている場合、桁値1は底による乗算を意味し、桁値-1はその逆数による乗算を意味します。

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

NAFへの変換

2進数で与えられた値のNAF表現を得るためのアルゴリズムはいくつかあります。その一つが、繰り返し除算を用いた以下の方法です。この方法では、結果として得られる商が2で割り切れるように、つまり次の係数が0になるように、非ゼロの係数を選択します。^[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。
^ ライトウィースナー, ジョージ・W. (1960). 「二進法算術」.コンピュータの進歩. 1 : 231–308 . doi :10.1016/S0065-2458(08)60610-5. ISBN 9780120121014。 {{cite journal}}: ISBN / Date incompatibility (help)
^ Hankerson, D.; Menezes, A.; Vanstone, SA (2004).楕円曲線暗号ガイド. Springer. p. 98. ISBN 978-0-387-21846-5。
^ Prodinger, Helmut. 「-1, 0, 1の数字を持つ整数の2進表現について」(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] ライトウィースナー, ジョージ・W. (1960). 「二進法算術」.コンピュータの進歩. 1 : 231–308 . doi :10.1016/S0065-2458(08)60610-5. ISBN 9780120121014。 {{cite journal}}: ISBN / Date incompatibility (help)

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

[4] Prodinger, Helmut. 「-1, 0, 1の数字を持つ整数の2進表現について」(PDF) .整数. 2021年6月25日閲覧。