エクスパンダーコード

エキスパンダーコード
二部展開グラフ
分類
タイプ	線形ブロックコード
ブロック長	${\displaystyle n}$
メッセージの長さ	${\displaystyle nm}$
レート	${\displaystyle 1-m/n}$
距離	${\displaystyle 2(1-\epsilon )\gamma \cdot n}$
アルファベットのサイズ	${\displaystyle 2}$
表記	${\displaystyle [n,nm,2(1-\epsilon )\gamma \cdot n]_{2}}$-コード
ヴ t e

符号理論では、エキスパンダーコードは、二部エキスパンダーグラフから構成される誤り訂正コードの一種です。エキスパンダーコードは、ユステセンコードとともに、一定の正のレート、一定の正の相対距離、および一定のアルファベットサイズを持つため、特に注目されています。実際、アルファベットには 2 つの要素しか含まれていないため、エキスパンダーコードはバイナリコードのクラスに属します。さらに、エキスパンダーコードは、コードのブロック長に比例した時間でエンコードおよびデコードできます。

符号理論において、エクスパンダ符号は、パリティ検査行列が二部エクスパンダグラフの隣接行列である線形ブロック符号です。これらの符号は、良好な相対距離を持ちます。ここで、 および は、後で定義されるエクスパンダグラフの特性であり、速度、および復号可能性 (実行時間のアルゴリズムが存在) です。 ${\displaystyle [n,nm]_{2}\,}$ ${\displaystyle 2(1-\varepsilon )\gamma \,}$${\displaystyle \varepsilon \,}$${\displaystyle \gamma \,}$ ${\displaystyle \left(1-{\tfrac {m}{n}}\right)\,}$${\displaystyle O(n)\,}$

を、変数と呼ばれるノードの集合と、制約と呼ばれるノードの集合の間の双正則グラフとします。 ${\displaystyle B}$${\displaystyle (c,d)}$${\displaystyle n}$${\displaystyle \{v_{1},\cdots ,v_{n}\}}$${\displaystyle cn/d}$${\displaystyle \{C_{1},\cdots ,C_{cn/d}\}}$

を、各制約 に対して、隣接する変数が となるように設計された関数とします。 ${\displaystyle b(i,j)}$${\displaystyle C_{i}}$${\displaystyle C_{i}}$${\displaystyle v_{b(i,1)},\cdots ,v_{b(i,d)}}$

をブロック長 の誤り訂正符号とする。拡張符号は、 の符号語が となるようなワードであるブロック長 の符号である。^[1]${\displaystyle {\mathcal {S}}}$${\displaystyle d}$ ${\displaystyle {\mathcal {C}}(B,{\mathcal {S}})}$${\displaystyle n}$${\displaystyle (x_{1},\cdots ,x_{n})}$${\displaystyle 1\leq i\leq cn/d}$${\displaystyle (x_{b(i,1)},\cdots ,x_{b(i,d)})}$${\displaystyle {\mathcal {S}}}$

非自明なロスレスエクスパンダーグラフが存在することが示されています。さらに、それらを明示的に構築することもできます。^[2]

のレートはその次元をブロック長で割ったものです。この場合、パリティ検査行列のサイズは なので、レートは少なくとも になります。 ${\displaystyle C\,}$${\displaystyle m\times n\,}$${\displaystyle C\,}$${\displaystyle (n-m)/n=1-m/n\,}$

