携帯電話で通話するとき、音声データはデジタル化されてから無線回線を通って基地局に送られます。この無線回線ではフェージングやノイズによってビット誤りが頻繁に発生しますが、通話品質が保たれるのはなぜでしょうか。その背後で働いているのが畳み込み符号（convolutional code）とビタビアルゴリズム（Viterbi algorithm）による誤り訂正です。
線形符号やハミング符号のようなブロック符号は、データを固定長のブロックに分割して独立に符号化します。一方、畳み込み符号は入力ビット列を連続的に処理し、現在の入力だけでなく過去の入力も利用して出力を生成します。この「記憶」の仕組みにより、ブロック符号よりも強力な誤り訂正を、比較的シンプルなハードウェアで実現できるのです。
畳み込み符号を理解すると、以下のような分野に直結する知識が得られます。
- モバイル通信: GSM、3G（UMTS）、4G LTEの物理レイヤで広く使われてきました
- 宇宙通信: NASAのボイジャー計画をはじめ、深宇宙探査の通信で標準的に使われています
- GPS: 衛星からの微弱な測位信号を地上で正しく受信するための誤り訂正に使われています
- デジタル放送: 地上波デジタルテレビ（ISDB-T、DVB-T）の内符号として採用されています
- ターボ符号: ターボ符号の構成要素として、シャノン限界に迫る性能を実現する基盤技術です
本記事の内容
- 畳み込み符号の定義 — ブロック符号との根本的な違い
- シフトレジスタによる符号化と生成多項式
- 状態遷移図とトレリス図の構築
- 自由距離と誤り訂正能力
- ビタビアルゴリズムの原理と正当性の証明
- 硬判定復号と軟判定復号
- Pythonによる実装とBER性能評価
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 線形符号の理論 — 生成行列と検査行列 — 線形符号の基本概念、ハミング距離
- ハミング符号の理論と誤り訂正能力 — ブロック符号の例
畳み込み符号の定義と構造
ブロック符号との根本的な違い
線形符号では、$k$ ビットの情報語を生成行列 $\bm{G}$ を使って $n$ ビットの符号語に変換しました。各ブロックは独立に処理され、前後のブロックとの関係はありません。
畳み込み符号は、これとは根本的に異なるアプローチを取ります。入力ビットが符号器に逐次的に供給され、各時刻の出力は現在の入力と過去の入力の関数として決まります。シフトレジスタに蓄えられた過去の入力が「記憶」として機能し、この記憶の長さが符号の性能を決定します。
大雑把に言えば、ブロック符号が「章ごとに独立した要約を作る」のに対し、畳み込み符号は「前の文脈を覚えながら連続的に文章を書く」ようなものです。文脈を利用するため、局所的な誤りに対してより頑健な符号化が可能になります。
パラメータの定義
畳み込み符号は3つのパラメータ $(n, k, K)$ で記述されます。
- $k$: 各時刻に入力するビット数
- $n$: 各時刻に出力するビット数（$n > k$）
- $K$: 拘束長（constraint length）— 各出力に影響を与える入力ビットの数
符号化率は $R = k/n$ です。最も基本的な場合は $k = 1$（1ビットずつ入力する）であり、本記事でもこの場合を中心に解説します。
拘束長 $K$ は符号の「記憶の深さ」を表します。$K$ が大きいほど過去の入力をより多く利用でき、誤り訂正能力が向上します。ただし、復号の計算量は $2^{K-1}$ に比例するため、$K$ を大きくしすぎると実装が困難になります。実用的には $K = 3$ から $K = 9$ 程度が使われます。
シフトレジスタの段数は $m = K – 1$ であり、符号器の状態数は $2^m = 2^{K-1}$ です。
シフトレジスタ符号器
最も基本的な $(2, 1, 3)$ 畳み込み符号を具体例として解説します。この符号は符号化率 $R = 1/2$、拘束長 $K = 3$ です。
符号器は2段のシフトレジスタ（$m = K – 1 = 2$ 段）からなります。時刻 $t$ で入力ビットが $u_t$、シフトレジスタの状態が $(s_1, s_2)$ のとき、2つの出力ビット $c_t^{(1)}$, $c_t^{(2)}$ は次のように計算されます。
$$ \begin{aligned} c_t^{(1)} &= u_t \oplus s_1 \oplus s_2 \\ c_t^{(2)} &= u_t \oplus s_2 \end{aligned} $$
ここで $\oplus$ は排他的論理和（XOR、$\mathrm{mod}\, 2$ の加算）です。各出力は、現在の入力 $u_t$ と過去の入力の一部の線形結合（$\mathrm{GF}(2)$ 上）で表されます。
シフトレジスタの更新は $(s_1, s_2) \leftarrow (u_t, s_1)$ です。新しい入力ビットがレジスタの先頭に入り、最後のビットが押し出されます。
生成多項式
畳み込み符号の構造は生成多項式で簡潔に表現できます。上の例では、
$$ g^{(1)}(D) = 1 + D + D^2, \quad g^{(2)}(D) = 1 + D^2 $$
ここで $D$ は遅延演算子（1時刻の遅延を表す）です。$g^{(1)}$ の係数 $(1, 1, 1)$ は $u_t$, $s_1$, $s_2$ すべてが $c_t^{(1)}$ に寄与することを表し、$g^{(2)}$ の係数 $(1, 0, 1)$ は $u_t$ と $s_2$ のみが $c_t^{(2)}$ に寄与することを表します。
8進数表記では $g^{(1)} = 7_8$（二進 $111$）、$g^{(2)} = 5_8$（二進 $101$）であり、$(7, 5)$ 符号と呼ばれます。
一般に、符号化率 $1/n$、拘束長 $K$ の畳み込み符号は $n$ 個の生成多項式 $g^{(1)}, g^{(2)}, \dots, g^{(n)}$ で定義されます。各生成多項式は $K$ ビットの二進数であり、どの入力ビット（現在と過去）が各出力に寄与するかを指定します。
具体的な符号化例
$(7, 5)$ 符号で入力 $\bm{u} = (1, 0, 1, 1, 0)$ を符号化してみましょう。初期状態は $(s_1, s_2) = (0, 0)$ です。
| 時刻 $t$ | 入力 $u_t$ | 状態 $(s_1, s_2)$ | $c_t^{(1)}$ | $c_t^{(2)}$ | 出力 |
|---|---|---|---|---|---|
| 1 | 1 | (0, 0) | $1 \oplus 0 \oplus 0 = 1$ | $1 \oplus 0 = 1$ | 11 |
| 2 | 0 | (1, 0) | $0 \oplus 1 \oplus 0 = 1$ | $0 \oplus 0 = 0$ | 10 |
| 3 | 1 | (0, 1) | $1 \oplus 0 \oplus 1 = 0$ | $1 \oplus 1 = 0$ | 00 |
| 4 | 1 | (1, 0) | $1 \oplus 1 \oplus 0 = 0$ | $1 \oplus 0 = 1$ | 01 |
| 5 | 0 | (1, 1) | $0 \oplus 1 \oplus 1 = 0$ | $0 \oplus 1 = 1$ | 01 |
符号化後の出力は $11\, 10\, 00\, 01\, 01$ です。入力の5ビットから出力の10ビットが生成され、符号化率 $R = 5/10 = 1/2$ であることが確認できます。
注意点として、符号化終了時にシフトレジスタを初期状態 $(0, 0)$ に戻すためのテールビット（$m = 2$ 個のゼロビット）を追加することが一般的です。これにより、復号器がトレリスの終端状態を既知として利用でき、復号性能が向上します。テールビットにより実効的な符号化率は $R = N/(n(N+m))$ とわずかに低下しますが、$N$ が大きければ影響は無視できます。
畳み込み符号の符号化を理解したところで、次に符号器の動作をグラフとして表現する方法を見ていきましょう。
状態遷移図とトレリス図
状態遷移図
畳み込み符号器は有限状態機械（finite state machine）として表現できます。$(2, 1, 3)$ 符号の場合、シフトレジスタの状態は $(s_1, s_2) \in \{00, 01, 10, 11\}$ の4通りです。
状態遷移図は、4つの状態をノードとし、入力ビットに応じた状態遷移を有向辺で表します。各辺には「入力/出力」のラベルが付きます。
たとえば、状態 $00$ で入力 $0$ の場合: 出力は $c^{(1)} = 0 \oplus 0 \oplus 0 = 0$、$c^{(2)} = 0 \oplus 0 = 0$、次の状態は $(0, 0) = 00$。つまり自己ループで出力 $00$ です。
状態 $00$ で入力 $1$ の場合: 出力は $c^{(1)} = 1 \oplus 0 \oplus 0 = 1$、$c^{(2)} = 1 \oplus 0 = 1$、次の状態は $(1, 0) = 10$。状態 $10$ へ遷移して出力 $11$ です。
全状態遷移を表にすると以下のようになります。
| 現在の状態 | 入力 | 出力 $(c^{(1)}, c^{(2)})$ | 次の状態 |
|---|---|---|---|
| 00 | 0 | 00 | 00 |
| 00 | 1 | 11 | 10 |
| 01 | 0 | 11 | 00 |
| 01 | 1 | 00 | 10 |
| 10 | 0 | 10 | 01 |
| 10 | 1 | 01 | 11 |
| 11 | 0 | 01 | 01 |
| 11 | 1 | 10 | 11 |
トレリス図
状態遷移図は符号器の静的な構造を表しますが、時間方向の展開がありません。トレリス図（trellis diagram）は、状態遷移図を時間方向に展開した図で、復号アルゴリズムの視覚的な理解に不可欠です。
トレリス図では、横軸に時刻、縦軸にシフトレジスタの状態を取ります。各時刻の各状態ノードから、入力0に対応する枝（通常は実線）と入力1に対応する枝（通常は破線）が伸び、次の時刻の対応する状態ノードに接続されます。
送信された符号語列は、トレリス上の初期状態（通常 $00$）から始まる一本のパス（path）に対応します。テールビットを使う場合、パスは最終的に状態 $00$ に戻ります。
トレリスの重要な性質は、任意の2つのパスが合流してから再び分岐するまでの区間で、出力が異なる（＝ハミング距離が0でない）ことです。この性質がビタビアルゴリズムの正当性を保証します。
自由距離
畳み込み符号の誤り訂正能力を決定する最も重要なパラメータが自由距離（free distance）$d_{\text{free}}$ です。自由距離は、全ゼロパスからの最小ハミング距離を持つパスとの距離として定義されます。
形式的には、状態 $00$ から出発し、少なくとも一度は状態 $00$ から離れた後、再び状態 $00$ に戻るすべてのパスの中で、出力のハミング重みが最小のものが $d_{\text{free}}$ です。
$$ d_{\text{free}} = \min_{\bm{u} \neq \bm{0}} w_H(\bm{c}(\bm{u})) $$
ここで $w_H$ はハミング重み、$\bm{c}(\bm{u})$ は入力 $\bm{u}$ に対する符号語です。
$(7, 5)$ 符号の場合、$d_{\text{free}} = 5$ です。状態 $00$ から入力1で状態 $10$ に移り、入力1で状態 $11$ に移り、入力1で状態 $11$ にとどまり…最短で状態 $00$ に戻るパスの出力重みを調べると、最小が5であることがわかります。
$d_{\text{free}} = 5$ なので、この符号は $\lfloor (d_{\text{free}} – 1) / 2 \rfloor = 2$ ビットの誤りを訂正できます。
代表的な畳み込み符号の自由距離を以下に示します。
| 符号 $(n, k, K)$ | 生成多項式 | $d_{\text{free}}$ |
|---|---|---|
| $(2, 1, 3)$ | $(7, 5)_8$ | 5 |
| $(2, 1, 4)$ | $(15, 17)_8$ | 6 |
| $(2, 1, 5)$ | $(23, 35)_8$ | 7 |
| $(2, 1, 7)$ | $(171, 133)_8$ | 10 |
| $(3, 1, 3)$ | $(7, 7, 5)_8$ | 8 |
拘束長 $K$ が大きいほど $d_{\text{free}}$ は増加し、誤り訂正能力が向上します。しかし、状態数が $2^{K-1}$ で指数的に増加するため、復号の計算量も急増します。NASA のボイジャー探査機では $(2, 1, 7)$ 畳み込み符号（$d_{\text{free}} = 10$、64状態）が使われました。
トレリスと距離特性を理解したところで、いよいよ最尤復号を効率的に実現するビタビアルゴリズムに進みましょう。
ビタビアルゴリズムの原理
最尤復号の問題設定
受信系列 $\bm{r} = (r_1, r_2, \dots, r_{nN})$ が与えられたとき、送信された符号語列 $\bm{c}$ を推定する問題を考えます。
$$ \hat{\bm{c}} = \arg\max_{\bm{c}} P(\bm{r} \mid \bm{c}) $$
二元対称通信路（BSC）では、$P(\bm{r} \mid \bm{c})$ を最大化することは $\bm{r}$ と $\bm{c}$ のハミング距離を最小化することと等価です。AWGN通信路では、ユークリッド距離を最小化することと等価です。
符号語列はトレリス上のパスに一対一に対応するため、最尤復号は「受信系列に最も近い（距離が最小の）パスを見つける問題」に帰着されます。
素朴にはすべてのパスを探索する必要がありますが、パスの数は $2^N$ で指数的に増加します。ビタビアルゴリズムは、動的計画法（dynamic programming）を使ってこの探索を $O(N \cdot 2^m)$ に効率化します。
アルゴリズムの核心 — 生き残りパスの原理
ビタビアルゴリズムの核心的なアイデアは次のとおりです。
主張: ある時刻 $t$ で同じ状態 $s$ に到達する2つのパスがあるとき、その時点でメトリック（累積距離）が大きい方のパスは、最終的な最尤パスの一部にはなりえない。
証明: 2つのパス $A$ と $B$ が時刻 $t$ の状態 $s$ で合流したとします。$A$ のメトリックが $B$ のメトリックより大きい（$A$ の方が受信系列から遠い）とします。時刻 $t$ 以降のパスの延長は両方とも同一であるため、パス $A$ を含む完全なパスのメトリックは、対応するパス $B$ を含む完全なパスのメトリックよりも常に大きくなります。したがって、パス $A$ が最尤パスの一部になることはありません。
この性質により、各時刻の各状態について、最小メトリックのパスだけを生き残りパス（survivor path）として残し、他のパスを枝刈り（pruning）できます。各時刻で状態数 $2^m$ 個のパスだけを追跡すればよく、パスの数が時刻とともに増大することはありません。
アルゴリズムの手順
ビタビアルゴリズムは以下の手順で進みます。
初期化: 各状態のパスメトリックを無限大に設定し、初期状態（通常 $00$）のパスメトリックを0にします。
$$ M_0(s) = \begin{cases} 0 & \text{if } s = 00 \\ \infty & \text{otherwise} \end{cases} $$
時刻 $t = 1, 2, \dots, N+m$ の各ステップ:
各状態 $s$ に到達するすべての遷移について、以下の処理を行います。
-
ブランチメトリックの計算: 前の状態 $s’$ から入力 $u$ で状態 $s$ に遷移するとき、その遷移に対応する出力 $\bm{c}(s’, u)$ と受信信号 $\bm{r}_t$ の距離を計算します。
- BSC（硬判定）: $\text{BM} = d_H(\bm{r}_t, \bm{c}(s’, u))$（ハミング距離）
- AWGN（軟判定）: $\text{BM} = \|\bm{r}_t – \bm{x}(s’, u)\|^2$（ユークリッド距離の二乗）
-
パスメトリックの更新: 各状態 $s$ に到達する候補パスのメトリックを計算します。
$$ M_t^{(u)}(s) = M_{t-1}(s’) + \text{BM}(s’, u) $$
- 比較・選択: 同じ状態 $s$ に到達する複数の候補パスのうち、メトリックが最小のものを生き残りパスとして選択します。
$$ M_t(s) = \min_{(s’, u)} M_t^{(u)}(s) $$
- パスの記録: 生き残りパスの遷移履歴を記録します。
終了処理: テールビットを使用する場合、最終的に状態 $00$ のパスメトリックが最小であり、そのパスが最尤パスです。テールビットを使用しない場合は、すべての状態の中でメトリックが最小のものを選びます。
トレースバック: 最終状態から遷移履歴を逆にたどり、各時刻の推定入力ビットを復元します。
計算量の解析
ビタビアルゴリズムの計算量を分析しましょう。
- 各時刻で、$2^m$ 個の状態のそれぞれについて2つ（入力0と入力1）のブランチメトリックを計算
- 時刻は $N + m$ 個
したがって、計算量は $O((N + m) \cdot 2^m)$ であり、系列長 $N$ に対して線形です。素朴な全探索 $O(2^N)$ と比べて劇的な改善です。
ただし、状態数 $2^m = 2^{K-1}$ に対しては指数的であり、拘束長 $K$ を大きくすると計算量が急増します。$K = 7$ で64状態、$K = 9$ で256状態となり、これが実用上の上限の目安です。
メモリ使用量は、パスの記録に $O(2^m \cdot (N + m))$ 必要です。実装上は、トレースバック長を $D \approx 5K$ 程度に制限し、スライディングウィンドウ方式で逐次的に復号することで、メモリを $O(2^m \cdot D)$ に抑えることが可能です。
軟判定復号と符号化利得
硬判定 vs 軟判定
ビタビアルゴリズムは、ブランチメトリックの計算方法によって硬判定（hard-decision）復号と軟判定（soft-decision）復号に分類されます。
硬判定復号: 受信信号を0または1に量子化してからビタビアルゴリズムに入力します。ブランチメトリックはハミング距離です。実装が単純ですが、量子化の段階で情報が失われます。
軟判定復号: 受信信号の実数値（信頼度情報を含む）をそのままビタビアルゴリズムに入力します。AWGN通信路の場合、ブランチメトリックはユークリッド距離の二乗（または等価的に相関値）です。
軟判定復号は硬判定復号に比べて約2〜3 dBの利得があります。これは「軟判定利得」と呼ばれ、量子化によって失われる情報を回復した結果です。具体的には、AWGN通信路上の $(2, 1, K)$ 畳み込み符号では、軟判定復号の符号化利得は次のように見積もられます。
$$ G_{\text{coding}} \approx R \cdot d_{\text{free}} \quad \text{(dB単位ではなくSNR比として)} $$
漸近的なBER解析
AWGN通信路上でのビタビ復号のBERは、高SNR領域で次のように近似できます。
硬判定の場合:
$$ P_b \lesssim B_{d_{\text{free}}} \cdot \mathrm{erfc}\left(\sqrt{d_{\text{free}} R \cdot E_b/N_0}\right)^{d_{\text{free}}} $$
軟判定の場合:
$$ P_b \lesssim B_{d_{\text{free}}} \cdot \mathrm{erfc}\left(\sqrt{d_{\text{free}} R \cdot E_b/N_0}\right) $$
ここで $B_{d_{\text{free}}}$ は自由距離に対する転送関数の係数です。軟判定では $\mathrm{erfc}$ の指数が1（1重の誤り関数）であるのに対し、硬判定では $d_{\text{free}}$ 乗になっています。軟判定のほうがBERの減少が急峻であり、これが約2 dBの利得の原因です。
硬判定と軟判定の違いを理解したところで、Pythonで実装して性能を確認しましょう。
Pythonによる実装
畳み込み符号器とビタビ復号器
import numpy as np
import matplotlib.pyplot as plt
from scipy.special import erfc
np.random.seed(42)
class ConvolutionalCode:
"""(2, 1, 3) 畳み込み符号 — 生成多項式 (7, 5)"""
def __init__(self):
self.n_output = 2
self.K = 3
self.m = self.K - 1 # レジスタ段数
self.n_states = 2 ** self.m # 状態数
# 状態遷移テーブルと出力テーブルの構築
self.next_state = np.zeros((self.n_states, 2), dtype=int)
self.output = np.zeros((self.n_states, 2, self.n_output), dtype=int)
for state in range(self.n_states):
s1 = (state >> 1) & 1
s2 = state & 1
for u in range(2):
# 生成多項式 g1 = 7 (111): c1 = u XOR s1 XOR s2
c1 = u ^ s1 ^ s2
# 生成多項式 g2 = 5 (101): c2 = u XOR s2
c2 = u ^ s2
# 次の状態
new_state = (u << 1) | s1
self.next_state[state, u] = new_state
self.output[state, u] = [c1, c2]
def encode(self, data):
"""入力ビット列を符号化する（テールビット付き）"""
state = 0
coded = []
for bit in data:
out = self.output[state, bit]
coded.extend(out)
state = self.next_state[state, bit]
# テールビット: 状態を00に戻す
for _ in range(self.m):
out = self.output[state, 0]
coded.extend(out)
state = self.next_state[state, 0]
return np.array(coded, dtype=int)
def viterbi_hard(self, received):
"""硬判定ビタビ復号"""
n_steps = len(received) // self.n_output
INF = float('inf')
# パスメトリック
metrics = np.full(self.n_states, INF)
metrics[0] = 0.0
# 生き残りパスの記録
paths = {s: [] for s in range(self.n_states)}
for t in range(n_steps):
r = received[t * 2: (t + 1) * 2]
new_metrics = np.full(self.n_states, INF)
new_paths = {}
for state in range(self.n_states):
if metrics[state] == INF:
continue
for u in range(2):
ns = self.next_state[state, u]
out = self.output[state, u]
# ハミング距離
bm = np.sum(r != out)
total = metrics[state] + bm
if total < new_metrics[ns]:
new_metrics[ns] = total
new_paths[ns] = paths[state] + [u]
metrics = new_metrics
paths = new_paths
# テールビット後は状態00に収束
decoded = paths[0]
# テールビット分を除去
return np.array(decoded[:-(self.m)], dtype=int) if len(decoded) > self.m else np.array([], dtype=int)
def viterbi_soft(self, received_soft):
"""軟判定ビタビ復号（AWGN通信路用）"""
n_steps = len(received_soft) // self.n_output
INF = float('inf')
metrics = np.full(self.n_states, INF)
metrics[0] = 0.0
paths = {s: [] for s in range(self.n_states)}
for t in range(n_steps):
r = received_soft[t * 2: (t + 1) * 2]
new_metrics = np.full(self.n_states, INF)
new_paths = {}
for state in range(self.n_states):
if metrics[state] == INF:
continue
for u in range(2):
ns = self.next_state[state, u]
out = self.output[state, u]
# BPSK信号 (0 -> +1, 1 -> -1)
x = 1.0 - 2.0 * out
# ユークリッド距離の二乗（相関メトリックの符号反転）
bm = np.sum((r - x) ** 2)
total = metrics[state] + bm
if total < new_metrics[ns]:
new_metrics[ns] = total
new_paths[ns] = paths[state] + [u]
metrics = new_metrics
paths = new_paths
decoded = paths[0]
return np.array(decoded[:-(self.m)], dtype=int) if len(decoded) > self.m else np.array([], dtype=int)
上のコードでは、$(7, 5)$ 畳み込み符号の符号器と、硬判定・軟判定の両方のビタビ復号器を実装しています。符号器は状態遷移テーブルと出力テーブルを事前に構築し、符号化と復号を効率的に行います。軟判定復号では受信信号の実数値をそのまま使い、ユークリッド距離でブランチメトリックを計算している点に注目してください。
BER性能のシミュレーション
硬判定と軟判定のBER性能を比較します。
code = ConvolutionalCode()
data_len = 200
R = 0.5 # 符号化率
EbN0_dB_range = np.arange(0, 8.5, 0.5)
ber_uncoded = []
ber_hard = []
ber_soft = []
n_trials = 500
for EbN0_dB in EbN0_dB_range:
EbN0 = 10 ** (EbN0_dB / 10)
sigma = np.sqrt(1.0 / (2.0 * R * EbN0))
# 未符号化BER (理論値)
ber_uncoded.append(0.5 * erfc(np.sqrt(EbN0)))
err_hard = 0
err_soft = 0
total = 0
for _ in range(n_trials):
data = np.random.randint(0, 2, data_len)
coded = code.encode(data)
# BPSK変調
x = 1.0 - 2.0 * coded
# AWGN通信路
noise = sigma * np.random.randn(len(coded))
r_soft = x + noise
# 硬判定: 受信信号を0/1に量子化
r_hard = (r_soft < 0).astype(int)
# 硬判定ビタビ復号
decoded_hard = code.viterbi_hard(r_hard)
# 軟判定ビタビ復号
decoded_soft = code.viterbi_soft(r_soft)
min_len = min(data_len, len(decoded_hard), len(decoded_soft))
err_hard += np.sum(decoded_hard[:min_len] != data[:min_len])
err_soft += np.sum(decoded_soft[:min_len] != data[:min_len])
total += min_len
ber_hard.append(max(err_hard / total, 1e-7))
ber_soft.append(max(err_soft / total, 1e-7))
# プロット
fig, ax = plt.subplots(figsize=(8, 6))
ax.semilogy(EbN0_dB_range, ber_uncoded, 'k--', linewidth=1.5,
label='Uncoded BPSK (theory)')
ax.semilogy(EbN0_dB_range, ber_hard, 'bo-', markersize=4, linewidth=1.5,
label='Conv(7,5) + Viterbi (hard)')
ax.semilogy(EbN0_dB_range, ber_soft, 'rs-', markersize=4, linewidth=1.5,
label='Conv(7,5) + Viterbi (soft)')
ax.set_xlabel('$E_b/N_0$ [dB]')
ax.set_ylabel('Bit Error Rate')
ax.set_title('Convolutional Code (7,5) 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 = $10^{-4}$ では、硬判定で約3 dB、軟判定で約5 dBの利得が得られます。
- 軟判定利得: 軟判定復号は硬判定復号に対して約2 dBの利得を持ちます。これは理論的に予測される値とよく一致しています。受信信号の実数値（信頼度情報）を量子化せずに活用することの効果が明確に現れています。
- BER曲線の傾き: SNRの増加に対するBERの減少は、未符号化の場合よりも急峻です。これは自由距離 $d_{\text{free}} = 5$ による誤り訂正の効果です。
トレリス図の可視化
ビタビアルゴリズムの動作を視覚的に理解するために、トレリス図と生き残りパスを可視化します。
def visualize_trellis(code, data, received_hard, n_show=8):
"""トレリス図とビタビ復号の生き残りパスの可視化"""
n_steps = min(n_show, len(data) + code.m)
coded = code.encode(data[:n_show - code.m]) if n_show > code.m else code.encode(data[:1])
fig, ax = plt.subplots(figsize=(14, 4))
state_labels = ['00', '01', '10', '11']
state_y = {0: 3, 1: 2, 2: 1, 3: 0} # y座標
# トレリスの全枝を薄く描画
for t in range(n_steps):
for state in range(code.n_states):
for u in range(2):
ns = code.next_state[state, u]
out = code.output[state, u]
color = 'lightblue' if u == 0 else 'lightsalmon'
ls = '-' if u == 0 else '--'
ax.plot([t, t + 1], [state_y[state], state_y[ns]],
color=color, linestyle=ls, linewidth=0.8, alpha=0.4)
# 正しいパスを太く描画
state = 0
full_data = list(data[:n_show - code.m]) + [0] * code.m
for t in range(n_steps):
u = full_data[t] if t < len(full_data) else 0
ns = code.next_state[state, u]
ax.plot([t, t + 1], [state_y[state], state_y[ns]],
'g-', linewidth=3, alpha=0.7)
state = ns
# ノードの描画
for t in range(n_steps + 1):
for s in range(code.n_states):
ax.plot(t, state_y[s], 'ko', markersize=8)
# ラベル
for s in range(code.n_states):
ax.text(-0.3, state_y[s], state_labels[s], ha='right', va='center',
fontsize=10, fontweight='bold')
ax.set_xlabel('Time step')
ax.set_ylabel('State')
ax.set_title('Trellis Diagram with Correct Path (green)')
ax.set_xlim(-0.5, n_steps + 0.5)
ax.set_ylim(-0.5, 3.5)
ax.set_yticks([])
ax.grid(True, alpha=0.2)
plt.tight_layout()
plt.show()
# 短い例でトレリス図を可視化
data_short = np.array([1, 0, 1, 1, 0, 1])
coded_short = code.encode(data_short)
noise_short = 0.5 * np.random.randn(len(coded_short))
r_short = (1.0 - 2.0 * coded_short) + noise_short
r_hard_short = (r_short < 0).astype(int)
visualize_trellis(code, data_short, r_hard_short, n_show=8)
トレリス図では、4つの状態が縦に、時間ステップが横に展開されています。緑の太い線が送信された正しいパスを示しています。薄い青の実線は入力0の遷移、薄い赤の破線は入力1の遷移です。ビタビアルゴリズムは、この中から受信信号に最も近いパスを見つけ出す動的計画法であることが視覚的に理解できます。
パンクチャリングによる符号化率の調整
実用的な通信システムでは、通信路の品質に応じて符号化率を柔軟に変える必要があります。畳み込み符号の符号化率を変えるたびに異なる符号器と復号器を設計するのは非効率的です。
パンクチャリング（puncturing）は、低符号化率の畳み込み符号の出力ビットの一部を規則的に削除（パンクチャ）することで、符号化率を引き上げる手法です。たとえば、$R = 1/2$ の畳み込み符号の出力から一定の規則で一部のビットを間引くことで、$R = 2/3$, $R = 3/4$ などの高符号化率を実現できます。
パンクチャリングパターンはパンクチャリング行列 $\bm{P}$ で指定します。たとえば、符号化率 $1/2$ を $2/3$ に引き上げるパンクチャリング行列は
$$ \bm{P} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} $$
です。行は出力（$c^{(1)}$, $c^{(2)}$）、列は時刻に対応し、1は送信、0は削除を意味します。2時刻分の入力2ビットに対して出力4ビットのうち3ビットを送信するため、符号化率は $2/3$ になります。
復号器側では、パンクチャされたビット位置に「消失」（erasure）を挿入し、信頼度0（軟判定値0）として扱います。ビタビアルゴリズムの構造はそのまま使えるため、復号器の変更は最小限で済みます。
パンクチャリングは自由距離を減少させるため、誤り訂正能力は低下しますが、符号化率の上昇によるスペクトル効率の向上との兼ね合いで、実用上有用な手法です。
まとめ
本記事では、畳み込み符号とビタビ復号の理論を解説しました。
- 畳み込み符号の構造: シフトレジスタによる「記憶」を持つ符号化であり、入力の時間的な関係を利用してブロック符号よりも強力な誤り訂正を実現する。構造は生成多項式で簡潔に記述される
- トレリス図: 符号器の状態遷移を時間方向に展開した図であり、符号語列とトレリス上のパスが一対一に対応する。復号アルゴリズムの基盤となる表現
- 自由距離: 畳み込み符号の誤り訂正能力を決定する中心的なパラメータ。拘束長 $K$ が大きいほど自由距離は増加するが、復号の計算量も指数的に増加する
- ビタビアルゴリズム: 動的計画法に基づく最尤復号。各時刻で各状態の生き残りパスのみを追跡することで、計算量を系列長に対して線形に抑える
- 軟判定利得: 受信信号の信頼度情報を活用する軟判定復号は、硬判定復号に対して約2 dBの利得を持つ
畳み込み符号とビタビ復号は、現代の通信システムの基盤技術として広く使われ続けています。
次のステップとして、以下の記事も参考にしてください。
- ターボ符号の理論 — 反復復号と性能限界 — 畳み込み符号を構成要素とした、シャノン限界に迫る符号
- LDPC符号の理論 — スパースグラフ符号 — グラフ構造に基づく別のアプローチ
- 線形符号の理論 — 生成行列と検査行列 — ブロック符号の基礎との比較