Polar符号

同義語:polar code

概要

Polar符号(polar code)とは、長さ $N=2^n$ の入力ビット列を再帰的な線形変換 $u\mapsto uG_N$ で混ぜて 1 本の通信路を $N$ 本の合成通信路に作り変え、良い合成通信路だけに情報を載せ、残りを既知の値に固定した 2 元線形符号である。$N$ が大きくなると合成通信路はほぼ完全なものとほぼ役に立たないものに分かれ(通信路の分極)、良いものの割合は対称容量に近づく。2 値消失通信路では、消失確率が $z\mapsto2z-z^2$、$z\mapsto z^2$ で変わるマルチンゲールの収束から分極が示され、逐次除去復号の誤りの確率は $O(N^{-1/4})$ になる。こうして容量未満の任意の速さが手間 $O(N\log N)$ の符号化と復号で達成される。

$$\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}} $$

前提知識: 通信路符号化定理, 線形符号, 相互情報量, マルチンゲール収束定理

Polar符号(polar code)は、Arıkan が 2009 年に導入した 2 元の 線形符号 で、長さ $N=2^n$ の入力を簡単な再帰で混ぜ合わせることにより、1 本の通信路を $N$ 本の「合成通信路」に作り変える。$N$ が大きくなると、合成通信路の大部分は「ほぼ雑音のない通信路」か「ほぼ何も伝えない通信路」のどちらかに分かれる。この現象を 通信路の分極 という。良い側の合成通信路だけに情報を載せ、残りには送受信者が前もって決めた値を載せた符号が Polar 符号である。逐次除去復号という $O(N\log N)$ の手間の復号で、容量より小さい任意の速さを誤りの確率 $\to0$ で達成する、初めての明示的な符号の族である。
この記事では、2 値消失通信路(入力ビットが確率 $\varepsilon$ で消える通信路)について、合成通信路の再帰式(lem-pc-recursion)、分極(thm-pc-polarization)、分極の速さ(thm-pc-rate)、逐次除去復号の誤りの評価(prop-pc-sc-bound)を証明し、Polar 符号が容量を達成すること(thm-pc-capacity)を示す。一般の 2 値入力の通信路での結果は主張として述べる。

設定

以下、対数は底 2 とし、情報量の単位は bit とする(通信路符号化定理 では自然対数を使っており、そこでの容量を $\log 2$ で割ると bit の値になる)。2 元体を $\mathbb F_2=\{0,1\}$、その加法を $\oplus$ と書く。

2 値入力の通信路と、その 2 つの量

2 値入力の無記憶な通信路(B-DMC)とは、有限集合 $\mathcal Y$ と、各 $x\in\{0,1\}$ についての $\mathcal Y$ 上の確率分布 $W(\cdot\mid x)$ の組 $W:\{0,1\}\to\mathcal Y$ である。$W$ の 対称容量 と Bhattacharyya パラメータ を
$$ I(W):=\sum_{y\in\mathcal Y}\sum_{x\in\{0,1\}}\frac12W(y\mid x)\log\frac{W(y\mid x)}{\frac12W(y\mid 0)+\frac12W(y\mid 1)},\qquad Z(W):=\sum_{y\in\mathcal Y}\sqrt{W(y\mid0)W(y\mid1)} $$
で定める。$I(W)$ は一様な入力 $X$ と出力 $Y$ の 相互情報量 で、$0\le I(W)\le1$ である。$Z(W)\in[0,1]$ は、入力が $0$ か $1$ かを出力から見分けにくいほど大きい。

消失型の通信路

B-DMC $V:\{0,1\}\to\mathcal Y$ が 消失型 であるとは、各 $y\in\mathcal Y$ について $V(y\mid0)=V(y\mid1)$ または $V(y\mid0)V(y\mid1)=0$ が成り立つことをいう。前者の $y$ を 消失出力 と呼び、
$$ z(V):=\sum_{y:\ V(y\mid0)=V(y\mid1)}V(y\mid0) $$
を $V$ の 消失確率 という。消失出力を受けとる確率は、入力が $0$ でも $1$ でも $z(V)$ である。消失出力でない $y$ を受けとれば、入力は一つに決まる。

