パーフェクトコードとMDSコードについて詳しく解説

導入

完全なコード(または、最大分離可能距離のMDS コード) は、コード理論の概念であり、より具体的には修正コードを扱います。

修正コードは、受信機が送信または保存後の変更を検出または修正できるようにするコードです。それは情報の冗長性によって可能になります。コードに不必要な冗長性が含まれていない場合、コードは完全であると言われます。この概念は最適性の基準に対応します。線形コードのコンテキストで表現された別の最適性基準を検証するコードは、 MDSであると言われます。

修正コードは多数あります。チェックサムは最も単純な例ですが、BCH やリードソロモンのような巡回コードも挙げることができます。完全なコードはさらにまれで、たとえば、ハミングコードや長さ23 の 2 進 Golay コードや長さ 11 の 3 進コードが挙げられます。

コンテクスト

修正コード

修正規定の根源は、データ送信に関連する非常に具体的な問題にあります。場合によっては、完全に信頼できるわけではない通信チャネルを使用してデータ送信が行われることがあります。データがこのパス上を循環する場合、変更される可能性があります。修正コードの目的は、エラーを検出または訂正できるように情報の冗長性を提供することです。

コードの形式化について簡単に思い出してみましょう。メッセージは、アルファベットAから取られたk文字で構成される単語であり、メッセージのセットをE で表すことにします。このメッセージは、必ずしもAに等しいとは限らないアルファベットA’のn文字を含む単語の単射適用 φ によってエンコードされます。 q がA’のカーディナリティを表し、 F がφ の到着セットを表すものとします。 F は、 q個の要素を持つアルファベットから取られたn文字で構成される単語の集合であり、したがってFは基数q ⁿです。集合 φ( E ) はFに含まれ、コードと呼ばれ、この集合の要素はコードワードと呼ばれます。コードの長さは、メッセージを構成する文字の数であるkに対応します。これらの表記は記事全体で使用されます。

ハミング距離

4次元バイナリハイパーキューブ

修正コードの理論における重要な概念は、ハミング距離の概念です。コード内の 2 つの単語と異なる文字の数を関連付けます。

「 row 」と「 case 」の間のハミング距離は 3 です。

右の図は、アルファベットの文字が 2 進数である、業界で広く使用されているケースを示しています。選択した例では、単語は 4 つの文字で構成されています。 2 つの単語を結合するにはグラフのセグメントを横断する必要があるため、 0110と1110の間の距離は1に等しくなります。 2 つの単語は最初の文字だけが異なることにも気づきます。同じアプローチにより、 0100と1001の間の距離が3に等しいことがわかります。

図の例では、アルファベットは有限体であり、実際には 2 つの法則、1 つは加法則、もう 1 つは乗法則を備えています。これにより、全体にベクトル空間構造が与えられます。この場合、距離はハミング重みと呼ばれる擬似ノルムから導出され、ゼロ以外の座標の数をベクトルに関連付けます。 2 つの単語間のハミング距離は、それらの差の重みに等しくなります。

一般的な場合

補正能力と最小距離

コードの分析で最初に現れる問題は、完全なコードの定義に使用されるパラメータtの値と意味です。値t は、半径tとコードワードの中心の閉じたボールが 2 つずつ交差しないような最大の整数に対応します。

$$ {t=\max \left\{ r \in \mathbb N \; :\; \forall x,x’ \in \varphi(E)\quad x \ne x’\Rightarrow B_r(x) \bigcap B_r(x’)=\varnothing \right\} \quad avec \quad B_r(x)=\{y\in F : d(x,y)\le r\}} $$

δ が 2 つのコードワード間の最小距離である場合、三角不等式は、 t が厳密に δ/2 より小さい場合、閉じたボールとコードワードの中心と半径tの交点が空の交点を持つことを示します。実際、 Fのワードmが中心cとc’ 、半径tの 2 つの閉じた球の要素である場合、次のようになります。

$$ {d(c,c’) \le d(c,m) + d(m,c’) \le t + t < \delta\;} $$

これは、最小距離 δ の定義により、 cとc’が等しいことを意味します。

逆に、 t がδ/2 以上の場合、半径tの閉じたボールが少なくとも 2 つ存在し、空ではない交差の 2 つの異なるコードポイントが中心になることを示します。ハミング距離関数は有限セットで値を取得するため、最小値に達します。 cとc’ をコードの 2 つのワードとし、d( c , c’)が δ に等しくなるようにします。ここで、δ は最小距離を示します。 2 つの単語cとc’ はδ座標だけ異なります。 m をcとc’ の間で異なるδ 座標の最初のtを除いてcと同じ座標を持つ単語とする。ここで、 mはc’ の座標を持ち、 m はcからtの距離にあり、それより短い距離にある。 c’のt以上であるため、次のように結論付けることができます。

コードワードの中心と半径 t をもつ閉じたボールが空の交差を持つような最大値t は、δ/2 より厳密に小さい最大の整数です。

さらに、確実に訂正できるエラーの最大数は値tに等しいことに気づきます。実際、パラメータtの定義に対応する単一のコードワードが送信メッセージの近くに存在する場合にのみ、エラーを確実に訂正できます。

ハミング端子

t 個のエラーを修正するために必要な冗長性の数を決定する 1 つのアプローチは、カウントすることです。空間の基数F 、ハミング距離の半径tの閉球の基数、したがってtエラーの訂正能力を持つコードによって送信されるメッセージの最大数を計算することが可能です。

空間Fは、 d文字を含むアルファベットから取られたn文字の単語によって形成されます。したがって、これにはd ⁿ個の要素が含まれます。

点cから指定されたハミング距離iにある点の数を計算してみましょう。 cからiの距離にある点の集合は、 cとは異なるi座標を持つ単語を含む点の集合です。セット内の各点は、 nから選択されたi要素のサブセットに対応します。この性質のセットの数は、ランクnのi番目の二項係数に対応します。セットの各要素には、 d – 1 個の可能な文字があります。 V _{t が}半径tの閉じた球の基数を表す場合、次のように推測します。

$$ {V_t=\sum_{i=0}^{t} {n \choose i} (d-1)^i} $$

コードでt 個のエラーを修正するには、これらのボールが互いに素である必要があります。彼らの会議の枢機卿はMに等しい。 V _t 。ここで、 M はコードの濃度を示します。ただし、この和集合は空間Fの基数よりも厳密に大きい基数を持つことはできません。これにより、定義と次の命題が生じます。

M がコードの基数を指定すると、次の加算が検証され、これはハミング限界と呼ばれます。

$$ {M \leq \frac{d^n}{V_t}\quad avec \quad V_t=\sum_{i=0}^{t} {n \choose i} (d-1)^i} $$

コードは、コードワードの中心と半径t を持つ閉じたボールがFの分割を形成する場合に限り、完全であると言われます。これにより、次の命題が生じます。

コードは、ハミング限界に達した場合にのみ完全になります。