折り畳まれた葦 ― ソロモンの暗号

上記の定義は、図によってより明確になる。${\displaystyle m=3}$、 どこ${\displaystyle m}$は折り畳みパラメータです。

メッセージは次のように表されます。${\displaystyle f(X)}$、リード・ソロモン符号化を使用してエンコードすると、次の値で構成される。${\displaystyle f}$で${\displaystyle x_{0},x_{1},x_{2},\ldots ,x_{n-1}}$、 どこ${\displaystyle x_{i}=\gamma ^{i}}$。

次に、3つの要素のグループでバンドリングを行い、長さのコードワードを作成します。${\displaystyle n/3}$アルファベット順${\displaystyle \mathbb {F} _{q}^{3}}$。

ここで注目すべき点は、実証された折りたたみ操作は速度を変えないということである。${\displaystyle R}$オリジナルのリード・ソロモン符号の。

これを証明するために、線形${\displaystyle [n,k,d]_{q}}$コード、長さ${\displaystyle n}$、寸法${\displaystyle k}$距離​${\displaystyle d}$.${\displaystyle m}$折りたたみ操作により、${\displaystyle \left[{\tfrac {n}{m}},{\tfrac {k}{m}},{\tfrac {d}{m}}\right]_{q^{m}}}$コード。これにより、レート${\displaystyle R={\tfrac {k}{n}}}$同じになるでしょう。

折り畳みリード・ソロモン符号は、基本的にリード・ソロモン符号と同じですが、より大きなアルファベットで表されます。これがどのように役立つかを示すために、次のような折り畳みリード・ソロモン符号を考えてみましょう。${\displaystyle m=3}$同じエラー率におけるリード・ソロモン符号と折り畳みリード・ソロモン符号の復号${\displaystyle \rho }$これらはほぼ同じ計算負荷のタスクです。折り畳まれたリード・ソロモン符号の受信語を展開し、それを元のリード・ソロモン符号の受信語として扱い、リード・ソロモンリスト復号アルゴリズムを実行できます。明らかに、このリストには距離内のすべての折り畳まれたリード・ソロモン符号語が含まれます。${\displaystyle \rho }$受け取った言葉に、削除できる余分なものがいくつか付いています。

また、折り畳まれたリード・ソロモン符号の復号はより容易な作業です。エラーの3分の1を訂正したいとしましょう。選択された復号アルゴリズムは、リード・ソロモン符号化の3番目のシンボルごとにエラーを訂正するエラーパターンを訂正する必要があります。しかし、折り畳み後、このエラーパターンはすべてのシンボルを破損します。${\displaystyle \mathbb {F} _{q}^{3}}$そして、エラー訂正の必要性を排除します。このエラーの伝播は、図の説明では青色で示されています。これは、エラーの割合が一定の場合、${\displaystyle \rho ,}$折り返し処理によって、チャネルがエラーを分散させる柔軟性が低下し、結果として修正が必要なエラーパターンの数が減少する。

これはウェルチ・ベルレカンプ型の補間法です（ウェルチ・ベルレカンプアルゴリズムの高次元への一般化と見なせるため）。コードワードを受け取ったとしましょう。${\displaystyle y}$の${\displaystyle m}$折り畳まれたリード・ソロモン符号は以下に示すとおりである。

${\displaystyle \left({\begin{bmatrix}y_{0}\\y_{1}\\y_{2}\\\cdots \\y_{m-1}\end{bmatrix}},{\begin{bmatrix}y_{m}\\y_{m+1}\\y_{m+2}\\\cdots \\y_{2m-1}\end{bmatrix}},\ldots ,{\begin{bmatrix}y_{n-m}\\y_{n-m+1}\\y_{n-m+2}\\\cdots \\y_{n-1}\end{bmatrix}}\right)}$

非ゼロ多項式を補間します

${\displaystyle Q(X,Y_{1},\ldots ,Y_{s})=A_{0}(X)+A_{1}(X)Y_{1}+\cdots +A_{s}(X)Y_{s},\qquad {\begin{cases}\deg(A_{i})\leqslant D&1\leqslant i\leqslant s\\\deg(A_{0})\leqslant D+k-1&\end{cases}}}$

慎重に選択された次数パラメータを使用すること${\displaystyle D}$。

${\displaystyle D=\left\lfloor {\frac {N(m-s+1)-k+1}{s+1}}\right\rfloor }$

したがって、補間要件は次のようになります。

${\displaystyle Q\left(\gamma ^{im+j},y_{im+j},y_{im+j+1},\ldots ,y_{im+j+s-1}\right)=0,\quad {\text{for}}\quad i=0,1,\ldots ,{\tfrac {n}{m}}-1,j=0,1,\ldots ,m-s.}$

