ANコード

ANコードは、算術アプリケーションで使用される誤り訂正コードです。 ^[1]算術コードは、電子機器の信頼性が低かった時代に、コンピュータプロセッサで算術演算の精度を確保するために一般的に使用されていました。算術コードは、プロセッサがエラーを検出して訂正するのに役立ちます。これらのコードがなければ、エラーが検出されないため、プロセッサの信頼性は低くなります。ANコードは、整数にちなんで名付けられた算術コードであり、コードワードのエンコードとデコードに使用されます。 ${\displaystyle A}$ ${\displaystyle N}$

これらのコードは、ハミング重みとハミング距離ではなく、算術重みを用いてコードワード間の算術距離を最大化する点で、他のほとんどのコードとは異なります。2つのワード間の算術距離は、算術演算を実行する際に発生するエラーの数を測る指標です。算術演算における1つのエラーが、受信した答えと正しい答えの間のハミング距離を大きくする可能性があるため、算術距離の使用は不可欠です。

算術重みと距離

基数における整数の算術重みは次のように定義される。 ${\displaystyle x}$ ${\displaystyle r}$

${\displaystyle w(x)=\min\{t|x=\sum _{i=1}^{t}a_{i}r^{n(i)}\}}$

ここで、< 、、です。 ^[2]単語の算術距離は、ハミング重みによって上限が決まります。これは、任意の整数を の標準多項式形式で表すことができるためです。ここで、は整数の桁です。 のすべての項を削除すると、ハミング重みに等しい がシミュレートされます。 は負になることが許されているため、算術重みは通常ハミング重みよりも小さくなります。たとえば、2 進数の整数のハミング重みは です。 であるため、これは算術重みの簡単な上限です。ただし、 は負になる可能性があるため、 と書くことができ、算術重みは に等しくなります。 ${\displaystyle |{a_{i}}|}$ ${\displaystyle r}$ ${\displaystyle n(i)\geq 0}$ ${\displaystyle r,n(i)\in \mathbb {Z} }$ ${\displaystyle x=\sum _{i=1}^{n}b_{i}r^{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle b_{i}=0}$ ${\displaystyle t}$ ${\displaystyle a_{i}}$ ${\displaystyle x=29}$ ${\displaystyle 11101}$ ${\displaystyle 4}$ ${\displaystyle x=2^{0}+2^{2}+2^{3}+2^{4}}$ ${\displaystyle a_{i}}$ ${\displaystyle x=2^{5}-2^{1}-2^{0}}$ ${\displaystyle 3}$

2つの整数間の算術距離は次のように定義される。

${\displaystyle d(x,y)=w(x-y)}$

これは算術符号を解析する際に使用される主要な指標の1つです。 ^{[3] [4]}

ANコード

ANコードは整数とで定義され、からまでの整数をエンコードするために使用されます。 ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle 0}$ ${\displaystyle B-1}$

${\displaystyle C=\{AN|N\in \mathbb {Z} ,0\leq N}$< ${\displaystyle B\}}$

の各選択によって異なるコードが生成されますが、 はコードの距離における有用な特性を確保するための制限因子として機能します。が大きすぎると、算術重みが非常に小さいコードワードがコードに入り、コード全体の距離が悪化する可能性があります。 これらのコードを使用するには、2 つの整数に対して算術演算を実行する前に、各整数に を掛けます。 コードワードに対する演算の結果を とします。 が適切にデコードされるためには、 も から の間にある必要があることに注意してください。デコードするには、 を単に除算します。が の因数でない場合は、少なくとも 1 つのエラーが発生しており、 からの算術距離が最小のコードワードが最適な解になります。 ハミング距離を使用するコードと同様に、AN コードは 個のエラーまで訂正できます。ここで はコードの距離です。 ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle 0}$ ${\displaystyle B-1}$ ${\displaystyle R/A}$ ${\displaystyle A}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle \lfloor {\frac {d-1}{2}}\rfloor }$ ${\displaystyle d}$

