ゼモールのデコードアルゴリズム

符号理論において、ジル・ゼモール^{[1]によって設計・開発された}ゼモールのアルゴリズムは、コード構築に対する再帰的な低複雑性のアプローチである。これは、シプサーとスピルマンのアルゴリズムを改良したものである。

ゼモールは、基となるグラフが二部グラフである、拡張コードのシプサー・スピルマン構成の典型的なクラスを検討しました。シプサーとスピルマンは、漸近的に優れた線形エラーコードの構成的ファミリーと、常に一定の割合のエラーを除去する単純な並列アルゴリズムを導入しました。この記事は、ベンカテサン・グルスワミ博士のコースノート^[2]に基づいています。

Zemor のアルゴリズムは、 Tanner グラフと呼ばれる種類の拡張グラフに基づいています。 コードの構築は Tanner によって初めて提案されました。^[3]このコードは、2 部グラフである二重被覆、正則拡張に基づいています。 = 、ここでは頂点の集合、は辺の集合、=および= 、ここでおよび は頂点の集合を表します。 を各グループの頂点の数、つまりとします。辺集合のサイズは=であり、 内のすべての辺はおよび の両方に 1 つの端点を持ちます。は を含む辺の集合を表します。 ${\displaystyle d}$${\displaystyle G}$${\displaystyle G}$${\displaystyle \left(V,E\right)}$${\displaystyle V}$${\displaystyle E}$${\displaystyle V}$${\displaystyle A}$ ${\displaystyle \cup}$ ${\displaystyle B}$${\displaystyle A}$ ${\displaystyle \cap}$ ${\displaystyle B}$${\displaystyle \emptyset}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n}$${\displaystyle |A|=|B|=n}$${\displaystyle E}$${\displaystyle N}$${\displaystyle nd}$${\displaystyle E}$${\displaystyle A}$${\displaystyle B}$${\displaystyle E(v)}$${\displaystyle v}$

上の順序付けを仮定すると、順序付けは のすべての辺に対してすべてのに対して行われます。を有限体とし、内の単語に対して 、単語のサブワードがによってインデックス付けされるとします。その単語を で表すものとします。頂点のサブセットおよび により、すべての単語が重複しないサブワードに分割されます。ここで、 はの要素全体にわたります。コード を構築するには、 であるコードである線形サブコード を考えます。この場合、アルファベットのサイズは です。任意の頂点 に対して、に隣接するの頂点の順序付けをとします。このコードでは、各ビットはの辺にリンクされています。 ${\displaystyle V}$${\displaystyle E(v)}$${\displaystyle v\in V}$ ${\displaystyle \mathbb {F} =GF(2)}$${\displaystyle x=(x_{e}),e\in E}$${\displaystyle \mathbb {F} ^{N}}$${\displaystyle E(v)}$${\displaystyle (x)_{v}}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x\in \mathbb {F} ^{N}}$${\displaystyle n}$${\displaystyle \left(x\right)_{v}\in \mathbb {F} ^{d}}$${\displaystyle v}$${\displaystyle A}$${\displaystyle C}$${\displaystyle C_{o}}$${\displaystyle [d,r_{o}d,\delta ]}$${\displaystyle q}$${\displaystyle 2}$${\displaystyle v\in V}$${\displaystyle v(1),v(2),\ldots ,v(d)}$${\displaystyle d}$${\displaystyle E}$${\displaystyle v}$${\displaystyle x_{e}}$${\displaystyle e}$${\displaystyle E}$

