リスト復号

同義語:list decoding

概要

リスト復号(list decoding)とは、受信語から距離 $e$ 以内の符号語を、1 つに決めず全部出力する復号で、どの受信語でも距離 $\rho n$ 以内の符号語が $L$ 個以下の符号を $(\rho,L)$ リスト復号可能という。$0< \rho< 1-1/q$ では、情報率 $1-H_q(\rho)-1/L$ 程度の $(\rho,L)$ リスト復号可能な符号が無作為に選んで得られ、十分長い符号の情報率が $1-H_q(\rho)$ を一定幅で越えると候補が指数個の受信語があるので、$1-H_q(\rho)$ をリスト復号の容量という。Reed–Solomon 符号では、受信語を 2 変数多項式で補間しその 1 次の因子を探す Sudan の方法で一意の復号の範囲を越える誤りの候補を多項式時間で列挙でき、Guruswami–Sudan の改良は Johnson 半径に届く。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 誤り訂正符号, Gilbert–Varshamov限界, Reed–Solomon符号

リスト復号(list decoding)とは、受け取った語から距離 $e$ 以内にある符号語を、1 つに決めずにすべて出力する復号である。誤りが最小距離 $d$ の半分未満なら候補は 1 つしかないが、それより多い誤りでも候補が少数に収まる符号は多い。候補の個数の上限を $L$ とし、誤りの割合を $\rho=e/n$ とするとき、符号が「どの受信語についても距離 $\rho n$ 以内の符号語が $L$ 個以下」をみたすことを $(\rho,L)$ リスト復号可能という。
情報率 $R$ の $q$ 元符号で $(\rho,L)$ リスト復号可能なものは、$L$ を大きな定数にとれば $R$ を $1-H_q(\rho)$ の近くまで大きくでき、$1-H_q(\rho)$ を一定の幅で越えると、十分長いどの符号でも候補が指数関数的に多い受信語がある。この境目 $1-H_q(\rho)$ を リスト復号の容量 という。アルゴリズムの側では、Reed–Solomon 符号について、2 変数多項式で受信語を補間し、その 1 次の因子を探すことで、一意の復号の半径を越える誤りの候補を多項式時間で列挙できる(Sudan、Guruswami–Sudan)。

問い答え
何を出力するか受信語から距離 $\rho n$ 以内の符号語の全体
組合せ論の限界容量 $1-H_q(\rho)$(無作為な符号で達成、越えると候補が指数個)
どの符号でも届く半径Johnson限界 の半径 $n\bigl(1-\sqrt{1-\delta}\bigr)$
Reed–Solomon 符号の算法Sudan:誤りの割合 $1-\sqrt{2R}$ 程度まで(証明)、Guruswami–Sudan:$1-\sqrt R$ まで
容量に届く明示的な符号折り畳み Reed–Solomon 符号(大きな文字の集合)

定義

$q\ge2$、文字の集合 $Q$($\lvert Q\rvert=q$)を固定し、Hamming 距離 $d(x,y)$、半径 $e$ の Hamming 球 $B(y,e)$、その大きさ $V_q(n,e)$、$q$ 元エントロピー関数 $H_q$ は Gilbert–Varshamov限界 の記事の定義のとおりとする。符号 $C\subseteq Q^n$ の情報率を $R=\log_q\lvert C\rvert/n$ とする。

リスト復号可能

$0\le\rho\le1$ と整数 $L\ge1$ について、符号 $C\subseteq Q^n$ が $(\rho,L)$ リスト復号可能 であるとは、すべての $y\in Q^n$ について
$$ \lvert B(y,\lfloor\rho n\rfloor)\cap C\rvert\le L $$
が成り立つことをいう。$C$ と $y$ と $e$ を与えて $B(y,e)\cap C$ を出力することを リスト復号 という。

$L=1$ は、距離 $\lfloor\rho n\rfloor$ 以内の符号語が高々 1 つ、すなわち一意に復号できることである。

一意に復号できる半径

$C$ を 2 語以上の符号、$d$ をその最小距離、$e\ge0$ を整数とする。どの $y$ についても $\lvert B(y,e)\cap C\rvert\le1$ であることと、$2e< d$ は同値である。

