シングルトン境界

符号理論において、シングルトン境界は、アメリカの数学者リチャード・コロム・シングルトン（1928–2007）にちなんで名付けられた、ブロック長、サイズ、最小距離を持つ任意のブロック符号 のサイズに関する比較的大まかな上限です。 これは、 Joshi (1958)によって、さらに以前には駒宮によって証明されたJoshi境界^{[ 1 ]}としても知られています${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle d}$

束縛の声明

長さ のコードワード集合の最小距離は と定義されます 。 ここで はと間のハミング距離です。この式は、長さ の - 進ブロックコードに含まれるコードワードの最大数と最小距離 を表します。 ${\displaystyle C}$ ${\displaystyle n}$ $${\displaystyle d=\min_{\{x,y\in C:x\neq y\}}d(x,y)}$$ ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle A_{q}(n,d)}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle d}$

すると、シングルトン境界は次のように述べられる。 $${\displaystyle A_{q}(n,d)\leq q^{n-d+1}.}$$

証明

まず、長さ の - 項単語の数はであることに注目してください。なぜなら、そのような単語の各文字は、残りの文字とは独立して、異なる値 のいずれかを取ることができるからです${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle q^{n}}$ ${\displaystyle q}$

ここで、最小距離 の任意の - 進ブロック符号を とします。明らかに、すべての符号語は互いに異なります。各符号語の最初の文字を削除して符号をパンクチャリングした場合でも、元の符号語はすべて互いに少なくともハミング距離であるため、結果として得られるすべての符号語は依然としてペアごとに異なります。したがって、変更された符号のサイズは元の符号と同じです。 ${\displaystyle C}$ ${\displaystyle q}$ ${\displaystyle d}$ ${\displaystyle c\in C}$ ${\displaystyle d-1}$ ${\displaystyle C}$ ${\displaystyle d}$

新たに得られた符号語はそれぞれ長さを持つ ため、最大で 個存在する。は任意であるため、この上限はこれらのパラメータを持つ最大の符号に対して成立するはずであり、したがって次の式が成り立つ。^{[ 2 ]}$${\displaystyle n-(d-1)=n-d+1,}$$ ${\displaystyle q^{n-d+1}}$ ${\displaystyle C}$ $${\displaystyle |C|\leq A_{q}(n,d)\leq q^{n-d+1}.}$$

線形符号

がブロック長、次元、元を持つ有限体上の最小距離を持つ線形符号である場合、最大符号語数はであり、シングルトン境界は次式を意味する。 したがって、 これは通常^{[ 3 ]} と表記される${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle q}$ ${\displaystyle q^{k}}$ $${\displaystyle q^{k}\leq q^{n-d+1},}$$ $${\displaystyle k\leq n-d+1,}$$ $${\displaystyle d\leq n-k+1.}$$

線形コードの場合、パリティ検査行列の階数がであることを観察することによって、シングルトン境界の別の証明が得られます。^{[ 4 ]}標準形式の任意の生成行列の行の重みが最大 であることを観察すれば、別の簡単な証明が得られます。 ${\displaystyle nk}$ ${\displaystyle n-k+1}$

歴史

この結果の通常の引用文献はシングルトン (1964)ですが、これはジョシ (1958)によって以前に証明されていました。ジョシは、この結果は駒宮 (1953)によってより複雑な証明を用いて以前に得られていたと指摘しています。ウェルシュ (1988 、p. 72) も駒宮 (1953)に関して同様のことを指摘しています。

MDS符号

シングルトン境界で等式を達成する線形ブロック符号は、MDS（最大距離分離可能）符号と呼ばれます。このような符号の例には、符号語のみを持つ符号（ の all-語、したがって最小距離）、 全体を使用する符号（最小距離 1）、単一のパリティシンボルを持つ符号（最小距離 2）、およびそれらの双対符号 などがあります。これらはしばしば自明なMDS符号 と呼ばれます${\displaystyle q}$ ${\displaystyle x}$ ${\displaystyle x\in \mathbb {F}_{q}}$ ${\displaystyle n}$ ${\displaystyle (\mathbb {F} _{q})^{n}}$

バイナリアルファベットの場合、単純なMDSコードのみが存在する。^{[ 5 ] [ 6 ]}

非自明なMDS符号の例としては、リード・ソロモン符号とその拡張版が挙げられる。^{[ 7 ] [ 8 ]}

MDS符号は、固定された と に対して、最も高い誤り訂正能力と誤り検出能力を持つため、ブロック符号の重要なクラスである。MDS符号を特徴付ける方法はいくつかある。 ^{[ 9 ]}${\displaystyle n}$ ${\displaystyle k}$

定理—を 上の線形 [ ] コードとします。以下は同値です。 ${\displaystyle C}$ ${\displaystyle n,k,d}$ ${\displaystyle \mathbb {F} _{q}}$