2 値消失通信路 $\mathrm{BEC}(\varepsilon)$ は、$\mathcal Y=\{0,1,?\}$、$W(x\mid x)=1-\varepsilon$、$W(?\mid x)=\varepsilon$ で定まる消失型の通信路である(通信路符号化定理 の例「2 値消失通信路」)。消失型の通信路 $V$ では $Z(V)=z(V)$、$I(V)=1-z(V)$ であり、とくに $\mathrm{BEC}(\varepsilon)$ の容量は $1-\varepsilon$ bit である。出力の名前を全単射で付け替えても(確率を保つ限り)消失型であることと $z$ は変わらない。

符号化と合成通信路

Polar 変換と合成通信路

$N=2^n$ とする。写像 $E_N:\mathbb F_2^N\to\mathbb F_2^N$ を、$E_1(u)=u$ と
$$ E_{2N}(u_1,\dots,u_{2N}):=\bigl(E_N(u_{\mathrm o}\oplus u_{\mathrm e}),\ E_N(u_{\mathrm e})\bigr),\qquad u_{\mathrm o}:=(u_1,u_3,\dots,u_{2N-1}),\ u_{\mathrm e}:=(u_2,u_4,\dots,u_{2N}) $$
で再帰的に定める。$E_N$ は線形なので、$N\times N$ 行列 $G_N$ によって $E_N(u)=uG_N$ と書ける($u$ は行ベクトル)。
B-DMC $W$ に対し、$u\in\mathbb F_2^N$ を $x=E_N(u)$ に変えて $W$ を $N$ 回独立に使う通信路を $W_N(y\mid u):=\prod_{k=1}^NW(y_k\mid x_k)$($y\in\mathcal Y^N$)とする。$1\le i\le N$ について、入力 $u_i$、出力 $(y,u_1^{i-1})$ の 合成通信路 を
$$ W_N^{(i)}(y,u_1^{i-1}\mid u_i):=\sum_{u_{i+1}^N\in\mathbb F_2^{N-i}}\frac1{2^{N-1}}\,W_N(y\mid u) $$
で定める。ここで $u_a^b:=(u_a,\dots,u_b)$ である。$W_N^{(i)}$ は「$u$ が一様に選ばれ、受信者が $y$ と正しい $u_1^{i-1}$ を知っているときに、$u_i$ を推定する通信路」である。

たとえば
$$ G_2=\begin{pmatrix}1&0\\1&1\end{pmatrix},\qquad G_4=\begin{pmatrix}1&0&0&0\\1&0&1&0\\1&1&0&0\\1&1&1&1\end{pmatrix} $$
であり、一般に $G_N$ は $F=G_2$ の $n$ 重の Kronecker積 $F^{\otimes n}$ の行を、行番号の 2 進表記を逆順にする置換 $B_N$ で並べ替えたもの $B_NF^{\otimes n}$ に等しい(Ari09 Prop. 16)。$E_{2N}$ の計算は $E_N$ を 2 回と排他的論理和 $N$ 回で済むので、ビット演算の回数 $T(N)$ は $T(2N)=2T(N)+N$、$T(1)=0$ を満たし、$T(N)=\frac N2\log N$ である。
合成通信路は、次の 2 つの操作の繰り返しで得られる。

1 段の変換

B-DMC $V:\{0,1\}\to\mathcal Y$ に対し、B-DMC $V^-:\{0,1\}\to\mathcal Y^2$ と $V^+:\{0,1\}\to\mathcal Y^2\times\{0,1\}$ を
$$ V^-(y_1,y_2\mid a):=\sum_{b\in\{0,1\}}\frac12V(y_1\mid a\oplus b)V(y_2\mid b),\qquad V^+(y_1,y_2,a\mid b):=\frac12V(y_1\mid a\oplus b)V(y_2\mid b) $$
で定める。$V^-$ は「$V$ に $a\oplus b$ と $b$ を通したとき、未知の $b$ を残して $a$ を推定する通信路」、$V^+$ は「$a$ を教えてもらって $b$ を推定する通信路」である。

合成通信路の再帰式

$N=2^n$、$1\le i\le N$ とし、$V:=W_N^{(i)}$ とおく。出力の名前の付け替えを除いて
$$ W_{2N}^{(2i-1)}=V^-,\qquad W_{2N}^{(2i)}=V^+ $$
が成り立つ(Ari09 Prop. 3)。

長さ $2N$ の入力を、奇数番と偶数番の和と偶数番に分ける

