シングルトンバウンド

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

集合の最小距離${\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}$-ary の長さの単語${\displaystyle n}$は$\displaystyle q^{n}}$なぜなら、そのような単語の各文字は、${\displaystyle q}$残りの文字とは無関係に、異なる値。

さあ${\displaystyle C}$恣意的である${\displaystyle q}$最小距離のブロックコード${\displaystyle d}$明らかに、すべてのコードワード${\displaystyle c\in C}$は別物です。最初の部分を削除してコードを破ると${\displaystyle d-1}$各コードワードの文字を考えると、結果として得られるすべてのコードワードはペアごとに異なっていなければなりません。なぜなら、${\displaystyle C}$ハミング距離は少なくとも${\displaystyle d}$互いに異なるため、変更後のコードのサイズは元のコードと同じになります。

新たに得られたコードワードはそれぞれ長さが $${\displaystyle n-(d-1)=n-d+1,}$$ したがって、最大で$\displaystyle q^{n-d+1}}$それらのうち。${\displaystyle C}$これは任意であり、この境界はこれらのパラメータを持つ最大のコードに対して成り立つ必要があり、したがって次のようになります。^{[ 2 ]}$${\displaystyle |C|\leq A_{q}(n,d)\leq q^{n-d+1}.}$$

もし${\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,}$$ これは通常^{[ 3 ]と表記されます。}$${\displaystyle d\leq n-k+1.}$$

線形コードの場合、パリティ検査行列のランクが${\displaystyle nk}$[ ^{4 ]標準形式の任意の}生成行列の行の重みが最大で${\displaystyle n-k+1}$。

この結果の一般的な引用元はSingleton (1964)ですが、これはJoshi (1958)によって以前に証明されていました。Joshiは、この結果はKomamiya (1953)によってより複雑な証明を用いて以前に得られていたと指摘しています。Welsh (1988 、p. 72)もKomamiya (1953)に関して同様のことを指摘しています。

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

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

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

MDSコードはブロックコードの重要なクラスです。${\displaystyle n}$そして${\displaystyle k}$MDS コードは、最も優れたエラー訂正および検出能力を備えています。MDS コードを特徴付ける方法はいくつかあります。^{[ 9 ]}

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

• ギルバートとヴァルシャモフが結ばれる
• グリースマー行き
• ハミングバウンド
• ジョンソン行き
• プロトキン拘束

• Joshi, DD (1958)、「最小距離符号の上限に関する注記」、Information and Control、1 (3): 289–295、doi : 10.1016/S0019-9958(58)80006-6
• 小宮義雄（1953）「論理数学の情報理論への応用」第3回日本応用数学全国大会論文集：437
• 凌三、興朝平（2004）『符号理論入門』ケンブリッジ大学出版局、ISBN 0-521-52923-9
• MacWilliams, FJ ; Sloane, NJA (1977)『誤り訂正符号の理論』 North-Holland、pp. 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
• Singleton, RC (1964)、「最大距離q進符号」、IEEE Trans. Inf. Theory、10 (2): 116–118、doi : 10.1109/TIT.1964.1053661
• Vermani, LR (1996),代数的符号理論の基礎, Chapman & Hall
• ウェルシュ、ドミニク（1988）、『暗号と暗号学』、オックスフォード大学出版局、ISBN 0-19-853287-3

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