$2e< d$ なら、$c\ne c'$ がともに $B(y,e)$ に入ると三角不等式から $d(c,c')\le2e< d$ となり矛盾する。逆に $2e\ge d$ とし、$d(c,c')=d$ となる符号語をとる。$c$ と $c'$ が異なる $d$ 個の座標のうち $\lceil d/2\rceil$ 個で $c'$ の文字、残りで $c$ の文字をとり、ほかの座標は $c$ と同じにした語を $y$ とすると、$d(y,c)=\lceil d/2\rceil\le e$、$d(y,c')=\lfloor d/2\rfloor\le e$ なので、$B(y,e)$ に 2 つの符号語が入る。$\square$

一意の復号では誤りの割合は相対距離 $\delta=d/n$ の半分未満に限られる。Johnson限界 の定理「Johnson 限界」によれば、$\rho<1-\sqrt{1-\delta}$ なら距離 $d$ のどの符号も $(\rho,nd)$ リスト復号可能であり、同じ記事の補題「半径の大小」により $1-\sqrt{1-\delta}>\delta/2$ である。リスト復号は、候補を多項式個に許すことで、一意の復号の壁の向こうまで復号の目標を延ばす。

リスト復号の容量

リスト復号の容量

$q\ge2$、$n\ge1$ とする。

  1. $0\le\rho\le1-1/q$、整数 $L\ge1$ とし、正の整数 $M$ が $M\le q^{(1-H_q(\rho)-1/L)n}$ をみたすとする。このとき $(\rho,L)$ リスト復号可能で $M/L$ 語以上の符号 $C\subseteq Q^n$ がある。
  2. $0\le e\le n$ を整数とし、$C\subseteq Q^n$ が $\lvert C\rvert\ge T(n+1)\,q^{(1-H_q(e/n))n}$($T>0$)をみたすとする。このとき $\lvert B(y,e)\cap C\rvert\ge T$ となる $y$ がある。

1:$M$ 個の語 $X_1,\dots,X_M$ を $Q^n$ から独立に一様に選ぶ。$e=\lfloor\rho n\rfloor$ とおくと、Gilbert–Varshamov限界 の記事の補題「球の体積の評価」の 1 から、固定した $y$ について
$$ \Pr[X_m\in B(y,e)]=\frac{V_q(n,e)}{q^n}\le q^{-(1-H_q(\rho))n} $$
である。$y\in Q^n$ と、番号の $L+1$ 元集合 $S\subseteq\{1,\dots,M\}$ の組で、$S$ のすべての $m$ について $X_m\in B(y,e)$ となるものを 悪い組 という。独立性から 1 つの組が悪い確率は $q^{-(L+1)(1-H_q(\rho))n}$ 以下で、組は $q^n\binom M{L+1}\le q^nM^{L+1}$ 個なので、
$$ \Pr[\text{悪い組がある}]\le q^n\,M^{L+1}q^{-(L+1)(1-H_q(\rho))n}\le q^n\,q^{-(L+1)n/L}=q^{-n/L}< 1 $$
である(2 つ目の不等号は $M^{L+1}\le q^{(L+1)(1-H_q(\rho))n-(L+1)n/L}$ による)。よって悪い組のない $X_1,\dots,X_M$ が存在する。$C=\{X_1,\dots,X_M\}$ とおくと、どの $y$ についても $B(y,e)$ に入る番号 $m$ は $L$ 個以下なので、$\lvert B(y,e)\cap C\rvert\le L$ である。とくに $y=X_m$ をとると、$X_m$ と同じ語になる番号は $L$ 個以下なので、$C$ の各語は高々 $L$ 個の番号から来ており、$\lvert C\rvert\ge M/L$ である。
2:Johnson限界 の補題「符号語の多い球」から、$\lvert B(y,e)\cap C\rvert\ge\lvert C\rvert V_q(n,e)/q^n$ となる $y$ がある。Gilbert–Varshamov限界 の記事の補題「球の体積の評価」の 2 から $V_q(n,e)\ge\binom ne(q-1)^e\ge q^{H_q(e/n)n}/(n+1)$ なので、右辺は $\lvert C\rvert q^{-(1-H_q(e/n))n}/(n+1)\ge T$ 以上である。$\square$

