エクスパンダーコード

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

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

エクスパンダーコード

符号理論において、エクスパンダ符号とは、パリティ検査行列が二部エクスパンダグラフの隣接行列である線形ブロック符号である。これらの符号は良好な相対距離を持ち、ここで、およびは後述するエクスパンダグラフの特性、レート、および復号可能性（実行時間のアルゴリズムが存在する）を有する。 ${\displaystyle [n,n-m]_{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 である場合に限り、頂点 となります。したがって、 は、すべての頂点が の偶数個の頂点に隣接している場合にコードワードとなります。(コードワードとなるためには、、ここではパリティ チェック行列です。したがって、 の各頂点はの各列に対応します。 に対する行列乗算により、目的の結果が得られます。)したがって、の 1 つの頂点に隣接している頂点がある場合、はコードワードではないことがすぐにわかります。のにおける隣接頂点を で表し、の隣接頂点のうち一意であるもの、つまり の 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\,}$

補題1

サイズごとに、。 ${\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}}\,}$

補題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 が存在する場合 y'のエントリiを反転する それ以外 失敗

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

---

証拠

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

正確さ

受信したコードワードが元のコードワードのコード距離の半分以内にある場合、アルゴリズムは正しいコードワードで終了することを示す必要があります。不正な変数の集合を、、とし、 における不満足な（奇数個の頂点に隣接する）頂点の集合をとします。次の補題が有用であることが証明されます。 ${\displaystyle S\,}$ ${\displaystyle s=|S|\,}$ ${\displaystyle R\,}$ ${\displaystyle c\,}$

補題3

の場合、の条件を満たすが存在します。 ${\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\,}$

補題4

から始めると、アルゴリズムのどのポイントにも到達しません。 ${\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]

参考文献

1. Sipser, M.; Spielman, DA (1996). 「Expander codes」. IEEE Transactions on Information Theory . 42 (6): 1710– 1722. doi :10.1109/18.556667.
2. Capalbo, M.; Reingold, O.; Vadhan, S.; Wigderson, A. (2002). 「ランダムネス導体と定数次数ロスレス展開器」. STOC '02 Proceedings of the third-fourth annual ACM symposium on Theory of compute . ACM. pp.  659– 668. doi :10.1145/509907.510003. ISBN 978-1-58113-495-7. S2CID  1918841。
3. Spielman, D. (1996). 「線形時間符号化および復号化可能な誤り訂正符号」. IEEE Transactions on Information Theory . 42 (6): 1723–31 . CiteSeerX 10.1.1.47.2736 . doi :10.1109/18.556668. 
4. Guruswami, V. (2006年11月15日). 「講義13：エクスパンダーコード」（PDF） . CSE 533：誤り訂正. ワシントン大学.
   Guruswami, V. (2010年3月). 「注8：エクスパンダー符号とその復号法」(PDF) .符号理論入門. カーネギーメロン大学.
   Guruswami, V. (2004年9月). 「ゲストコラム：誤り訂正符号とエクスパンダーグラフ」 . ACM SIGACT News . 35 (3): 25– 41. doi :10.1145/1027914.1027924. S2CID  17550280.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Expander_code&oldid=1322733251"