と仮定します。この場合、エクスパンダー コードの距離は少なくとも になります。 ${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$${\displaystyle (n,m,d,\gamma ,1-\varepsilon )\,}$${\displaystyle C\,}$${\displaystyle 2(1-\varepsilon )\gamma n\,}$

におけるすべてのコードワードを頂点 のサブセットと見なすことができる点に注意してください。つまり、コードワードの 番目のインデックスが 1 である場合に限り、頂点 であると言えます。この場合、 はコードワードであるためには、すべての頂点が の偶数個の頂点に隣接している必要があります。(コードワードであるためには、、ここで はパリティ チェック行列です。この場合、 の各頂点はの各列に対応します。 に対する行列乗算により、目的の結果が得られます。) したがって、頂点がの単一の頂点に隣接している場合、 はコードワードではないことがすぐにわかります。のにおける隣接頂点を で表し、の隣接頂点のうち一意であるもの、つまり の単一の頂点に隣接するものを表すものとします。 ${\displaystyle c\,}$${\displaystyle C\,}$${\displaystyle S\subset L\,}$${\displaystyle v_{i}\in S\,}$${\displaystyle i\,}$${\displaystyle c\,}$${\displaystyle v\in R\,}$${\displaystyle S\,}$${\displaystyle cP=0\,}$${\displaystyle P\,}$${\displaystyle R\,}$${\displaystyle P\,}$${\displaystyle {\text{GF}}(2)=\{0,1\}\,}$${\displaystyle v\in R\,}$${\displaystyle S\,}$${\displaystyle c\,}$${\displaystyle N(S)\,}$${\displaystyle R\,}$${\displaystyle S\,}$${\displaystyle U(S)\,}$${\displaystyle S\,}$${\displaystyle S\,}$

サイズごとに、。 ${\displaystyle S\subset L\,}$${\displaystyle |S|\leq \gamma n\,}$${\displaystyle d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,}$

自明なことですが、 はを意味するので です。 のすべての頂点の次数はなのでが成り立ちます。 グラフの拡張特性により、異なる頂点に向かう辺の集合が存在する必要があります。 残りの辺により、最大で 個の隣接辺が一意ではなくなるため、 となります。 ${\displaystyle |N(S)|\geq |U(S)|\,}$${\displaystyle v\in U(S)\,}$${\displaystyle v\in N(S)\,}$${\displaystyle |N(S)|\leq d|S|\,}$${\displaystyle S\,}$${\displaystyle d\,}$${\displaystyle d(1-\varepsilon )|S|\,}$${\displaystyle d\varepsilon |S|\,}$${\displaystyle d\varepsilon |S|\,}$${\displaystyle U(S)\geq d(1-\varepsilon )|S|-d\varepsilon |S|=d(1-2\varepsilon )|S|\,}$

十分に小さいものには必ず一意の隣接点が存在する。これは より成り立つ。 ${\displaystyle S\,}$${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$

すべてのサブセットには一意の隣接サブセットがあります。 ${\displaystyle T\subset L\,}$${\displaystyle |T|<2(1-\varepsilon )\gamma n\,}$

補題 1 は の場合を証明しているので、 と仮定します。が となるようにします。補題 1 により、であることが分かります。すると、頂点がにある場合と の場合の両方とも、 であることが分かります。したがって、補題 1 の最初の部分により、 であることが分かります。 、であり、したがって は空ではありません。 ${\displaystyle |T|\leq \gamma n\,}$${\displaystyle 2(1-\varepsilon )\gamma n>|T|>\gamma n\,}$${\displaystyle S\subset T\,}$${\displaystyle |S|=\gamma n\,}$${\displaystyle |U(S)|\geq d(1-2\varepsilon )|S|\,}$${\displaystyle v\in U(S)\,}$${\displaystyle U(T)\,}$${\displaystyle v\notin N(T\setminus S)\,}$${\displaystyle |T\setminus S|\leq 2(1-\varepsilon )\gamma n-\gamma n=(1-2\varepsilon )\gamma n\,}$${\displaystyle |N(T\setminus S)|\leq d(1-2\varepsilon )\gamma n\,}$${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$${\displaystyle |U(T)|\geq |U(S)\setminus N(T\setminus S)|\geq |U(S)|-|N(T\setminus S)|>0\,}$${\displaystyle U(T)\,}$

に少なくとも 1 つの一意の近傍がある場合、つまり の場合、に対応する対応するワードはコードワードにはならないことに注意してください。これは、パリティ チェック マトリックスによってすべてゼロのベクトルに乗算されないためです。前の議論により、 です。 は線形であるため、の距離は少なくとも であると結論付けられます。 ${\displaystyle T\subset L\,}$${\displaystyle |U(T)|>0\,}$${\displaystyle c\,}$${\displaystyle T\,}$${\displaystyle c\in C\implies wt(c)\geq 2(1-\varepsilon )\gamma n\,}$${\displaystyle C\,}$${\displaystyle C\,}$${\displaystyle 2(1-\varepsilon )\gamma n\,}$

拡張コードのエンコード時間は、行列乗算によって一般線形コードのエンコード時間の上限が決まります。Spielman の結果は、エンコードが時間内に可能であることを示しています。^[3]${\displaystyle O(n^{2})\,}$${\displaystyle O(n)\,}$

以下のアルゴリズムを使用する と、時間内にエクスパンダーコードのデコードが可能になります。${\displaystyle O(n)\,}$${\displaystyle \varepsilon <{\tfrac {1}{4}}\,}$

を のコードワードの 番目のインデックスに対応する の頂点とします。を受信語、 とします。を、 を とします。次に貪欲アルゴリズムを考えます。 ${\displaystyle v_{i}\,}$${\displaystyle L\,}$${\displaystyle i\,}$${\displaystyle C\,}$${\displaystyle y\in \{0,1\}^{n}\,}$${\displaystyle V(y)=\{v_{i}\mid {\text{the }}i^{\text{th}}{\text{ position of }}y{\text{ is a }}1\}\,}$${\displaystyle e(i)\,}$${\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is even}}\}|\,}$${\displaystyle o(i)\,}$${\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is odd}}\}|\,}$

入力:受信した単語。 ${\displaystyle y\,}$

