通信における最も根本的な問いの一つは、「雑音のある通信路で、どこまで正確に情報を送れるのか？」というものです。1948年、クロード・シャノンは通信路容量 $C$ という理論限界を示し、$C$ 以下の伝送レートであれば誤り率を限りなくゼロに近づけられることを証明しました。しかし、この証明はランダム符号を用いた存在証明であり、「具体的にどのような符号を使えば限界に到達できるのか」という構成的な問いには答えていませんでした。
それから60年以上もの間、ターボ符号やLDPC符号がシャノン限界に極めて近い性能を実現してきましたが、理論的にシャノン限界を達成する構成的な符号は見つかっていませんでした。2009年、Erdal Arıkanが発表したポーラー符号（Polar Code）は、この長年の未解決問題に終止符を打ちました。ポーラー符号は、チャネル分極（Channel Polarization）という美しいメカニズムにより、符号長を無限にすると厳密にシャノン限界を達成することが証明された初めての符号です。
ポーラー符号を理解すると、以下のような広い分野への見通しが開けます。
- 5G NR（New Radio）の制御チャネル符号化: 3GPPは5Gの制御チャネル（PDCCH, PUCCH）にポーラー符号を採用しました。次世代通信規格を理解するための必須知識です
- 情報理論の構成的達成: シャノン限界の「存在証明」から「構成的証明」へと進化する、情報理論の歴史的マイルストーンです
- 誤り訂正符号の設計原理: チャネル分極という全く新しい符号設計パラダイムは、LDPC符号やターボ符号とは根本的に異なるアプローチであり、符号理論の理解を深めます
本記事の内容
- チャネル分極の直感的理解と数学的定式化
- 2×2基本変換行列とクロネッカー積による構成
- チャネル分極定理の証明概要
- 情報ビットと凍結ビットの配置設計
- SC（逐次キャンセレーション）復号アルゴリズム
- SCL（逐次キャンセレーションリスト）復号による性能向上
- 5G NRにおけるポーラー符号の採用
- Pythonでのチャネル分極シミュレーションとSC復号の実装
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
ポーラー符号の歴史的意義
シャノン限界と構成的符号の探究
1948年にシャノンが発表した通信路符号化定理は、二元対称通信路（BSC）やAWGN通信路における通信路容量 $C$ を定義し、伝送レート $R < C$ であれば誤り率を任意に小さくできることを示しました。しかし、この定理はランダムに生成した符号の集合上で平均をとるという確率的議論に基づいており、「具体的にどの符号を使えばよいか」は示していません。
その後の数十年にわたり、研究者たちはシャノン限界に到達する実用的な符号を探し求めました。1993年にBerrou、Glavieux、Thitimajshimaが発明したターボ符号は、反復復号によりシャノン限界に0.5 dB以内まで迫る画期的な成果でした。1996年にはGallagerが1960年代に提案していたLDPC符号が再発見され、やはりシャノン限界に極めて近い性能を示しました。
しかし、これらの符号はいずれも「経験的にシャノン限界に近い」ことがシミュレーションで確認されたものであり、理論的にシャノン限界を達成することが厳密に証明されたわけではありませんでした。
Arıkanの画期的論文
2009年、トルコのビルケント大学のErdal Arıkanは、IEEE Transactions on Information Theoryに “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Discrete Memoryless Channels” を発表しました。この論文で提案されたポーラー符号は、以下の点で画期的でした。
- 構成的: 符号の具体的な構成方法が明示的に与えられている
- 容量達成: 符号長 $N \to \infty$ でシャノン限界を厳密に達成することが数学的に証明されている
- 低複雑度: 符号化は $O(N \log N)$、SC復号も $O(N \log N)$ で実行できる
この成果は、シャノンの定理から60年以上を経て、通信路符号化定理の「構成的証明」を与えたものと言えます。Arıkanはこの業績により、2018年にIEEEリチャード・W・ハミング賞を受賞しています。
ポーラー符号の核心は「チャネル分極」という現象にあります。次のセクションでは、このチャネル分極が何を意味するのかを直感的に理解していきましょう。
チャネル分極の直感的理解
良いチャネルと悪いチャネルへの二極化
チャネル分極を一言で表すなら、「複数の同一チャネルを特定の方法で組み合わせると、チャネルが”良いもの”と”悪いもの”に二極化する」という現象です。
日常的なアナロジーで考えてみましょう。教室に30人の生徒がいて、全員の学力が平均的（例えば偏差値50）だとします。ここで、ある特殊な組分けとグループ学習を行うと、半分のグループは学力が大きく向上し（偏差値70以上）、残り半分は学力が低下する（偏差値30以下）という現象が起きたとします。全体の平均は変わらないのに、個々のグループの学力は極端に分かれる — これがチャネル分極のイメージです。
通信路の文脈では、$N$ 本の同一な二元入力離散無記憶通信路（B-DMC）$W$ を特定の線形変換で結合すると、$N$ 本の合成チャネル $W_N^{(i)}$（$i = 1, 2, \dots, N$）が得られます。$N \to \infty$ のとき、これらの合成チャネルは以下のように分極します。
- ほぼ完全なチャネル（対称容量 $\approx 1$）: 情報をほぼ誤りなく伝送できる。その割合は通信路容量 $I(W)$ に一致する
- ほぼ無用なチャネル（対称容量 $\approx 0$）: 情報をほとんど伝送できない。その割合は $1 – I(W)$ に一致する
中間的な品質のチャネルはほとんど存在しなくなります。この二極化こそがチャネル分極の本質です。
ポーラー符号の設計思想
チャネル分極が起きるなら、符号の設計方針は明確です。
- 良いチャネル（容量 $\approx 1$）には情報ビットを載せる — これらは正確に伝送される
- 悪いチャネル（容量 $\approx 0$）には凍結ビット（frozen bit）を載せる — 送信側と受信側で事前に既知の固定値（通常は0）を入れる
良いチャネルの数は $N \cdot I(W)$ に近づくため、伝送レートは $R \approx I(W) = C$ となり、シャノン限界が達成されます。
この発想は、従来の誤り訂正符号の設計思想とは根本的に異なります。ターボ符号やLDPC符号は、冗長ビットを付加して受信側で誤りを訂正するという「符号語空間を賢く設計する」アプローチです。一方、ポーラー符号は「チャネル自体を変換して、良いチャネルだけを使う」というアプローチをとります。
それでは、チャネル分極を実現する具体的な数学的構成を見ていきましょう。
2×2基本変換行列
最小単位の結合
チャネル分極の構成は、$2 \times 2$ の基本変換行列（カーネル）から始まります。2本の独立な通信路 $W$ を組み合わせる最小の操作を考えます。
2つの入力ビット $u_1, u_2 \in \{0, 1\}$ に対し、以下の線形変換（$\text{GF}(2)$ 上、すなわち排他的論理和 XOR による演算）を施します。
$$ \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} u_1 \\ u_2 \end{pmatrix} $$
$\text{GF}(2)$ 上の演算なので、具体的には次のようになります。
$$ x_1 = u_1 \oplus u_2, \quad x_2 = u_2 $$
ここで $\oplus$ は排他的論理和（XOR、$\text{GF}(2)$ 上の加算）です。$x_1$ と $x_2$ はそれぞれ独立な通信路 $W$ を通して送信され、受信側では $y_1$ と $y_2$ が観測されます。
この基本行列を $\bm{F}_2$ と書きます。
$$ \bm{F}_2 = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} $$
2つの合成チャネル
この結合操作により、2つの合成チャネル（synthetic channel）が生まれます。
合成チャネル $W_2^{(1)}$（$u_1$ に対するチャネル）:
$u_1$ を復号する際、$u_2$ の値はまだわかりません。受信者は $(y_1, y_2)$ の観測のみから $u_1$ を推定する必要があります。このチャネルの遷移確率は次のように書けます。
$$ W_2^{(1)}(y_1, y_2 | u_1) = \sum_{u_2} \frac{1}{2} W(y_1 | u_1 \oplus u_2) W(y_2 | u_2) $$
ここで、$u_2$ が等確率で $0$ または $1$ をとると仮定しているため、$1/2$ の重みが付いています。$u_2$ の不確実性が $u_1$ の推定を困難にするため、$W_2^{(1)}$ は元のチャネル $W$ よりも劣化します。
合成チャネル $W_2^{(2)}$（$u_2$ に対するチャネル）:
$u_2$ を復号する際、$u_1$ はすでに正しく復号されているとします（逐次キャンセレーション復号の仮定）。受信者は $(y_1, y_2, u_1)$ から $u_2$ を推定します。
$$ W_2^{(2)}(y_1, y_2, u_1 | u_2) = \frac{1}{2} W(y_1 | u_1 \oplus u_2) W(y_2 | u_2) $$
$u_1$ が既知であることにより追加情報が得られるため、$W_2^{(2)}$ は元のチャネル $W$ よりも改善されます。
対称容量の保存と分極
2つの合成チャネルの対称容量の和は、元の2チャネルの容量の和に等しいことが示されます。
$$ I(W_2^{(1)}) + I(W_2^{(2)}) = 2 I(W) $$
つまり、全体の情報伝送能力は保存されています。しかし、個々のチャネルの品質は以下のように変化します。
$$ I(W_2^{(1)}) \leq I(W) \leq I(W_2^{(2)}) $$
$W$ が完全チャネル（$I(W) = 1$）でも完全に無用なチャネル（$I(W) = 0$）でもない限り、不等号は厳密に成り立ちます。つまり、1回の変換でも既にチャネル品質の分離が始まっているのです。
この基本変換を再帰的に繰り返すと、分極はますます顕著になります。次のセクションでは、この再帰構成の一般化を見ていきます。
再帰的構成とクロネッカー積
符号長 $N = 2^n$ への拡張
ポーラー符号の符号化行列は、基本行列 $\bm{F}_2$ のクロネッカー積（Kronecker product）を用いて構成されます。符号長 $N = 2^n$ の場合、生成行列は次のように定義されます。
$$ \bm{G}_N = \bm{B}_N \bm{F}_2^{\otimes n} $$
ここで、$\bm{F}_2^{\otimes n}$ は $\bm{F}_2$ の $n$ 回クロネッカー積です。
$$ \bm{F}_2^{\otimes n} = \underbrace{\bm{F}_2 \otimes \bm{F}_2 \otimes \cdots \otimes \bm{F}_2}_{n \text{ 回}} $$
$\bm{B}_N$ はビット反転順列行列（bit-reversal permutation matrix）で、入力ビットのインデックスを二進数表現で反転した順序に並べ替える操作です。
具体例を見ましょう。$N = 4$（$n = 2$）の場合を計算します。
まず $\bm{F}_2^{\otimes 2}$ を求めます。クロネッカー積の定義に従い、$\bm{F}_2$ の各要素を $\bm{F}_2$ 倍します。
$$ \bm{F}_2^{\otimes 2} = \bm{F}_2 \otimes \bm{F}_2 = \begin{pmatrix} 1 \cdot \bm{F}_2 & 0 \cdot \bm{F}_2 \\ 1 \cdot \bm{F}_2 & 1 \cdot \bm{F}_2 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{pmatrix} $$
ビット反転順列 $\bm{B}_4$ を適用すると（インデックスの二進表現を反転: $00 \to 00, 01 \to 10, 10 \to 01, 11 \to 11$、つまり2番目と3番目を入れ替え）、生成行列 $\bm{G}_4$ が得られます。
符号化の手順
符号化は以下の手順で行います。
- 情報ビットと凍結ビットの配置: 長さ $N$ の入力ベクトル $\bm{u} = (u_1, u_2, \dots, u_N)$ において、良いチャネルに対応するインデックスの集合 $\mathcal{A}$（情報集合）に情報ビットを配置し、残りのインデックス $\mathcal{A}^c$（凍結集合）には既知の固定値（通常 $0$）を配置する
- 行列乗算: 符号語 $\bm{x} = \bm{u} \bm{G}_N$ を $\text{GF}(2)$ 上で計算する
- 送信: $\bm{x}$ の各ビットを独立なチャネル $W$ を通して送信する
符号化率は $R = |\mathcal{A}| / N$ です。$|\mathcal{A}| \approx N \cdot I(W)$ と選べば、$R \approx I(W) = C$ となります。
重要なのは、$\bm{G}_N = \bm{B}_N \bm{F}_2^{\otimes n}$ の構造により、符号化が $O(N \log N)$ の計算量で実行できることです。これはバタフライ演算（FFTと同様の構造）として効率的に実装できます。
符号化の構成が理解できたところで、次にチャネル分極が本当に起こることを数学的に示す証明の概要を見ていきましょう。
チャネル分極の数学的証明の概要
合成チャネルの再帰的定義
符号長 $N = 2^n$ に対して、$N$ 本の合成チャネル $W_N^{(i)}$（$i = 1, 2, \dots, N$）が定義されます。これらは以下の再帰関係で構成されます。
$N = 2$ の場合は前述の通りです。$N > 2$ の場合、$W_N^{(i)}$ は $W_{N/2}^{(j)}$ から次のように構成されます。
$$ W_N^{(2i-1)}(y_1^N, u_1^{2i-2} | u_{2i-1}) : \text{劣化チャネル（マイナス変換）} $$
$$ W_N^{(2i)}(y_1^N, u_1^{2i-1} | u_{2i}) : \text{改善チャネル（プラス変換）} $$
ここで $y_1^N = (y_1, y_2, \dots, y_N)$、$u_1^{j} = (u_1, u_2, \dots, u_j)$ と略記しています。
各合成チャネルの品質を測る指標として、バタチャリヤパラメータ（Bhattacharyya parameter）$Z(W)$ を用います。
$$ Z(W) = \sum_{y \in \mathcal{Y}} \sqrt{W(y|0) W(y|1)} $$
$Z(W)$ は $[0, 1]$ の値をとり、$Z(W) = 0$ なら完全なチャネル（誤りなし）、$Z(W) = 1$ なら完全に無用なチャネルです。バタチャリヤパラメータは最尤復号の誤り確率の上界を与えるため、チャネル品質の指標として適しています。
分極の再帰関係
マイナス変換とプラス変換に対して、バタチャリヤパラメータは以下の関係を満たします。
$$ Z(W^{-}) \leq 2Z(W) – Z(W)^2 $$
$$ Z(W^{+}) = Z(W)^2 $$
ここで $W^{-}$ は劣化チャネル、$W^{+}$ は改善チャネルを表します。プラス変換の関係 $Z(W^{+}) = Z(W)^2$ は特に重要です。もし $Z(W) < 1$ であれば、プラス変換を繰り返すたびに $Z$ は二乗されるため、急速に $0$ に近づきます。つまり、プラス変換が連続して適用されるチャネルは急速に完全なチャネルに近づきます。
マルチンゲール収束による分極の証明
分極の証明はマルチンゲール理論を用いて行われます。ランダムプロセス $\{B_n\}$ を次のように定義します。
$B_0 = Z(W)$ とし、各ステップで等確率 $1/2$ でプラス変換またはマイナス変換を適用します。
$$ B_{n+1} = \begin{cases} B_n^2 & \text{(確率 } 1/2 \text{, プラス変換)} \\ 2B_n – B_n^2 & \text{(確率 } 1/2 \text{, マイナス変換)} \end{cases} $$
このプロセスの期待値を計算すると、次のことがわかります。
$$ \mathbb{E}[B_{n+1} | B_n] = \frac{1}{2} B_n^2 + \frac{1}{2}(2B_n – B_n^2) = B_n $$
$B_n^2$ と $2B_n – B_n^2$ の平均をとると、$B_n^2 / 2 + B_n – B_n^2 / 2 = B_n$ となることから、$\{B_n\}$ はマルチンゲールであることがわかります。$\{B_n\}$ は $[0, 1]$ に値をとる有界マルチンゲールなので、マルチンゲール収束定理により $B_n$ は概収束します。
収束先を $B_\infty$ とすると、$B_\infty$ は $B_\infty^2 = B_\infty$（プラス変換の極限）と $2B_\infty – B_\infty^2 = B_\infty$（マイナス変換の極限）を満たす必要があるため、$B_\infty \in \{0, 1\}$ のいずれかに収束します。
さらに、$\mathbb{E}[B_\infty] = B_0 = Z(W)$ であること、および対称容量との関係 $I(W) = 1 – Z(W)$（BSCの場合）を用いると、次の定理が導かれます。
チャネル分極定理（Arıkan, 2009）:
任意の二元入力離散無記憶通信路 $W$ に対し、$N = 2^n \to \infty$ のとき、合成チャネル $W_N^{(i)}$ の対称容量 $I(W_N^{(i)})$ が以下を満たす割合は次の通りです。
$$ \frac{1}{N} \left| \left\{ i : I(W_N^{(i)}) \in (1-\delta, 1] \right\} \right| \to I(W) \quad (N \to \infty) $$
$$ \frac{1}{N} \left| \left\{ i : I(W_N^{(i)}) \in [0, \delta) \right\} \right| \to 1 – I(W) \quad (N \to \infty) $$
任意の $\delta > 0$ に対してこれが成り立ちます。つまり、合成チャネルは容量がほぼ $1$ のもの（割合 $I(W)$）と容量がほぼ $0$ のもの（割合 $1 – I(W)$）に二極化し、中間的なチャネルは消失します。
容量達成の帰結
この分極定理から、ポーラー符号がシャノン限界を達成することが直ちに導かれます。容量がほぼ $1$ のチャネル（$N \cdot I(W)$ 本）に情報ビットを載せれば、各ビットの誤り率は $\delta$ 以下にできます。全体のブロック誤り率は
$$ P_e \leq \sum_{i \in \mathcal{A}} Z(W_N^{(i)}) = O(2^{-N^\beta}) $$
と指数的に減少することが示されています（ある $\beta < 1/2$ に対して）。伝送レートは $R = |\mathcal{A}|/N \to I(W) = C$ です。
マルチンゲール収束という確率論の深い結果が、通信路符号化の根本定理の構成的証明に使われるという事実は、数学と情報理論の美しい接点を示しています。
証明の概要が理解できたところで、次に符号設計の実践的な側面 — どのチャネルに情報ビットを配置するか — について見ていきましょう。
情報ビットと凍結ビットの配置
チャネル品質の評価と信頼性系列
ポーラー符号を設計するには、$N$ 本の合成チャネルのうちどれが「良い」チャネルかを判定する必要があります。この判定には、各合成チャネルの信頼性を何らかの指標で評価し、上位 $K = N \cdot R$ 本を情報チャネルとして選びます。
信頼性の評価方法にはいくつかのアプローチがあります。
1. バタチャリヤパラメータによる評価
前述のバタチャリヤパラメータ $Z(W_N^{(i)})$ を各合成チャネルに対して計算し、$Z$ が小さいもの（信頼性が高いもの）から $K$ 本を情報チャネルとして選びます。BSCに対しては、再帰関係を用いて $O(N)$ で全チャネルの $Z$ 値を計算できます。
2. 密度発展法（Density Evolution）
AWGN通信路のように、遷移確率が連続値をとるチャネルに対しては、合成チャネルの尤度比分布をモンテカルロ法で追跡する密度発展法が用いられます。各合成チャネルの相互情報量 $I(W_N^{(i)})$ を直接推定し、相互情報量が高いチャネルを情報チャネルとして選びます。
3. ガウス近似（Gaussian Approximation）
密度発展法の計算量を削減するため、尤度比の対数がガウス分布に従うと近似する方法です。各合成チャネルの品質をスカラー値（平均LLR）で追跡できるため、計算が大幅に簡略化されます。AWGN通信路に対しては十分な精度が得られます。
凍結ビットの役割
凍結ビットは単なる「使わないチャネルの穴埋め」ではなく、復号において重要な役割を果たします。SC復号では、復号は $u_1$ から $u_N$ まで順番に行われます。凍結ビットの値は送信側と受信側で事前に共有されているため、これらのビットを復号する必要はなく、既知の値をそのまま使えます。
この既知情報は、後続のビットの復号精度を向上させます。これは、凍結ビットが一種の「サイド情報」として機能し、復号の逐次的な進行を支えているためです。
具体例: $N = 8$, $R = 1/2$ の場合
$N = 8$、符号化率 $R = 1/2$ のポーラー符号を考えます。情報ビット数は $K = N \cdot R = 4$ です。
BSC（クロスオーバー確率 $p = 0.11$）に対するバタチャリヤパラメータを再帰的に計算すると、$8$ 本の合成チャネルに対する $Z$ 値は例えば以下のようになります（値は概算）。
| チャネル $i$ | $Z(W_8^{(i)})$ | 信頼性 |
|---|---|---|
| 1 | 0.994 | 低 |
| 2 | 0.914 | 低 |
| 3 | 0.840 | 低 |
| 4 | 0.383 | 中 |
| 5 | 0.737 | 低 |
| 6 | 0.190 | 高 |
| 7 | 0.101 | 高 |
| 8 | 0.004 | 高 |
$Z$ 値が小さい上位4つのチャネル（$i = 4, 6, 7, 8$）を情報チャネルとして選び、残り（$i = 1, 2, 3, 5$）を凍結チャネルとします。
$$ \mathcal{A} = \{4, 6, 7, 8\}, \quad \mathcal{A}^c = \{1, 2, 3, 5\} $$
入力ベクトル $\bm{u}$ は次のように構成されます。
$$ \bm{u} = (0, 0, 0, d_1, 0, d_2, d_3, d_4) $$
ここで $d_1, d_2, d_3, d_4$ が伝送したい情報ビットです。
情報ビットの配置が決まれば、あとは受信側でどのように復号するかが問題です。次のセクションでは、ポーラー符号の基本的な復号アルゴリズムであるSC復号を解説します。
SC（逐次キャンセレーション）復号
SC復号の基本的な考え方
SC復号（Successive Cancellation Decoding）は、Arıkanの原論文で提案されたポーラー符号の基本的な復号アルゴリズムです。その名前が示す通り、ビットを $u_1, u_2, \dots, u_N$ の順に逐次的に復号し、各ビットの復号結果を後続のビットの復号に利用するという方法です。
SC復号の直感的なイメージは「ドミノ倒し」です。最初のビットを復号すると、その情報が次のビットの復号を助けます。次のビットが復号されると、さらにその次のビットの復号に情報が伝播します。このように、前段の復号結果を「キャンセレーション」（既知情報として除去）することで、後段の復号精度が向上していきます。
SC復号の数学的定式化
受信信号 $\bm{y} = (y_1, y_2, \dots, y_N)$ が与えられたとき、$u_i$ の復号は以下の規則で行われます。
凍結ビットの場合（$i \in \mathcal{A}^c$）:
$$ \hat{u}_i = 0 \quad (\text{既知の凍結値}) $$
情報ビットの場合（$i \in \mathcal{A}$）:
$$ \hat{u}_i = \begin{cases} 0 & \text{if } L_N^{(i)}(\bm{y}, \hat{\bm{u}}_1^{i-1}) \geq 0 \\ 1 & \text{if } L_N^{(i)}(\bm{y}, \hat{\bm{u}}_1^{i-1}) < 0 \end{cases} $$
ここで $L_N^{(i)}$ は対数尤度比（LLR: Log-Likelihood Ratio）で、次のように定義されます。
$$ L_N^{(i)}(\bm{y}, \hat{\bm{u}}_1^{i-1}) = \ln \frac{W_N^{(i)}(\bm{y}, \hat{\bm{u}}_1^{i-1} | u_i = 0)}{W_N^{(i)}(\bm{y}, \hat{\bm{u}}_1^{i-1} | u_i = 1)} $$
$L_N^{(i)} > 0$ ならば $u_i = 0$ の確率が高く、$L_N^{(i)} < 0$ ならば $u_i = 1$ の確率が高いことを意味します。
LLRの再帰計算
LLRの計算は、ポーラー符号のバタフライ構造を利用して再帰的に行えます。$N = 2$ の基本ケースを考えると、マイナス変換とプラス変換のLLRは以下のように計算されます。
マイナス変換（$f$ 関数）:
2つのLLR値 $L_a$ と $L_b$ に対し、合成後のLLRは次のように計算されます。
$$ f(L_a, L_b) = 2 \tanh^{-1}\left(\tanh\frac{L_a}{2} \cdot \tanh\frac{L_b}{2}\right) $$
数値的に安定な近似として、以下のmin-sum近似がよく用いられます。
$$ f(L_a, L_b) \approx \text{sign}(L_a) \cdot \text{sign}(L_b) \cdot \min(|L_a|, |L_b|) $$
プラス変換（$g$ 関数）:
過去の復号結果 $\hat{u}_s \in \{0, 1\}$ を用いて、次のように計算されます。
$$ g(L_a, L_b, \hat{u}_s) = (-1)^{\hat{u}_s} L_a + L_b $$
$\hat{u}_s = 0$ のとき $g = L_a + L_b$（情報を加算）、$\hat{u}_s = 1$ のとき $g = -L_a + L_b$（符号を反転して加算）となります。
SC復号のバタフライ構造
$N = 2^n$ の場合、SC復号は $n$ 段のバタフライネットワークとして構成されます。各段で $f$ 関数と $g$ 関数を交互に適用し、受信LLR（チャネルからの初期値）から各ビットの復号LLRを計算します。
復号の流れを $N = 4$ の場合で示します。
- チャネルからの初期LLR: $L_1^{(1)}, L_1^{(2)}, L_1^{(3)}, L_1^{(4)}$
- 第1段（左半分と右半分の結合）: – $f(L_1^{(1)}, L_1^{(3)})$ と $f(L_1^{(2)}, L_1^{(4)})$ を計算
- 第2段（さらに細かい結合）: – $f$ 関数の結果に対して再度 $f$ と $g$ を適用
- ビット $u_1$ の復号 → $u_2$ の復号 → $g$ 関数で情報伝播 → $u_3$ の復号 → $u_4$ の復号
全体の計算量は $O(N \log N)$ です。これはFFT（高速フーリエ変換）と同じオーダーであり、符号長が長くても効率的に復号できます。
SC復号の限界
SC復号は理論的にはシャノン限界を達成しますが、それは $N \to \infty$ の漸近的な話です。実用的な有限長（$N = 256 \sim 2048$ 程度）では、以下の問題があります。
- 有限長性能の低さ: 同じ符号長のLDPC符号やターボ符号と比較して、BER性能が劣る
- 誤り伝播: SC復号では、一度誤った復号をすると、その誤りが後続のビットの復号に悪影響を及ぼす。これがドミノ倒しの負の側面です
この問題を解決するために提案されたのが、次のセクションで解説するSCL復号です。
SCL（逐次キャンセレーションリスト）復号
SC復号の改良
SCL復号（Successive Cancellation List Decoding）は、Tal と Vardy が2015年に提案した改良アルゴリズムです。SC復号が各ステップで1つの候補のみを追跡するのに対し、SCL復号は $L$ 個の候補パスを並行して追跡します。
SC復号を「1本の道を歩く探索」に例えるなら、SCL復号は「$L$ 人のチームで $L$ 本の道を並行して探索する」ようなものです。分岐点（情報ビットの復号）に到達するたびに、各パスが $u_i = 0$ と $u_i = 1$ の両方の候補に分岐し、合計 $2L$ 個の候補から尤度の高い上位 $L$ 個を残します。
SCL復号のアルゴリズム
SCL復号の手順は以下の通りです。
初期化: $L$ 本のパスを用意し、全て同じ初期状態（空のパス）から開始します。
各ビット $i = 1, 2, \dots, N$ について:
- $i \in \mathcal{A}^c$（凍結ビット）の場合: 全パスに $\hat{u}_i = 0$ を追加します
- $i \in \mathcal{A}$（情報ビット）の場合: – 各パスを $\hat{u}_i = 0$ と $\hat{u}_i = 1$ に分岐させ、$2L$ 個の候補パスを生成します – 各候補パスのパスメトリック（対数尤度の累積和）を計算します – パスメトリックの上位 $L$ 個の候補パスのみを残し、残りを枝刈りします
最終選択: 全ビットの復号が完了したら、$L$ 本のパスの中から最もパスメトリックが高いものを最終復号結果とします。
パスメトリックの計算
パスメトリック $PM_l$（パス $l$ の累積対数尤度）は次のように更新されます。
$$ PM_l^{(i)} = PM_l^{(i-1)} + \begin{cases} 0 & \text{if } \hat{u}_i = h(L_N^{(i)}) \\ |L_N^{(i)}| & \text{if } \hat{u}_i \neq h(L_N^{(i)}) \end{cases} $$
ここで $h(L) = 0$ if $L \geq 0$, $h(L) = 1$ if $L < 0$ は硬判定関数です。SC復号の判定結果と異なる選択をした場合にペナルティ $|L_N^{(i)}|$ が加算されます。パスメトリックが小さいほど尤もらしいパスです。
CRC連接によるさらなる改善
SCL復号の性能をさらに向上させる手法として、CRC（巡回冗長検査）をポーラー符号と連接する方法があります。情報ビット列の末尾にCRCビットを付加して符号化し、復号時には $L$ 本の候補パスの中からCRC検査に合格するものを選択します。
CA-SCL復号（CRC-Aided SCL Decoding）と呼ばれるこの手法は、リスト内の正解パスを高い確率で特定でき、短い符号長でもLDPC符号やターボ符号に匹敵する性能を実現します。5G NRで採用されたポーラー符号も、CA-SCL復号を前提として設計されています。
計算量の比較
| 復号アルゴリズム | 計算量 | 性能 |
|---|---|---|
| SC | $O(N \log N)$ | 漸近的に最適だが有限長では劣る |
| SCL（リストサイズ $L$） | $O(L \cdot N \log N)$ | $L$ 増大で性能向上 |
| CA-SCL | $O(L \cdot N \log N)$ | CRC連接により大幅に改善 |
$L = 8 \sim 32$ 程度で実用的な性能が得られることが知られています。$L$ を増やすほど性能は向上しますが、計算量とメモリ使用量も線形に増加するため、ハードウェア実装においては適切な $L$ の選択が重要です。
SCL復号の実用性能の高さが認められ、ポーラー符号は5G NRの制御チャネルに正式採用されました。次のセクションでは、5G NRにおける採用の詳細を見ていきます。
5G NRにおけるポーラー符号の採用
3GPPにおける符号選定の経緯
2016年、3GPP（Third Generation Partnership Project）は5G NRの通信路符号を選定する議論を行いました。データチャネルにはLDPC符号が、制御チャネルにはポーラー符号が採用されるという歴史的な決定がなされました。
この決定に至った背景には、以下の技術的な理由があります。
制御チャネルの特性:
- 制御情報は短いビット列（数十〜数百ビット）である
- 極めて低い誤り率が要求される（制御情報の誤りはデータ全体の復号失敗につながる）
- レイテンシの制約が厳しい
ポーラー符号の利点:
- 短い符号長でもCA-SCL復号により優れた性能を発揮する
- 符号化率の柔軟な調整が容易（凍結ビットの配置を変えるだけ）
- レート整合（Rate Matching）が柔軟に行える
5G NRでの具体的な使用
5G NRでは、ポーラー符号は以下のチャネルで使用されています。
ダウンリンク制御チャネル（PDCCH）: 基地局から端末への制御情報（リソース割当、変調方式の指定など）の伝送に使用されます。情報ビット長は最大140ビット程度です。
アップリンク制御チャネル（PUCCH）: 端末から基地局への制御情報（ACK/NACK、チャネル品質指標など）の伝送に使用されます。
ブロードキャストチャネル（PBCH）: セル情報のブロードキャストに使用されます。
一方、データチャネル（PDSCH, PUSCH）にはLDPC符号が採用されています。これは、データチャネルでは長い符号長（数千〜数万ビット）が使われ、LDPC符号のほうが長符号長での復号効率（スループット）に優れるためです。
5G NR向けのポーラー符号の設計パラメータ
5G NRのポーラー符号には、学術的な標準形に対していくつかの実用的な改良が施されています。
- 分散CRC: CRCビットを情報ビット列の末尾に集中させるのではなく、情報ビット列の途中に分散配置することで、SCL復号の早い段階でパスの枝刈りを効率化しています
- レート整合: 符号化されたビット列からパンクチャリングやリピティションにより、任意の符号化率を実現します
- 信頼性系列（Reliability Sequence）: 3GPPが規定する固定の信頼性系列に基づいてチャネルの品質順序を定めます。これにより、送受信間で信頼性系列を毎回計算する必要がなくなります
ポーラー符号の理論と実用的な側面を理解したところで、いよいよPythonでチャネル分極の現象をシミュレーションし、SC復号を実装してみましょう。
Pythonでチャネル分極のシミュレーション
バタチャリヤパラメータによる分極の可視化
まず、二元消失通信路（BEC: Binary Erasure Channel）を例に、チャネル分極が実際に起こることを確認します。BECは消失確率 $\varepsilon$ をパラメータにもつ最も単純なチャネルの一つで、バタチャリヤパラメータの再帰計算が厳密に行えるため、分極の観察に最適です。
BECに対するバタチャリヤパラメータの再帰関係は以下の通りです。
$$ Z(W^{-}) = 2Z(W) – Z(W)^2, \quad Z(W^{+}) = Z(W)^2 $$
以下のコードで、$N = 2^n$ のときの合成チャネルのバタチャリヤパラメータの分布を可視化します。
import numpy as np
import matplotlib.pyplot as plt
def channel_polarization_bec(epsilon, n):
"""BECに対するチャネル分極のシミュレーション
Parameters
----------
epsilon : float
BECの消失確率（初期バタチャリヤパラメータ）
n : int
分極のステージ数（符号長 N = 2^n）
Returns
-------
z_values : ndarray
各合成チャネルのバタチャリヤパラメータ
"""
# 初期値: 全チャネル同一
z = np.array([epsilon])
for stage in range(n):
# マイナス変換（劣化）とプラス変換（改善）
z_minus = 2 * z - z**2 # 劣化チャネル
z_plus = z**2 # 改善チャネル
# 交互に配置
z = np.concatenate([z_minus, z_plus])
return z
# パラメータ設定
epsilon = 0.5 # BEC(0.5): 通信路容量 C = 1 - 0.5 = 0.5
stages = [2, 4, 6, 8, 10]
fig, axes = plt.subplots(1, len(stages), figsize=(20, 4))
for ax, n in zip(axes, stages):
N = 2**n
z = channel_polarization_bec(epsilon, n)
z_sorted = np.sort(z)
ax.bar(range(N), z_sorted, width=1.0, color='steelblue', alpha=0.7)
ax.set_title(f'N = {N}', fontsize=12)
ax.set_xlabel('Channel index (sorted)')
ax.set_ylabel('Bhattacharyya parameter Z')
ax.set_ylim([0, 1])
ax.axhline(y=0.5, color='red', linestyle='--', alpha=0.5, label='Z = 0.5')
ax.legend(fontsize=8)
plt.suptitle('Channel Polarization for BEC(0.5)', fontsize=14, y=1.02)
plt.tight_layout()
plt.savefig('channel_polarization_bec.png', dpi=150, bbox_inches='tight')
plt.show()
このグラフから、チャネル分極の核心的な特徴が読み取れます。
- $N$ が小さい段階（$N = 4, 16$）では、バタチャリヤパラメータは0から1まで広く分布しています。まだ分極が十分に進んでおらず、中間的な品質のチャネルが多数存在します。
- $N$ が大きくなるにつれて（$N = 64, 256, 1024$）、パラメータは $0$ 付近と $1$ 付近に集中し、中間的な値をもつチャネルは急速に消失します。これがまさにチャネル分極です。
- $Z \approx 0$ のチャネル（良いチャネル）の割合は、通信路容量 $C = 1 – \varepsilon = 0.5$ に近づいていきます。これは分極定理の予測と完全に一致します。
分極の進行を定量的に確認
次に、分極の進行をより定量的に確認するため、$Z < 0.01$（ほぼ完全なチャネル）と $Z > 0.99$（ほぼ無用なチャネル）の割合が $N$ に対してどう変化するかを調べます。
import numpy as np
import matplotlib.pyplot as plt
def channel_polarization_bec(epsilon, n):
"""BECに対するチャネル分極"""
z = np.array([epsilon])
for stage in range(n):
z_minus = 2 * z - z**2
z_plus = z**2
z = np.concatenate([z_minus, z_plus])
return z
epsilon = 0.5 # C = 0.5
n_values = range(1, 21)
frac_good = [] # Z < 0.01 の割合
frac_bad = [] # Z > 0.99 の割合
frac_middle = [] # 0.01 <= Z <= 0.99 の割合
for n in n_values:
z = channel_polarization_bec(epsilon, n)
N = len(z)
frac_good.append(np.sum(z < 0.01) / N)
frac_bad.append(np.sum(z > 0.99) / N)
frac_middle.append(np.sum((z >= 0.01) & (z <= 0.99)) / N)
fig, ax = plt.subplots(figsize=(10, 6))
ax.plot(list(n_values), frac_good, 'b-o', markersize=4, label='Good channels (Z < 0.01)')
ax.plot(list(n_values), frac_bad, 'r-s', markersize=4, label='Bad channels (Z > 0.99)')
ax.plot(list(n_values), frac_middle, 'g-^', markersize=4, label='Middle channels')
ax.axhline(y=0.5, color='blue', linestyle='--', alpha=0.3, label='C = 0.5')
ax.set_xlabel('n (N = 2^n)', fontsize=12)
ax.set_ylabel('Fraction of channels', fontsize=12)
ax.set_title('Polarization Progress: BEC(0.5)', fontsize=14)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
ax.set_xlim([1, 20])
ax.set_ylim([0, 1.05])
plt.tight_layout()
plt.savefig('polarization_progress.png', dpi=150, bbox_inches='tight')
plt.show()
print(f"n=10 (N=1024): good={frac_good[9]:.4f}, bad={frac_bad[9]:.4f}, middle={frac_middle[9]:.4f}")
print(f"n=15 (N=32768): good={frac_good[14]:.4f}, bad={frac_bad[14]:.4f}, middle={frac_middle[14]:.4f}")
print(f"n=20 (N=1048576): good={frac_good[19]:.4f}, bad={frac_bad[19]:.4f}, middle={frac_middle[19]:.4f}")
上のグラフと数値から、分極の進行が定量的に確認できます。
- 良いチャネルの割合（青線）は $n$ の増加とともに通信路容量 $C = 0.5$ に収束していきます。$n = 20$（$N \approx 100$ 万）の時点で、良いチャネルの割合はほぼ $0.5$ に到達しています。
- 中間的なチャネルの割合（緑線）は $n$ の増加とともに急速にゼロに近づきます。$n = 15$ 程度で中間チャネルはほぼ消失します。
- 分極の収束速度は対数的であり、十分な分極を得るにはある程度大きな $N$ が必要です。これがポーラー符号の有限長性能が限定的である理由の一つです。
チャネル分極が実際に起こることを確認できました。次に、SC復号をPythonで実装し、ポーラー符号の誤り訂正性能を検証します。
PythonでのSC復号の実装
完全なSC復号の実装
以下では、BSC（二元対称通信路）とAWGN通信路上でのポーラー符号のSC復号を実装します。まず、符号化と復号の基本コンポーネントを実装します。
import numpy as np
def polar_encode(u, n):
"""ポーラー符号の符号化
Parameters
----------
u : ndarray (N,)
入力ビット列（情報ビット + 凍結ビット）
n : int
ステージ数（N = 2^n）
Returns
-------
x : ndarray (N,)
符号語
"""
N = 2**n
x = u.copy()
# バタフライ演算による符号化（GF(2)上）
step = 1
for stage in range(n):
for i in range(0, N, 2 * step):
for j in range(step):
x[i + j] = x[i + j] ^ x[i + j + step]
step *= 2
return x
この符号化関数は、$\bm{F}_2^{\otimes n}$ の行列乗算をバタフライ演算として $O(N \log N)$ で実装しています。各ステージで隣接するビットペアにXOR演算を適用します。
次に、SC復号の再帰的なLLR計算を実装します。
import numpy as np
def sc_decode(llr, frozen_set, n):
"""SC復号（逐次キャンセレーション復号）
Parameters
----------
llr : ndarray (N,)
チャネルからの初期LLR値
frozen_set : set
凍結ビットのインデックス集合
n : int
ステージ数（N = 2^n）
Returns
-------
u_hat : ndarray (N,)
復号されたビット列
"""
N = 2**n
u_hat = np.zeros(N, dtype=int)
def f_func(la, lb):
"""マイナス変換のLLR計算（min-sum近似）"""
return np.sign(la) * np.sign(lb) * np.minimum(np.abs(la), np.abs(lb))
def g_func(la, lb, us):
"""プラス変換のLLR計算"""
return (1 - 2 * us) * la + lb
def recursive_sc(llr_vec, bit_idx, node_idx, depth):
"""SC復号の再帰関数
Parameters
----------
llr_vec : ndarray
現在のノードへの入力LLR
bit_idx : int
現在の復号対象ビットの開始インデックス
node_idx : int
現在のノード番号（デバッグ用）
depth : int
再帰の深さ
"""
length = len(llr_vec)
if length == 1:
# 葉ノード: 復号判定
if bit_idx in frozen_set:
u_hat[bit_idx] = 0
else:
u_hat[bit_idx] = 0 if llr_vec[0] >= 0 else 1
return
half = length // 2
# 左の子ノード（マイナス変換）
llr_left = f_func(llr_vec[:half], llr_vec[half:])
recursive_sc(llr_left, bit_idx, 2 * node_idx, depth + 1)
# 左の子ノードの復号結果を取得
left_bits = np.zeros(half, dtype=int)
# 左の子ノードで復号されたビットを再符号化して取得
left_bits = u_hat[bit_idx:bit_idx + half]
# 部分再符号化
partial = left_bits.copy()
step = 1
sub_n = int(np.log2(half)) if half > 1 else 0
for stage in range(sub_n):
for i in range(0, half, 2 * step):
for j in range(step):
partial[i + j] = partial[i + j] ^ partial[i + j + step]
step *= 2
# 右の子ノード（プラス変換）
llr_right = g_func(llr_vec[:half], llr_vec[half:], partial)
recursive_sc(llr_right, bit_idx + half, 2 * node_idx + 1, depth + 1)
recursive_sc(llr, 0, 1, 0)
return u_hat
このSC復号の実装では、再帰的にバタフライ構造をたどりながら各ビットのLLRを計算しています。葉ノードに到達するたびに、凍結ビットなら値を0に固定し、情報ビットならLLRの符号で硬判定を行います。左の子ノードの復号結果を部分再符号化してから右の子ノードのLLR計算に渡す点が、SC復号の「逐次キャンセレーション」の本質です。
AWGN通信路でのBER性能評価
実装したSC復号を使って、AWGN通信路におけるポーラー符号のBER（ビット誤り率）性能を評価します。
import numpy as np
import matplotlib.pyplot as plt
def polar_encode(u, n):
"""ポーラー符号の符号化"""
N = 2**n
x = u.copy()
step = 1
for stage in range(n):
for i in range(0, N, 2 * step):
for j in range(step):
x[i + j] = x[i + j] ^ x[i + j + step]
step *= 2
return x
def compute_bhattacharyya_awgn(snr_linear, n):
"""AWGN通信路に対するバタチャリヤパラメータの近似計算（ガウス近似）"""
N = 2**n
# 初期値: BPSK over AWGNの場合
sigma2 = 1.0 / snr_linear
# ガウス近似: 平均LLRで追跡
mu = np.array([2.0 / sigma2]) # 初期平均LLR
for stage in range(n):
# マイナス変換の近似
mu_minus = phi_inv(1 - (1 - phi(mu))**2)
# プラス変換
mu_plus = 2 * mu
mu = np.concatenate([mu_minus, mu_plus])
# バタチャリヤパラメータの近似
z = np.exp(-mu / 2)
z = np.clip(z, 0, 1)
return z
def phi(x):
"""ガウス近似のphi関数"""
result = np.zeros_like(x)
idx_small = x < 10
idx_large = ~idx_small
# 小さいxに対する計算
if np.any(idx_small):
result[idx_small] = np.exp(-0.4527 * x[idx_small]**0.86 + 0.0218)
result[idx_small] = np.clip(result[idx_small], 0, 1)
# 大きいxに対しては0
result[idx_large] = 0.0
return result
def phi_inv(y):
"""phi関数の逆関数の近似"""
y = np.clip(y, 1e-12, 1 - 1e-12)
return ((-np.log(y) + 0.0218) / 0.4527) ** (1 / 0.86)
def design_polar_code(n, K, snr_db):
"""ポーラー符号の設計（情報チャネルの選択）"""
snr_linear = 10**(snr_db / 10)
z = compute_bhattacharyya_awgn(snr_linear, n)
N = 2**n
# Z値が小さい上位K個を情報チャネルとする
sorted_indices = np.argsort(z)
info_set = set(sorted_indices[:K])
frozen_set = set(range(N)) - info_set
return info_set, frozen_set
def f_func(la, lb):
"""マイナス変換（min-sum近似）"""
return np.sign(la) * np.sign(lb) * np.minimum(np.abs(la), np.abs(lb))
def g_func(la, lb, us):
"""プラス変換"""
return (1 - 2 * us) * la + lb
def sc_decode(llr, frozen_set, n):
"""SC復号"""
N = 2**n
u_hat = np.zeros(N, dtype=int)
def recursive_sc(llr_vec, bit_idx):
length = len(llr_vec)
if length == 1:
if bit_idx in frozen_set:
u_hat[bit_idx] = 0
else:
u_hat[bit_idx] = 0 if llr_vec[0] >= 0 else 1
return
half = length // 2
llr_left = f_func(llr_vec[:half], llr_vec[half:])
recursive_sc(llr_left, bit_idx)
left_bits = u_hat[bit_idx:bit_idx + half].copy()
partial = left_bits.copy()
sub_n = int(np.log2(half)) if half > 1 else 0
step = 1
for stage in range(sub_n):
for i in range(0, half, 2 * step):
for j in range(step):
partial[i + j] = partial[i + j] ^ partial[i + j + step]
step *= 2
llr_right = g_func(llr_vec[:half], llr_vec[half:], partial)
recursive_sc(llr_right, bit_idx + half)
recursive_sc(llr, 0)
return u_hat
# シミュレーションパラメータ
n = 8 # 符号長 N = 256
N = 2**n
R = 0.5 # 符号化率
K = int(N * R) # 情報ビット数 = 128
snr_db_range = np.arange(0, 6.5, 0.5)
num_trials = 500
ber_results = []
design_snr = 2.0 # 設計SNR（dB）
info_set, frozen_set = design_polar_code(n, K, design_snr)
for snr_db in snr_db_range:
snr_linear = 10**(snr_db / 10)
sigma = np.sqrt(1 / (2 * R * snr_linear))
total_errors = 0
total_bits = 0
for trial in range(num_trials):
# 情報ビット生成
info_bits = np.random.randint(0, 2, K)
# 入力ベクトル構成
u = np.zeros(N, dtype=int)
info_indices = sorted(info_set)
for idx, bit in zip(info_indices, info_bits):
u[idx] = bit
# 符号化
x = polar_encode(u, n)
# BPSK変調 (0 -> +1, 1 -> -1)
s = 1 - 2 * x.astype(float)
# AWGN通信路
noise = sigma * np.random.randn(N)
r = s + noise
# チャネルLLR計算
llr = 2 * r / (sigma**2)
# SC復号
u_hat = sc_decode(llr, frozen_set, n)
# 情報ビットの誤り数
decoded_info = np.array([u_hat[idx] for idx in info_indices])
total_errors += np.sum(info_bits != decoded_info)
total_bits += K
ber = total_errors / total_bits
ber_results.append(ber)
print(f"Eb/N0 = {snr_db:.1f} dB: BER = {ber:.6f}")
# BERのプロット
fig, ax = plt.subplots(figsize=(10, 7))
ber_array = np.array(ber_results)
mask = ber_array > 0 # BER=0のポイントは対数スケールで表示不可
ax.semilogy(snr_db_range[mask], ber_array[mask], 'bo-', markersize=6, label=f'Polar SC (N={N}, R={R})')
# 未符号化BPSKの理論曲線
from scipy.special import erfc
snr_fine = np.linspace(0, 6.5, 100)
ber_uncoded = 0.5 * erfc(np.sqrt(10**(snr_fine / 10)))
ax.semilogy(snr_fine, ber_uncoded, 'r--', label='Uncoded BPSK')
# シャノン限界の表示
shannon_limit = 10 * np.log10((2**(2*R) - 1) / (2*R))
ax.axvline(x=shannon_limit, color='green', linestyle=':', linewidth=2, label=f'Shannon limit ({shannon_limit:.2f} dB)')
ax.set_xlabel('Eb/N0 (dB)', fontsize=12)
ax.set_ylabel('BER', fontsize=12)
ax.set_title(f'Polar Code SC Decoding Performance (N={N}, R={R})', fontsize=14)
ax.legend(fontsize=10)
ax.grid(True, which='both', alpha=0.3)
ax.set_ylim([1e-5, 1])
ax.set_xlim([0, 6.5])
plt.tight_layout()
plt.savefig('polar_sc_ber.png', dpi=150, bbox_inches='tight')
plt.show()
上のBER曲線から、以下の重要な特徴が読み取れます。
- ポーラー符号は未符号化BPSKに比べて大きな符号化利得を示しています。同じBER（例えば $10^{-3}$）を達成するために必要な $E_b/N_0$ が数dB小さくなっており、誤り訂正符号としての効果が確認できます。
- シャノン限界（緑の破線）との差は、$N = 256$ という比較的短い符号長のSC復号では数dB程度あります。これは、SC復号の有限長性能がLDPC符号やターボ符号に及ばないという理論的予測と一致しています。
- 高SNR領域（$E_b/N_0 > 4$ dB 付近）ではBERが急激に減少するウォーターフォール特性が見られます。これは、チャネル分極により良いチャネルの品質が十分に高くなると、情報ビットの復号誤り率が急速に低下するためです。
チャネル分極の可視化（AWGN通信路）
最後に、AWGN通信路に対してもチャネル分極が起こることを可視化します。
import numpy as np
import matplotlib.pyplot as plt
def phi(x):
"""ガウス近似のphi関数"""
result = np.zeros_like(x, dtype=float)
idx_small = x < 10
result[idx_small] = np.exp(-0.4527 * x[idx_small]**0.86 + 0.0218)
result[idx_small] = np.clip(result[idx_small], 0, 1)
return result
def phi_inv(y):
"""phi関数の逆関数"""
y = np.clip(y, 1e-12, 1 - 1e-12)
return ((-np.log(y) + 0.0218) / 0.4527) ** (1 / 0.86)
def compute_mutual_info_awgn(snr_db, n):
"""AWGN通信路に対する各合成チャネルの相互情報量を計算（ガウス近似）"""
snr_linear = 10**(snr_db / 10)
sigma2 = 1.0 / (2 * snr_linear)
# 初期平均LLR
mu = np.array([2.0 / sigma2])
for stage in range(n):
mu_minus = phi_inv(1 - (1 - phi(mu))**2)
mu_plus = 2 * mu
mu = np.concatenate([mu_minus, mu_plus])
# 相互情報量の近似: I ≈ 1 - phi(mu)
I = 1 - phi(mu)
I = np.clip(I, 0, 1)
return I
# 複数のSNRで分極を観察
n = 10 # N = 1024
N = 2**n
snr_values = [0, 1, 2, 3]
fig, axes = plt.subplots(1, len(snr_values), figsize=(20, 5))
for ax, snr_db in zip(axes, snr_values):
I = compute_mutual_info_awgn(snr_db, n)
I_sorted = np.sort(I)
ax.bar(range(N), I_sorted, width=1.0, color='darkorange', alpha=0.7)
ax.set_title(f'Eb/N0 = {snr_db} dB', fontsize=12)
ax.set_xlabel('Channel index (sorted)')
ax.set_ylabel('Mutual Information I')
ax.set_ylim([0, 1.05])
# 通信路容量の表示
C = np.mean(I)
ax.axhline(y=C, color='blue', linestyle='--', alpha=0.5, label=f'Mean I = {C:.3f}')
good = np.sum(I > 0.99) / N
bad = np.sum(I < 0.01) / N
ax.text(0.05, 0.85, f'Good: {good:.1%}\nBad: {bad:.1%}',
transform=ax.transAxes, fontsize=9, verticalalignment='top',
bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.5))
ax.legend(fontsize=8)
plt.suptitle(f'Channel Polarization for AWGN (N={N})', fontsize=14, y=1.02)
plt.tight_layout()
plt.savefig('polarization_awgn.png', dpi=150, bbox_inches='tight')
plt.show()
AWGN通信路に対する分極の可視化から、以下のことが読み取れます。
- AWGN通信路でもBEC同様にチャネル分極が明確に観察されます。相互情報量がほぼ $1$（良い）かほぼ $0$（悪い）に二極化しており、中間的なチャネルはごくわずかです。
- SNRが高いほど良いチャネルの割合が増加します。これは通信路容量 $C$ がSNRとともに増大することと整合しています。
- 各SNRにおける良いチャネルの割合は、AWGN通信路容量の理論値 $C = \frac{1}{2}\log_2(1 + \text{SNR})$ にほぼ一致します（符号化率 $R = 1/2$ でのBPSK伝送の場合）。
ポーラー符号とLDPC符号・ターボ符号の比較
ポーラー符号の位置づけを理解するために、他の主要な誤り訂正符号と比較しておきましょう。
設計思想の違い
ターボ符号（1993年）: 2つの再帰的畳み込み符号をインターリーバで結合し、反復復号（ターボ原理）で性能を引き出します。設計は直感とシミュレーションに依存する部分が大きく、理論的な容量達成の証明はありません。
LDPC符号（1960年代提案、1990年代再発見）: 疎なパリティ検査行列で定義され、ビリーフプロパゲーション（BP）復号で復号します。密度発展法により、特定のアンサンブルがシャノン限界に漸近的に到達することが示されていますが、個々の符号に対する厳密な証明は困難です。
ポーラー符号（2009年）: チャネル分極に基づく完全に代数的な構成で、個々の符号がシャノン限界を達成することが厳密に証明されています。理論的な美しさと証明可能性において他を凌駕します。
性能比較
| 特性 | ターボ符号 | LDPC符号 | ポーラー符号（CA-SCL） |
|---|---|---|---|
| 容量達成 | 未証明（近い） | アンサンブルで証明 | 個々の符号で証明 |
| 短符号長性能 | 良い | 普通 | CA-SCLで良い |
| 長符号長性能 | 良い | 非常に良い | 良い |
| 復号遅延 | 反復回数依存 | 反復回数依存 | $O(N \log N)$、逐次的 |
| ハードウェア効率 | 中 | 高（並列化容易） | 中（逐次的処理がボトルネック） |
| 規格採用 | 3G/4G（LTE） | 4G（Wi-Fi等）, 5G データ | 5G 制御 |
この比較から、ポーラー符号は理論的な裏付けの強さと短符号長での競争力が、5G NRの制御チャネルへの採用を後押ししたことがわかります。一方、長符号長でのスループット性能ではLDPC符号が依然として優位であり、データチャネルにはLDPC符号が採用されています。
まとめ
本記事では、ポーラー符号の理論的基盤であるチャネル分極から、SC復号・SCL復号のアルゴリズム、5G NRでの採用まで、包括的に解説しました。
- チャネル分極: 同一の通信路を $2 \times 2$ 基本変換行列とクロネッカー積で結合すると、合成チャネルが「ほぼ完全」と「ほぼ無用」に二極化する。良いチャネルの割合は通信路容量 $I(W)$ に一致する
- ポーラー符号の構成: 良いチャネルに情報ビットを、悪いチャネルに凍結ビットを配置することで、シャノン限界を達成する符号を構成的に実現する
- 分極の数学的証明: バタチャリヤパラメータのマルチンゲール収束により、分極が厳密に証明される
- SC復号: 逐次的にビットを復号する $O(N \log N)$ のアルゴリズム。漸近的には最適だが、有限長では性能が限定的
- SCL復号とCA-SCL: リスト探索とCRC連接により、短符号長でも実用的な性能を実現。5G NRの採用はCA-SCLを前提としている
- 5G NR: ポーラー符号はPDCCH、PUCCH、PBCHなどの制御チャネルに採用され、LDPC符号（データチャネル）と共存している
ポーラー符号は、シャノンの通信路符号化定理から60年以上を経て、「理論的にシャノン限界を達成する構成的な符号」という長年の夢を実現した画期的な成果です。その背景にあるチャネル分極という美しい数学的構造は、情報理論と符号理論の深い関係を示しています。
次のステップとして、以下の記事も参考にしてください。