リストのデコード

符号理論では、リスト復号法は、誤り率が大きい場合の誤り訂正符号の一意復号法の代替法です。この概念は、1950 年代にエリアスによって提案されました。リスト復号法の基本的な考え方は、復号アルゴリズムが単一の可能なメッセージを出力する代わりに、そのうちの 1 つが正しい可能性のあるリストを出力するというものです。これにより、一意復号法で許容されるよりも多くのエラーを処理できます。

符号理論における一意の復号モデルは、受信したワードから 1 つの有効なコードワードを出力するように制約されており、エラーの割合がこれより大きいことは許容できませんでした。このため、確率的ノイズ モデル (シャノンが提案) と敵対的ノイズ モデル (リチャード ハミングが検討) のエラー訂正パフォーマンスの間にギャップが生じました。1990 年代半ば以降、符号理論コミュニティによるアルゴリズムの大幅な進歩により、このギャップは埋められました。この進歩の多くは、リスト復号と呼ばれる緩和されたエラー訂正モデルに基づいています。リスト復号では、デコーダーは最悪の病的なエラー パターンに対してコードワードのリストを出力し、実際に送信されたコードワードが出力リストに含まれます。ただし、一般的なエラー パターンの場合、デコーダーは受信したワードに対して一意の単一のコードワードを出力します。これはほぼ常に当てはまります (ただし、すべてのコードに当てはまるとは限りません)。ここでの改善は、エラー訂正パフォーマンスが 2 倍になるという点で重要です。これは、デコーダーが最小距離の半分の障壁に制限されなくなったためです。このモデルは非常に魅力的です。なぜなら、コードワードのリストを持っている方が、ただ諦めるよりも確実に優れているからです。リストデコードの概念は、複雑性理論において多くの興味深い応用があります。

チャネル ノイズをモデル化する方法は、信頼性の高い通信が可能な速度を制御するという点で重要な役割を果たします。チャネルの動作をモデル化する考え方には、主に 2 つの流派があります。

• シャノンが研究した確率的ノイズモデルでは、チャネルの確率的動作がよくわかっており、エラーが多すぎたり少なすぎたりする確率が低いという意味で、チャネルノイズが正確にモデル化されます。
• ハミングによって考えられた最悪のケースまたは敵対的ノイズ モデル。このモデルでは、チャネルは、合計エラー数の制限に従ってコードワードを任意に破損する敵対者として機能します。

リストデコーディングのハイライトは、敵対的ノイズ条件下でも、訂正可能なエラーの割合と割合の間で情報理論的に最適なトレードオフを実現できることです。したがって、ある意味では、これは、より弱い確率的ノイズ モデルの場合に可能なレベルまでエラー訂正のパフォーマンスを向上させることに似ています。

を誤り訂正符号とします。言い換えると、は長さ、次元、サイズ のアルファベット上の最小距離の符号です。リスト復号化問題は次のように定式化できます。 ${\displaystyle {\mathcal {C}}}$${\displaystyle (n,k,d)_{q}}$${\displaystyle {\mathcal {C}}}$${\displaystyle n}$${\displaystyle k}$${\displaystyle d}$${\displaystyle \Sigma }$${\displaystyle q}$

入力:受信した単語、エラー範囲${\displaystyle x\in \Sigma ^{n}}$ ${\displaystyle e}$

出力:からのハミング距離が最大 であるすべてのコードワードのリスト。 ${\displaystyle x_{1},x_{2},\ldots ,x_{m}\in {\mathcal {C}}}$${\displaystyle x}$${\displaystyle e}$