要点:$u\mapsto(u_{\mathrm o}\oplus u_{\mathrm e},u_{\mathrm e})$ は全単射で、$W_{2N}$ は長さ $N$ の 2 つの $W_N$ の積に分かれる。未知の成分についての和も 2 つに分かれ、$W_N^{(i)}$ の積になる。

詳しい証明を開く

$u\in\mathbb F_2^{2N}$ に $s:=u_{\mathrm o}\oplus u_{\mathrm e}$、$t:=u_{\mathrm e}$ を対応させる写像は全単射で、$s_j=u_{2j-1}\oplus u_{2j}$、$t_j=u_{2j}$ である。$E_{2N}$ の定義から、$y=(y',y'')$($y',y''\in\mathcal Y^N$)について $W_{2N}(y\mid u)=W_N(y'\mid s)\,W_N(y''\mid t)$。また $u_1^{2i-2}$ と $(s_1^{i-1},t_1^{i-1})$ は互いに決まり合い、$u_{2i+1}^{2N}$ を動かすことは $(s_{i+1}^N,t_{i+1}^N)$ を動かすことと同じである。$\frac1{2^{2N-1}}=\frac12\cdot\frac1{2^{N-1}}\cdot\frac1{2^{N-1}}$ に注意すると、$a:=u_{2i-1}$、$b:=u_{2i}$(従って $s_i=a\oplus b$、$t_i=b$)として $$W_{2N}^{(2i)}(y,u_1^{2i-1}\mid b)=\frac12\Bigl(\sum_{s_{i+1}^N}\frac{W_N(y'\mid s)}{2^{N-1}}\Bigr)\Bigl(\sum_{t_{i+1}^N}\frac{W_N(y''\mid t)}{2^{N-1}}\Bigr)=\frac12V(y',s_1^{i-1}\mid a\oplus b)\,V(y'',t_1^{i-1}\mid b)$$ となる。出力 $(y,u_1^{2i-1})$ と $\bigl((y',s_1^{i-1}),(y'',t_1^{i-1}),a\bigr)$ は全単射で対応するので、これは $V^+$ である。$W_{2N}^{(2i-1)}$ は定義により $W_{2N}^{(2i)}$ をさらに $u_{2i}=b$ について和をとったものなので、同じ対応で $V^-$ になる。$\square$

消失型の通信路の変換

$V$ が消失型で消失確率が $z$ なら、$V^-$ と $V^+$ も消失型で、消失確率はそれぞれ $2z-z^2$ と $z^2$ である(Ari09 Prop. 6)。

消失出力が一つでもあれば $a$ は分からず、両方なければ分かる

要点:$V^+$ では $y_1,y_2$ の両方が消失出力のときだけ $b$ が分からず、$V^-$ では少なくとも一方が消失出力なら $a$ が分からない。消失は確率 $z$ で独立に起こるので、確率は $z^2$ と $1-(1-z)^2$。

詳しい証明を開く

$V^+(y_1,y_2,a\mid b)$ を考える。$y_2$ が消失出力でなければ $V(y_2\mid b)$ が $0$ になる $b$ がある。$y_1$ が消失出力でなければ $V(y_1\mid a\oplus b)$ が $0$ になる $b$ がある。どちらの場合も一方の $b$ で値が $0$ になる。$y_1,y_2$ がともに消失出力なら値は $\frac12V(y_1\mid0)V(y_2\mid0)$ で $b$ によらない。よって $V^+$ は消失型で、消失出力は「$y_1,y_2$ がともに消失出力」のものである。入力 $b$ のもとで $a$ は一様、$Y_1,Y_2$ はそれぞれ確率 $z$ で消失出力となり、それらは独立なので、消失確率は $z^2$。

$V^-(y_1,y_2\mid a)$ を考える。$y_1,y_2$ がともに消失出力でなければ、$a\oplus b$ と $b$ がそれぞれ一つに決まり、$a$ も決まるので、一方の $a$ で値は $0$。$y_1$ が消失出力なら $V(y_1\mid a\oplus b)=V(y_1\mid0)$ だから値は $\frac12V(y_1\mid0)\sum_bV(y_2\mid b)$ で $a$ によらない。$y_2$ が消失出力なら $c=a\oplus b$ と置き換えて値は $\frac12V(y_2\mid0)\sum_cV(y_1\mid c)$ でやはり $a$ によらない。よって $V^-$ は消失型で、消失確率は「少なくとも一方が消失出力」の確率 $1-(1-z)^2=2z-z^2$。$\square$