容量の漸近形

$0< \rho< 1-1/q$ とする。

  1. $\varepsilon>0$ に対し $L=\lceil1/\varepsilon\rceil$ とすると、すべての $n\ge1$ で情報率 $1-H_q(\rho)-\varepsilon-(1+\log_qL)/n$ 以上の $(\rho,L)$ リスト復号可能な符号がある。
  2. $\varepsilon>0$ とし、情報率 $1-H_q(\rho)+\varepsilon$ 以上の符号の列 $C_n\subseteq Q^n$ を考える。$n$ が十分大きければ、ある $y$ について $\lvert B(y,\lfloor\rho n\rfloor)\cap C_n\rvert\ge q^{\varepsilon n/2}$ である。

1:$1-H_q(\rho)-1/L< 0$ なら、1 語だけの符号が $(\rho,L)$ リスト復号可能で情報率 $0$ をもち、主張の右辺は負なのでよい。そうでなければ $M=\lfloor q^{(1-H_q(\rho)-1/L)n}\rfloor\ge1$ に thm-ld-capacity の 1 を当てる。$1/L\le\varepsilon$ と、$x\ge1$ なら $\lfloor x\rfloor\ge x/2$ であることから $\lvert C\rvert\ge M/L\ge q^{(1-H_q(\rho)-\varepsilon)n}/(2L)$ であり、$\log_q2\le1$ なので情報率は $1-H_q(\rho)-\varepsilon-(1+\log_qL)/n$ 以上である。
2:$e_n=\lfloor\rho n\rfloor$ とおくと $e_n/n\to\rho$ で、$H_q$ は連続なので、十分大きな $n$ で $H_q(e_n/n)\ge H_q(\rho)-\varepsilon/4$ かつ $(n+1)\le q^{\varepsilon n/4}$ である。このとき $\lvert C_n\rvert\ge q^{(1-H_q(\rho)+\varepsilon)n}\ge q^{\varepsilon n/2}(n+1)q^{(1-H_q(e_n/n))n}$ なので、thm-ld-capacity の 2 を $T=q^{\varepsilon n/2}$ で当てればよい。$\square$

GRS25 Theorem 7.4.1(p. 143)と Theorem 7.4.2(p. 144)は、同じ容量を「情報率 $1-H_q(\rho)-1/L$ の $(\rho,L)$ リスト復号可能な符号がある」「情報率 $1-H_q(\rho)+\varepsilon$ では候補が $q^{\Omega(\varepsilon n)}$ 個になる」という形で述べている。上の 1 は、無作為に選んだ語に重複がありうることを、符号の大きさを $M/L$ で下から抑えることで処理した形である。

  • 2 元対称通信路との一致。 $q=2$ の容量 $1-H_2(\rho)$ は、誤りが確率 $\rho$ で独立に起こる 2元対称通信路 の容量と同じ式である。リスト復号では誤りの位置を敵が選んでよい代わりに、候補を $L$ 個まで許している。
  • 大きな文字の集合。 $H_q(x)=x\log_q(q-1)+H_2(x)\log_q2$ なので $H_q(\rho)\le\rho+\log_q2$ であり、容量は $1-\rho-\log_q2$ 以上である。$q$ を大きくとれば、誤りの割合 $\rho$ を $1-R$ の近くまで許すことになる。距離 $d=n-k+1$ の Reed–Solomon 符号では、どの符号にも使える Johnson限界 の半径は $1-\sqrt{1-\delta}\approx1-\sqrt R$ で、$0< R< 1$ なら $1-R>1-\sqrt R$ なので、容量は Johnson 半径よりも先にある(GRS25 p. 146)。

Reed–Solomon 符号のリスト復号