受信語（これは送信されたコードワード のノイズバージョンです）が与えられると、デコーダーは受信語に「最も近い」コードワードに賭けることで、送信されたコードワードを出力しようとします。2 つのコードワード間のハミング距離は、受信語が与えられるとデコーダーによって最も近いコードワードを見つけるための測定基準として使用されます。 がコード の最小ハミング距離である場合、位置が正確に だけ異なる2 つのコードワードと が存在します。ここで、受信語がコードワード と から等距離にある場合、デコーダーは と のどちらを元の送信されたコードワードとして出力すべきかを決定できないため、明確なデコードは不可能になります。その結果、最小距離の半分は、一意のデコードのみを主張する場合、それを超えると明確なエラー訂正が不可能になる組み合わせの障壁として機能します。しかし、上記で検討したような受信語は最悪の場合にのみ発生し、ハミングボールが高次元空間に詰め込まれる方法を見ると、最小距離の半分を超えるエラーパターンの場合でも、受信語からハミング距離内にあるコードワードは 1 つしかありません。この主張は、自然なアンサンブルから選択されたランダムコードに対して高い確率で成立することが示されており、十分に研究され、実際のアプリケーションで非常に普及しているリードソロモンコードの場合はさらに高い確率で成立します。実際、 q元対称チャネルの容量定理に関するシャノンの証明は、ランダムコードに対する上記の主張に照らして考えることができます。 ${\displaystyle y}$${\displaystyle c}$${\displaystyle d}$${\displaystyle {\mathcal {C}}}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$${\displaystyle d}$${\displaystyle y}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$${\displaystyle y}$${\displaystyle e}$${\displaystyle c}$${\displaystyle e}$

リストデコーディングの規定により、最悪のエラーに対して、デコーダーは小さなコードワードのリストを出力することができます。コンテキスト固有の情報や副次的な情報があれば、リストを整理して元の送信されたコードワードを復元できる可能性があります。したがって、一般的に、これは一意のデコーディングよりも強力なエラー回復モデルであると思われます。

多項式時間のリスト復号アルゴリズムが存在するためには、受信語の周りの半径 のハミング球(ブロック長 に関する誤り率) のコードワード数が少ないという組み合わせ上の保証が必要です。これは、リスト サイズ自体がアルゴリズムの実行時間の下限であることは明らかだからです。したがって、リスト サイズはコードのブロック長の多項式である必要があります。この要件の組み合わせ上の結果として、コードのレートに上限が課せられます。リスト復号は、この上限を満たすことが期待されます。レート のコードが存在し、誤り率が に近づくまでリスト復号できることが非構成的に示されています。この量は、文献ではリスト復号容量と呼ばれています。これは、一意の復号モデルと比較して大幅な利点であり、2 倍の誤りを訂正できる可能性があります。当然、メッセージを復元するには、送信されたシンボルの少なくとも一部が正しい必要があります。これは、デコードを実行するために必要な正しいシンボルの数に関する情報理論的な下限であり、リスト デコードを使用すると、この情報理論的な制限を潜在的に達成できます。ただし、この可能性を実現するには、明示的なコード (多項式時間で構築できるコード) と、エンコードとデコードを実行するための効率的なアルゴリズムが必要です。 ${\displaystyle pn}$${\displaystyle r}$${\displaystyle p}$${\displaystyle n}$${\displaystyle n}$${\displaystyle R}$${\displaystyle 1-R}$${\displaystyle 1-R}$${\displaystyle R}$

任意の誤り率と整数に対して、コードは、リストサイズが最大で誤り率 までリスト復号可能である、または任意の に対して、からのハミング距離内にあるコードワードの数が最大で${\displaystyle 0\leqslant p\leqslant 1}$${\displaystyle L\geqslant 1}$${\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}$${\displaystyle p}$${\displaystyle L}$${\displaystyle (p,L)}$${\displaystyle y\in \Sigma ^{n}}$${\displaystyle c\in C}$${\displaystyle pn}$${\displaystyle y}$${\displaystyle L.}$

コードのリスト デコード可能性と、最小距離やレートなどの他の基本的なパラメータとの関係は、かなりよく研究されています。すべてのコードは、最小距離の半分を超えてジョンソン半径と呼ばれる境界まで、小さなリストを使用してリスト デコードできることが示されています。これは、リストデコード半径が よりもはるかに大きい、レートの良いリスト デコード可能なコードの存在を証明するため、非常に重要です。言い換えると、ジョンソン境界により、 よりもわずかに大きい半径のハミング ボールに多数のコードワードが存在する可能性が排除されます。つまり、リスト デコードではるかに多くのエラーを修正できることを意味します。 ${\displaystyle (p,L)}$${\displaystyle {\tfrac {d}{2}}.}$${\displaystyle {\tfrac {d}{2}}}$

定理 (リスト復号容量)および とします。次の 2 つのステートメントは、十分に大きいブロック長 に対して成立します。 ${\displaystyle q\geqslant 2,0\leqslant p\leqslant 1-{\tfrac {1}{q}}}$${\displaystyle \epsilon \geqslant 0.}$${\displaystyle n}$