コードは、のすべての頂点に対してがのコードワードとなるようなのバイナリベクトルの集合として定義できます。この場合、 のすべての辺が のちょうどの頂点に隣接するという特別なケースを考えることができます。これは、 と がそれぞれ正則グラフの頂点集合と辺集合を構成することを意味します。 ${\displaystyle C}$${\displaystyle x=\left(x_{1},x_{2},\ldots ,x_{N}\right)}$${\displaystyle \{0,1\}^{N}}$${\displaystyle v}$${\displaystyle V}$${\displaystyle \left(x_{v(1)},x_{v(2)},\ldots ,x_{v(d)}\right)}$${\displaystyle C_{o}}$${\displaystyle E}$${\displaystyle 2}$${\displaystyle V}$${\displaystyle V}$${\displaystyle E}$${\displaystyle d}$${\displaystyle G}$

このようにして構築されたコードを コード と呼びます。 与えられたグラフと与えられたコードに対して、与えられた頂点 に接続するエッジを順序付けるさまざまな方法があるため、複数のコードが存在します。つまり、 です。実際、コードは、すべての に対してとなるすべてのコードワードで構成されています。コードはにおいて線形です。これは、線形であるサブコード から生成されるためです。コードは、すべての に対してと定義されます。 ${\displaystyle C}$${\displaystyle \left(G,C_{o}\right)}$${\displaystyle G}$${\displaystyle C_{o}}$${\displaystyle \left(G,C_{o}\right)}$${\displaystyle v}$${\displaystyle v(1),v(2),\ldots ,v(d)}$${\displaystyle C}$${\displaystyle x_{v}\in C_{o}}$${\displaystyle v\in A,B}$${\displaystyle C}$${\displaystyle [N,K,D]}$${\displaystyle \mathbb {F} }$${\displaystyle C_{o}}$${\displaystyle C}$${\displaystyle C=\{c\in \mathbb {F} ^{N}:(c)_{v}\in C_{o}\}}$${\displaystyle v\in V}$

この図では、グラフとコードを示しています。 ${\displaystyle (x)_{v}=\left(x_{e1},x_{e2},x_{e3},x_{e4}\right)\in C_{o}}$${\displaystyle G}$${\displaystyle C}$

行列 において、は の隣接行列の2 番目に大きい固有値に等しいとします。ここで、最大の固有値は です。2 つの重要な主張がなされています。 ${\displaystyle G}$${\displaystyle \lambda}$${\displaystyle G}$${\displaystyle d}$

${\displaystyle \left({\dfrac {K}{N}}\right)\geq 2r_{o}-1}$
数字ノードが次数、サブコードノードが次数 である二部グラフから構築された線形コードのレートを とします。パラメータとレートを持つ単一の線形コードが各サブコードノードに関連付けられている場合、 となります${\displaystyle R}$${\displaystyle m}$${\displaystyle n}$${\displaystyle \left(n,k\right)}$${\displaystyle r=\left({\dfrac {k}{n}}\right)}$${\displaystyle k\geq 1-\left(1-r\right)m}$。

を線形コードのレートとし、これは に等しいものとします。グラフにサブコード ノード があるとします。サブコードの次数が の場合、各数字ノードはグラフのエッジの に接続されているため、コードには数字が含まれている必要があります。各サブコード ノードは、合計 の方程式をパリティ チェック マトリックスに提供します。これらの方程式は線形独立ではない可能性があります。したがって、 、つまりこの 2 部グラフの数字ノードの値は であり、ここでは であるため、次のように記述できます。${\displaystyle R}$${\displaystyle K/N}$${\displaystyle S}$${\displaystyle n}$${\displaystyle \left({\dfrac {n}{m}}\right)S}$${\displaystyle m}$${\displaystyle \left(n\right)S}$${\displaystyle (nk)}$${\displaystyle \left(nk\right)S}$${\displaystyle \left({\dfrac {K}{N}}\right)\geq \left({\dfrac {({\dfrac {n}{m}})S-(n-k)S}{({\dfrac {n}{m}})S}}\right)}$
${\displaystyle \geq 1-m\left({\dfrac {n-k}{n}}\right)}$
${\displaystyle \geq 1-m\left(1-r\right)}$${\displaystyle m}$${\displaystyle 2}$${\displaystyle r=r_{o}}$
${\displaystyle \left({\dfrac {K}{N}}\right)\geq 2r_{o}-1}$