lem-pc-recursion と lem-pc-bec を $W=\mathrm{BEC}(\varepsilon)$ から繰り返し使うと、すべての $W_N^{(i)}$ は消失型で、その消失確率 $z_N^{(i)}$ は
$$ z_1^{(1)}=\varepsilon,\qquad z_{2N}^{(2i-1)}=2z_N^{(i)}-\bigl(z_N^{(i)}\bigr)^2,\qquad z_{2N}^{(2i)}=\bigl(z_N^{(i)}\bigr)^2 $$
で計算できる。$(2z-z^2)+z^2=2z$ だから、$\sum_{i=1}^Nz_N^{(i)}=N\varepsilon$ がすべての $N$ で成り立つ。$1-z$ が容量なので、これは「合成通信路の容量の和は $N(1-\varepsilon)$ で、分配が変わるだけ」ということである。

分極

2 値消失通信路の分極

$0\le\varepsilon\le1$、$0< \delta< \frac12$ とし、$W=\mathrm{BEC}(\varepsilon)$ とする。$N=2^n$ について
$$ \frac1N\#\{i\mid z_N^{(i)}< \delta\}\to1-\varepsilon,\qquad \frac1N\#\{i\mid z_N^{(i)}>1-\delta\}\to\varepsilon\qquad(n\to\infty) $$
が成り立つ。とくに、消失確率が $\delta$ 以上 $1-\delta$ 以下の合成通信路の割合は $0$ に近づく。

消失確率の列はマルチンゲールで、端でしか止まれない

独立で一様な $\{-,+\}$ 値の確率変数 $B_1,B_2,\dots$ をとり、$Z_0:=\varepsilon$、
$$ Z_{k+1}:=\begin{cases}2Z_k-Z_k^2&(B_{k+1}=-)\\ Z_k^2&(B_{k+1}=+)\end{cases} $$
とおく。再帰式によって、長さ $2^n$ の消失確率の多重集合 $\{z_{2^n}^{(i)}\}_i$ は、長さ $2^{n-1}$ の各値 $z$ を 2 つの値 $2z-z^2$、$z^2$ に置き換えて得られる。従って $Z_n$ の分布は、$\{1,\dots,N\}$ から一様に選んだ $i$ についての $z_N^{(i)}$ の分布に等しい。示すべきことは $P(Z_n< \delta)\to1-\varepsilon$、$P(Z_n>1-\delta)\to\varepsilon$ である。
$\mathcal F_k$ を $B_1,\dots,B_k$ の生成する $\sigma$-代数とすると、$Z_k$ は $\mathcal F_k$ 可測で
$$ E[Z_{k+1}\mid\mathcal F_k]=\frac12(2Z_k-Z_k^2)+\frac12Z_k^2=Z_k $$
(条件付き期待値)。よって $(Z_k)$ は $[0,1]$ に値をとるマルチンゲールであり、マルチンゲール収束定理 により、ほとんど確実に極限 $Z_\infty$ をもつ。ところが、どちらの場合も
$$ |Z_{k+1}-Z_k|=Z_k(1-Z_k) $$
である。左辺はほとんど確実に $0$ に近づくので、$Z_\infty(1-Z_\infty)=0$、すなわち $Z_\infty\in\{0,1\}$ がほとんど確実に成り立つ。有界収束定理と $E[Z_k]=E[Z_0]=\varepsilon$ から $E[Z_\infty]=\varepsilon$、従って $P(Z_\infty=1)=\varepsilon$、$P(Z_\infty=0)=1-\varepsilon$。
ほとんど確実な収束から確率収束が従うので、$P(|Z_n-Z_\infty|\ge\delta)\to0$。$\{Z_\infty=0,\ |Z_n-Z_\infty|< \delta\}\subseteq\{Z_n< \delta\}$ より $\liminf P(Z_n< \delta)\ge1-\varepsilon$、同様に $\liminf P(Z_n>1-\delta)\ge\varepsilon$。$\delta< \frac12$ なので 2 つの事象は交わらず、確率の和は $1$ 以下である。よって $\limsup P(Z_n< \delta)\le1-\liminf P(Z_n>1-\delta)\le1-\varepsilon$ となり、両方の極限が求める値に等しい。$\square$