i) の場合、-リストのデコード可能なコードが存在します。${\displaystyle R\leqslant 1-H_{q}(p)-\epsilon }$${\displaystyle (p,O(1/\epsilon ))}$

ii) の場合、すべての-list デコード可能なコードは を持ちます。${\displaystyle R\geqslant 1-H_{q}(p)+\epsilon }$${\displaystyle (p,L)}$${\displaystyle L=q^{\Omega (n)}}$

どこ

${\displaystyle H_{q}(p)=p\log _{q}(q-1)-p\log _{q}p-(1-p)\log _{q}(1-p)}$

は、連続性によって次のように拡張され、定義される - 元エントロピー関数である。${\displaystyle q}$${\displaystyle p\in (0,1)}$${\displaystyle [0,1].}$

つまり、チャネル容量に近づくレートでは、効率的なデコード アルゴリズムを可能にする多項式サイズのリストを持つリスト デコード可能なコードが存在するのに対し、チャネル容量を超えるレートでは、リスト サイズが指数関数的になり、効率的なデコード アルゴリズムの存在が排除されます。

リスト復号容量の証明は、 -ary 対称チャネルの容量と正確に一致するという点で重要です。実際、「リスト復号容量」という用語は、リスト復号における敵対的チャネルの容量として読み取る必要があります。また、リスト復号容量の証明は、コードのレートとリスト復号で訂正できるエラーの割合との間の最適なトレードオフを正確に示す重要な結果です。 ${\displaystyle q}$${\displaystyle qSC_{p}}$

証明の背後にある考え方は、ランダムなコードが選択され、レートが一定である限り高い確率でリスト復号可能であることを示す、バイナリ対称チャネル の容量に関するシャノンの証明に似ています。上記の量を超えるレートの場合、リストのサイズが超多項式的に大きくなること が示されます。${\displaystyle BSC_{p}}$${\displaystyle (p,L)}$${\displaystyle R\leqslant 1-H_{q}(p)-{\tfrac {1}{L}}.}$${\displaystyle L}$

「悪い」イベントとは、受信した単語とメッセージが与えられたときに、すべての に対してとなるイベントとして定義されます。ここで、 は修正したいエラーの割合であり、 は受信した単語を中心とする 半径 のハミング球です。${\displaystyle y\in [q]^{n}}$${\displaystyle L+1}$${\displaystyle m_{0},\ldots ,m_{L}\in [q]^{k},}$${\displaystyle {\mathcal {C}}(m_{i})\in B(y,pn)}$${\displaystyle 0\leqslant i\leqslant L}$${\displaystyle p}$${\displaystyle B(y,pn)}$${\displaystyle pn}$${\displaystyle y}$

さて、固定メッセージに関連付けられたコードワードがハミングボール内に存在する確率は次のように与えられる。 ${\displaystyle {\mathcal {C}}(m_{i})}$${\displaystyle m_{i}\in [q]^{k}}$${\displaystyle B(y,pn)}$

${\displaystyle \Pr \left[C(m_{i})\in B(y,pn)\right]={\frac {\mathrm {Vol} _{q}(y,pn)}{q^{n}}}\leqslant q^{-n(1-H_{q}(p))},}$

ここで、量は、受信した単語を中心とする半径 のハミング球の体積です。上記の関係の不等式は、ハミング球の体積の上限から生じます。量は、 内の任意の単語を中心とする半径 のハミング球の体積を非常に正確に推定します。言い換えると、ハミング球の体積は並進不変です。証明の概要を続けるために、確率論の和集合上界を思い起こさせます。これは、与えられたものに対して悪いイベントが発生する確率の上限が量 で制限されることを示しています。 ${\displaystyle Vol_{q}(y,pn)}$${\displaystyle pn}$${\displaystyle y}$${\displaystyle q^{H_{q}(p)}}$${\displaystyle p}$${\displaystyle [q]^{n}.}$${\displaystyle (y,m_{0},\dots ,m_{L})}$${\displaystyle q^{-n(L+1)(1-H_{q}(p))}}$

上記を念頭に置くと、「あらゆる」悪い出来事が起こる確率は 未満であることが示せます。これを示すために、受信可能なすべての単語と、メッセージのすべての可能なサブセットを調べます。${\displaystyle 1}$${\displaystyle y\in [q]^{n}}$${\displaystyle L}$${\displaystyle [q]^{k}.}$