${\displaystyle D\geq N\left({\dfrac {(\delta -({\dfrac {\lambda }{d}}))}{(1-({\dfrac {\lambda }{d}})}})\right)^{2}}$

${\displaystyle =N\left(\delta ^{2}-O\left({\dfrac {\lambda }{d}}\right)\right)}$ ${\displaystyle \rightarrow (1)}$

がレート、ブロック コード長、最小相対距離の線形コードであり、が2 番目に大きい固有値 を持つ正則グラフのエッジ頂点接続グラフである場合、コードのレートは少なくとも、最小相対距離は少なくとも になります。${\displaystyle S}$${\displaystyle r}$${\displaystyle d}$${\displaystyle \delta }$${\displaystyle B}$${\displaystyle d}$${\displaystyle \lambda }$${\displaystyle C(B,S)}$${\displaystyle 2r_{o}-1}$${\displaystyle \left(\left({\dfrac {\delta -\left({\dfrac {\lambda }{d}}\right)}{1-\left({\dfrac {\lambda }{d}}\right)}}\right)\right)^{2}}$

が正則グラフから導出されるとします。したがって、 の変数の数は で、制約の数は です。Alon-Chung ^[4]によれば、がサイズ のの頂点のサブセットである場合、によって誘導されるサブグラフに含まれる辺の数は最大 です。 ${\displaystyle B}$${\displaystyle d}$${\displaystyle G}$${\displaystyle C(B,S)}$${\displaystyle \left({\dfrac {dn}{2}}\right)}$${\displaystyle n}$${\displaystyle X}$${\displaystyle G}$${\displaystyle \gamma n}$${\displaystyle X}$${\displaystyle G}$${\displaystyle \left({\dfrac {dn}{2}}\right)\left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\gamma \right)\right)}$

その結果、どの変数セットも少なくとも制約を隣接変数として持つことになります。したがって、制約あたりの変数の平均数は、次のようになります。${\displaystyle \left({\dfrac {dn}{2}}\right)\left(\gamma ^{2}+\left({\dfrac {\lambda }{d}}\right)\gamma \left(1-\gamma \right)\right)}$${\displaystyle \gamma n}$${\displaystyle \left({\dfrac {({\dfrac {2nd}{2}})\left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\gamma \right)\right)}{\gamma n}}\right)}$ ${\displaystyle =d\left(\gamma +({\dfrac {\lambda }{d}})\left(1-\gamma \right)\right)}$ ${\displaystyle \rightarrow (2)}$

したがって、 の場合、相対重み のワードは のコードワードにはなり得ません。 に対して不等式が満たされます。したがって、 は相対重み またはそれ以下のゼロ以外のコードワードを持つことはできません 。 ${\displaystyle d\left(\gamma +({\dfrac {\lambda }{d}})\left(1-\gamma \right)\right)<\gamma d}$${\displaystyle \left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\gamma \right)\right)}$${\displaystyle C(B,S)}$${\displaystyle (2)}$${\displaystyle \gamma <\left({\dfrac {1-({\dfrac {\lambda }{d}})}{\delta -({\dfrac {\lambda }{d}})}}\right)}$${\displaystyle C(B,S)}$${\displaystyle \left({\dfrac {\delta -({\dfrac {\lambda }{d}})}{1-({\dfrac {\lambda }{d}})}}\right)^{2}}$