分極が起こる理由は、最後の等式 $|Z_{k+1}-Z_k|=Z_k(1-Z_k)$ にある。マルチンゲールであるだけでは端に寄る理由にならない(ex-pc-martingale)。$Z_k$ が中ほどにある限り大きく揺さぶられ続けるので、収束するには端に行くしかない。
良い合成通信路の割合は、容量を超えることもない。

良い合成通信路の個数の上限

$W=\mathrm{BEC}(\varepsilon)$、$0< \delta< 1$ とする。すべての $N=2^n$ について
$$ \#\{i\mid z_N^{(i)}< \delta\}\le\frac{N(1-\varepsilon)}{1-\delta}. $$

$\sum_i(1-z_N^{(i)})=N(1-\varepsilon)$ で各項は $0$ 以上、$z_N^{(i)}< \delta$ の項は $1-\delta$ より大きい。$\square$

Polar 符号の誤りの確率を小さくするには、良い合成通信路の消失確率が十分速く $0$ に近づくことが要る。

分極の速さ

$W=\mathrm{BEC}(\varepsilon)$、$0\le R< 1-\varepsilon$ とする。定数 $C$ があって、十分大きいすべての $N=2^n$ について、$\#A_N\ge NR$ かつ
$$ z_N^{(i)}\le C\,N^{-5/4}\qquad(i\in A_N) $$
を満たす集合 $A_N\subseteq\{1,\dots,N\}$ がある(Ari09 Theorem 2 の 2 値消失通信路の場合)。

一度小さくなった後は、$+$ の回数が半分近くあれば速く減る

prf-thm-pc-polarization の $Z_k$ を使う。$\zeta:=2^{-4}$ とし、$m\ge0$ について事象 $T_m:=\{Z_k\le\zeta\ (k\ge m)\}$ をとる。$T_m$ は $m$ について増加し、$Z_k\to0$ となる $\omega$ はある $T_m$ に属するから、$\lim_mP(T_m)\ge P(Z_\infty=0)=1-\varepsilon$。$\gamma:=1-\varepsilon-R>0$ とし、$P(T_m)\ge1-\varepsilon-\gamma/2$ となる $m$ を一つ固定する。
$n>m$ について、$B_{m+1},\dots,B_n$ のうち $+$ の個数を $K$ とし、$U_n:=\{K\ge\frac9{20}(n-m)\}$ とおく。$K$ は二項分布 $\mathrm{Bin}(n-m,\frac12)$ に従うので、Chebyshevの不等式 により
$$ P(U_n^c)\le P\Bigl(\Bigl|K-\frac{n-m}2\Bigr|\ge\frac{n-m}{20}\Bigr)\le\frac{(n-m)/4}{(n-m)^2/400}=\frac{100}{n-m}. $$
$T_m\cap U_n$ の上で $Z_n$ を評価する。$k\ge m$ では $Z_k\le\zeta$ だから、$B_{k+1}=-$ なら $Z_{k+1}\le2Z_k$、$B_{k+1}=+$ なら $Z_{k+1}=Z_k^2\le\zeta Z_k=2^{-4}Z_k$。よって
$$ Z_n\le Z_m\cdot2^{(n-m-K)-4K}\le2^{-4}\cdot2^{(n-m)-5K}\le2^{-4}\cdot2^{-\frac54(n-m)}=C\,N^{-5/4},\qquad C:=2^{\frac54m-4}. $$
従って $n$ が $n-m\ge200/\gamma$ を満たせば
$$ P\bigl(Z_n\le CN^{-5/4}\bigr)\ge P(T_m\cap U_n)\ge P(T_m)-P(U_n^c)\ge1-\varepsilon-\gamma=R. $$
$Z_n$ の分布は一様に選んだ $i$ についての $z_N^{(i)}$ の分布だったから、$A_N:=\{i\mid z_N^{(i)}\le CN^{-5/4}\}$ が求める集合である。$\square$

Polar 符号と逐次除去復号

Polar 符号

$N=2^n$、集合 $A\subseteq\{1,\dots,N\}$(情報集合)と、$A^c$ 上の値 $u_{A^c}$(凍結ビット)を決める。$\#A$ ビットのメッセージを $u_A$ に入れ、$u=(u_A,u_{A^c})$ を $x=E_N(u)=uG_N$ に符号化して送る。速さは $\#A/N$ である。通信路 $W$ に対し、合成通信路 $W_N^{(i)}$ の $Z$ の値が小さい順に $K$ 個の $i$ を $A$ にとったものを、$W$ に対する長さ $N$、次元 $K$ の Polar 符号 という。凍結ビットは送受信者が共有する($0$ にとることが多い)。