Reed–Solomon符号 $\mathrm{RS}_q(\mathbf a,k)$ は、次数 $k-1$ 以下の多項式 $f$ の値の列 $(f(a_1),\dots,f(a_n))$ の全体である(評価点 $a_1,\dots,a_n\in\mathbb F_q$ は相異なる)。受信語 $y$ について、$f(a_l)=y_l$ となる $l$ の個数を $f$ の 一致数 という。誤り $e$ 個以内の候補を求めることは、一致数 $n-e$ 以上の $f$ をすべて求めることである。一意の復号(Reed–Solomon符号 の定理「Welch–Berlekamp の復号」)では一致数が $(n+k)/2$ 程度必要だが、次の方法では $\lceil\sqrt{2(k-1)n}\,\rceil$ を超えればよい。
$w=k-1$ とし、2 変数多項式の単項式 $X^iY^j$ の $(1,w)$ 次数 を $i+wj$、多項式の $(1,w)$ 次数をその単項式の $(1,w)$ 次数の最大値とする。

Sudan の方法

$2\le k\le n\le q$、相異なる評価点 $a_1,\dots,a_n\in\mathbb F_q$、$y\in\mathbb F_q^n$ とし、$w=k-1$、整数 $D\ge1$ について $N(D)=\lvert\{(i,j)\in\mathbb Z_{\ge0}^2: i+wj\le D\}\rvert$ とおく。

  1. $N(D)>n$ なら、$(1,w)$ 次数が $D$ 以下の $0$ でない $Q\in\mathbb F_q[X,Y]$ で、$Q(a_l,y_l)=0$($l=1,\dots,n$)をみたすものがある。
  2. 1 のような $Q$ について、次数 $k-1$ 以下で一致数が $D$ より大きい $f$ は、$Y-f(X)$ が $Q$ を割り切る。そのような $f$ は $\lfloor D/w\rfloor$ 個以下である。
  3. $D=\bigl\lceil\sqrt{2wn}\,\bigr\rceil$ は $N(D)>n$ をみたす。したがって一致数が $\lceil\sqrt{2(k-1)n}\,\rceil$ より大きい $f$ はすべて $Q$ の 1 次の因子 $Y-f(X)$ として現れ、その個数は $\lfloor D/(k-1)\rfloor$ 以下である。

1:$Q=\sum_{i+wj\le D}c_{ij}X^iY^j$ の $N(D)$ 個の係数 $c_{ij}$ について、条件 $Q(a_l,y_l)=0$ は $n$ 本の斉次一次方程式である。未知数の個数が方程式の本数より多いので、$0$ でない解がある。
2:$f$ を次数 $k-1$ 以下、一致数 $t>D$ とし、$P(X)=Q(X,f(X))$ とおく。$Q$ の各単項式 $X^iY^j$ は $X^if(X)^j$ になり、その次数は $i+(k-1)j\le D$ 以下なので、$P$ は $0$ か次数 $D$ 以下である。$f(a_l)=y_l$ となる $l$ では $P(a_l)=Q(a_l,y_l)=0$ なので、$P$ は相異なる $t>D$ 個の根をもち、多項式環 の定理「根の個数」により $P=0$ である。$Q$ を $\mathbb F_q[X]$ を係数とする $Y$ の多項式と見て、モニックな $Y-f(X)$ で割ると $Q=(Y-f(X))S+r$($r\in\mathbb F_q[X]$)と書け、$Y=f(X)$ を代入して $r=P=0$ である。
個数:$Q$ は整域 $\mathbb F_q[X]$ を係数とする $Y$ の $0$ でない多項式で、$Y$ についての次数は $wj\le D$ から $\lfloor D/w\rfloor$ 以下である。整域の上の $0$ でない多項式の根の個数は次数以下なので(商体の上で考える)、相異なる $f$ は $\lfloor D/w\rfloor$ 個以下である。
3:$L=\lfloor D/w\rfloor$ とおくと、$j=0,\dots,L$ のそれぞれで $i$ は $0,\dots,D-wj$ の $D-wj+1$ 通りなので
$$ N(D)=\sum_{j=0}^{L}(D-wj+1)=(L+1)(D+1)-\frac{wL(L+1)}2=\frac{L+1}2\,(2D+2-wL)\ge\frac{(L+1)(D+2)}2 $$
である($wL\le D$)。$L+1>D/w$ なので $N(D)>\frac{D(D+2)}{2w}>\frac{D^2}{2w}\ge n$ である。$\square$