たとえば、 を持つ AN コードでは、とを加算する操作は、両方のオペランドをエンコードすることから始まります。この結果、操作 になります。次に、解を求めるために、 を割ります。 >である限り、これはコードの下で可能な操作になります。 および となるようなオペランドの 2 進表現のそれぞれにエラーが発生したと仮定すると、になります。 であるため、受信したワードと正しい解の間のハミング重みは、エラー数だけ後になることに注意してください。算術重みを計算するには、 を取ります。これはまたはとして表すことができます。どちらの場合も、算術距離は、発生したエラーの数であるため、予想どおりになります。このエラーを修正するには、算術距離の観点から受信したワードに最も近いコードワードを計算するアルゴリズムが使用されます。アルゴリズムの詳細については説明しません。 ${\displaystyle A=3}$ ${\displaystyle 15}$ ${\displaystyle 16}$ ${\displaystyle R=45+48=93}$ ${\displaystyle 93/3=31}$ ${\displaystyle B}$ ${\displaystyle 31}$ ${\displaystyle 45=101101\rightarrow 101111}$ ${\displaystyle 48=110000\rightarrow 110001}$ ${\displaystyle R=101111+110001=1100000}$ ${\displaystyle 93=1011101}$ ${\displaystyle 5}$ ${\displaystyle 2}$ ${\displaystyle 1100000-1011101=11}$ ${\displaystyle 11=2^{0}+2^{1}}$ ${\displaystyle 11=2^{2}-2^{0}}$ ${\displaystyle 2}$