逐次除去復号

受信語 $y$ に対し、$i=1,2,\dots,N$ の順に $\hat u_i$ を決める。$i\notin A$ なら $\hat u_i:=u_i$(凍結ビット)。$i\in A$ なら、すでに決めた $\hat u_1^{i-1}$ を使って
$$ \hat u_i:=\begin{cases}0&\bigl(W_N^{(i)}(y,\hat u_1^{i-1}\mid0)\ge W_N^{(i)}(y,\hat u_1^{i-1}\mid1)\bigr)\\1&(\text{それ以外})\end{cases} $$
とする。これを 逐次除去復号(SC 復号)という。合成通信路の尤度は lem-pc-recursion によって長さ $N/2$ の尤度から再帰的に計算でき、全体の手間は $O(N\log N)$ である(Ari09 Theorem 5、Sect. VIII)。

逐次除去復号の誤りの確率

$W=\mathrm{BEC}(\varepsilon)$ とする。どの情報集合 $A$、凍結ビット、メッセージについても、逐次除去復号が $\hat u\ne u$ となる確率は
$$ P_e\le\sum_{i\in A}z_N^{(i)} $$
を満たす(一般の B-DMC では、凍結ビットについて平均した誤りの確率が $\sum_{i\in A}Z(W_N^{(i)})$ 以下になる。Ari09 Prop. 2)。

最初の誤りは消失出力でしか起こらない

