1993年、国際通信会議（ICC）の会場で、ベルー（Claude Berrou）とグラヴュー（Alain Glavieux）が発表した一本の論文が、符号理論の歴史を塗り替えました。彼らが提案したターボ符号（turbo code）は、シャノンが1948年に理論的に示した通信路容量にきわめて近い性能を実現した最初の実用的な符号だったのです。シャノンの定理から45年、「理論限界に到達できる符号が本当に存在するのか」という長年の問いに対する実践的な解答が、ついに与えられました。
ターボ符号の革新性は二つの核心的なアイデアに集約されます。第一に、二つの畳み込み符号をインターリーバ（interleaver）で結合した並列連接構造。第二に、二つの復号器が情報を交換しながら反復的に推定精度を高めていく反復復号（iterative decoding）です。特に後者は、自動車のターボエンジンが排気ガスのエネルギーを再利用して出力を高めるのと類似しており、「ターボ」という名前の由来にもなっています。
ターボ符号を理解すると、以下のような分野への応用と理論的洞察が得られます。
- モバイル通信: 3G（UMTS/CDMA2000）および4G LTEの制御チャネルでターボ符号が標準採用されています
- 深宇宙通信: NASAやESAの深宇宙探査ミッションで、極低SNR環境での高信頼通信に使われています
- デジタル放送: DVB-RCS（衛星デジタル放送のリターンリンク）で採用されています
- 理論的意義: シャノン限界への実用的到達可能性を世界で初めて実証し、LDPC符号の再発見やポーラー符号の発明といった後続の研究を刺激しました
本記事の内容
- 並列連接構造と再帰的組織畳み込み符号器（RSC）の設計原理
- インターリーバの役割と設計法
- 反復復号の原理 — 外部情報の交換メカニズム
- BCJRアルゴリズム（MAP復号）の完全な導出
- ターボ符号の性能と距離特性
- EXIT チャートによる収束解析
- Pythonによる実装とBER性能評価
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 畳み込み符号とビタビ復号の理論 — 畳み込み符号の基本構造、トレリス図、ビタビアルゴリズム
- 線形符号の理論 — 生成行列と検査行列 — 線形符号の基本概念
再帰的組織畳み込み符号器（RSC）
なぜ「再帰的」で「組織的」なのか
ターボ符号の構成要素は、通常の畳み込み符号ではなく再帰的組織畳み込み符号器（RSC: Recursive Systematic Convolutional encoder）です。畳み込み符号で学んだ通常の非再帰符号器とは二つの点で異なります。
組織符号（systematic code）とは、入力ビットがそのまま出力の一部として現れる符号です。出力は「入力ビットそのもの（組織ビット）」と「パリティビット」に分かれます。組織符号は復号の失敗時にも入力推定が可能であり、反復復号との相性が良いという利点があります。
再帰的符号器（recursive encoder）とは、出力のフィードバックを持つ符号器です。非再帰符号器では入力がシフトレジスタを通り抜けると影響が消えますが、再帰符号器ではフィードバックにより入力の影響が長期間持続します。この性質は、符号のフレームワイト（符号語の重み）の分布に大きく影響し、ターボ符号の優れた性能の鍵となります。
RSC符号器の具体例
最もよく使われるRSC符号器の例として、生成多項式 $(1, g_1/g_0)$ を持つ符号化率 $1/2$、拘束長 $K = 4$ の符号器を見ましょう。$g_0 = (1111)_2 = 15_8$、$g_1 = (1101)_2 = 13_8$ とします。
非再帰符号器の生成多項式 $(g_0, g_1)$ を再帰的組織形式に変換するには、入力にフィードバック多項式 $g_0$ を適用し、出力をフィードフォワード多項式 $g_1/g_0$ とします。
入力ビット $u_t$ に対して、シフトレジスタの内部状態を $s_1, s_2, s_3$ とすると、動作は次のようになります。
$$ \begin{aligned} w_t &= u_t \oplus s_1 \oplus s_2 \oplus s_3 \quad (\text{フィードバック: } g_0)\\ c_t^{(\text{sys})} &= u_t \quad (\text{組織ビット})\\ c_t^{(\text{par})} &= w_t \oplus s_1 \oplus s_3 \quad (\text{パリティビット: } g_1) \end{aligned} $$
状態更新は $(s_1, s_2, s_3) \leftarrow (w_t, s_1, s_2)$ です。
フィードバック接続 $g_0$ により、入力ビットの効果がシフトレジスタ内を循環し続けます。これにより、重み1の入力（1ビットだけ1のシーケンス）でも、パリティビット列の重みが高くなります。非再帰符号器では重み1の入力に対する符号語重みが低く、これがターボ符号の誤り率の底（エラーフロア）の原因になるため、再帰構造が本質的に重要なのです。
トレリス表現
RSC符号器もビタビ復号で学んだトレリス図で表現できます。拘束長 $K$ のRSC符号器は $2^{K-1}$ 個の状態を持ち、各状態から入力0と入力1に対応する2本の枝が出ます。
トレリス図はBCJRアルゴリズムによるMAP復号の基盤となります。ビタビアルゴリズムが「最もありそうなパス全体」を見つけるのに対し、BCJRアルゴリズムは「各ビットごとの最もありそうな値」を見つけます。この違いが反復復号において重要になります。
RSC符号器の構造を理解したところで、次にターボ符号全体の構成を見ていきましょう。
ターボ符号の構成
並列連接構造
ターボ符号の符号器は、2つのRSC符号器をインターリーバで結合した並列連接（parallel concatenation）構造です。
入力ビット列 $\bm{u} = (u_1, u_2, \dots, u_N)$ に対して、符号化は次の手順で行われます。
- 第1符号器: $\bm{u}$ をそのまま入力し、組織ビット $\bm{u}$ とパリティビット $\bm{p}_1 = (p_{1,1}, p_{1,2}, \dots, p_{1,N})$ を生成
- インターリーバ: $\bm{u}$ のビット順序をある置換 $\pi$ に従って並べ替え、$\bm{u}_\pi = (u_{\pi(1)}, u_{\pi(2)}, \dots, u_{\pi(N)})$ を作る
- 第2符号器: $\bm{u}_\pi$ を入力し、パリティビット $\bm{p}_2 = (p_{2,1}, p_{2,2}, \dots, p_{2,N})$ を生成
送信される符号語は $(\bm{u}, \bm{p}_1, \bm{p}_2)$ であり、各RSC符号器が符号化率 $1/2$ の場合、ターボ符号全体の符号化率は
$$ R = \frac{N}{3N} = \frac{1}{3} $$
です。組織ビットは1組だけ送信すれば十分であり（両方の符号器が同じ入力を受けるため）、パリティビットを2組送信します。
実用的には、パンクチャリング（puncturing）によって符号化率を調整します。パリティビットの一部を間引いて送信しないことで、符号化率を $1/2$ や $3/4$ などに引き上げることができます。たとえば、$\bm{p}_1$ と $\bm{p}_2$ から交互にビットを間引けば、符号化率 $R = N/(2N) = 1/2$ になります。
インターリーバの役割
インターリーバはターボ符号の性能を決定する最も重要な要素の一つです。その役割を直感的に理解しましょう。
畳み込み符号には「苦手なエラーパターン」があります。たとえば、低重みの入力パターン（少数のビットだけ1であるもの）は低重みの符号語を生成し、ノイズに対する耐性が弱くなります。
インターリーバは、第1符号器にとって低重みの符号語を生成する入力パターンを、第2符号器にとっては高重みの符号語を生成するように「かき混ぜる」役割を果たします。2つの符号器が同時に低重みの符号語を生成する確率が極めて小さくなるため、ターボ符号全体としてのエラー耐性が大幅に向上します。
インターリーバの設計には様々な方法があります。
ランダムインターリーバ: 置換 $\pi$ をランダムに選ぶ最も単純な方法です。漸近的に（$N \to \infty$ で）最適に近い性能を持つことが知られており、理論的な解析に適しています。
S-ランダムインターリーバ: ランダムインターリーバに「近接するビットが近接する位置にマッピングされない」という制約を追加したものです。パラメータ $S$ は最小距離の制約で、$|i – j| < S$ ならば $|\pi(i) - \pi(j)| \geq S$ を満たします。
QPP（Quadratic Permutation Polynomial）インターリーバ: $\pi(i) = (f_1 i + f_2 i^2) \mod N$ の形をしたインターリーバです。代数的な構造を持つため、ハードウェア実装が効率的であり、3GPP LTEで採用されています。争奪不要な並列復号が可能という実装上の大きな利点があります。
テールバイト処理
各RSC符号器のシフトレジスタは初期状態（通常は全ゼロ）から開始しますが、符号化終了時の状態は入力に依存して異なります。復号のためにはトレリスの終端状態を既知にする必要があります。
テールビット方式: 各符号器の終端に、シフトレジスタを全ゼロ状態に戻すためのビットを追加します。第1符号器のテールビットは容易に決定できますが、第2符号器のテールビットはインターリーブ後の入力に依存するため、独立に計算する必要があります。テールビットにより符号化率がわずかに低下します。
サーキュラーテイリング: トレリスを円環状にし、終端状態と初期状態を一致させる方法です。効率的ですが、復号がやや複雑になります。
ターボ符号の構成を理解したところで、いよいよ反復復号の核心に進みましょう。
反復復号の原理
外部情報の概念
ターボ復号の核心は、2つのSISO（Soft-Input Soft-Output）復号器が外部情報（extrinsic information）を交換しながら反復的に推定精度を高めていく仕組みです。
各復号器が出力する各ビット $u_k$ の対数尤度比（LLR）は、3つの成分に分解できます。
$$ L(u_k) = \underbrace{L_{\mathrm{ch}}(u_k)}_{\text{通信路情報}} + \underbrace{L_a(u_k)}_{\text{事前情報}} + \underbrace{L_e(u_k)}_{\text{外部情報}} $$
- 通信路情報 $L_{\mathrm{ch}}(u_k)$: 受信信号から直接得られる情報。AWGN通信路では $L_{\mathrm{ch}}(u_k) = 2r_k/\sigma^2$（$r_k$ は受信値）
- 事前情報 $L_a(u_k)$: 他の復号器から提供される、$u_k$ についての事前的な推定
- 外部情報 $L_e(u_k)$: この復号器がトレリス構造（符号の制約）を利用して新たに推定した情報
外部情報は、通信路情報と事前情報を「差し引いた」残りの情報です。
$$ L_e(u_k) = L(u_k) – L_{\mathrm{ch}}(u_k) – L_a(u_k) $$
なぜ通信路情報と事前情報を差し引くのでしょうか。もし復号器の出力 $L(u_k)$ をそのまま他方の復号器に渡すと、通信路情報 $L_{\mathrm{ch}}(u_k)$ が二重にカウントされてしまいます。外部情報だけを渡すことで、各復号器が独立に発見した「新しい情報」のみが交換され、情報の二重計上を避けることができます。
反復復号のアルゴリズム
反復復号は次の手順で進みます。
初期化: 事前情報を $L_a^{(1)}(u_k) = 0$（全ビットに対して無情報）に設定します。
反復 $\ell$ の各ステップ:
ステップ1 — 復号器1の動作: 第1復号器は、以下の入力を受け取ります。 – 組織ビットの受信値 $\bm{r}_{\text{sys}}$ から得られる通信路情報 – パリティビット $\bm{p}_1$ の受信値 $\bm{r}_{p1}$ – 事前情報 $L_a^{(1)}$（前回の反復で復号器2から提供されたもの）
BCJRアルゴリズムを用いて事後LLR $L^{(1)}(u_k)$ を計算し、外部情報を抽出します。
$$ L_e^{(1)}(u_k) = L^{(1)}(u_k) – L_{\mathrm{ch}}^{\text{sys}}(u_k) – L_a^{(1)}(u_k) $$
ステップ2 — インターリーブ: 復号器1の外部情報をインターリーブして、復号器2の事前情報とします。
$$ L_a^{(2)}(u_{\pi(k)}) = L_e^{(1)}(u_k) $$
ステップ3 — 復号器2の動作: 第2復号器は、以下の入力を受け取ります。 – インターリーブされた組織ビットの受信値 – パリティビット $\bm{p}_2$ の受信値 $\bm{r}_{p2}$ – 事前情報 $L_a^{(2)}$
BCJRアルゴリズムで事後LLR $L^{(2)}$ を計算し、外部情報を抽出します。
$$ L_e^{(2)}(u_{\pi(k)}) = L^{(2)}(u_{\pi(k)}) – L_{\mathrm{ch}}^{\text{sys}}(u_{\pi(k)}) – L_a^{(2)}(u_{\pi(k)}) $$
ステップ4 — デインターリーブ: 復号器2の外部情報をデインターリーブ（逆置換）して、次の反復での復号器1の事前情報とします。
$$ L_a^{(1)}(u_k) = L_e^{(2)}(u_{\pi(k)}) \quad (\text{デインターリーブ後}) $$
終了判定: 所定の反復回数（通常6〜10回）に達するか、または収束条件（外部情報の変化が十分小さい）を満たしたら終了します。最終的な硬判定は、最後の復号器（通常は復号器2）の事後LLRの符号で行います。
$$ \hat{u}_k = \begin{cases} 0 & \text{if } L^{(2)}(u_{\pi(k)}) \geq 0 \\ 1 & \text{if } L^{(2)}(u_{\pi(k)}) < 0 \end{cases} $$
（デインターリーブして元の順序に戻します）
反復の効果を直感的に理解する
反復復号がなぜ効くのか、直感的に理解しましょう。
第1復号器は、$\bm{p}_1$ のパリティ制約を使って各ビットの推定を行いますが、この推定は不完全です。推定が難しいビット（通信路のノイズが大きい箇所）については、確信度が低い外部情報が出力されます。
第2復号器は、第1復号器の外部情報を事前情報として受け取ります。加えて、$\bm{p}_2$ という別のパリティ制約を使うため、第1復号器が苦手としたビットについても新たな情報を獲得できることがあります。インターリーバのおかげで、第1符号器のパリティ制約と第2符号器のパリティ制約は異なるビットの組み合わせを結びつけているからです。
第2復号器の外部情報が第1復号器に戻されると、第1復号器は「前回は苦手だったビット」について新たな事前情報を得ることになり、次の反復ではより精度の高い推定が可能になります。
このフィードバックループにより、各反復で推定精度が向上し、最終的に非常に低い誤り率が達成されます。ただし、情報の二重計上を避けるために外部情報のみを交換する、という設計が本質的に重要です。
反復復号の原理を理解したところで、その中核をなすBCJRアルゴリズムを詳しく見ていきましょう。
BCJRアルゴリズム — MAP復号の導出
ビタビアルゴリズムとの違い
ビタビアルゴリズムは、トレリス上で「最もありそうなパス全体」を見つけます。つまり、系列全体 $\bm{u}$ を最尤推定します。
$$ \hat{\bm{u}}_{\text{ML}} = \arg\max_{\bm{u}} P(\bm{r} \mid \bm{u}) $$
一方、BCJRアルゴリズムは各ビット $u_k$ ごとに独立にMAP（Maximum A Posteriori）推定を行います。
$$ \hat{u}_k = \arg\max_{u \in \{0,1\}} P(u_k = u \mid \bm{r}) $$
ビタビは系列全体を最適化するため、個々のビットは最適でない場合がありますが、BCJRは各ビットを個別に最適化します。ターボ復号では各ビットのLLRが必要なため、BCJRアルゴリズムが使われるのです。
事後LLRの分解
BCJRアルゴリズムの目標は、各ビット $u_k$ の事後対数尤度比
$$ L(u_k) = \log \frac{P(u_k = 0 \mid \bm{r})}{P(u_k = 1 \mid \bm{r})} $$
を効率的に計算することです。ベイズの定理を使ってこの式を展開していきましょう。
まず、$P(u_k = i \mid \bm{r})$ をトレリスの状態遷移で表現します。時刻 $k$ における状態遷移 $(s_{k-1} = s’, s_k = s)$ は入力 $u_k$ と一対一に対応するため、
$$ P(u_k = i \mid \bm{r}) = \sum_{(s’, s) : u_k = i} P(s_{k-1} = s’, s_k = s \mid \bm{r}) $$
ここで和は、$u_k = i$ に対応するすべての状態遷移 $(s’, s)$ について取ります。
前向き・後ろ向き再帰の定義
$P(s_{k-1} = s’, s_k = s \mid \bm{r})$ を効率的に計算するために、3つの量を定義します。
前向き確率（$\alpha$）:
$$ \alpha_k(s) = P(s_k = s, r_1, r_2, \dots, r_k) $$
時刻1から $k$ までの受信信号と、時刻 $k$ の状態 $s$ の同時確率です。
後ろ向き確率（$\beta$）:
$$ \beta_k(s) = P(r_{k+1}, r_{k+2}, \dots, r_N \mid s_k = s) $$
時刻 $k$ の状態が $s$ であるという条件のもとで、時刻 $k+1$ から $N$ までの受信信号の条件付き確率です。
ブランチメトリック（$\gamma$）:
$$ \gamma_k(s’, s) = P(s_k = s, r_k \mid s_{k-1} = s’) $$
状態 $s’$ から $s$ への遷移と、時刻 $k$ の受信信号の同時確率です。
これら3つの量を使うと、事後確率は次のように表されます。
$$ P(s_{k-1} = s’, s_k = s \mid \bm{r}) = \frac{\alpha_{k-1}(s’) \cdot \gamma_k(s’, s) \cdot \beta_k(s)}{P(\bm{r})} $$
したがって、事後LLRは
$$ L(u_k) = \log \frac{\sum_{(s’, s) : u_k = 0} \alpha_{k-1}(s’) \cdot \gamma_k(s’, s) \cdot \beta_k(s)}{\sum_{(s’, s) : u_k = 1} \alpha_{k-1}(s’) \cdot \gamma_k(s’, s) \cdot \beta_k(s)} $$
分母 $P(\bm{r})$ は $u_k = 0$ と $u_k = 1$ で共通なので、LLRの計算では消えます。
再帰式
$\alpha$、$\beta$ は再帰的に計算できます。
前向き再帰:
$$ \alpha_k(s) = \sum_{s’} \alpha_{k-1}(s’) \cdot \gamma_k(s’, s) $$
初期条件: $\alpha_0(0) = 1$、$\alpha_0(s) = 0$（$s \neq 0$）（初期状態が全ゼロの場合）。
後ろ向き再帰:
$$ \beta_{k-1}(s’) = \sum_s \beta_k(s) \cdot \gamma_k(s’, s) $$
初期条件: テールバイトの場合 $\beta_N(0) = 1$、$\beta_N(s) = 0$（$s \neq 0$）。
ブランチメトリックの計算
AWGN通信路の場合、ブランチメトリック $\gamma_k(s’, s)$ は次のように計算されます。
状態遷移 $(s’, s)$ に対応する入力を $u$、符号器出力を $(c^{\text{sys}}, c^{\text{par}})$ とすると、
$$ \gamma_k(s’, s) = P(u_k = u) \cdot p(r_k^{\text{sys}} \mid c^{\text{sys}}) \cdot p(r_k^{\text{par}} \mid c^{\text{par}}) $$
BPSK変調（$0 \to +1$, $1 \to -1$）とガウス雑音のもとで、
$$ p(r \mid c) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(r – (1-2c))^2}{2\sigma^2}\right) $$
対数領域で計算すると、
$$ \log \gamma_k(s’, s) = \frac{L_a(u_k)}{2} u_k + \frac{L_c}{2} (r_k^{\text{sys}} x^{\text{sys}} + r_k^{\text{par}} x^{\text{par}}) + \text{const} $$
ここで $L_a(u_k)$ は事前情報のLLR、$L_c = 2/\sigma^2$ は通信路信頼度、$x = 1 – 2c$ はBPSK信号です。
対数領域での実装
数値的な安定性のため、$\alpha$, $\beta$, $\gamma$ の計算はすべて対数領域で行います。和の計算にはmax*演算（Jacobian logarithm）を使います。
$$ \log(e^a + e^b) = \max(a, b) + \log(1 + e^{-|a-b|}) $$
補正項 $\log(1 + e^{-|a-b|})$ はルックアップテーブルで効率的に実装できます。補正項を省略したものがMax-Log-MAPアルゴリズムであり、わずかな性能劣化と引き換えに計算量を大幅に削減できます。
BCJRアルゴリズムの導出を理解したところで、ターボ符号の理論的な性能特性を見ていきましょう。
ターボ符号の距離特性と性能限界
最小距離と重み分布
線形符号の誤り訂正能力は、最小ハミング距離 $d_{\min}$ で決まります。しかし、ターボ符号の $d_{\min}$ は意外にも符号長 $N$ とともに対数的にしか成長しないことが知られています。
ランダムインターリーバを用いたターボ符号の最小距離は、確率的に次のオーダーです。
$$ d_{\min} = O(\log N) $$
これは、ブロック符号（BCH符号やリード・ソロモン符号）の最小距離が $N$ に比例して成長するのとは対照的です。
では、なぜ $d_{\min}$ が小さいにもかかわらず、ターボ符号はシャノン限界に近い性能を達成できるのでしょうか。その理由は、低重みの符号語の個数（多重度）が非常に少ないことにあります。$d_{\min}$ に近い重みの符号語は存在しますが、全符号語に占める割合がきわめて小さいため、中〜高SNRまでは事実上無視できるのです。
ウォーターフォール領域とエラーフロア
ターボ符号のBER曲線には2つの特徴的な領域があります。
ウォーターフォール領域: 中程度のSNRにおいて、BERが急激に低下する領域です。この領域では反復復号が効果的に機能し、各反復で外部情報の品質が向上します。密度発展法やEXITチャートの解析から、ウォーターフォールの開始点（しきい値）を予測できます。
エラーフロア領域: 高SNRにおいて、BERの低下速度が緩やかになる領域です。この領域でのBERは $d_{\min}$ に支配されます。具体的には、
$$ \text{BER} \approx \frac{d_{\min}}{N} \cdot A_{d_{\min}} \cdot \mathrm{erfc}\left(\sqrt{d_{\min} R \cdot E_b/N_0}\right) $$
ここで $A_{d_{\min}}$ は最小距離の多重度です。エラーフロアのレベルは、インターリーバの設計と符号長 $N$ に依存します。$N$ が大きいほどエラーフロアは低くなり、実用上問題にならないレベルに抑えられます。
シャノン限界との距離
ターボ符号の性能は、以下のように特徴づけられます。
符号化率 $R = 1/3$ のターボ符号（拘束長 $K = 4$, $N = 65536$）は、$\mathrm{BER} = 10^{-5}$ で $E_b/N_0 \approx 0.7$ dBを達成します。シャノン限界は $E_b/N_0 = -0.49$ dBですから、シャノン限界から約1.2 dBの差です。
符号化率 $R = 1/2$（パンクチャリング使用）では、シャノン限界から約0.7 dBの差で $\mathrm{BER} = 10^{-5}$ を達成できます。
さらに最適化されたターボ符号（16状態のRSC符号器、最適化インターリーバ）では、シャノン限界から0.5 dB以内まで近づくことが報告されています。
EXITチャートによる収束解析
EXITチャートとは
EXITチャート（Extrinsic Information Transfer chart）は、ターボ復号の収束を可視化・解析するための強力な手法です。1999年にテン・ブリンク（Stephan ten Brink）が提案しました。
EXITチャートの基本的な考え方は、各成分復号器の入出力を相互情報量で特徴づけることです。
- 入力相互情報量 $I_A$: 事前情報 $L_a$ とビット $u_k$ の相互情報量 $I(u_k; L_a)$
- 出力相互情報量 $I_E$: 外部情報 $L_e$ とビット $u_k$ の相互情報量 $I(u_k; L_e)$
各復号器の伝達特性（EXIT関数）$I_E = T(I_A, E_b/N_0)$ は、入力の事前情報の品質が向上すると出力の外部情報の品質も向上する、という単調増加関数です。
復号軌跡の可視化
EXITチャート上で、復号器1のEXIT関数 $I_{E,1} = T_1(I_{A,1})$ と復号器2のEXIT関数 $I_{E,2} = T_2(I_{A,2})$を描画します。ただし、復号器2の関数は軸を入れ替えて $I_{A,2} = T_2^{-1}(I_{E,2})$ として描きます。
反復復号の軌跡は、2つの曲線の間を階段状に進みます。
- 復号器1: 入力 $I_{A,1} = 0$ から $I_{E,1}$ を計算
- 復号器2: $I_{A,2} = I_{E,1}$ から $I_{E,2}$ を計算
- 復号器1: $I_{A,1} = I_{E,2}$ から $I_{E,1}$ を計算
- 以下繰り返し
2つのEXIT曲線が交差しなければ（「トンネル」が開いていれば）、軌跡は $(1, 1)$ に到達し、復号が成功します。2つの曲線が交差すると、軌跡はそこで停滞し、復号が失敗します。
しきい値は、2つのEXIT曲線がちょうど接する $E_b/N_0$ で定義されます。このしきい値がウォーターフォール領域の開始点を決定します。
EXITチャートによる符号設計
EXITチャートは符号設計の指針としても使えます。理想的には、2つのEXIT曲線の間の「トンネル」面積を最小にすることが、シャノン限界に最も近い性能を達成する条件です。
2つの曲線の間の面積は、符号化率 $R$ とシャノン限界との差に対応することが知られています（面積定理）。
$$ A_{\text{tunnel}} \approx 1 – R/C $$
ここで $C$ は通信路容量です。トンネル面積が0に近い（= 2つの曲線がほぼ一致する）ほど、シャノン限界に近い性能が得られます。
ターボ符号の理論的な性能特性を理解したところで、Pythonで実装して確認しましょう。
Pythonによる実装とBER性能評価
RSC符号器とBCJRアルゴリズムの実装
import numpy as np
import matplotlib.pyplot as plt
from scipy.special import erfc
np.random.seed(42)
class RSCEncoder:
"""再帰的組織畳み込み符号器 (2, 1, 3)
フィードバック多項式: g0 = 7 (111), フィードフォワード: g1 = 5 (101)
"""
def __init__(self):
self.K = 3 # 拘束長
self.n_states = 4 # 2^(K-1)
# 状態遷移テーブルと出力テーブルを構築
self.next_state = np.zeros((4, 2), dtype=int)
self.output_par = np.zeros((4, 2), dtype=int)
for state in range(4):
s0 = (state >> 1) & 1
s1 = state & 1
for u in range(2):
# フィードバック: w = u XOR s0 XOR s1
w = u ^ s0 ^ s1
# パリティ出力: p = w XOR s1
p = w ^ s1
# 次の状態: (w, s0)
ns = (w << 1) | s0
self.next_state[state, u] = ns
self.output_par[state, u] = p
def encode(self, u):
"""入力ビット列uを符号化し、パリティビット列を返す"""
N = len(u)
parity = np.zeros(N, dtype=int)
state = 0
for k in range(N):
parity[k] = self.output_par[state, u[k]]
state = self.next_state[state, u[k]]
return parity, state
def bcjr_decode(r_sys, r_par, La, sigma2, encoder):
"""BCJRアルゴリズムによるMAP復号
r_sys: 組織ビットの受信値
r_par: パリティビットの受信値
La: 事前情報LLR
sigma2: 雑音分散
戻り値: 事後LLR, 外部情報LLR
"""
N = len(r_sys)
n_states = encoder.n_states
Lc = 2.0 / sigma2 # 通信路信頼度
# ブランチメトリック (対数領域)
# gamma[k, s', s] は対数領域で計算
log_gamma = np.full((N, n_states, n_states), -1e10)
for k in range(N):
for s_prev in range(n_states):
for u in range(2):
s_next = encoder.next_state[s_prev, u]
p = encoder.output_par[s_prev, u]
# BPSK: 0 -> +1, 1 -> -1
x_sys = 1 - 2 * u
x_par = 1 - 2 * p
# 対数ブランチメトリック
lg = (La[k] / 2.0) * (1 - 2 * u) # 事前情報の寄与
lg += (Lc / 2.0) * r_sys[k] * x_sys # 組織ビットの寄与
lg += (Lc / 2.0) * r_par[k] * x_par # パリティビットの寄与
log_gamma[k, s_prev, s_next] = lg
# 前向き再帰 (対数alpha)
log_alpha = np.full((N + 1, n_states), -1e10)
log_alpha[0, 0] = 0.0
for k in range(N):
for s in range(n_states):
vals = []
for s_prev in range(n_states):
val = log_alpha[k, s_prev] + log_gamma[k, s_prev, s]
if val > -1e9:
vals.append(val)
if vals:
log_alpha[k + 1, s] = max(vals) + np.log(
sum(np.exp(v - max(vals)) for v in vals))
# 正規化
max_a = np.max(log_alpha[k + 1])
if max_a > -1e9:
log_alpha[k + 1] -= max_a
# 後ろ向き再帰 (対数beta)
log_beta = np.full((N + 1, n_states), -1e10)
# テールなしの場合: 全状態で均等初期化
log_beta[N] = 0.0
for k in range(N - 1, -1, -1):
for s_prev in range(n_states):
vals = []
for s in range(n_states):
val = log_beta[k + 1, s] + log_gamma[k, s_prev, s]
if val > -1e9:
vals.append(val)
if vals:
log_beta[k, s_prev] = max(vals) + np.log(
sum(np.exp(v - max(vals)) for v in vals))
# 正規化
max_b = np.max(log_beta[k])
if max_b > -1e9:
log_beta[k] -= max_b
# 事後LLR計算
L_post = np.zeros(N)
for k in range(N):
log_p0 = -1e10 # P(u_k = 0 | r)
log_p1 = -1e10 # P(u_k = 1 | r)
for s_prev in range(n_states):
for u in range(2):
s_next = encoder.next_state[s_prev, u]
val = (log_alpha[k, s_prev] + log_gamma[k, s_prev, s_next]
+ log_beta[k + 1, s_next])
if u == 0:
if val > log_p0:
diff = log_p0 - val
log_p0 = val + np.log(1 + np.exp(diff)) if diff > -30 else val
else:
diff = val - log_p0
log_p0 = log_p0 + np.log(1 + np.exp(diff)) if diff > -30 else log_p0
else:
if val > log_p1:
diff = log_p1 - val
log_p1 = val + np.log(1 + np.exp(diff)) if diff > -30 else val
else:
diff = val - log_p1
log_p1 = log_p1 + np.log(1 + np.exp(diff)) if diff > -30 else log_p1
L_post[k] = log_p0 - log_p1
# 外部情報 = 事後LLR - 通信路LLR - 事前情報
Lch_sys = Lc * r_sys
Le = L_post - Lch_sys - La
return L_post, Le
上のコードでは、RSC符号器とBCJRアルゴリズムの対数領域実装を行っています。ブランチメトリック、前向き再帰、後ろ向き再帰の各ステップが理論どおりに実装されている点に注目してください。数値的な安定性のために対数領域で計算し、正規化も行っています。
ターボ符号の反復復号シミュレーション
def turbo_encode(u, interleaver, encoder):
"""ターボ符号の符号化"""
p1, _ = encoder.encode(u)
u_interleaved = u[interleaver]
p2, _ = encoder.encode(u_interleaved)
return p1, p2
def turbo_decode(r_sys, r_p1, r_p2, interleaver, sigma2, encoder, n_iter=8):
"""ターボ復号（反復復号）"""
N = len(r_sys)
deinterleaver = np.argsort(interleaver)
La1 = np.zeros(N) # 復号器1への事前情報
for it in range(n_iter):
# 復号器1
_, Le1 = bcjr_decode(r_sys, r_p1, La1, sigma2, encoder)
# インターリーブして復号器2へ
La2 = Le1[interleaver]
r_sys_int = r_sys[interleaver]
# 復号器2
L_post2, Le2 = bcjr_decode(r_sys_int, r_p2, La2, sigma2, encoder)
# デインターリーブして復号器1へ
La1 = Le2[deinterleaver]
# 最終判定（復号器2の事後LLR）
u_hat_int = (L_post2 < 0).astype(int)
u_hat = u_hat_int[deinterleaver]
return u_hat
# --- BERシミュレーション ---
encoder = RSCEncoder()
N = 256 # ブロック長
R = 1.0 / 3.0 # 符号化率
EbN0_dB_range = np.arange(0, 4.5, 0.5)
ber_uncoded = []
ber_turbo = []
n_frames = 300
for EbN0_dB in EbN0_dB_range:
EbN0 = 10 ** (EbN0_dB / 10)
sigma2 = 1.0 / (2.0 * R * EbN0)
sigma = np.sqrt(sigma2)
# 未符号化BER（理論値）
ber_uncoded.append(0.5 * erfc(np.sqrt(EbN0)))
total_errors = 0
total_bits = 0
for _ in range(n_frames):
# ランダム情報ビット
u = np.random.randint(0, 2, N)
interleaver = np.random.permutation(N)
# 符号化
p1, p2 = turbo_encode(u, interleaver, encoder)
# BPSK変調
x_sys = 1.0 - 2.0 * u
x_p1 = 1.0 - 2.0 * p1
x_p2 = 1.0 - 2.0 * p2
# AWGN通信路
r_sys = x_sys + sigma * np.random.randn(N)
r_p1 = x_p1 + sigma * np.random.randn(N)
r_p2 = x_p2 + sigma * np.random.randn(N)
# 復号
u_hat = turbo_decode(r_sys, r_p1, r_p2, interleaver, sigma2,
encoder, n_iter=8)
total_errors += np.sum(u_hat != u)
total_bits += N
ber_turbo.append(max(total_errors / total_bits, 1e-7))
# シャノン限界の計算
shannon_limit = 10 * np.log10((2**(1/R) - 1) / (2 * R))
fig, ax = plt.subplots(figsize=(8, 6))
ax.semilogy(EbN0_dB_range, ber_uncoded, 'b--', linewidth=1.5,
label='Uncoded BPSK (theory)')
ax.semilogy(EbN0_dB_range, ber_turbo, 'ro-', markersize=5, linewidth=1.5,
label=f'Turbo (N={N}, R={R:.2f}, 8 iter)')
ax.axvline(shannon_limit, color='g', linestyle='--', linewidth=1.5,
label=f'Shannon limit: {shannon_limit:.2f} dB')
ax.set_xlabel('$E_b/N_0$ [dB]')
ax.set_ylabel('Bit Error Rate')
ax.set_title('Turbo Code BER Performance')
ax.legend()
ax.grid(True, which='both', alpha=0.3)
ax.set_ylim(1e-6, 1)
plt.tight_layout()
plt.show()
このシミュレーション結果から、以下のことが読み取れます。
- 符号化利得: ターボ符号は未符号化BPSKに対して大きな符号化利得を達成しています。同じBERを達成するために必要な $E_b/N_0$ が数dB低下しています。
- ウォーターフォール特性: ある $E_b/N_0$ を境にBERが急激に低下する急峻な遷移が観察されます。この遷移はEXITチャートのトンネルが開く点に対応しています。
- シャノン限界への接近: 緑の破線で示されたシャノン限界に対して、比較的短い符号長（$N = 256$）でも相当近い性能が得られています。符号長を $N = 10000$ 以上に増やすと、さらにシャノン限界に接近します。
反復ごとのBER改善の可視化
反復復号で各反復がBERをどれだけ改善するかを可視化します。
def turbo_decode_with_trace(r_sys, r_p1, r_p2, interleaver, sigma2,
encoder, u_true, n_iter=10):
"""反復ごとのBERを記録するターボ復号"""
N = len(r_sys)
deinterleaver = np.argsort(interleaver)
La1 = np.zeros(N)
ber_trace = []
for it in range(n_iter):
_, Le1 = bcjr_decode(r_sys, r_p1, La1, sigma2, encoder)
La2 = Le1[interleaver]
r_sys_int = r_sys[interleaver]
L_post2, Le2 = bcjr_decode(r_sys_int, r_p2, La2, sigma2, encoder)
La1 = Le2[deinterleaver]
u_hat = (L_post2 < 0).astype(int)[deinterleaver]
ber_trace.append(np.mean(u_hat != u_true))
return ber_trace
# 特定のSNRでの反復ごとのBER
N = 512
EbN0_dB_values = [1.0, 1.5, 2.0, 2.5]
n_frames = 100
fig, ax = plt.subplots(figsize=(8, 5))
for EbN0_dB in EbN0_dB_values:
EbN0 = 10 ** (EbN0_dB / 10)
sigma2 = 1.0 / (2.0 * R * EbN0)
sigma = np.sqrt(sigma2)
avg_trace = np.zeros(10)
for _ in range(n_frames):
u = np.random.randint(0, 2, N)
interleaver = np.random.permutation(N)
p1, p2 = turbo_encode(u, interleaver, encoder)
x_sys = 1.0 - 2.0 * u
r_sys = x_sys + sigma * np.random.randn(N)
r_p1 = (1.0 - 2.0 * p1) + sigma * np.random.randn(N)
r_p2 = (1.0 - 2.0 * p2) + sigma * np.random.randn(N)
trace = turbo_decode_with_trace(r_sys, r_p1, r_p2, interleaver,
sigma2, encoder, u, n_iter=10)
avg_trace += np.array(trace)
avg_trace /= n_frames
ax.semilogy(range(1, 11), [max(b, 1e-7) for b in avg_trace],
'o-', markersize=5, label=f'$E_b/N_0$ = {EbN0_dB} dB')
ax.set_xlabel('Iteration number')
ax.set_ylabel('BER')
ax.set_title('BER improvement with iterations')
ax.legend()
ax.grid(True, which='both', alpha=0.3)
ax.set_ylim(1e-5, 0.5)
plt.tight_layout()
plt.show()
このグラフから、反復復号の効果が明確に読み取れます。最初の数回の反復でBERが急激に改善し、その後は収束して改善幅が小さくなります。SNRが高いほど収束が速く、低SNRでは多くの反復が必要です。実用的には6〜8回の反復で十分な性能が得られることがわかります。
また、しきい値以下のSNR（この例では $E_b/N_0 = 1.0$ dB）では、反復を重ねてもBERが十分に低下しません。これはEXITチャートにおいて「トンネルが閉じている」状況に対応しています。
ターボ符号とLDPC符号の比較
ターボ符号とLDPC符号はどちらもシャノン限界に近い性能を持つ現代的な符号ですが、設計哲学と特性が異なります。
構造: ターボ符号は畳み込み符号の連接であるのに対し、LDPC符号はスパースなパリティ検査行列で定義されるブロック符号です。ターボ符号のトレリス構造は逐次的な処理に適しており、LDPC符号のグラフ構造は並列処理に適しています。
復号の並列性: LDPC符号のBP復号は高度に並列化できるため、高スループットの実装に有利です。ターボ符号のBCJR復号はトレリスに沿った逐次処理が含まれるため、並列化に限界があります。この差が、5G NRでLDPC符号が採用された主な理由の一つです。
短符号長の性能: 符号長が短い（$N < 1000$）場合、ターボ符号がLDPC符号より良い性能を示す傾向があります。これは、ターボ符号のトレリス構造が短い符号長でも有効に機能するためです。
エラーフロア: ターボ符号のエラーフロアは $d_{\min}$ が $O(\log N)$ であるため、高SNRで顕在化しやすいです。LDPC符号のエラーフロアはトラッピングセットに起因し、符号設計で制御可能です。
まとめ
本記事では、ターボ符号の理論と実装について解説しました。
- 並列連接構造: 2つのRSC符号器をインターリーバで結合する構造が、低重みの符号語の多重度を抑制し、優れた距離特性を実現する
- 反復復号: 2つのSISO復号器が外部情報を交換する反復プロセスにより、各反復で推定精度が向上する。情報の二重計上を避けるために外部情報のみを交換することが本質的に重要
- BCJRアルゴリズム: 前向き再帰（$\alpha$）と後ろ向き再帰（$\beta$）を組み合わせて各ビットの事後LLRを効率的に計算するMAP復号アルゴリズム
- 性能特性: ウォーターフォール領域とエラーフロア領域の2つの特性領域を持ち、シャノン限界から0.5 dB以内の性能を達成可能
- EXITチャート: 復号の収束をトンネルの開閉で可視化し、しきい値の予測と符号設計の指針を提供する
ターボ符号は、シャノンの理論的限界に実用的に到達できることを世界で初めて実証した歴史的な符号であり、その後の符号理論の発展（LDPC符号の再発見、ポーラー符号の発明）を大きく刺激しました。
次のステップとして、以下の記事も参考にしてください。
- LDPC符号の理論 — スパースグラフ符号 — もう一つのシャノン限界級符号
- 畳み込み符号とビタビ復号の理論 — ターボ符号の構成要素