すると、単項式の数は${\displaystyle Q(X,Y_{1},\ldots ,Y_{s})}$は

${\displaystyle (D+1)s+D+k=(D+1)(s+1)+k-1>N(m-s+1)}$

単項式の数は${\displaystyle Q(X,Y_{1},\ldots ,Y_{s})}$は補間条件の数よりも大きい。以下の補題がある。

補題１。${\displaystyle 0\neq Q\in \mathbb {F} _{q}[X,Y_{1},\ldots ,Y_{s}]}$上記の補間条件を満たすものは、次の同次線形システムを解くことによって見つけることができる。${\displaystyle \mathbb {F} _{q}}$最大で${\displaystyle Nm}$制約と変数。さらに、この補間は次のように実行できます。${\displaystyle O(Nm\log ^{2}(Nm)\log \log(Nm))}$作戦${\displaystyle \mathbb {F} _{q}}$[ ^{3 ]​}

この補題は、補間ステップがほぼ線形時間で実行できることを示している。

ここまでで、多変数多項式に必要なすべてのことを説明しました。${\displaystyle Q(X,Y_{1},\ldots ,Y_{s})}$残りの作業は、メッセージ多項式に焦点を当てることです。${\displaystyle f(X)}$。

補題2.候補メッセージ多項式${\displaystyle f(X)\in \mathbb {F} [X]}$次数が最大で の多項式です${\displaystyle k-1}$折り畳みリード・ソロモン符号化が受信語と一致する${\displaystyle y}$少なくとも${\displaystyle t}$列

${\displaystyle t>{{D+k-1} \over {m-s+1}},}$

それから ${\displaystyle Q(X,f(X),f(\gamma X),\ldots ,f(\gamma _{s-1}X))=0.}$^{[ 4 ]}

ここで「同意する」とは、${\displaystyle m}$列の値は、コードワード内の対応する値と一致する必要があります。${\displaystyle y}$。

この補題は、そのような多項式が${\displaystyle Q(X,Y_{1},\ldots ,Y_{s})}$これらのメッセージ多項式に対して満たされなければならない代数的条件を提示する${\displaystyle f(x)}$私たちが関心を持っているのはリストのデコードです。

補題2とパラメータを組み合わせる${\displaystyle D}$、 我々は持っています

${\displaystyle t(m-s+1)>{\frac {N(m-s+1)+s(k-1)}{s+1}}}$

さらに、復号化の限界値を取得できます。

${\displaystyle t\geqslant {\frac {N}{s+1}}+{\frac {s}{s+1}}\cdot {\frac {k}{m-s+1}}=N\left({\frac {1}{s+1}}+{\frac {s}{s+1}}\cdot {\frac {mR}{m-s+1}}\right)}$

分数的一致度は

${\displaystyle {\dfrac {1}{s+1}}+{\dfrac {s}{s+1}}\cdot {\dfrac {mR}{m-s+1}}}$

このステップでは、すべての多項式を見つける方法に焦点を当てます。${\displaystyle f\in {\mathbb {F} _{q}[X]}}$学位は${\displaystyle k-1}$そして、ステップ 1 から得られる方程式を満たす。

${\displaystyle A_{0}(X)+A_{1}(X)f(X)+A_{2}(X)f(\gamma X)+\cdots +A_{s}(X)f(\gamma ^{s-1}X)=0}$

上記の式は線形システム方程式を形成するので${\displaystyle \mathbb {F} _{q}}$係数において${\displaystyle f_{0},f_{1},\ldots ,f_{k-1}}$多項式の

${\displaystyle f(X)=f_{0}+f_{1}X+\cdots +f_{k-1}X^{k-1},}$

上記の方程式の解はアフィン部分空間である${\displaystyle \mathbb {F} _{q}^{k}}$この事実が、効率的なアルゴリズムを生み出す鍵となるポイントです。つまり、線形システムを解くことができるのです。

解の次元はどれくらい大きいのか、という疑問が生じるのは当然です。次元に上限はあるのでしょうか？効率的なリスト復号アルゴリズムを構築する上で、上限を持つことは非常に重要です。なぜなら、任意の復号問題に対して、すべての符号語を単純に出力できるからです。

実際、以下の補題が示すように、上限は確かに存在します。

補題 3.順序が${\displaystyle \gamma }$少なくとも${\displaystyle k}$（特に${\displaystyle \gamma }$が原始的である場合、解の次元は最大で${\displaystyle s-1}$[ ^{5 ]​}

この補題は、解空間の次元の上限を示している。

最後に、上記の分析に基づいて、以下の定理が得られます。