送った $u$ を固定する。$\mathrm{BEC}(\varepsilon)$ の出力は、消える位置の集合 $S\subseteq\{1,\dots,N\}$ と、$k\notin S$ での $y_k=x_k$ で決まり、$S$ は $u$ と独立に確率 $\varepsilon^{\#S}(1-\varepsilon)^{N-\#S}$ で現れる。
$i\in A$ を固定し、正しい $u_1^{i-1}$ について、$u_1^{i-1}$ で始まり $E_N(v)_k=y_k$($k\notin S$)を満たす $v\in\mathbb F_2^N$ の集合 $\Gamma$ を考える。$\Gamma$ は $u$ を含み、$E_N$ が線形なので、部分空間 $L_S:=\{w\mid w_1^{i-1}=0,\ E_N(w)_k=0\ (k\notin S)\}$ の剰余類 $u+L_S$ である。定義から $W_N^{(i)}(y,u_1^{i-1}\mid b)$ は、$\Gamma$ のうち $v_i=b$ の元の個数に $2^{-(N-1)}\varepsilon^{\#S}(1-\varepsilon)^{N-\#S}$ を掛けたものである。$L_S$ のすべての元が $w_i=0$ を満たすなら、$\Gamma$ の元はすべて $v_i=u_i$ で、正しい $u_i$ の尤度だけが正になる。そうでなければ $\Gamma$ のちょうど半分が $v_i=0$ で、2 つの尤度は等しい(消失出力)。後者の条件は $S$ だけで決まるので、それを満たす $S$ の集合を $\mathcal S_i$ とし、$D_i:=\{S\in\mathcal S_i\}$ とおく。
$D_i$ の確率は $u$ によらないので、$u$ を一様に選んだときの確率、すなわち $W_N^{(i)}$ の消失確率 $z_N^{(i)}$ に等しい。
最初の誤りが段 $i$ で起こる事象を $F_i$ とする。$F_i$ の上では $\hat u_1^{i-1}=u_1^{i-1}$ なので、段 $i$ の判定は正しい $u_1^{i-1}$ を使っている。$D_i$ が起きていなければ正しい $u_i$ の尤度だけが正だから $\hat u_i=u_i$ となる。よって $F_i\subseteq D_i$ であり、凍結ビットで誤ることはないから
$$ P_e=P\Bigl(\bigcup_{i\in A}F_i\Bigr)\le\sum_{i\in A}P(D_i)=\sum_{i\in A}z_N^{(i)}.\qquad\square $$

Polar 符号は 2 値消失通信路の容量を達成する

$W=\mathrm{BEC}(\varepsilon)$、$0\le R< 1-\varepsilon$ とする。十分大きい $N=2^n$ について、速さ $R$ 以上の Polar 符号(凍結ビットは任意)であって、逐次除去復号での誤りの確率が、どのメッセージについても
$$ P_e\le C\,N^{-1/4} $$
となるものがある。ここで $C$ は $\varepsilon,R$ だけによる定数である。とくに容量 $1-\varepsilon$ 未満の任意の速さが、符号化と復号の手間 $O(N\log N)$ で達成できる。

thm-pc-rate の $A_N$ と定数 $C$ をとり、$K:=\#A_N\ge NR$ とする。$A_N$ の元の消失確率は $C N^{-5/4}$ 以下で、消失確率の小さい順に $K$ 個とった集合 $A$ でも同じ評価が成り立つ。prop-pc-sc-bound により
$$ P_e\le\sum_{i\in A}z_N^{(i)}\le K\cdot CN^{-5/4}\le C\,N^{-1/4}. $$
手間の評価は def-pc-synthetic の後の計算と def-pc-sc による。$\square$

通信路符号化定理 は容量未満の速さを達成する符号の 存在 をランダムな符号で示すが、符号の構成と復号の手間は与えない。thm-pc-capacity はその両方を与える。一方、prop-pc-count により、容量を超える速さでは、情報集合の全部を良い合成通信路にとることはできない。

一般の 2 値入力の通信路

2 値消失通信路以外では合成通信路はもう消失型ではなく、$Z$ の値は再帰式で正確には追えない。それでも次が成り立つ。

一般の B-DMC での分極と Polar 符号

$W$ を B-DMC とする。
(1) 1 段の変換は対称容量を保つ:$I(V^-)+I(V^+)=2I(V)$、$I(V^-)\le I(V^+)$。また $Z(V^+)=Z(V)^2$、$Z(V^-)\le2Z(V)-Z(V)^2$ であり、後者の等号は $V$ が消失型のときに限る(Ari09 Prop. 4–5)。
(2) 任意の $0< \delta< 1$ について、$I(W_N^{(i)})>1-\delta$ となる $i$ の割合は $I(W)$ に、$I(W_N^{(i)})< \delta$ となる $i$ の割合は $1-I(W)$ に近づく(Ari09 Theorem 1)。
(3) $R< I(W)$ なら、凍結ビットについて平均した逐次除去復号の誤りの確率が $O(N^{-1/4})$ となる速さ $R$ 以上の Polar 符号がある。$W$ が対称な通信路なら、凍結ビットは任意でよい(Ari09 Theorems 3–4)。
(4) $R< I(W)$ と $\beta< \frac12$ について、(3) の誤りの確率は $o(2^{-N^\beta})$ にできる。逆に $I(W)< 1$ なら、$\beta>\frac12$ について、一様に選んだ $i$ で $Z(W_N^{(i)})\ge2^{-N^\beta}$ となる確率は $1$ に近づく(AT09 Theorems 1–2)。

この記事では証明しない。対称な通信路(2 元対称通信路 $\mathrm{BSC}(p)$ など)では $I(W)$ は容量に等しいので、(3) から Polar 符号はその容量を達成する。

証明の方針と関連する結果を開く

(2) の証明では、$Z_k$ の代わりに $I(W_N^{(i)})$ から作った列 $I_k$ がマルチンゲールになること((1) の第 1 式)を使い、$I$ と $Z$ を結ぶ不等式で両者が同時に端に寄ることを示す。

Guruswami–Rudra–Sudan は、同じ構成を Bernoulli 分布に従う誤りの列の圧縮として定式化し、条件付きエントロピーの列が「局所的に分極する」ことから強い分極を導いて、$\mathrm{BSC}(p)$ で容量との差 $\epsilon$ を符号長 $\mathrm{poly}(1/\epsilon)$ で達成する(GRS25 Theorem 16.1.1, p. 312、Definition 16.5.2–Lemma 16.5.5, pp. 327–328)。

例と反例

消失確率 1/2 の通信路での表

$W=\mathrm{BEC}(\frac12)$ とする。再帰式から
$$ N=2:\ \Bigl(\frac34,\frac14\Bigr),\qquad N=4:\ \Bigl(\frac{15}{16},\frac9{16},\frac7{16},\frac1{16}\Bigr). $$
$N=8$ では次のとおりで、合計は $4=8\cdot\frac12$ である。

$i$12345678
$256\,z_8^{(i)}$2552252078117549311
$G_8$ の第 $i$ 行の重み12242448

次元 $4$ の Polar 符号の情報集合は $A=\{4,6,7,8\}$ で、prop-pc-sc-bound の上界は $\frac{81+49+31+1}{256}=\frac{81}{128}\approx0.633$。凍結ビットを $0$ とし、メッセージと消え方の全部で平均すると、逐次除去復号の誤りの確率は $\frac{1087}{4096}\approx0.265$ であった。上界は成り立っているが、短い符号では等号から遠い。

この $A$ は $G_8$ の重み $4$ 以上の行を選んだもので、得られる符号は長さ $8$ の 1 次の Reed–Muller符号(拡大 Hamming符号)である。行の重みで情報集合を選ぶ規則と、合成通信路の良さで選ぶ規則は、長くなると分かれる。

行の重みで選ぶと悪い合成通信路を含む

$W=\mathrm{BEC}(\frac12)$、$N=32$、次元 $16$ とする。重み $8$ 以上の行を選ぶと、選ばれなかった合成通信路より消失確率の大きいものが入る。

数値と長い符号での結果を開く

重み $8$ 以上の行(行番号 $i$ で $i-1$ の 2 進表記に $1$ が 3 個以上あるもの)を選ぶと $i=8$ が入る。ところが $z_{32}^{(8)}\approx0.597$ で、選ばれなかった $i=25$ の $z_{32}^{(25)}\approx0.403$ より悪い。$\sum_{i\in A}z_{32}^{(i)}$ は、行の重みで選ぶと約 $2.016$、Polar 符号では約 $1.823$ である。

Arıkan は、速さを固定して $N\to\infty$ とすると、行の重みで選ぶ規則に入る $i-1=0\cdots01\cdots1$ の合成通信路の容量が $0$ に近づき、逐次除去型の復号で Reed–Muller 符号は信頼できなくなることを示した(Ari09 Sect. X)。

2 元対称通信路での 1 段の変換

$W=\mathrm{BSC}(\frac1{10})$ では $Z(W)=0.6$、$Z(W^+)=0.36=Z(W)^2$ だが、$Z(W^-)\approx0.7684$ は $2Z-Z^2=0.84$ より真に小さい。従って 2 値消失通信路の再帰式 $z^-=2z-z^2$ は $\mathrm{BSC}$ では成り立たない。thm-pc-general (1) の不等式が等号にならない例である。

数値を開く

$Z(W)=2\sqrt{0.1\cdot0.9}=0.6$。数値計算により $I(W)\approx0.5310$ であり、$$I(W^-)\approx0.3199< I(W)< I(W^+)\approx0.7421,\qquad I(W^-)+I(W^+)\approx1.0620=2I(W)$$ となる(thm-pc-general (1) の第 1 式)。

反例:端に寄らないマルチンゲール

独立で一様な符号 $\sigma_k\in\{\pm1\}$ をとり、$X_0:=\frac12$、$X_{k+1}:=X_k+\sigma_{k+1}2^{-(k+3)}$ とおく。$|X_k-\frac12|\le\sum_{k\ge0}2^{-(k+3)}=\frac12\cdot\frac12$ なので $X_k\in[\frac14,\frac34]$ で、$(X_k)$ は $[0,1]$ に値をとるマルチンゲールである。極限 $X_\infty$ は存在するが $[\frac14,\frac34]$ にあり、$0$ にも $1$ にも近づかない。これは「有界なマルチンゲールなら端に寄る」が誤りであることを示す。thm-pc-polarization で効いているのは、揺れの大きさ $Z_k(1-Z_k)$ が中ほどで小さくならないことである。

主張反例満たされない条件
有界なマルチンゲールは $0$ か $1$ に収束するex-pc-martingale揺れが中ほどで下から押さえられること
どの通信路でも $Z(W^-)=2Z-Z^2$$\mathrm{BSC}(\frac1{10})$(ex-pc-bsc)消失型であること
行の重みの大きい順に選べば最良の情報集合$N=32$ の $\mathrm{BEC}(\frac12)$(ex-pc-rm)合成通信路の良さで選ぶこと
上界 $\sum_{i\in A}z_N^{(i)}$ は短い符号でも誤りの確率に近い$N=8$ の $\mathrm{BEC}(\frac12)$(ex-pc-bec-half)和集合の評価が等号に近いこと
容量を超える速さでも良い合成通信路だけで情報集合を作れるprop-pc-count速さ $< 1-\varepsilon$

関連項目

参考文献

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