グルスワミ・スーダンリスト復号アルゴリズム

入力 ：フィールド${\displaystyle F}$; n 個の異なる要素のペア${\displaystyle {(x_{i},y_{i})_{i=1}^{n}}}$で${\displaystyle F\times F}$; および整数${\displaystyle d}$そして${\displaystyle t}$。

出力：すべての関数のリスト${\displaystyle f:F\to F}$満足

${\displaystyle f(x)}$は多項式である${\displaystyle x}$最大で${\displaystyle d}$

スーダンのアルゴリズムをよりよく理解するために、まず、RSコードのリスト復号アルゴリズムの初期バージョンまたは基本バージョンと考えられる別のアルゴリズム、ベルレカンプ・ウェルチアルゴリズムについて知っておくと良いでしょう。ウェルチとベルレカンプは当初、最適な閾値で多項式時間で問題を解決できるアルゴリズムを考案しました。${\displaystyle t}$である${\displaystyle t\geq (n+d+1)/2}$スーダンのアルゴリズムのメカニズムは、ステップ 1 で有界な 2 変数多項式を計算する必要がある点を除いて、ベルレカンプ-ウェルチのアルゴリズムとほぼ同じです。${\displaystyle (1,k)}$度。ベルレカンプとウェルチのアルゴリズムを改良したリード・ソロモン符号のスーダンのリスト復号アルゴリズムは、次の問題を解決できます。${\displaystyle t=({\sqrt {2nd}})}$この上限は、一意復号の上限よりも優れている。${\displaystyle 1-\left({\frac {R}{2}}\right)}$のために${\displaystyle R<0.07}$。

定義1（加重度）

重量について${\displaystyle w_{x},w_{y}\in \mathbb {Z} ^{+}}$、${\displaystyle (w_{x},w_{y})}$– 単項式の重み付き次数${\displaystyle q_{ij}x^{i}y^{j}}$は${\displaystyle iw_{x}+jw_{y}}$.${\displaystyle (w_{x},w_{y})}$– 多項式の重み付き次数${\displaystyle Q(x,y)=\sum _{ij}q_{ij}x^{i}y^{j}}$は、係数がゼロでない単項式の中で、${\displaystyle (w_{x},w_{y})}$– 単項式の重み付き次数。

例えば、${\displaystyle xy^{2}}$もっている${\displaystyle (1,3)}$-7度

アルゴリズム：

入力:${\displaystyle n,d,t}$; {${\displaystyle (x_{1},y_{1})\cdots (x_{n},y_{n})}$} /* パラメータ l、m は後で設定します。 */

ステップ1：ゼロでない2変数多項式を見つける${\displaystyle Q:F^{2}\mapsto F}$満足

• ${\displaystyle Q(x,y)}$もっている${\displaystyle (1,d)}$重み付き次数最大${\displaystyle D=m+ld}$
• すべての${\displaystyle i\in [n]}$、

ステップ2．Qを既約因子に因数分解する。

ステップ3．すべての多項式を出力する${\displaystyle f}$そのため${\displaystyle (yf(x))}$Qの因数であり、${\displaystyle f(x_{i})=y_{i}}$少なくとも t の値に対して${\displaystyle i\in [n]}$

上記のアルゴリズムが多項式時間で実行され、正しい結果を出力することを証明する必要がある。それは、以下の主張を証明することによって行うことができる。

請求項１：

関数が${\displaystyle Q:F^{2}\to F}$（２）を満たすものが存在するならば、それを多項式時間で見つけることができる。

証拠：

2変数多項式${\displaystyle Q(x,y)}$の${\displaystyle (1,d)}$重み付き次数最大${\displaystyle D}$一意に記述できる${\displaystyle Q(x,y)=\sum _{j=0}^{l}\sum _{k=0}^{m+(lj)d}q_{kj}x^{k}y^{j}}$すると、係数を見つける必要がある$q_{kj}}$制約を満たす${\displaystyle \sum _{j=0}^{l}\sum _{k=0}^{m+(lj)d}q_{kj}x_{i}^{k}y_{i}^{j}=0}$、すべての${\displaystyle i\in [n]}$これは未知数に関する線形方程式です。$q_{kj}}$}。ガウス消去法を用いれば、多項式時間で解を見つけることができます。