さて、パート(ii)の証明に移ると、レートがリスト復号能力を超えるとき、すべての の周りには超多項式数のコードワードがあることを示す必要があります。レート の場合、 は超多項式に大きいことを示す必要があります。コードワード を固定します。次に、ランダムに選択したすべての に対して、 ${\displaystyle y\in [q]^{n}}$${\displaystyle |{\mathcal {C}}\cap B(y,pn)|}$${\displaystyle R\geqslant 1-H_{q}(p)+\epsilon }$${\displaystyle c\in {\mathcal {C}}}$${\displaystyle y\in [q]^{n}}$

${\displaystyle \Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]}$

ハミング球は並進不変である。ハミング球の体積の定義と、から一様にランダムに選択されるという事実から、次の式も成り立つ。 ${\displaystyle y}$${\displaystyle [q]^{n}}$

${\displaystyle \Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]={\frac {\mathrm {Vol} (y,pn)}{q^{n}}}\geqslant q^{-n(1-H_{q}(p))-o(n)}}$

ここで、指標変数を定義してみましょう。 ${\displaystyle X_{c}}$

${\displaystyle X_{c}={\begin{cases}1&c\in B(y,pn)\\0&{\text{otherwise}}\end{cases}}}$

ハミングボールの体積の期待値を取ると、

${\displaystyle {\begin{aligned}E[|B(y,pn)|]&=\sum _{c\in {\mathcal {C}}}E[X_{c}]\\[4pt]&=\sum _{c\in {\mathcal {C}}}\Pr[X_{c}=1]\\[4pt]&\geqslant \sum q^{-n(1-H_{q}(p)+o(n))}\\[4pt]&=\sum q^{n(R-1+H_{q}(p)+o(1))}\\[4pt]&\geqslant q^{\Omega (n)}\end{aligned}}}$

したがって、確率的方法により、レートがリスト復号能力を超えると、リストのサイズが超多項式的に大きくなることを示しました。これで、リスト復号能力の証明の概要が完了します。

^{2023年、3つの画期的な研究[1] [2] [3]}を基に、符号理論家は、ランダムな評価ポイントで定義されたリード・ソロモン符号は、高い確率で、線形サイズのアルファベットのリストデコード容量までリストデコード可能であることを示しました。

1995 年から 2007 年にかけて、符号理論コミュニティは、より効率的なリスト復号アルゴリズムを徐々に開発しました。は正規化された距離または相対距離であるジョンソン半径まで復号できるリード ソロモン コードのアルゴリズムが存在します。ただし、リード ソロモン コードの場合、これはエラーの一部が修正できることを意味します。最も有名なリスト復号アルゴリズムのいくつかを以下に示します。 ${\displaystyle 1-{\sqrt {1-\delta }}}$${\displaystyle \delta }$${\displaystyle \delta =1-R}$${\displaystyle 1-{\sqrt {R}}}$

• スーダン '95 – Madhu Sudanによって開発された、エラーまでの効率的なリスト復号化を実現した、リード・ソロモン符号の最初の非自明なリスト復号化アルゴリズム。${\displaystyle 1-{\sqrt {2R}}}$
• Guruswami–Sudan '98 – Madhu Sudan と当時彼の博士課程の学生であったVenkatesan Guruswamiによる、エラーまでのリード–ソロモン符号のリスト復号化のための上記アルゴリズムの改良。${\displaystyle 1-{\sqrt {R}}}$
• Parvaresh–Vardy '05 – 画期的な論文で、Farzad Parvaresh とAlexander Vardy は、低レートで半径を超えてリストデコードできるコードを発表しました。彼らのコードは、通常のリード・ソロモン コードの場合のように相関多項式を評価することによって得られるリード・ソロモン コードのバリエーションです。${\displaystyle 1-{\sqrt {R}}}$${\displaystyle R}$${\displaystyle m\geqslant 1}$${\displaystyle 1}$
• Guruswami–Rudra '06 - さらにもう 1 つの画期的な発見として、Venkatesan Guruswami と Atri Rudra は、リスト復号能力を実現する明示的なコードを提示しました。つまり、任意の に対して半径 までリスト復号できます。言い換えれば、これは最適な冗長性を備えたエラー訂正です。これは、約 50 年間未解決だった疑問に答えるものでした。この研究は、Communications of the ACM の Research Highlights セクション (「近年コンピュータ サイエンスで発表された最も重要な研究成果を特集」) に招待され、2007 年 9 月 21 日発行の Science 誌の「Coding and Computing Join Forces」という記事で取り上げられました。彼らに与えられたコードは、折り畳みリード ソロモン コードと呼ばれ、単なるリード ソロモン コードに過ぎませんが、コードワード シンボルを注意深く束ねることで、より大きなアルファベット上のコードとして見なされます。${\displaystyle 1-R-\epsilon }$${\displaystyle \epsilon >0}$

