二次剰余コード

平方剰余符号は巡回符号の一種です。

二次剰余符号の例には、 上のハミング符号、 上の2 進ゴレイ符号、 上の3 進ゴレイ符号などがあります。 ${\displaystyle (7,4)}$ ${\displaystyle GF(2)}$${\displaystyle (23,12)}$ ${\displaystyle GF(2)}$${\displaystyle (11,6)}$ ${\displaystyle GF(3)}$

と が素数でが奇数で が を法とする 平方剰余であるとき、 有限体上の長さ の平方剰余符号が存在する。巡回符号としてのその生成多項式は次のように与えられる。 ${\displaystyle p}$${\displaystyle GF(l)}$${\displaystyle p}$${\displaystyle l}$${\displaystyle p}$${\displaystyle l}$${\displaystyle p}$

${\displaystyle f(x)=\prod _{j\in Q}(x-\zeta ^{j})}$

ここで、は集合 におけるの平方剰余の集合で あり、 は の有限拡大体における の原始 乗根です。 が の平方剰余であるという条件は、の係数が 内にあることを保証します。 コードの次元は です 。 を別の原始乗根で置き換えると、が の平方 剰余であるかどうかによって、同じコードまたは同等のコードが生成されます。 ${\displaystyle Q}$${\displaystyle p}$${\displaystyle \{1,2,\ldots ,p-1\}}$${\displaystyle \zeta}$${\displaystyle p}$${\displaystyle GF(l)}$${\displaystyle l}$${\displaystyle p}$${\displaystyle f}$${\displaystyle GF(l)}$${\displaystyle (p+1)/2}$${\displaystyle \zeta}$${\displaystyle p}$${\displaystyle \zeta^{r}}$${\displaystyle r}$${\displaystyle p}$

別の構成では、統一の語源を避けます。定義

${\displaystyle g(x)=c+\sum _{j\in Q}x^{j}}$

適切な に対して。 のとき、となるように 選択します。 が奇数の場合、 を選択します 。ここで、またはがと合同であるか を 法として であるかに応じて 選択します。 すると、平方剰余コードも生成されます。より正確には、によって生成されたのイデアルは、 平方剰余コードに対応します。 ${\displaystyle c\in GF(l)}$${\displaystyle l=2}$${\displaystyle c}$${\displaystyle g(1)=1}$${\displaystyle l}$${\displaystyle c=(1+{\sqrt {p^{*}}})/2}$${\displaystyle p^{*}=p}$${\displaystyle -p}$${\displaystyle p}$${\displaystyle 1}$${\displaystyle 3}$${\displaystyle 4}$${\displaystyle g(x)}$${\displaystyle F_{l}[X]/\langle X^{p}-1\rangle }$${\displaystyle g(x)}$

長さ の平方剰余符号の最小重みは より大きくなります。これが平方根の境界です。 ${\displaystyle p}$${\displaystyle {\sqrt {p}}}$

全体のパリティチェック桁を平方剰余コードに追加すると、拡張平方剰余コードが得られます。 を法としての場合、拡張平方剰余コードは自己双対です。それ以外の場合は、その双対と同等ですが、等しくはありません。グリーソン・プランジの定理(アンドリュー・グリーソンとユージン・プランジにちなんで名付けられました) により、拡張平方剰余コードの自己同型群には、 または と同型である部分群があります。 ${\displaystyle p\equiv 3}$${\displaystyle 4}$${\displaystyle PSL_{2}(p)}$${\displaystyle SL_{2}(p)}$

1980 年代後半から、2 乗剰余符号のエラーを訂正するための代数復号アルゴリズムが数多く開発されました。これらのアルゴリズムは、コード長が最大 113 の 2 乗剰余符号の (真の) エラー訂正能力を実現できます。ただし、長い 2 進 2 乗剰余符号と非 2 進 2 乗剰余符号の復号は依然として課題となっています。現在、2 乗剰余符号の復号は、エラー訂正符号の理論において依然として活発な研究分野です。 ${\displaystyle \lfloor (d-1)/2\rfloor }$

• FJ MacWilliams と NJA Sloane、「誤り訂正符号の理論」、North-Holland Publishing Co.、アムステルダム-ニューヨーク-オックスフォード、1977 年。
• Blahut, RE (2006 年 9 月)、「グリーソン-プランジ定理」、IEEE Trans. Inf. Theory、37 (5)、ピスカタウェイ、ニュージャージー州、米国: IEEE プレス: 1269–1273、doi :10.1109/18.133245。
• M. Elia、「(23,12,7) Golay コードの代数的復号化」、IEEE Transactions on Information Theory、第 33 巻、第 1 号、150-151 ページ、1987 年 1 月。
• Reed, IS, Yin, X., Truong, TK, (32, 16, 8) 二次剰余コードの代数的復号化。IEEE Trans. Inf. Theory 36(4), 876–880 (1990)
• Reed, IS, Truong, TK, Chen, X., Yin, X., (41, 21, 9) 二次剰余コードの代数的復号化。IEEE Trans. Inf. Theory 38(3), 974–986 (1992)
• ハンフリーズ、JF 三元（13、7、5）二次剰余コードの代数的復号化。IEEE Trans. Inf. Theory 38(3)、1122–1125（1992年5月）
• Chen, X., Reed, IS, Truong, TK, (73, 37, 13) 二次剰余コードのデコード。IEE Proc., Comput. Digit. Tech. 141(5), 253–258 (1994)
• Higgs, RJ, Humphreys, JF: 三進法 (23, 12, 8) の二次剰余コードのデコード。IEE Proc., Comm. 142(3), 129–134 (1995 年 6 月)
• He, R., Reed, IS, Truong, TK, Chen, X., (47, 24, 11) 二次剰余コードのデコード。IEEE Trans. Inf. Theory 47(3), 1181–1186 (2001)
• ……。
• Y. Li、Y. Duan、HC Chang、H. Liu、TK Truong、「シンドロームの差を利用した2乗剰余符号の復号」、IEEE Trans. Inf. Theory 64(7)、5179-5190 (2018)