$Q$ は一次方程式を掃き出し法で解いて求まり、1 次の因子 $Y-f(X)$ は 2 変数多項式の因数分解で求まる。因数分解は多項式時間でできることが知られている(GRS25 p. 245)ので、この方法は全体として多項式時間で動く。一致数 $t$ を情報率 $R=k/n$ で表すと、$t/n>\sqrt{2R}$ 程度で足り、誤りの割合 $1-\sqrt{2R}$ 程度まで候補を列挙できる(GRS25 Algorithm 12.2.2・Theorem 12.2.7, pp. 251–252)。これは $R< 3-2\sqrt2\approx0.17$ で一意の復号の割合 $(1-R)/2$ を上回る($1-\sqrt{2R}>(1-R)/2$ は $(1+R)/2>\sqrt{2R}$ と書き直せ、$R>0$ ではこの両辺が正なので $(1+R)^2>8R$、すなわち $R^2-6R+1>0$ と同値である。この 2 次式の根は $3\pm2\sqrt2$ で、$3+2\sqrt2>1$ である)。

2 本の直線が隠れた受信語

$q=13$、評価点を $\mathbb F_{13}$ の全体 $0,1,\dots,12$、$k=2$ とする($[13,2,12]_{13}$ の Reed–Solomon 符号)。一意に復号できるのは誤り $\lfloor11/2\rfloor=5$ 個までである。$f_1=X$、$f_2=-X+6$ とし、
$$ y=(0,1,2,3,4,5,6,\ 12,11,10,9,8,7) $$
を受け取ったとする。$y$ は $x=0,\dots,6$ で $f_1$ と、$x=3,7,\dots,12$ で $f_2$ と一致する($f_2(3)=3$ が交点)ので、$f_1$、$f_2$ の一致数はどちらも $7$、誤りはどちらも $6$ 個である。最も近い符号語は 1 つに決まらない。
thm-ld-sudan では $w=1$、$D=\lceil\sqrt{26}\,\rceil=6$ で、$N(6)=28>13$ である。13 本の方程式は一次独立で、28 個の係数の解空間は 15 次元ある。どの解 $Q$ をとっても、$Y-X$ と $Y+X-6$ は $Q$ の因子である。一致数が $6$ より大きい $f$ は $f_1,f_2$ だけなので(3 本目があれば、$f_1$、$f_2$ のそれぞれと 1 点以下でしか一致しないので、一致数は $2$ 以下になる)、一致数の確かめを通す出力は $\{f_1,f_2\}$ である。

Guruswami–Sudan の方法と容量への到達

thm-ld-sudan の補間に、各点 $(a_l,y_l)$ で $Q$ が $r$ 重に $0$ になるという条件を加えると、根を数える段で各一致が $r$ 個分に数えられ、一致数 $\sqrt{(k-1)n}$ 程度、すなわち誤りの割合 $1-\sqrt R$ まで多項式時間で候補を列挙できる(Guruswami–Sudan。GRS25 Algorithm 12.2.3・Theorem 12.2.12, p. 257。この記事では証明しない)。これは Johnson限界 の半径と一致する。Reed–Solomon 符号を $1-\sqrt R$ より先まで効率よくリスト復号できるかは未解決である(同 Open Question 12.2.1, p. 258)。
容量 $1-R$ の側には、Reed–Solomon 符号の連続する $m$ 個の値を 1 文字にまとめた 折り畳み Reed–Solomon 符号 で届く。情報率 $R$ の折り畳み Reed–Solomon 符号を、長さ $N$ について $(N/\varepsilon)^{O(1/\varepsilon)}$ の時間で誤りの割合 $1-R-\varepsilon$ までリスト復号できる(Guruswami–Rudra。GRS25 Definition 17.1.1, p. 346、Theorem 17.3.8, p. 363。この記事では証明しない)。ただし文字の集合の大きさは $(N/\varepsilon)^{O(1/\varepsilon^2)}$ で長さとともに増える。2 元のような小さい文字の集合で容量に届く明示的な符号と効率のよい算法は知られていない(同 p. 147、p. 364)。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなる結論
$\rho\le1-1/q$(thm-ld-capacity の 1)$q=2$、$n=100$、$\rho=0.9$、$L=2$、$M=8$$(\rho,L)$ リスト復号可能で $M/L=4$ 語以上の符号がある
一致数が $D$ より大きい(thm-ld-sudan の 2)ex-ld-two-lines の受信語で一致数 $2$ 以上一致数がその値以上の $f$ はすべて $Y-f(X)\mid Q$
$2e< d$(prop-ld-unique)ex-ld-two-lines の符号で $e=6$球の中の符号語は 1 つ以下
反例の確かめ