定理１．折り畳まれたリード・ソロモン符号について${\displaystyle FRS_{q}^{(m)}[n,k]}$ブロック長${\displaystyle N={\tfrac {n}{m}}}$そして評価する${\displaystyle R={\tfrac {k}{n}},}$以下のことはすべての整数に当てはまる。${\displaystyle s,1\leqslant s\leqslant m}$受信した単語が与えられた場合${\displaystyle y\in (\mathbb {F} _{q}^{m})^{N}}$、 で${\displaystyle O((Nm\log q)^{2})}$時間内に、最大次元の部分空間の基底を見つけることができる。${\displaystyle s-1}$すべてのメッセージ多項式を含む${\displaystyle f\in \mathbb {F} _{q}[X]}$次数が${\displaystyle k}$FRSエンコーディングが異なる${\displaystyle y}$せいぜい一部

${\displaystyle {\frac {s}{s+1}}\left(1-{\frac {mR}{m-s+1}}\right)}$

の${\displaystyle N}$符号語の位置。

いつ${\displaystyle s=m=1}$すると、これは最大で分数までの一意の復号アルゴリズムに還元されることがわかります。${\displaystyle (1-R)/2}$エラーの数。言い換えれば、一意の復号アルゴリズムはリスト復号アルゴリズムの特殊機能として扱うことができます。その量は約${\displaystyle n^{O(1/\varepsilon )}}$リストデコード半径を達成するパラメータ選択の場合${\displaystyle 1-R-\varepsilon }$。

定理1は、誤差半径がどれくらい大きくなるかを正確に示している。

これでようやく解のサブスペースが得られました。しかし、まだ1つの問題が残っています。最悪の場合のリストサイズは${\displaystyle n^{\Omega (1/\varepsilon )}}$しかし、実際に近接するコードワードのリストは、その部分空間内のごく一部にすぎません。そのため、部分空間を絞り込むための何らかの処理が必要です。この処理には、${\displaystyle q^{s}}$最悪の場合の実行時間。残念ながら、折り畳まれたリード・ソロモン符号のリストサイズの上限を改善する方法がわからないため、実行時間を改善する方法もわかりません。

可能なすべての次数から慎重に部分集合を選択してコードを変更すれば、状況は改善する。${\displaystyle k-1}$多項式をメッセージとして使用すると、リストサイズは大幅に小さくなり、レートの低下もわずかであることがわかっています。これについては次のステップで簡単に説明します。

折り畳まれたリード・ソロモン符号の復号問題を、補間ステップに使用する線形システムと、候補解部分空間を見つけるための線形システムの2つに分解することで、復号問題の複雑さを2次まで低減することに成功した。しかし、最悪の場合、出力リストのサイズの上限はかなり悪くなる。

ステップ2で述べたように、可能なすべての次数から部分集合だけを慎重に選択すれば${\displaystyle k-1}$多項式をメッセージとして用いることで、リストのサイズを大幅に削減できます。ここでは、その議論をさらに詳しく見ていきましょう。

この目標を達成するために、係数ベクトルを制限するというアイデアが考えられます。${\displaystyle (f_{0},f_{1},\ldots ,f_{k-1})}$特別なサブセットへ${\displaystyle \nu \subseteq \mathbb {F} _{q}^{k}}$これは以下の2つの条件を満たします。

条件1.セット${\displaystyle \nu }$十分に大きい必要がある（${\displaystyle |\nu |\geq q^{(1-\varepsilon )k}}$)

これは、レートが最大で係数だけ減少することを確実にするためです。${\displaystyle (1-\varepsilon )}$。

条件2.セット${\displaystyle \nu }$どの部分空間とも低い交差を持つべきである${\displaystyle S}$寸法${\displaystyle s}$満足${\displaystyle S\subset \mathbb {F} _{q}^{k}}$そして${\displaystyle |S\cap \nu |\leqslant L.}$このような部分集合は、部分空間回避部分集合と呼ばれる。

最悪の場合のリストサイズの上限は${\displaystyle n^{\Omega (1/\varepsilon )}}$、そしてそれは比較的小さな境界に縮小することができる${\displaystyle O(1/\varepsilon ^{2})}$部分空間回避型部分集合を用いることによって。

このステップでは、ステップ 2 で得られた解部分空間の各要素をチェックする必要があるため、${\displaystyle q^{s}}$最悪の場合の時間（${\displaystyle s}$は解部分空間の次元である。

DvirとLovettは、Guruswamiの研究に基づいて結果を改善し、リストのサイズを定数にまで削減することに成功した。

ここでは、解部分空間を剪定するために用いられるアイデアのみを紹介します。剪定プロセスの詳細については、参考文献に記載されているGuruswami、Dvir、Lovettの論文を参照してください。

ステップ3を考慮しない場合、このアルゴリズムは2乗時間で実行できます。このアルゴリズムの概要を以下に示します。