コードの距離が小さくなりすぎないようにするために、モジュラーANコードを定義します。モジュラーANコードは、の部分群です。コードは、 の要素を頂点とするグラフで定義されるモジュラー距離で測定されます。2つの頂点とが連結されている場合、その場合のみ、 ${\displaystyle C}$ ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ ${\displaystyle m=AB}$ ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ ${\displaystyle x{\pmod {m}}}$ ${\displaystyle x'{\pmod {m}}}$

${\displaystyle x-x'\equiv \pm c\cdot r^{j}{\pmod {m}}}$

ここで、< < ,である。2つの単語間のモジュラー距離は、グラフ上のそれらのノード間の最短経路の長さである。単語のモジュラー重みは、その単語からの距離が次の値に等しい。 ${\displaystyle c,j\in \mathbb {Z} }$ ${\displaystyle 0}$ ${\displaystyle c}$ ${\displaystyle r}$ ${\displaystyle j\geq 0}$ ${\displaystyle 0}$

${\displaystyle w_{m}(x)=min\{w(y)|y\in \mathbb {Z} ,y\equiv x{\pmod {m}}\}}$

実際には、 の値は、コンピュータの演算処理のほとんどが で実行されるため、コードが境界外になったとしてもコンピュータ自体も境界外になるため、追加のデータ損失が発生しないように選択されるのが一般的です。 を選択すると、他のコードよりも距離が大きくなる傾向があります。 ${\displaystyle m}$ ${\displaystyle m=r^{n}-1}$ ${\displaystyle \mod 2^{n}-1}$ ${\displaystyle m=r^{n}-1}$

モジュラー重み を使用すると、AN コードは巡回コードになります。 ${\displaystyle m=r^{n}-1}$

定義: 巡回 AN コードはのサブグループであるコードです(ただし ) 。 ${\displaystyle C}$ ${\displaystyle [r^{n}-1]}$ ${\displaystyle [r^{n}-1]=\{0,1,2,\dots ,r^{n}-1\}}$

巡回AN符号は環の主イデアルです。整数とが存在し、かつAN符号の定義を満たします。巡回AN符号は巡回符号のサブセットであり、同じ性質を持ちます。 ${\displaystyle [r^{n}-1]}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle AB=r^{n}-1}$ ${\displaystyle A,B}$

マンデルバウム・バローズコード

マンデルバウム・バローズ符号は、D. マンデルバウムと JT バローズによって導入された巡回 AN 符号の一種です。 ^{[5] [6]}これらの符号は、および、 を割り切れない素数を 選択することで作成されます。 は、および となる正の整数とします。例えば、 を選択すると、を底とする において<となるマンデルバウム・バローズ符号が生成されます。 ${\displaystyle B}$ ${\displaystyle r}$ ${\displaystyle \mathbb {Z} /B\mathbb {Z} }$ ${\displaystyle r}$ ${\displaystyle -1}$ ${\displaystyle m=r^{n}-1}$ ${\displaystyle n}$ ${\displaystyle r^{n}\equiv 1{\pmod {B}}}$ ${\displaystyle A=(r^{n}-1)/B}$ ${\displaystyle r=2,B=5,n=4}$ ${\displaystyle A=(r^{n}-1)/B=3}$ ${\displaystyle C=\{3N|N\in \mathbb {Z} ,0\leq N}$ ${\displaystyle 5\}}$ ${\displaystyle 2}$

マンデルバウム・バローズ符号の距離を分析するには、次の定理が必要です。

定理： を生成器 を持つ巡回ANコードとし、 ${\displaystyle C\subset [r^{n}-1]}$ ${\displaystyle A}$

${\displaystyle B=|C|=(r^{n}-1)/A}$

それから、

${\displaystyle \sum _{x\in C}w_{m}(x)=n(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

証明：それぞれが一意の巡回NAF ^[7]表現を持つと仮定する。 ${\displaystyle x\in C}$

${\displaystyle x\equiv \sum _{i=0}^{n-1}c_{i,x}r^{i}{\pmod {r^{n}-1}}}$

およびの要素を持つ行列を定義します。この行列は本質的に 内のすべてのコードワードのリストであり、各列はコードワードです。は巡回的であるため、行列の各列には同じ数のゼロが含まれます。次に を計算します。これはで終わらないコードワードの数を掛けたものです。巡回NAFであるための特性として、の場合に限り、 <となります。<の場合であるため、<となります。この場合、最後のビットがゼロである整数の数は です。これにコードワード内の文字を掛けると、 のコードワードの重みの合計が希望どおりに得られます。 ${\displaystyle n\times B}$ ${\displaystyle c_{i,x}}$ ${\displaystyle 0\leq i\leq n-1}$ ${\displaystyle x\in C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle n|\{x\in C|c_{n-1,x}\neq 0\}|}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle c_{n-1,x}\neq 0}$ ${\displaystyle y\in \mathbb {Z} }$ ${\displaystyle y\equiv x{\pmod {r^{n}-1}},{\frac {m}{r+1}}}$ ${\displaystyle y\leq {\frac {mr}{r+1}}}$ ${\displaystyle x=AN{\pmod {r^{n}-1}}}$ ${\displaystyle 0\leq N}$ ${\displaystyle B}$ ${\displaystyle {\frac {B}{r+1}}}$ ${\displaystyle N\leq {\frac {Br}{r+1}}}$ ${\displaystyle \lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor }$ ${\displaystyle n}$ ${\displaystyle n(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

前回の定理を用いて、マンデルバウム・バローズ符号は等距離（つまり、すべての符号語のペアは同じ距離を持つ）であることを示します。

${\displaystyle {\frac {n}{B-1}}(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

証明： とすると、は で割り切れません。これは、 が存在することを意味します。次に です。これは、すべてのコードワードの重みが と同じであるため、 が等距離であることを証明しています。すべてのコードワードの重みは同じであり、前の定理によりすべてのコードワードの合計重みがわかっているため、コードの距離は、合計重みをコードワードの数（0 を除く）で割ることで求められます。 ${\displaystyle x\in C,x\neq 0}$ ${\displaystyle x=AN{\pmod {r^{n}-1}}}$ ${\displaystyle N}$ ${\displaystyle B}$ ${\displaystyle \exists j(N\equiv \pm r^{j}{\pmod {B}})}$ ${\displaystyle w_{m}(x)=w_{m}(\pm r^{j}A)=w_{m}(A)}$ ${\displaystyle C}$ ${\displaystyle A}$

参照

• エラー検出と訂正
• 前方誤り訂正

参考文献

1. ピーターソン、W. ウェズリー、Jr、EJ ウェルドン（1972年3月15日）。『誤り訂正符号』第2版。MITプレス。ISBN 978-0-262-52731-6。
2. Clark, W.; Liang, J. (1973年11月). 「整数の一般的な基数表現における算術的重みについて（対応）」. IEEE Transactions on Information Theory . 19 (6): 823– 826. doi :10.1109/TIT.1973.1055100.
3. ピーターソン、W. ウェズリー、Jr、EJ ウェルドン（1972年3月15日）。『誤り訂正符号』第2版。MITプレス。ISBN 978-0-262-52731-6。
4. Astola, J. (1986年5月). 「完全算術符号に関する注記（対応）」. IEEE Transactions on Information Theory . 32 (3): 443– 445. doi :10.1109/TIT.1986.1057175.
5. Massey, James L.; García, Oscar N. (1972). 「コンピュータ演算における誤り訂正符号」.情報システム科学の進歩. pp.  273– 326. doi :10.1007/978-1-4615-9053-8_5. ISBN 978-1-4615-9055-2。
6. JH Van Lint (1982). 符号理論入門. GTM. 86. ニューヨーク: Springer-Verlag.
7. Clark, WEとLiang, JJ: 算術符号のモジュラー重みと巡回非隣接形式について. IEEE Trans. Info. Theory, 20 pp. 767-770(1974)

Retrieved from "https://en.wikipedia.org/w/index.php?title=AN_codes&oldid=1311143174"