行列 では、 がから離れて有界であると仮定できます。が奇数素数である の値に対して、任意の数の頂点を持つ - 正則二部グラフのシーケンスの明示的な構成があり、シーケンスの 各グラフはラマヌジャン グラフです。これは不等式 を満たすため、ラマヌジャン グラフと呼ばれます。グラフ では、特定の展開特性が、固有値と の間の分離として確認できます。グラフがラマヌジャン グラフである場合、その式は 最終的にになり、 が大きくなります。 ${\displaystyle G}$${\displaystyle \lambda /d}$${\displaystyle 1}$${\displaystyle d}$${\displaystyle d-1}$${\displaystyle d}$${\displaystyle G}$${\displaystyle \lambda (G)\leq 2{\sqrt {d-1}}}$${\displaystyle G}$${\displaystyle d}$${\displaystyle \lambda }$${\displaystyle G}$${\displaystyle (1)}$${\displaystyle 0}$${\displaystyle d}$

以下に記述する反復復号アルゴリズムは、 の頂点と を交互に処理して のコードワードを修正し、次にのコードワードを修正するように切り替えます。ここで、グラフの片側の頂点に関連付けられたエッジは、その側の他の頂点には接続されません。実際、ノード セットとがどの順序で処理されるかは重要ではありません。頂点処理は並列で実行することもできます。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle G}$${\displaystyle C_{o}}$${\displaystyle A}$${\displaystyle C_{o}}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$

デコーダーは、エラー数未満の任意のコードワードを正しく回復するデコーダーを表します。 ${\displaystyle \mathbb {D} :\mathbb {F} ^{d}\rightarrow C_{o}}$${\displaystyle C_{o}}$${\displaystyle \left({\dfrac {d}{2}}\right)}$

受信した単語: 出力:${\displaystyle w=(w_{e}),e\in E}$
${\displaystyle z\leftarrow w}$
For ${\displaystyle t\leftarrow 1}$ to ${\displaystyle m}$ do //${\displaystyle m}$ is the number of iterations
{ if (${\displaystyle t}$ is odd) // Here the algorithm will alternate between its two vertex sets.
${\displaystyle X\leftarrow A}$
else ${\displaystyle X\leftarrow B}$
Iteration ${\displaystyle t}$: For every ${\displaystyle v\in X}$, let ${\displaystyle (z)_{v}\leftarrow \mathbb {D} ((z)_{v})}$ // Decoding ${\displaystyle z_{v}}$ to its nearest codeword.
}
${\displaystyle z}$

は二部なので、頂点の集合は辺集合の分割= を誘導します。集合は別の分割=を誘導します。 ${\displaystyle G}$${\displaystyle A}$${\displaystyle E}$${\displaystyle \cup _{v\in A}E_{v}}$${\displaystyle B}$${\displaystyle E}$${\displaystyle \cup _{v\in B}E_{v}}$

を受信ベクトルとし、 を思い出してください。アルゴリズムの最初の反復は、 によって誘導されるコードの完全なデコードをごとに適用することから構成されます。これは、 ごとに、ベクトルを の最も近いコードワードの 1 つに置き換えることを意味します。 のエッジのサブセットは に対して互いに素であるため、 のこれらの サブベクトルのデコードは並列に実行できます。 ${\displaystyle w\in \{0,1\}^{N}}$${\displaystyle N=dn}$${\displaystyle E_{v}}$${\displaystyle v\in A}$${\displaystyle v\in A}$${\displaystyle \left(w_{v(1)},w_{v(2)},\ldots ,w_{v(d)}\right)}$${\displaystyle C_{o}}$${\displaystyle E_{v}}$${\displaystyle v\in A}$${\displaystyle n}$${\displaystyle w}$