リード・ソロモン符号は広く普及しており、優れた代数的特性を備えているため、リード・ソロモン符号のリスト復号アルゴリズムは研究者の主な関心事でした。リード・ソロモン符号のリスト復号問題は、次のように定式化できます。

入力: リード・ソロモン符号の場合、のペアが与えられます。ここで、は受信語の 番目のビットであり、は有限体内の異なる点であり、 は誤差パラメータです。 ${\displaystyle [n,k+1]_{q}}$${\displaystyle (\alpha _{i},y_{i})}$${\displaystyle 1\leq i\leq n}$${\displaystyle y_{i}}$${\displaystyle i}$${\displaystyle \alpha _{i}}$${\displaystyle F_{q}}$${\displaystyle e=n-t}$

出力: 目標は、最大で次数 の多項式のうち、少なくとも の値に対してとなるメッセージ長であるものをすべて見つけることです。ここでは、より多くのエラーを許容できるように、 をできるだけ小さくしたいと考えています。 ${\displaystyle P(X)\in F_{q}[X]}$${\displaystyle k}$${\displaystyle p(\alpha _{i})=y_{i}}$${\displaystyle t}$${\displaystyle i}$${\displaystyle t}$

上記の定式化により、リード・ソロモン符号のリスト復号アルゴリズムの一般的な構造は次のようになります。

ステップ 1 : (補間)となる非ゼロの 2 変数多項式を見つけます。 ${\displaystyle Q(X,Y)}$${\displaystyle Q(\alpha _{i},y_{i})=0}$${\displaystyle 1\leq i\leq n}$

ステップ 2 : (根の探索/因数分解)が の因数、つまりとなるようなすべての次数多項式を出力します。これらの多項式のそれぞれについて、の値が少なくとも であるかどうかを確認します。そうであれば、そのような多項式を出力リストに含めます。 ${\displaystyle k}$${\displaystyle p(X)}$${\displaystyle Y-p(X)}$${\displaystyle Q(X,Y)}$${\displaystyle Q(X,p(X))=0}$${\displaystyle p(\alpha _{i})=y_{i}}$${\displaystyle t}$${\displaystyle i\in [n]}$${\displaystyle p(X)}$

二変数多項式は効率的に因数分解できるため、上記のアルゴリズムは多項式時間で実行されます。

いくつかの興味深いコード ファミリのリスト デコード用に開発されたアルゴリズムは、計算複雑性や暗号化 の分野で興味深い応用が見出されています。以下は、符号理論以外の応用のサンプル リストです。

• 一方向順列からのハードコア述語の構築。
• NP 探索問題の証人の予測。
• ブール関数の困難さを増幅します。
• ランダムマトリックスの永久平均ケース硬度。
• 抽出器と疑似乱数ジェネレータ。
• 効率的な裏切り者追跡。

• Madhu Sudanによるリストデコードに関する調査
• マドゥ・スーダンが教えるコースのノート
• ルカ・トレヴィサンが教えたコースのノート
• ベンカテサン・グルスワミが教えたコースのノート
• Atri Rudra が教えたコースのノート
• P. エリアス、「ノイズの多いチャネルのリスト デコード」、技術レポート 335、MIT 電子工学研究所、1957 年。
• P. エリアス、「リストデコード用のエラー訂正コード」、IEEE Transactions on Information Theory、第 37 巻、5 ～ 12 ページ、1991 年。
• JM Wozencraft、「リストデコード」、四半期進捗報告書、MIT 電子工学研究所、第 48 巻、90 ～ 95 ページ、1958 年。
• ベンカテサン・グルスワミ博士論文
• リストデコードにおけるアルゴリズムの結果
• 折り畳みリード・ソロモン符号