• ${\displaystyle C}$ MDS コードです。
• の生成行列の任意の列は線形独立です。${\displaystyle k}$ ${\displaystyle C}$
• パリティ検査行列の任意の列は線形独立です。${\displaystyle nk}$ ${\displaystyle C}$
• ${\displaystyle C^{\perp}}$ MDS コードです。
• が標準形式の の生成行列である場合、 のすべての正方部分行列は非特異です。${\displaystyle G=(I|A)}$ ${\displaystyle C}$ ${\displaystyle A}$
• 任意の座標位置が与えられると、その位置を正確にサポートする(最小重みの) コードワードが存在します。${\displaystyle d}$

これらの特徴付けの最後は、マクウィリアムズの恒等式を用いて、MDSコードの完全な重み分布を明示的に表す式を可能にする。^{[ 10 ]}

定理—を 上の線形 [ ] MDS 符号とする。を の重みの符号語数とすると、 ${\displaystyle C}$ ${\displaystyle n,k,d}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle A_{w}}$ ${\displaystyle C}$ ${\displaystyle w}$ $${\displaystyle A_{w}={\binom {n}{w}}\sum _{j=0}^{wd}(-1)^{j}{\binom {w}{j}}(q^{w-d+1-j}-1)={\binom {n}{w}}(q-1)\sum _{j=0}^{wd}(-1)^{j}{\binom {w-1}{j}}q^{wdj}.}$$

射影幾何学における弧

MDSコードの生成行列の列の線型独立性により、有限射影幾何学におけるオブジェクトからMDSコードを構築することができる。有限体上の（幾何学的）次元の有限射影空間を とする。この射影空間において同次座標で表される点の集合を とする。これらの点の同次座標を列とする行列を形成する。すると、^{[ 11 ]}${\displaystyle PG(N,q)}$ ${\displaystyle N}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle K=\{P_{1},P_{2},\dots,P_{m}\}}$ ${\displaystyle (N+1)\times m}$ ${\displaystyle G}$

定理—が (空間) -弧である場合、かつ が上の MDS コードの生成行列である場合に限ります。 ${\displaystyle K}$ ${\displaystyle m}$ ${\displaystyle G}$ ${\displaystyle [m,N+1,mN]}$ ${\displaystyle \mathbb {F} _{q}}$

参照

• ギルバート・ヴァルシャモフ境界
• グリースマー境界
• ハミング境界
• ジョンソン境界
• プロトキン製本

注釈

1. Keedwell, A. Donald; Dénes, József (1991年1月24日).ラテン方陣：理論と応用における新展開. アムステルダム: エルゼビア. p. 270. ISBN 0-444-88899-3。
2. Ling & Xing 2004、93ページ
3. ローマン 1992、175ページ
4. プレス 1998、26ページ
5. ヴェルマーニ 1996、命題 9.2
6. Ling & Xing 2004、p. 94 注釈 5.4.7
7. マクウィリアムズ＆スローン 1977年、第11章
8. リン＆シン 2004、94ページ
9. Roman 1992、p. 237、定理5.3.7
10. ローマン 1992、240ページ
11. Bruen, AA; Thas, JA; Blokhuis, A. (1988)「MDSコードについて、PG(n,q)の弧、qが偶数、およびB. Segreの3つの基本問題の解」、Invent. Math.、92 (3): 441– 459、Bibcode : 1988InMat..92..441B、doi : 10.1007/bf01393742、S2CID 120077696 

参考文献

• Joshi, DD (1958)、「最小距離コードの上限に関する注記」、Information and Control、1 (3): 289– 295、doi : 10.1016/S0019-9958(58)80006-6
• 駒宮 雄三 (1953)「論理数学の情報理論への応用」第3回応用数学会講演論文集: 437
• Ling, San; Xing, Chaoping (2004), Coding Theory / A First Course , Cambridge University Press, ISBN 0-521-52923-9
• マクウィリアムズ、FJ；スローン、NJA（1977年）『誤り訂正符号の理論』ノースホランド、  33、37ページ、ISBN 0-444-85193-3
• Pless, Vera (1998)、誤り訂正符号理論入門（第3版）、Wiley Interscience、ISBN 0-471-19047-0
• ローマン、スティーブン（1992）『符号化と情報理論』GTM、第134巻、シュプリンガー・フェアラーク、ISBN 0-387-97812-7
• シングルトン、RC (1964)、「最大距離q値符号」、IEEE Trans. Inf. Theory、10 (2): 116– 118、doi : 10.1109/TIT.1964.1053661
• ヴェルマニ、LR（1996）、代数的符号理論の要素、チャップマン＆ホール
• ウェルシュ、ドミニク（1988年）、コードと暗号、オックスフォード大学出版局、ISBN 0-19-853287-3

参考文献

• JH van Lint ( 1992).符号理論入門. GTM . 第86巻（第2版）. Springer-Verlag. p.  61. ISBN 3-540-54894-7。
• ニーダーライター、ハラルド、シン、チャオピン (2001)。「6. 代数的符号理論への応用」有限体上の曲線上の有理点。理論と応用。ロンドン数学会講義ノートシリーズ。第285巻。ケンブリッジ：ケンブリッジ大学出版局。ISBN 0-521-66543-4. Zbl  0971.11033 .