この反復により、新しいベクトル が生成されます。次の反復では、前の手順を に適用しますが、を に置き換えます。つまり、 の頂点によって誘導されるすべてのサブベクトルをデコードします。以降の反復では、 の頂点によって誘導されるサブベクトルと の頂点によって誘導されるサブベクトルに並列デコードを交互に適用して、これらの 2 つの手順を繰り返します。注: [およびが完全な二部グラフである場合、は と 自身との積符号であり、上記のアルゴリズムは積符号の自然な困難な反復デコードに簡約されます]。 ${\displaystyle z}$${\displaystyle z}$${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$
${\displaystyle d=n}$${\displaystyle G}$${\displaystyle C}$${\displaystyle C_{o}}$

ここで、反復回数はです。一般に、上記のアルゴリズムは、 の値に対して、ハミング重みが を超えないコードワードを訂正できます。ここで、復号化アルゴリズムは、エラーベクトルの重みが 未満である場合にコードワードを返す、サイズと深さの回路として実装されています。 ${\displaystyle m}$${\displaystyle \left({\dfrac {(\log {n})}{\log(2-\alpha )}}\right)}$${\displaystyle ({\dfrac {1}{2}}).\alpha N\delta \left(({\dfrac {\delta }{2}})-({\dfrac {\lambda }{d}})\right)=\left(({\dfrac {1}{4}}).\alpha N(\delta ^{2}-O({\dfrac {\lambda }{d}})\right)}$${\displaystyle \alpha <1}$${\displaystyle O(N\log {N})}$${\displaystyle O(\log {N})}$${\displaystyle \alpha N\delta ^{2}(1-\epsilon )/4}$

が十分に高い次数のラマヌジャン グラフである場合、任意の に対して、復号化アルゴリズムはラウンドでエラーを訂正できます(ここで、ビッグ表記は への依存性を隠します)。これは、単一のプロセッサ上で線形時間で実装できます。プロセッサ上では、各ラウンドを定数時間で実装できます。${\displaystyle G}$${\displaystyle \alpha <1}$${\displaystyle ({\dfrac {\alpha \delta _{o}^{2}}{4}})(1-\in )N}$${\displaystyle O(\log {n})}$${\displaystyle O}$${\displaystyle \alpha }$${\displaystyle n}$

Since the decoding algorithm is insensitive to the value of the edges and by linearity, we can assume that the transmitted codeword is the all zeros - vector. Let the received codeword be ${\displaystyle w}$. The set of edges which has an incorrect value while decoding is considered. Here by incorrect value, we mean ${\displaystyle 1}$ in any of the bits. Let ${\displaystyle w=w^{0}}$ be the initial value of the codeword, ${\displaystyle w^{1},w^{2},\ldots ,w^{t}}$ be the values after first, second . . . ${\displaystyle t}$ stages of decoding. Here, ${\displaystyle X^{i}={e\in E|x_{e}^{i}=1}}$, and ${\displaystyle S^{i}={v\in V^{i}|E_{v}\cap X^{i+1}!=\emptyset }}$. Here ${\displaystyle S^{i}}$ corresponds to those set of vertices that was not able to successfully decode their codeword in the ${\displaystyle i^{th}}$ round. From the above algorithm ${\displaystyle S^{1}<S^{0}}$ as number of unsuccessful vertices will be corrected in every iteration. We can prove that ${\displaystyle S^{0}>S^{1}>S^{2}>\cdots }$ is a decreasing sequence. In fact, ${\displaystyle |S_{i+1}|<=({\dfrac {1}{2-\alpha }})|S_{i}|}$. As we are assuming, ${\displaystyle \alpha <1}$, the above equation is in a geometric decreasing sequence. So, when ${\displaystyle |S_{i}|<n}$, more than ${\displaystyle log_{2-\alpha }n}$ rounds are necessary. Furthermore, ${\displaystyle \sum |S_{i}|=n\sum ({\dfrac {1}{(2-\alpha )^{i}}})=O(n)}$, and if we implement the ${\displaystyle i^{th}}$ round in ${\displaystyle O(|S_{i}|)}$ time, then the total sequential running time will be linear.

1. It is lengthy process as the number of iterations ${\displaystyle m}$ in decoder algorithm takes is ${\displaystyle [(\log {n})/(\log(2-\alpha ))]}$
2. Zemor's decoding algorithm finds it difficult to decode erasures. A detailed way of how we can improve the algorithm is

given in.^[5]

• Expander codes
• Tanner graph
• Linear time encoding and decoding of error-correcting codes