請求項２：

もし${\displaystyle (m+1)(l+1)+d{\begin{pmatrix}l+1\\2\end{pmatrix}}>n}$すると関数が存在する${\displaystyle Q(x,y)}$満足させる（２）

証拠：

ゼロでない解が存在することを保証するために、係数の数は${\displaystyle Q(x,y)}$制約の数よりも大きくなければなりません。最大次数は${\displaystyle deg_{x}(Q)}$の${\displaystyle x}$で${\displaystyle Q(x,y)}$m であり、最大次数は${\displaystyle deg_{y}(Q)}$の${\displaystyle y}$で${\displaystyle Q(x,y)}$は${\displaystyle l}$すると、${\displaystyle Q(x,y)}$最大で${\displaystyle m+ld}$線形システムが同次であることを確認する必要がある。${\displaystyle q_{jk}=0}$すべての線形制約を満たします。しかし、解が恒等的にゼロになる可能性があるため、これは（2）を満たしません。非ゼロ解が存在することを保証するには、線形システムの未知数の数が${\displaystyle (m+1)(l+1)+d{\begin{pmatrix}l+1\\2\end{pmatrix}}>n}$非ゼロになる可能性がある${\displaystyle Q(x,y)}$この値はnより大きいので、制約条件よりも変数の数が多くなり、したがってゼロ以外の解が存在します。

請求項３：

もし${\displaystyle Q(x,y)}$は、(2)を満たす関数であり、${\displaystyle f(x)}$関数は(1)を満たし、${\displaystyle t>m+ld}$、 それから${\displaystyle (yf(x))}$分ける${\displaystyle Q(x,y)}$

証拠：

関数を考える${\displaystyle p(x)=Q(x,f(x))}$これは多項式です${\displaystyle x}$そして、それはせいぜい${\displaystyle m+ld}$任意の単項式を考える${\displaystyle q_{jk}x^{k}y^{j}}$の${\displaystyle Q(x)}$。 以来${\displaystyle Q}$もっている${\displaystyle (1,d)}$重み付き次数最大${\displaystyle m+ld}$次のように言える${\displaystyle k+jd\leq m+ld}$したがって、この用語は${\displaystyle q_{kj}x^{k}f(x)^{j}}$は多項式である ${\displaystyle x}$最大で ${\displaystyle k+jd\leq m+ld}$。 したがって${\displaystyle p(x)}$学位は最大で${\displaystyle m+ld}$

次に、${\displaystyle p(x)}$は完全にゼロです。${\displaystyle Q(x_{i},f(x_{i}))}$ゼロになるとき${\displaystyle y_{i}=f(x_{i})}$次のように言える${\displaystyle p(x_{i})}$厳密により大きい場合はゼロになります${\displaystyle m+ld}$ポイント。したがって${\displaystyle p}$次数よりもゼロの数が多いため、恒等的にゼロであり、${\displaystyle Q(x,f(x))\equiv 0}$

最適な値を見つける${\displaystyle m}$そして${\displaystyle l}$。 ご了承ください${\displaystyle m+ld<t}$そして${\displaystyle (m+1)(l+1)+d{\begin{pmatrix}l+1\\2\end{pmatrix}}>n}$ 特定の値に対して ${\displaystyle l}$最小値を計算できます${\displaystyle m}$2番目の条件が成り立つ場合、2番目の条件を入れ替えることで、${\displaystyle m}$最大で${\displaystyle (n+1-d{\begin{pmatrix}l+1\\2\end{pmatrix}})/2-1}$ この値を最初の条件に代入すると、${\displaystyle t}$少なくとも${\displaystyle {\frac {n+1}{l+1}}+{\frac {dl}{2}}}$ 次に、上記の未知パラメータの式を最小化する。${\displaystyle l}$方程式を微分してそれをゼロに等しいとおくことで、それを行うことができます。そうすることで、次の式が得られます。${\displaystyle l={\sqrt {\frac {2(n+1)}{d}}}-1}$ 元に戻すと${\displaystyle l}$価値を${\displaystyle m}$そして${\displaystyle t}$1つ手に入れる ${\displaystyle m\geq {\sqrt {\frac {(n+1)d}{2}}}-{\sqrt {\frac {(n+1)d}{2}}}+{\frac {d}{2}}-1={\frac {d}{2}}-1}$${\displaystyle t>{\sqrt {\frac {2(n+1)d^{2}}{d}}}-{\frac {d}{2}}-1}$${\displaystyle t>{\sqrt {2(n+1)d}}-{\frac {d}{2}}-1}$