y'をyに初期化する
一方、Rには、V(y')の奇数個の頂点に隣接するavが存在する。
    o(i) > e(i) となる i が存在する場合
        エントリ i を y に反転する'
    それ以外
        失敗

出力:失敗、または変更されたコードワード。 ${\displaystyle y'\,}$

まずアルゴリズムの正確性を示し、次にその実行時間を調べます。

受信したコードワードが元のコードワードのコード距離の半分以内にある場合、アルゴリズムが正しいコードワードで終了することを示さなければなりません。破損した変数の集合を、、とし、 内の満たされていない（奇数の頂点に隣接する）頂点の集合を とします。次の補題が役立ちます。 ${\displaystyle S\,}$${\displaystyle s=|S|\,}$${\displaystyle R\,}$${\displaystyle c\,}$

の場合、となるが存在します。 ${\displaystyle 0<s<\gamma n\,}$${\displaystyle v_{i}\,}$${\displaystyle o(i)>e(i)\,}$

補題 1 により、 であることが分かっています。したがって、 であるため、平均頂点には少なくとも 個の一意の隣接頂点があります (一意の隣接頂点は満たされず、したがって に寄与することを思い出してください)。したがって、の頂点が存在します。 ${\displaystyle U(S)\geq d(1-2\varepsilon )s\,}$${\displaystyle d(1-2\varepsilon )>d/2\,}$${\displaystyle o(i)\,}$${\displaystyle \varepsilon <{\tfrac {1}{4}}\,}$${\displaystyle v_{i}\,}$${\displaystyle o(i)>e(i)\,}$

したがって、まだコードワードに到達していない場合は、反転する頂点が常に存在します。次に、エラーの数が を超えて増加することは決してないことを示します。 ${\displaystyle \gamma n\,}$

から始めると、アルゴリズムのどのポイントにも 到達しません。${\displaystyle s<\gamma (1-2\varepsilon )n\,}$${\displaystyle s=\gamma n\,}$

頂点 を反転すると、とが交換され、 であったため、反転するたびに右側の満たされていない頂点の数が少なくとも 1 つ減少することを意味します。 であるため、グラフの -正則性により、満たされていない頂点の初期数は最大 です。エラーのある文字列に到達した場合、補題 1 により、少なくとも 個 の一意の近傍が存在することになり、これは少なくとも 個の満たされていない頂点が存在することを意味し、矛盾が生じます。 ${\displaystyle v_{i}\,}$${\displaystyle o(i)\,}$${\displaystyle e(i)\,}$${\displaystyle o(i)>e(i)\,}$${\displaystyle s<\gamma (1-2\varepsilon )n\,}$${\displaystyle d\gamma (1-2\varepsilon )n\,}$${\displaystyle d\,}$${\displaystyle \gamma n\,}$${\displaystyle d\gamma (1-2\varepsilon )n\,}$${\displaystyle d\gamma (1-2\varepsilon )n\,}$

補題 3 と 4 は、 ( の距離の半分) から開始すると、反転する頂点が必ず見つかることを示しています。各反転により、 の満たされていない頂点の数が少なくとも 1 減少するため、アルゴリズムは最大ステップで終了し、補題 3 により、あるコードワードで終了します。(コードワードでない場合は、反転する頂点がいくつかあることになります)。補題 4 は、正しいコードワードから より遠くなることはないことを示しています。コードには距離があるため( より)、終了するコードワードは正しいコードワードでなければなりません。これは、ビット反転の数が距離の半分未満であるためです (したがって、他のコードワードに到達するほど遠くまで移動することはできませんでした)。 ${\displaystyle s<\gamma (1-2\varepsilon )n\,}$${\displaystyle C\,}$${\displaystyle v_{i}\,}$${\displaystyle R\,}$${\displaystyle m\,}$${\displaystyle \gamma n\,}$${\displaystyle 2(1-\varepsilon )\gamma n>\gamma n\,}$${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$

ここで、アルゴリズムが線形時間デコードを実現できることを示します。を定数とし、 をの任意の頂点の最大次数とします。は既知の構成では定数であることにも注意してください。 ${\displaystyle {\tfrac {n}{m}}\,}$${\displaystyle r\,}$${\displaystyle R\,}$${\displaystyle r\,}$

1. 前処理:各頂点に奇数個の隣接頂点があるか偶数個であるかを計算するのに時間がかかります。${\displaystyle O(mr)\,}$${\displaystyle R\,}$
2. 前処理 2:を持つ頂点のリストを計算するのに時間がかかります。${\displaystyle O(dn)=O(dmr)\,}$${\displaystyle v_{i}\,}$${\displaystyle L\,}$${\displaystyle o(i)>e(i)\,}$
3. 各反復: リストの最初の要素を削除するだけです。 の奇数/偶数頂点のリストを更新するには、必要に応じて挿入/削除を行い、エントリを更新するだけです。 次に、の頂点のリストのエントリを、偶数隣接頂点よりも奇数隣接頂点が多いように更新し、必要に応じて挿入/削除を行います。 したがって、各反復には時間がかかります。${\displaystyle R\,}$${\displaystyle O(d)\,}$${\displaystyle O(dr)\,}$${\displaystyle L\,}$${\displaystyle O(dr)\,}$
4. 上で述べたように、反復の総数は最大 です。${\displaystyle m\,}$

これにより、合計実行時間が与えられます。ここで、およびは定数です。 ${\displaystyle O(mdr)=O(n)\,}$${\displaystyle d\,}$${\displaystyle r\,}$

• エキスパンダーグラフ
• 低密度パリティ検査符号
• 誤り訂正符号の線形時間符号化と復号化
• ABNNR および AEL コード

この記事はベンカテサン・グルスワミ博士の講義ノートに基づいています。^[4]