携帯電話で「圏外ギリギリ」の弱い電波でも通話やデータ通信ができるのはなぜでしょうか。ノイズに埋もれた信号からビット列を取り出すには誤り訂正符号が欠かせませんが、長らく「どんな符号を使えばシャノンの通信路容量に到達できるのか」という問いには、満足のいく数学的な答えがありませんでした。2009年、トルコの研究者アリカン（Erdal Arıkan）が提案したPolar符号（極符号、polar code）は、「通信路容量を確実に達成すること」を初めて数学的に証明した符号であり、その美しさと実用性から5G NRの制御チャネルに正式採用されました。
Polar符号の核心はチャネル分極（channel polarization）という現象です。同じ品質のたくさんの通信路を巧みに組み合わせると、不思議なことに「ほぼ完璧に通る通信路」と「ほとんど何も通さない通信路」の2種類に分かれていきます。良い通信路に大事なビットを乗せ、悪い通信路には固定値（凍結ビット）を入れる——これがPolar符号のアイデアのすべてです。この単純なアイデアが、なぜ容量達成という強力な性質を生むのかを、本記事では数式の導出を一切省略せずに追いかけます。
Polar符号を理解すると、以下のような分野への応用が見えてきます。
- 5G/6G通信: 5G NRでは制御チャネル（PDCCH、PBCH等）にPolar符号が採用され、短いブロック長でも高い信頼性が求められる場面を支えています
- IoT・低遅延通信: 短パケット通信（short packet communication）でPolar符号 + CRC支援リスト復号（CA-SCL）が優れた性能を示し、URLLC（超高信頼低遅延通信）の鍵技術となっています
- 深宇宙・衛星通信: 低SNR環境での信頼通信に向けて、容量達成符号としてのPolar符号の研究が進んでいます
本記事の内容
- チャネル分極の直感と、容量保存・分極化の原理
- バタチャリヤ係数の再帰式による合成チャネルの信頼度評価と凍結ビット設計
- 逐次除去（SC: Successive Cancellation）復号のf関数・g関数の再帰構造の導出
- PythonによるN=256 Polar符号の構成とSC復号、AWGN通信路上のBER曲線のモンテカルロ評価
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- LDPC符号の理論 — スパースグラフ符号の原理と復号アルゴリズム — もう一つのシャノン限界級符号。反復復号とLLRの扱いが共通します
- 通信路容量とは — シャノンの情報理論の核心 — Polar符号が「達成する」ターゲットである通信路容量の定義
- AWGNチャネルモデルとBPSK復調 — 本記事のシミュレーションで使う雑音モデルと変調方式
チャネル分極とは — 良い通信路と悪い通信路に分ける
まず素朴なたとえから始めましょう。あなたが2人の配達人にそれぞれ手紙を1通ずつ託すとします。どちらの配達人も「3割の確率で手紙を落とす」程度の信頼性しかありません。普通に1人1通ずつ運ばせれば、両方とも「3割で失敗する平凡な配達人」のままです。
ところがアリカンは、2つの通信路をある特別な組み合わせ方でつなぐと、片方が「ほとんど落とさない超優秀な配達人」に、もう片方が「ほとんど落とす役立たず」に変質することを発見しました。2つを足して2で割れば平均は変わらないはずなのに、品質が両極端に「分極」してしまうのです。これを何段も繰り返すと、通信路の集団は「ほぼ完璧（容量1に近い）」なグループと「ほぼ無価値（容量0に近い）」なグループにくっきり二分されます。
この現象がチャネル分極です。Polar符号のアイデアは拍子抜けするほど単純です。
- たくさんの通信路を分極させる
- 「ほぼ完璧」なグループに情報ビットを乗せる
- 「ほぼ無価値」なグループには送信側・受信側が事前に知っている固定値（凍結ビット、frozen bit、通常は0）を入れる
無価値な通信路は元から何も伝えられないので、そこに既知の値を置いても情報の損失はありません。完璧な通信路だけを使って情報を運ぶので、誤りはほとんど起きない——これがPolar符号の戦略です。では、この「特別な組み合わせ方」とは具体的に何で、なぜ分極が起きるのかを数式で見ていきましょう。
基本変換 — 2つの通信路を1段で合成する
結合と分割
$W$ を二元入力離散無記憶通信路（B-DMC: Binary-input Discrete Memoryless Channel）とします。入力 $x \in \{0, 1\}$、出力 $y$、遷移確率 $W(y \mid x)$ で表されます。同一の $W$ を2つ用意し、2ビットの入力 $(u_1, u_2)$ を次のように変換してから送ります。
$$ x_1 = u_1 \oplus u_2, \quad x_2 = u_2 $$
ここで $\oplus$ はXOR（mod 2 の加算）です。$x_1$ を1本目の $W$ に、$x_2$ を2本目の $W$ に通し、出力 $(y_1, y_2)$ を得ます。送信側から見れば、これは入力 $(u_1, u_2)$ から出力 $(y_1, y_2)$ への合成通信路 $W_2$ を作ったことになります。その遷移確率は、$x_1, x_2$ が一意に決まることから
$$ W_2(y_1, y_2 \mid u_1, u_2) = W(y_1 \mid u_1 \oplus u_2) \, W(y_2 \mid u_2) $$
です。ここからが分極の肝です。この合成通信路を、$u_1$ と $u_2$ を順番に復号する2つの仮想的な通信路に「分割」します。
第1の分割通信路 $W^{-}$（$u_1$ を、$u_2$ を未知としたまま推定する通信路）:
$$ W^{-}(y_1, y_2 \mid u_1) = \sum_{u_2 \in \{0,1\}} \frac{1}{2} W_2(y_1, y_2 \mid u_1, u_2) = \frac{1}{2}\sum_{u_2} W(y_1 \mid u_1 \oplus u_2) W(y_2 \mid u_2) $$
$u_2$ について周辺化（平均化）しているのは、$u_1$ を復号する段階では $u_2$ がまだ分からないからです。$u_2$ は等確率で 0 か 1 とみなすので $1/2$ を掛けます。
第2の分割通信路 $W^{+}$（$u_1$ はすでに正しく分かっている前提で $u_2$ を推定する通信路）:
$$ W^{+}(y_1, y_2, u_1 \mid u_2) = \frac{1}{2} W_2(y_1, y_2 \mid u_1, u_2) = \frac{1}{2} W(y_1 \mid u_1 \oplus u_2) W(y_2 \mid u_2) $$
$W^{+}$ の出力には $y_1, y_2$ に加えて $u_1$ も含まれている点が重要です。これは「逐次的に復号する」という前提——$u_2$ を推定するときには $u_1$ の推定値が既知である——を反映しています。$W^{-}$ より $W^{+}$ のほうが多くの情報（$u_1$ の値）を使える分だけ「良い」通信路になります。
容量は保存され、信頼度は分極する
ここで決定的に重要な2つの性質を述べます。$I(W)$ を通信路 $W$ の対称容量（一様入力での相互情報量）とすると、
$$ I(W^{-}) + I(W^{+}) = 2 I(W) $$
$$ I(W^{-}) \leq I(W) \leq I(W^{+}) $$
が成り立ちます。第1式は容量保存則です。2つに分割しても、合計の伝送能力は元の2本分のまま変わりません。第2式は分極の芽です。一方の容量は下がり、もう一方は上がるので、2つの通信路は元の $W$ より差が開きます。等号が成立するのは $I(W)$ が 0 または 1 のとき（すでに分極しきっているとき）だけです。
直感的には、$W^{+}$ は $u_1$ という追加情報を使えるので有利、$W^{-}$ は $u_2$ の不確かさを背負うので不利、と理解できます。容量の総和は変わらないまま、片方に「良さ」が集まっていくのです。この基本変換を再帰的に積み重ねると、分極がどんどん進みます。次に、その再帰構造を見ましょう。
再帰的な構成 — N通信路への一般化
クロネッカー積による生成行列
基本変換を $n$ 段繰り返すと、$N = 2^n$ 本の通信路を一度に分極させられます。$N$ ビットの入力ベクトル $\bm{u} = (u_1, \dots, u_N)$ と送信ベクトル $\bm{x} = (x_1, \dots, x_N)$ の関係は、生成行列 $\bm{G}_N$ を使って
$$ \bm{x} = \bm{u} \, \bm{G}_N \pmod 2 $$
と書けます。生成行列はカーネル行列
$$ \bm{F} = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} $$
のクロネッカー積 $n$ 乗で与えられます。
$$ \bm{G}_N = \bm{F}^{\otimes n}, \quad \bm{F}^{\otimes n} = \bm{F} \otimes \bm{F}^{\otimes (n-1)} $$
ここで $\otimes$ はクロネッカー積です。たとえば $N = 4$（$n = 2$）なら
$$ \bm{F}^{\otimes 2} = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{pmatrix} $$
となります。アリカンの原論文ではビット反転置換 $\bm{B}_N$ を挟んで $\bm{G}_N = \bm{B}_N \bm{F}^{\otimes n}$ と定義しますが、置換は単なるインデックスの並べ替えであり符号の性能には影響しないため、本記事では簡単のため $\bm{G}_N = \bm{F}^{\otimes n}$ を採用します。$\bm{F}$ は2進数の世界で $\bm{F} = \bm{F}^{-1}$（自分自身が逆行列）という性質を持つので、符号化と復号で同じ構造を使い回せます。
合成チャネルの定義
この変換によって、$N$ 個の分割通信路 $W_N^{(i)}$（$i = 1, \dots, N$）が生まれます。第 $i$ 番目の通信路は、「$u_1, \dots, u_{i-1}$ がすでに分かっている前提で、$u_i$ を出力 $\bm{y}$ から推定する」仮想通信路です。
$$ W_N^{(i)}(\bm{y}, u_1^{i-1} \mid u_i) = \sum_{u_{i+1}^N} \frac{1}{2^{N-1}} W_N(\bm{y} \mid \bm{u}) $$
ここで $u_1^{i-1} = (u_1, \dots, u_{i-1})$ は既知ビット、$u_{i+1}^N = (u_{i+1}, \dots, u_N)$ はまだ未知の後続ビットで、これらを周辺化（平均化）しています。$1$ 段の基本変換における $W^{-}, W^{+}$ がそれぞれ $W_2^{(1)}, W_2^{(2)}$ に対応します。重要なのは、これらの通信路が次の再帰関係を満たすことです。
$$ W_{2N}^{(2i-1)} = (W_N^{(i)})^{-}, \quad W_{2N}^{(2i)} = (W_N^{(i)})^{+} $$
つまり、$N$ 本の分極済み通信路それぞれにもう一度基本変換を適用すると $2N$ 本になり、奇数番目が $W^{-}$ 型（劣化）、偶数番目が $W^{+}$ 型（向上）になります。この再帰を繰り返すと、容量保存則によって総容量は $N \cdot I(W)$ に保たれたまま、個々の通信路の容量 $I(W_N^{(i)})$ は 0 か 1 のどちらかにどんどん近づいていきます。
分極定理
アリカンが証明した分極定理は次のように述べられます。任意の B-DMC $W$ と任意の $\delta \in (0, 1)$ について、$N \to \infty$ で
$$ \frac{\#\{i : I(W_N^{(i)}) > 1 – \delta\}}{N} \to I(W), \quad \frac{\#\{i : I(W_N^{(i)}) < \delta\}}{N} \to 1 - I(W) $$
が成り立ちます。言葉にすると、「容量がほぼ1の通信路の割合は $I(W)$ に、容量がほぼ0の通信路の割合は $1 – I(W)$ に収束し、中途半端な通信路は消えてなくなる」ということです。良い通信路の割合がちょうど容量 $I(W)$ になるので、そこへ情報を乗せれば符号化率 $R = I(W)$、すなわち容量達成が実現します。これがPolar符号が容量達成符号である理由です。
理論的には容量がほぼ1の通信路を選べばよいのですが、実際にどの通信路が良いかを定量的に評価する尺度が必要です。次にその評価指標を導入します。
バタチャリヤ係数による信頼度評価と凍結ビット設計
バタチャリヤ係数とは
各分割通信路 $W_N^{(i)}$ の「悪さ」を測る指標として、バタチャリヤ係数（Bhattacharyya parameter）$Z(W)$ を使います。直感的には、通信路に 0 を送ったときの出力分布と 1 を送ったときの出力分布が「どれだけ見分けにくいか（重なっているか）」を表す量で、0 に近いほど良い通信路、1 に近いほど悪い通信路です。定義は
$$ Z(W) = \sum_{y} \sqrt{W(y \mid 0) \, W(y \mid 1)} $$
です。2つの分布が完全に分離していれば積の平方根は至るところ 0 になり $Z = 0$、完全に一致していれば $Z = 1$ になります。バタチャリヤ係数は最尤推定の誤り確率の上界を与え、$1$ ビット伝送の誤り確率 $P_e$ は $P_e \leq Z(W)$ で抑えられます。容量 $I(W)$ とは $Z$ が小さいほど $I$ が大きいという逆向きの関係にあります。
再帰式の導出
バタチャリヤ係数の何が嬉しいかというと、合成チャネルに対して閉じた再帰式が成り立つことです。基本変換に対して
$$ Z(W^{+}) = Z(W)^2 $$
$$ Z(W^{-}) \leq 2 Z(W) – Z(W)^2 $$
が成り立ち、特に二元消失通信路（BEC）では下側も等号
$$ Z(W^{-}) = 2 Z(W) – Z(W)^2 $$
になります。$Z(W^{+}) = Z(W)^2$ をきちんと導いておきましょう。定義より
$$ Z(W^{+}) = \sum_{y_1, y_2, u_1} \sqrt{W^{+}(y_1, y_2, u_1 \mid 0) \, W^{+}(y_1, y_2, u_1 \mid 1)} $$
$W^{+}$ の定義 $W^{+}(y_1, y_2, u_1 \mid u_2) = \frac{1}{2} W(y_1 \mid u_1 \oplus u_2) W(y_2 \mid u_2)$ を代入します。
$$ Z(W^{+}) = \sum_{y_1, y_2, u_1} \frac{1}{2}\sqrt{W(y_1 \mid u_1) W(y_2 \mid 0) \cdot W(y_1 \mid u_1 \oplus 1) W(y_2 \mid 1)} $$
ここで $u_2 = 0$ のとき $u_1 \oplus u_2 = u_1$、$u_2 = 1$ のとき $u_1 \oplus 1$ を使いました。$y_2$ に関する項と $y_1$ に関する項が分離できるので、和を分配します。
$$ Z(W^{+}) = \frac{1}{2}\left(\sum_{y_2}\sqrt{W(y_2 \mid 0) W(y_2 \mid 1)}\right) \left(\sum_{y_1, u_1}\sqrt{W(y_1 \mid u_1) W(y_1 \mid u_1 \oplus 1)}\right) $$
第1因子はまさに $Z(W)$ の定義そのものです。第2因子は $u_1 = 0$ と $u_1 = 1$ の両方で $\sqrt{W(y_1\mid 0)W(y_1\mid 1)}$ という同じ和になるので $2Z(W)$ です。したがって
$$ Z(W^{+}) = \frac{1}{2} \cdot Z(W) \cdot 2 Z(W) = Z(W)^2 $$
が得られました。$Z(W) \leq 1$ なので $Z(W)^2 \leq Z(W)$、つまり $W^{+}$ は必ず元より良く（$Z$ が小さく）なります。一方 $Z(W^{-}) \geq Z(W)$ なので $W^{-}$ は悪くなり、ここでも分極が確認できます。
凍結ビットの選び方
実際の符号設計では、初期通信路のバタチャリヤ係数 $Z(W)$ から出発し、上の再帰式を $n$ 段適用して $N$ 個の $Z(W_N^{(i)})$ をすべて計算します。BEC近似（消失確率 $\epsilon$ から $Z = \epsilon$ で出発し、両方を等号の再帰式で更新）を使えば、AWGN通信路でも実用的に十分良い設計が得られます。手順は次のとおりです。
- 設計SNRから初期バタチャリヤ係数 $Z_0$ を決める
- 再帰式 $z \mapsto (2z – z^2, \; z^2)$ を $n$ 段適用し、各通信路の $Z(W_N^{(i)})$ を求める
- $Z(W_N^{(i)})$ が小さい（信頼度が高い）順に $K$ 本の通信路を選び、そこに情報ビットを置く
- 残り $N – K$ 本を凍結ビット集合 $\mathcal{F}$ とし、固定値（通常 0）を入れる
符号化率は $R = K/N$ です。良い通信路だけに情報を乗せるので、$N$ が大きくなるほど誤り率が下がります。この凍結ビット設計こそが、Polar符号の「設計」の本体です。
設計ができたところで、いよいよ受信側の復号アルゴリズムへ進みます。Polar符号の真価は、この再帰構造をそのまま使った効率的な復号にあります。
逐次除去（SC）復号の導出
逐次的に1ビットずつ決める
Polar符号の標準的な復号法が逐次除去復号（SC: Successive Cancellation decoding）です。名前のとおり、$u_1, u_2, \dots, u_N$ をこの順に1つずつ推定していきます。第 $i$ ビットを推定するときには、すでに確定した $\hat{u}_1, \dots, \hat{u}_{i-1}$ を既知として利用します。これはまさに分割通信路 $W_N^{(i)}$ の定義（先行ビットが既知）に対応しています。
判定規則は、凍結ビットかどうかで分かれます。
$$ \hat{u}_i = \begin{cases} 0 & (i \in \mathcal{F}, \ \text{凍結ビット}) \\[4pt] \displaystyle \arg\max_{u \in \{0,1\}} W_N^{(i)}(\bm{y}, \hat{u}_1^{i-1} \mid u) & (i \notin \mathcal{F}, \ \text{情報ビット}) \end{cases} $$
凍結ビットは送受信で既知なので無条件に 0 とします。情報ビットは、先行ビットの推定値を条件として尤度が高いほうを選びます。この「尤度の最大化」を効率よく行うために、LDPC符号と同様に対数尤度比（LLR） で計算します。
LLRと f関数・g関数
ビット $u$ に関するLLRを
$$ L = \ln \frac{W(\cdot \mid u = 0)}{W(\cdot \mid u = 1)} $$
と定義します。SC復号は、生成行列の再帰構造（バタフライ構造）をたどってLLRを上位から下位へ伝播させます。基本変換 $x_1 = u_1 \oplus u_2, \; x_2 = u_2$ の1段に対して、下位の2つのLLR $L_1, L_2$（$x_1, x_2$ に対応する通信路から来たLLR）から、$u_1, u_2$ のLLRを計算する2つの演算が現れます。
f関数（$u_1$ 用、$W^{-}$ に対応）: $u_1$ は $u_2$ が未知のまま推定するので、$W^{-}$ の周辺化が反映されます。正確には
$$ L(u_1) = f(L_1, L_2) = 2 \tanh^{-1}\!\left(\tanh\frac{L_1}{2}\tanh\frac{L_2}{2}\right) $$
これは2つのLLRを「XORの確率」として合成する演算で、LDPC符号の検査ノード更新と同じ形をしています。実装では数値的に扱いやすい min-sum近似 がよく使われます。
$$ f(L_1, L_2) \approx \operatorname{sign}(L_1)\operatorname{sign}(L_2)\,\min(|L_1|, |L_2|) $$
絶対値の小さいほう（信頼度の低いほう）が結果のボトルネックになり、符号は2つの符号の積で決まる、というXORの直感に合致します。
g関数（$u_2$ 用、$W^{+}$ に対応）: $u_2$ を推定するときは $u_1$ の推定値 $\hat{u}_1$ がすでに分かっています。$x_1 = u_1 \oplus u_2$ なので $\hat{u}_1$ の値に応じて符号を反転して足し合わせます。
$$ L(u_2) = g(L_1, L_2, \hat{u}_1) = (-1)^{\hat{u}_1} L_1 + L_2 $$
$\hat{u}_1 = 0$ なら $L_1 + L_2$（2つの独立な情報源のLLRを加算）、$\hat{u}_1 = 1$ なら $-L_1 + L_2$（$x_1$ のビットが反転している効果を打ち消す）となります。これは変数ノードの加算更新に対応します。f関数で $u_1$ を先に確定させ、その結果を使ってg関数で $u_2$ を確定させる——この「先に決めた結果を使い回す」順序こそが「逐次除去」の名の由来です。
木構造としての再帰
$N = 2^n$ の符号では、f関数とg関数の再帰が深さ $n$ の二分木を成します。根（ルート）には受信LLR $L_{\mathrm{ch}}(y_j) = 2 y_j / \sigma^2$ が $N$ 個並びます（AWGN通信路、$y_j$ は受信値、$\sigma^2$ は雑音分散）。各ノードで、
- 左の子へは f関数でLLRを渡し（$u$ の前半グループを推定）、
- 左の子から返ってきた部分和ビット（partial sum、確定ビットを生成行列で前向きに伝搬した値）を使い、
- 右の子へは g関数でLLRを渡す（後半グループを推定）、
という手順を再帰的に行います。葉（リーフ）に到達したら、凍結ビットなら 0、情報ビットならLLRの符号で硬判定します。葉で決めたビットは親へ戻り、g関数の $\hat{u}_1$ や次のグループの計算に使われます。計算量はこの二分木をたどるコストで決まり、$O(N \log N)$ です。これはLDPCのBP復号と同等のオーダーで、$N$ が大きくても実用的です。
復号の仕組みが分かったので、次は実際にN=256のPolar符号を構成してAWGN通信路でBERを測り、符号化利得を確認しましょう。
Pythonによる実装
凍結ビット集合の設計
まず、バタチャリヤ係数の再帰式を使って、どの通信路に情報ビットを置くか（凍結ビット集合）を設計します。BEC近似で設計SNRから初期 $Z_0$ を決め、$n$ 段の再帰で各通信路の $Z$ を求めます。
import numpy as np
import matplotlib.pyplot as plt
def design_polar_code(N, K, design_snr_db):
"""バタチャリヤ係数の再帰式で凍結ビット集合を設計する。
戻り値: 情報ビット位置(信頼度の高いK本)の昇順インデックス配列"""
n = int(np.log2(N))
# 設計SNRからBEC近似の初期バタチャリヤ係数を決める
snr = 10 ** (design_snr_db / 10)
z = np.exp(-snr) # AWGN近似での初期Z(W)
Z = np.array([z]) # 1本から開始
# n段の再帰: 各段で本数が2倍になる
for _ in range(n):
Z_next = np.zeros(2 * len(Z))
for i, zi in enumerate(Z):
Z_next[2 * i] = 2 * zi - zi ** 2 # W^- (劣化)
Z_next[2 * i + 1] = zi ** 2 # W^+ (向上)
Z = Z_next
# Zが小さい(信頼度が高い)順にK本を情報ビットに割り当て
reliability_order = np.argsort(Z) # Z昇順 = 信頼度降順
info_positions = np.sort(reliability_order[:K])
return info_positions, Z
# N=256, 符号化率 R=0.5 (K=128), 設計SNR 2dB
N, K = 256, 128
info_pos, Z = design_polar_code(N, K, design_snr_db=2.0)
print(f"N={N}, K={K}, R={K/N}")
print(f"情報ビット位置の数: {len(info_pos)}")
print(f"最良チャネルのZ: {Z.min():.2e}, 最悪チャネルのZ: {Z.max():.4f}")
このコードでは、1本の通信路から出発して再帰式 $z \mapsto (2z – z^2,\ z^2)$ を $n = 8$ 段適用し、$N = 256$ 本それぞれのバタチャリヤ係数を計算しています。出力を見ると最良チャネルの $Z$ は極めて 0 に近く、最悪チャネルの $Z$ は 1 に近い値になっており、通信路がはっきり両極端に分極していることが数値で確認できます。信頼度の高い上位 $K = 128$ 本を情報ビット位置に選ぶことで、符号化率 $R = 0.5$ の符号が設計できました。
分極の様子を可視化する
設計したバタチャリヤ係数を並べて、本当に「良い通信路」と「悪い通信路」に二分されているかを目で確かめます。
# 各チャネルのバタチャリヤ係数をソートして分布を見る
Z_sorted = np.sort(Z)
plt.figure(figsize=(8, 5))
plt.plot(np.arange(N), Z_sorted, '.', markersize=4, color='tab:blue')
plt.axhline(0.5, color='gray', linestyle='--', alpha=0.6)
plt.xlabel('Channel index (sorted by reliability)')
plt.ylabel('Bhattacharyya parameter $Z$')
plt.title(f'Channel Polarization (N={N}, design SNR=2dB)')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
このグラフから、チャネル分極の本質がはっきり読み取れます。バタチャリヤ係数を昇順に並べると、多くの通信路が $Z \approx 0$（ほぼ完璧）か $Z \approx 1$（ほぼ無価値）のどちらかに張り付いており、中間の値を取る通信路はごく少数です。これはまさに分極定理が予言する「中途半端な通信路が消える」現象であり、左側の $Z$ が小さい通信路群に情報ビットを乗せれば誤りを抑えられることが視覚的に納得できます。
符号化の実装
生成行列 $\bm{F}^{\otimes n}$ による符号化を実装します。行列を陽に持たず、再帰的なバタフライ演算で $O(N \log N)$ で計算します。
def polar_encode(u):
"""生成行列 F^{⊗n} による符号化 (in-placeのバタフライ演算)。
x = u F^{⊗n} (mod 2) を再帰的に計算する。"""
N = len(u)
x = u.copy()
step = 1
while step < N:
for start in range(0, N, 2 * step):
for j in range(start, start + step):
# F = [[1,0],[1,1]] のバタフライ: 上半分にXORを足し込む
x[j] = x[j] ^ x[j + step]
step *= 2
return x
def encode_message(msg_bits, info_pos, N):
"""情報ビットを信頼チャネルに配置し、凍結ビットは0にして符号化"""
u = np.zeros(N, dtype=int)
u[info_pos] = msg_bits # 情報ビットを信頼度の高い位置へ
x = polar_encode(u) # 凍結ビットは0のまま
return x, u
# 動作確認: ランダムな情報ビットを符号化
rng = np.random.default_rng(0)
msg = rng.integers(0, 2, size=K)
x, u = encode_message(msg, info_pos, N)
print(f"送信符号語の長さ: {len(x)}, 重み(1の数): {x.sum()}")
このコードでは、情報ビットを設計済みの信頼チャネル位置 info_pos に配置し、凍結ビット位置を 0 のままにして生成行列を作用させています。バタフライ演算は $\bm{F}$ の構造（上半分に下半分をXORで足し込む）を段階的に適用するもので、行列積を陽に計算するより圧倒的に高速です。出力から、長さ $N = 256$ の符号語が正しく生成されていることが確認できます。
SC復号の実装
f関数・g関数の再帰でSC復号を実装します。LLRを上位から下位へ伝播させ、確定ビット（部分和）を下位から上位へ戻します。
def f_func(l1, l2):
"""f関数 (min-sum近似): W^- に対応するLLR合成"""
return np.sign(l1) * np.sign(l2) * np.minimum(np.abs(l1), np.abs(l2))
def g_func(l1, l2, u_sum):
"""g関数: W^+ に対応するLLR合成 (確定ビットu_sumで符号反転)"""
return (1 - 2 * u_sum) * l1 + l2 # u_sum=0 -> l1+l2, u_sum=1 -> -l1+l2
def sc_decode(llr, info_pos, N):
"""逐次除去(SC)復号。llr: 受信LLR配列(長さN)"""
n = int(np.log2(N))
frozen = np.ones(N, dtype=bool)
frozen[info_pos] = False # 情報ビット位置はFalse
u_hat = np.zeros(N, dtype=int)
def recurse(llr_in, depth, offset):
"""長さ len(llr_in) の部分問題を解き、確定ビット列を返す"""
m = len(llr_in)
if m == 1:
idx = offset # この葉のビット位置
if frozen[idx]:
u_hat[idx] = 0 # 凍結ビットは0
else:
u_hat[idx] = 0 if llr_in[0] >= 0 else 1 # 硬判定
return np.array([u_hat[idx]])
half = m // 2
l1, l2 = llr_in[:half], llr_in[half:]
# 左の子: f関数でLLRを渡す
left_llr = f_func(l1, l2)
u_left = recurse(left_llr, depth + 1, offset)
# 右の子: 左の確定ビットを使ってg関数でLLRを渡す
right_llr = g_func(l1, l2, u_left)
u_right = recurse(right_llr, depth + 1, offset + half)
# 部分和を親へ戻す (F のバタフライ: 上半分にXOR)
return np.concatenate([(u_left ^ u_right), u_right])
recurse(llr, 0, 0)
return u_hat[info_pos] # 情報ビットのみ取り出す
このコードがSC復号の心臓部です。recurse は長さ $m$ の部分問題を、f関数で左半分のLLRを作って再帰し、その確定ビットをg関数に渡して右半分を再帰する、という分割統治で解いています。葉に到達したら凍結ビットは 0、情報ビットはLLRの符号で硬判定します。親へ戻す際に上半分へXOR（部分和）を取っているのは、生成行列 $\bm{F}$ の前向き伝搬を逆算しているためで、これがg関数で使う $\hat{u}_1$ に相当します。再帰の深さは $n = \log_2 N$ なので計算量は $O(N \log N)$ です。
AWGN通信路でのBERシミュレーション
設計・符号化・復号がそろったので、AWGN通信路上でビット誤り率（BER）をモンテカルロで測り、未符号化BPSKと比較して符号化利得を確認します。
def simulate_ber(N, K, info_pos, ebn0_db_range, num_frames=2000, seed=1):
"""Polar符号のBERをモンテカルロで測定"""
rng = np.random.default_rng(seed)
R = K / N
ber_polar, ber_uncoded = [], []
from scipy.special import erfc
for ebn0_db in ebn0_db_range:
ebn0 = 10 ** (ebn0_db / 10)
sigma = np.sqrt(1 / (2 * R * ebn0)) # 符号化率を考慮した雑音標準偏差
ber_uncoded.append(0.5 * erfc(np.sqrt(ebn0))) # 未符号化の理論BER
bit_errors, total_bits = 0, 0
for _ in range(num_frames):
msg = rng.integers(0, 2, size=K)
x, _ = encode_message(msg, info_pos, N)
s = 1 - 2 * x # BPSK: 0->+1, 1->-1
y = s + sigma * rng.standard_normal(N) # AWGN
llr = 2 * y / (sigma ** 2) # 受信LLR
msg_hat = sc_decode(llr, info_pos, N)
bit_errors += np.sum(msg_hat != msg)
total_bits += K
ber_polar.append(max(bit_errors / total_bits, 1e-6))
return ber_polar, ber_uncoded
ebn0_range = np.arange(0, 6.5, 0.5)
ber_polar, ber_uncoded = simulate_ber(N, K, info_pos, ebn0_range, num_frames=2000)
ここでは各 $E_b/N_0$ について、ランダムなメッセージを符号化してBPSK変調し、AWGN雑音を加えてから受信LLR $2y/\sigma^2$ を計算し、SC復号して誤りビット数を数えています。雑音の標準偏差 $\sigma$ を符号化率 $R$ で補正しているのは、符号化によって増えた冗長ビット分のエネルギー配分を公平に比較するためです。続いてBER曲線を描きます。
plt.figure(figsize=(8, 5))
plt.semilogy(ebn0_range, ber_uncoded, 'b--', label='Uncoded BPSK (theory)')
plt.semilogy(ebn0_range, ber_polar, 'ro-', label=f'Polar SC (N={N}, K={K})')
plt.xlabel('$E_b/N_0$ (dB)')
plt.ylabel('BER')
plt.title('Polar Code BER Performance (AWGN, SC decoding)')
plt.legend()
plt.grid(True, which='both', alpha=0.3)
plt.ylim(1e-6, 1)
plt.tight_layout()
plt.show()
このBER曲線から、Polar符号の効果が3点読み取れます。第一に、同じBERを達成するのに必要な $E_b/N_0$ がPolar符号では未符号化より数dB低く、明確な符号化利得が得られています。たとえば BER $= 10^{-3}$ 付近では、未符号化が約7dB必要なのに対しPolar符号は数dB低い値で到達します。第二に、$E_b/N_0$ がある値を超えるとBERが急降下するウォーターフォール領域が見えます。これは分極が十分に進む領域に対応します。第三に、$N = 256$ という比較的短い符号長でも利得が確認でき、符号長を伸ばせばカーブはさらに急峻になります。なお、SC復号は1ビットずつ確定するため誤りの伝搬が起きやすく、実用ではCRCを併用するリスト復号（CA-SCL）でこの欠点を補います。
符号長による性能の違い
最後に、符号長 $N$ を変えて分極の進み具合がBERにどう効くかを比較します。
plt.figure(figsize=(8, 5))
for N_test in [64, 128, 256, 512]:
info_t, _ = design_polar_code(N_test, N_test // 2, design_snr_db=2.0)
ber_t, _ = simulate_ber(N_test, N_test // 2, info_t,
ebn0_range, num_frames=1500, seed=7)
plt.semilogy(ebn0_range, ber_t, 'o-', markersize=4, label=f'N={N_test}, R=0.5')
plt.xlabel('$E_b/N_0$ (dB)')
plt.ylabel('BER')
plt.title('Effect of Block Length on Polar Code (SC, R=0.5)')
plt.legend()
plt.grid(True, which='both', alpha=0.3)
plt.ylim(1e-6, 1)
plt.tight_layout()
plt.show()
この比較から、符号長を伸ばすほどBER曲線が左下へ移動し、同じ $E_b/N_0$ でより低いBERを達成できることが分かります。これは分極定理の「$N \to \infty$ で良い通信路がきれいに分離する」という主張の有限長版であり、短い $N$ では分極が不完全なため中途半端な通信路が残り利得が小さく、長い $N$ では分極が進んで符号化利得が大きくなる、という理論的予測がシミュレーションで裏付けられています。実用の5G NRでは数百ビット規模の制御情報にPolar符号が使われており、本実装と同じ原理が動いているわけです。
まとめ
本記事では、Polar符号とSC復号の理論・導出・実装を解説しました。
- チャネル分極: 同一通信路を $x_1 = u_1 \oplus u_2,\ x_2 = u_2$ という基本変換で組み合わせ、$W^{-}$（劣化）と $W^{+}$（向上）に分割する操作を再帰すると、容量保存則 $I(W^-) + I(W^+) = 2I(W)$ を保ったまま個々の通信路の容量が 0 か 1 に分極します
- 容量達成: 分極定理により、容量がほぼ1の通信路の割合は $I(W)$ に収束するため、そこへ情報ビットを乗せると符号化率が容量に等しくなり、容量達成が実現します
- バタチャリヤ係数: $Z(W^+) = Z(W)^2$、$Z(W^-) = 2Z(W) – Z(W)^2$（BEC）という再帰式で各通信路の信頼度を評価し、$Z$ の小さい通信路に情報ビット、大きい通信路に凍結ビットを割り当てます
- SC復号: f関数（min-sum近似によるXOR的合成）とg関数（確定ビットで符号反転した加算）の二分木再帰で、$u_1$ から順に1ビットずつ $O(N\log N)$ で復号します
- 実装と検証: N=256のPolar符号をAWGN通信路で評価し、未符号化BPSKに対する明確な符号化利得と、符号長を伸ばすほど性能が向上する分極の効果を確認しました
Polar符号は、シャノンの理論限界を「証明付きで」達成する初めての符号という理論的金字塔でありながら、5G制御チャネルという最先端の実用にも使われている稀有な符号です。SC復号の弱点である誤り伝搬は、CRC支援リスト復号（CA-SCL）によって克服され、短ブロック長ではLDPC符号やターボ符号を凌ぐ性能を発揮します。
次のステップとして、以下の記事も参考にしてください。
- LDPC符号の理論 — スパースグラフ符号の原理と復号アルゴリズム — LLRメッセージパッシングの考え方が共通する、もう一つの容量級符号
- 通信路容量とは — シャノンの情報理論の核心 — Polar符号が達成するターゲットの定義と意味
- AWGNチャネルモデルとBPSK復調 — 本記事のシミュレーションの土台となる雑音モデル