を考えて${\displaystyle (n,k)}$有限体上のリード・ソロモン符号${\displaystyle \mathbb {F} =GF(q)}$評価セット付き${\displaystyle (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})}$正の整数${\displaystyle r}$Guruswami-Sudanリストデコーダーはベクトルを受け取ります${\displaystyle \beta =(\beta _{1},\beta _{2},\ldots ,\beta _{n})}$${\displaystyle \in }$$\displaystyle \mathbb {F} ^{n}}$入力として、次数 の多項式のリストを出力します。${\displaystyle \leq k}$これらはコードワードと1対1で対応している。

そのアイデアは、2変数多項式にさらに制約を追加することです。${\displaystyle Q(x,y)}$その結果、制約条件の数と根の数の両方が増加する。

2変数多項式${\displaystyle Q(x,y)}$重複度がゼロである${\displaystyle r}$で${\displaystyle (0,0)}$つまり${\displaystyle Q(x,y)}$学位の期間がない${\displaystyle \leq r}$ここで、x次数は${\displaystyle f(x)}$は、 の任意の x 項の最大次数として定義されます。${\displaystyle f(x)}$${\displaystyle \qquad }$${\displaystyle deg_{x}f(x)}$${\displaystyle =}$${\displaystyle \max _{i\in I}\{i\}}$

例えば：${\displaystyle Q(x,y)=y-4x^{2}}$。

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig1.jpg

したがって、${\displaystyle Q(x,y)}$(0,0)に重複度1の零点を持つ。

させて${\displaystyle Q(x,y)=y+6x^{2}}$。

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig2.jpg

したがって、${\displaystyle Q(x,y)}$(0,0)に重複度1の零点を持つ。

させて${\displaystyle Q(x,y)=(y-4x^{2})(y+6x^{2})=y^{2}+6x^{2}y-4x^{2}y-24x^{4}}$

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig3.jpg

したがって、${\displaystyle Q(x,y)}$(0,0)に重複度2の零点を持つ。

同様に、${\displaystyle Q(x,y)=[(y-\beta )-4(x-\alpha )^{2})][(y-\beta )+6(x-\alpha )^{2})]}$ それから、${\displaystyle Q(x,y)}$に重複度2の零点がある${\displaystyle (\alpha ,\beta )}$。

送信された符号語を${\displaystyle (f(\alpha _{1}),f(\alpha _{2}),\ldots ,f(\alpha _{n}))}$、${\displaystyle (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})}$送信された符号語のサポートセットと受信された符号語のサポートセットは${\displaystyle (\beta _{1},\beta _{2},\ldots ,\beta _{n})}$

アルゴリズムは以下のとおりです。

・補間ステップ

受信ベクトルについて${\displaystyle (\beta _{1},\beta _{2},\ldots ,\beta _{n})}$非ゼロの2変数多項式を構築する${\displaystyle Q(x,y)}$と${\displaystyle (1,k)-}$最大で加重度${\displaystyle d}$そのため${\displaystyle Q}$重複度がゼロである${\displaystyle r}$各ポイントで${\displaystyle (\alpha _{i},\beta _{i})}$どこ${\displaystyle 1\leq i\leq n}$

${\displaystyle Q(\alpha _{i},\beta _{i})=0\,}$

