リストのデコード

符号理論において、リスト復号法は、誤り率の高い誤り訂正符号における一意復号法の代替手法です。この概念は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}$

（p、L)-リストのデコード可能性

任意の誤り率と整数に対して、コードは、リストサイズが最大で誤り率 までリストデコード可能である、または、任意の に対して、 からハミング距離内にあるコードワードの数が最大で${\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].}$

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

リスト復号容量の証明は、-元対称通信路の容量と正確に一致するという点で重要です。実際、「リスト復号容量」という用語は、リスト復号における敵対的通信路の容量として読み替えるべきです。また、リスト復号容量の証明は、符号のレートとリスト復号において訂正可能な誤り率との間の最適なトレードオフを明確に示す重要な結果です。 ${\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 –マドゥ・スーダンが開発した、エラーまでの効率的なリスト復号化を実現したリード・ソロモン符号用の最初の非自明なリスト復号化アルゴリズム。${\displaystyle 1-{\sqrt {2R}}}$
• Guruswami–Sudan '98 – Madhu Sudan と当時彼の博士課程の学生であったVenkatesan Guruswamiによる、エラーまでの Reed–Solomon 符号のリスト復号化のための上記のアルゴリズムの改良。${\displaystyle 1-{\sqrt {R}}}$
• パルヴァレシュ・ヴァーディ '05 – 画期的な論文において、ファルザド・パルヴァレシュとアレクサンダー・ヴァーディは、低レートにおいて半径を超えてリスト復号可能な符号を発表しました。彼らの符号はリード・ソロモン符号の変種であり、通常のリード・ソロモン符号の場合のように相関多項式を評価するのではなく、相関多項式を評価することで得られます。${\displaystyle 1-{\sqrt {R}}}$ ${\displaystyle R}$ ${\displaystyle m\geqslant 1}$ ${\displaystyle 1}$
• Guruswami–Rudra '06 - さらにもう一つの飛躍的進歩として、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 探索問題の証人を予測する。
• ブール関数の困難さを増幅します。
• ランダムマトリックスの永久マトリックスの平均ケース硬度。
• 抽出器と疑似乱数ジェネレータ。
• 効率的な裏切り者追跡。

参照

• 折り畳みリード・ソロモン符号

参考文献

1. Brakensiek, Joshua; Gopi, Sivakanth; Makam, Visu (2023-06-02). 「汎用リード・ソロモン符号によるリスト復号能力の実現」.第55回ACM計算理論シンポジウム議事録. STOC 2023. ニューヨーク州ニューヨーク：Association for Computing Machinery. pp.  1488– 1501. arXiv : 2206.05256 . doi :10.1145/3564246.3585128. ISBN 978-1-4503-9913-5。
2. Guo, Zeyu; Zhang, Zihan (2023-11-06). 「ランダムパンクチャードリードソロモン符号は多項式サイズのアルファベット上でリスト復号能力を実現する」. 2023 IEEE 第64回コンピュータサイエンス基礎シンポジウム (FOCS) . FOCS 2023, サンタクルーズ, カリフォルニア州, 米国. IEEE. pp.  164– 176. arXiv : 2304.01403 . doi :10.1109/FOCS57990.2023.00019. ISBN 979-8-3503-1894-4。
3. Alrabiah, Omar; Guruswami, Venkatesan; Li, Ray (2023). 「ランダムパンクチャードリードソロモン符号は線形サイズの体上でリスト復号能力を実現する」arXiv : 2304.09445 [cs.IT].

歴史的:

• エリアス、ピーター (1957). 「ノイズの多い通信路におけるリスト復号法」(PDF) . 1957-IRE WESCON 大会記録, 第2部. pp.  94– 104.
• Wozencraft, JM (1958). 「リストデコード」.四半期進捗報告書, MIT電子工学研究所. 48 : 90–95 .

レビュー記事:

• エリアス, P. (1991年1月). 「リスト復号のための誤り訂正符号」. IEEE Transactions on Information Theory . 37 (1): 5– 12. doi :10.1109/18.61123.
• Sudan, Madhu (2000), van Leeuwen, Jan; 渡辺 修; 萩谷 正美; Mosses, Peter D. (編)、「リストデコーディング：アルゴリズムとアプリケーション」、理論計算機科学：理論情報学の新境地を探る、計算機科学講義ノート、第1872巻、ベルリン、ハイデルベルク：Springer Berlin Heidelberg、pp.  25– 41、doi :10.1007/3-540-44929-9_3、ISBN 978-3-540-67823-6、 2025年6月7日取得
• Guruswami, Venkatesan (2005). 誤り訂正符号のリスト復号法. コンピュータサイエンス講義ノート. 第3282巻. ベルリン, ハイデルベルク: Springer Berlin Heidelberg. doi :10.1007/b104335. hdl :1721.1/8700. ISBN 978-3-540-24051-8。
• Guruswami, Venkatesan (2006). 「リストデコードにおけるアルゴリズム的結果」 .理論計算機科学の基礎と動向. 2 (2): 107– 195. doi :10.1561/0400000007. ISSN  1551-305X.

外部リンク

• マドゥ・スーダンが教えたコースのノート
• ルカ・トレヴィサンが教えたコースのノート
• ベンカテサン・グルスワミによる講義のノート
• アトリ・ルドラが教えたコースのノート