要点:各行で、外した条件のほかは仮定をみたし、結論が成り立たない。

確かめを開く

1 行目:$1-H_2(0.9)-1/2\approx0.0310$ で $q^{0.0310\cdot100}=2^{3.10\ldots}\ge8$ なので $M=8$ は仮定をみたし、結論は 4 語以上の $(0.9,2)$ リスト復号可能な符号の存在である。しかし 3 語以上のどの符号 $C$ についても、Johnson限界 の補題「符号語の多い球」から、ある $y$ で $\lvert B(y,90)\cap C\rvert\ge3V_2(100,90)/2^{100}$ であり、$V_2(100,90)=2^{100}-\sum_{i=91}^{100}\binom{100}i>\frac23\cdot2^{100}$ なので右辺は $2$ を超え、3 語以上が入る。よって $(0.9,2)$ リスト復号可能な符号は 2 語以下である。

2 行目:$Q$ は $0$ でないので、$Y$ の多項式として根は $\lfloor D/w\rfloor=6$ 個以下である。一方、一致数 $2$ 以上の 1 次以下の $f$ は、$f_1$、$f_2$ と、点 $(0,0)$ と $f_2$ の上の点 $(x,f_2(x))$($x=7,\dots,12$)を通る 6 本の直線の、少なくとも $8$ 個ある($f_2$ の上の 2 点と $(0,0)$ が同じ直線に乗ると、その直線は $f_2$ だが $f_2(0)=6\ne0$ なので、6 本は相異なり、$f_1,f_2$ とも異なる)。よってそのうち少なくとも 2 個は $Q$ の根にならない。

3 行目:最小距離は $12$ で $2e=12\not< 12$ である。ex-ld-two-lines の $y$ は $f_1$、$f_2$ の符号語からともに距離 $6$ にあるので、$B(y,6)$ に 2 個の符号語が入る。

歴史と広がり

  • 名前の由来。 リスト復号は Elias(Eli57)と Wozencraft(Woz58)が定義した(GRS25 §7.7, p. 159)。
  • Reed–Solomon 符号の算法。 thm-ld-sudan の方法は Sudan(Sud97)、重複度を使う改良は Guruswami–Sudan(GS99)による(GRS25 §12.5, p. 270)。折り畳み Reed–Solomon 符号で容量に届くことは Guruswami–Rudra(GR08)による(同 §17.4, p. 363)。
  • 無作為な線形符号。 情報率 $1-H_q(\rho)-\varepsilon$ の無作為な線形符号は、高い確率で $(\rho,O(1/\varepsilon))$ リスト復号可能になることが知られている(2 元では Guruswami–Håstad–Sudan–Zuckerman、一般の $q$ では Guruswami–Håstad–Kopparty。GRS25 p. 159)。
  • 限界との関係。 符号の大きさの上界の Plotkin限界 や Elias–Bassalygo の限界(Johnson限界 の定理「Elias–Bassalygo の限界(2 元)」)も、球の中の符号語を数える同じ型の議論から出る。

関連項目

参考文献

[2]
Peter Elias, List decoding for noisy channels, Technical Report 335, Research Laboratory of Electronics, MIT, 1957
[3]
John M. Wozencraft, List decoding, Quarterly Progress Report, Research Laboratory of Electronics, MIT, 1958, pp. 90–95

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する