・因数分解のステップ

すべての因数を見つけます${\displaystyle Q(x,y)}$形式${\displaystyle y-p(x)}$そして${\displaystyle p(\alpha _{i})=\beta _{i}}$少なくとも${\displaystyle t}$値${\displaystyle i}$

どこ${\displaystyle 0\leq i\leq n}$＆${\displaystyle p(x)}$次数が の多項式です${\displaystyle \leq k}$

次数 の多項式を思い出してください${\displaystyle \leq k}$これらはコードワードと1対1で対応しています。したがって、このステップではコードワードのリストが出力されます。

命題：

${\displaystyle Q(x,p(x))\equiv 0}$もし${\displaystyle y-p(x)}$は${\displaystyle Q(x,y)}$

証拠：

以来、${\displaystyle y-p(x)}$は${\displaystyle Q(x,y)}$、${\displaystyle Q(x,y)}$次のように表すことができます

${\displaystyle Q(x,y)=L(x,y)(y-p(x))}$${\displaystyle +}$${\displaystyle R(x)}$

どこ、${\displaystyle L(x,y)}$は、${\displaystyle Q(x,y)}$で割る${\displaystyle y-p(x)}$${\displaystyle R(x)}$残りは

さて、もし${\displaystyle y}$に置き換えられます${\displaystyle p(x)}$、 ${\displaystyle Q(x,p(x))}$${\displaystyle \equiv }$${\displaystyle 0}$のみ${\displaystyle R(x)}$${\displaystyle \equiv }$${\displaystyle 0}$

定理：

もし${\displaystyle p(\alpha )=\beta }$、 それから${\displaystyle (x-\alpha )^{r}}$は${\displaystyle Q(x,p(x))}$

証拠：

${\displaystyle Q(x,y)}$${\displaystyle =}$${\displaystyle \sum _{u,v}}$${\displaystyle Q_{u,v}}$${\displaystyle (\alpha ,\beta )}$${\displaystyle (x-\alpha )^{u}}$${\displaystyle (y-\beta )^{v}}$式2より

${\displaystyle Q(x,p(x))}$${\displaystyle =}$${\displaystyle \sum _{u,v}}$${\displaystyle Q_{u,v}}$${\displaystyle (\alpha ,\beta )}$${\displaystyle (x-\alpha )^{u}}$${\displaystyle (p(x)-\beta )^{v}}$

与えられた条件、${\displaystyle p(\alpha )}$${\displaystyle =}$${\displaystyle \beta }$${\displaystyle (p(x)-\beta )}$モジュール${\displaystyle (x-\alpha )}$${\displaystyle =}$${\displaystyle 0}$

したがって、${\displaystyle (x-\alpha )^{u}}$${\displaystyle (p(x)-\beta )^{v}}$モジュール${\displaystyle (x-\alpha )^{u+v}}$${\displaystyle =}$${\displaystyle 0}$

したがって、${\displaystyle (x-\alpha )^{r}}$は${\displaystyle Q(x,p(x))}$。

上記で証明したように、

${\displaystyle t\cdot r>D}$

${\displaystyle t>{\frac {D}{r}}}$

${\displaystyle {\frac {D(D+2)}{2(k-1)}}>n{\begin{pmatrix}r+1\\2\end{pmatrix}}}$ ここで、LHS は係数の数の上限です。${\displaystyle Q(x,y)}$そして右辺は先に証明された補題である。

${\displaystyle D={\sqrt {knr(r-1)}}\,}$

したがって、${\displaystyle t=\left\lceil {\sqrt {kn(1-{\frac {1}{r}})}}\right\rceil }$

代わりの${\displaystyle r=2kn}$、

${\displaystyle t>\left\lceil {\sqrt {kn-{\frac {1}{2}}}}\right\rceil >\left\lceil {\sqrt {kn}}\right\rceil }$

したがって、グルスワミ・スーダンリスト復号アルゴリズムは、リード・ソロモン符号を最大でリスト復号できることが証明された。${\displaystyle 1-{\sqrt {R}}}$エラー。