畳み込み符号とビタビ復号 — 冗長ビットで誤りを訂正する符号化利得

この回で学ぶこと

これまでの回では、BPSKのビット誤り率 $P_b = Q(\sqrt{2E_b/N_0})$ や、それを最尤推定として導く検出理論など、「与えられた変調方式に、冗長性を一切足さずにビットをそのまま乗せたらどうなるか」という**無符号化(uncoded)**の世界だけを扱ってきました。一方シャノンの通信路容量定理では、伝送レート $R$ が通信路容量 $C$ を下回りさえすれば、「符号化の工夫」だけで誤り率をいくらでも小さくできることを見ました。この回はその「符号化の工夫」に初めて踏み込みます。

具体的に扱うのは 畳み込み符号 (convolutional code) と、それを最尤復号する ビタビアルゴリズム (Viterbi algorithm) です。畳み込み符号は、情報ビットにあえて冗長なビットを追加してから送信し、受信側でその冗長性を使って誤りを検出・訂正する仕組みです。そして冗長ビットを追加すると当然データレートは落ちる(あるいは帯域が広がる)わけですが、その代わりに同じ誤り率を達成するのに必要な $E_b/N_0$ を大きく下げられる。この「必要な $E_b/N_0$ の低減量」を 符号化利得 (coding gain) と呼びます。

畳み込み符号とビタビ復号は、1970年代のボイジャー計画以来、深宇宙通信における誤り訂正符号の事実上の出発点であり、今日でもCCSDS標準に規定され続けている、極めて息の長い技術です。この回では、符号器の構成、状態遷移とトレリス線図による可視化、そしてビタビ復号を「動的計画法による最尤系列推定」として導出し、最後に自由距離という指標からBERの上界と符号化利得を数式で評価します。

なぜ冗長ビットが誤りを訂正できるのか

まず直感をつかむために、極端に単純な例から始めましょう。1ビットの情報 $b \in \{0,1\}$ を3回繰り返して送る繰り返し符号を考えます。送信系列は $b,b,b$ の3ビット、BSC(二元対称通信路、ビット反転確率 $p$)を通ると、受信側は多数決で $b$ を推定できます。3ビットのうち2ビット以上反転しなければ誤りは起きないので、誤り率は

$$P_{\text{block}} = \binom{3}{2}p^2(1-p) + \binom{3}{3}p^3 = 3p^2 - 2p^3$$

$p$ が十分小さければ $P_{\text{block}} \approx 3p^2 \ll p$ となり、無符号化の誤り率 $p$ より劇的に改善します。ただし代償として、同じ情報量を送るのに3倍の時間(あるいは3倍の帯域)がかかる。符号化率でいえば $R_c = 1/3$ です。

繰り返し符号は最も単純な誤り訂正符号ですが、冗長ビットの使い方として非効率です。同じ符号化率でも、冗長ビットの生成方法を工夫すれば、もっと強力な誤り訂正能力を引き出せます。畳み込み符号は、単純にビットをコピーするのではなく、現在の入力ビットと過去数ビットの入力の**線形結合(モジュロ2和)**を出力することで、1つの出力ビットに複数の情報ビットの痕跡を畳み込みます。この「時間的に広がった依存関係」こそが、ビタビ復号によって効率よく解読できる構造を持ちながら、繰り返し符号よりはるかに強い誤り訂正能力を生み出す鍵になります。

畳み込み符号器の構成

畳み込み符号器は、$k$ 個の入力ビットに対して $n$ 個の出力ビットを生成する回路で、符号化率は

$$R_c = \frac{k}{n}$$

と定義されます。以下では最も基本的な $k=1, n=2$ の場合(符号化率 $R_c = 1/2$)を例に、$K$ 段のシフトレジスタで構成される符号器を考えます。$K$ は**拘束長(constraint length)**と呼ばれ、「1つの出力ビットが何ビット分の入力履歴に依存するか」を表します。

具体例として、拘束長 $K=3$ のシフトレジスタを考えましょう。時刻 $k$ の入力ビットを $u_k$、シフトレジスタに保持されている過去の入力を $u_{k-1}, u_{k-2}$ とすると、2つの出力ビットはそれぞれの**生成多項式(generator polynomial)**が指定するタップの位置でモジュロ2和を取って作られます。

$$v_k^{(1)} = u_k \oplus u_{k-1} \oplus u_{k-2}, \qquad v_k^{(2)} = u_k \oplus u_{k-2}$$

($\oplus$ はモジュロ2加算、すなわちXORです。)これを遅延演算子 $D$(1時刻分の遅延を表す形式変数)を使った多項式表記で書くと、生成多項式は

$$g_1(D) = 1 + D + D^2, \qquad g_2(D) = 1 + D^2$$

であり、入力系列の母関数を $U(D) = \sum_k u_k D^k$ とすれば、出力系列はGF(2)上の多項式の積として

$$V^{(1)}(D) = U(D)\, g_1(D), \qquad V^{(2)}(D) = U(D)\, g_2(D)$$

と表せます。「畳み込み」符号という名前は、まさにこの演算が(モジュロ2の)畳み込み積分そのものであることに由来します。実務では生成多項式は8進数(オクタル)表記で書かれることが多く、$g_1(D)=1+D+D^2$ はタップ係数 $(1,1,1)$ を2進数として読んで8進数に直すと $7_8$、$g_2(D)=1+D^2$ はタップ係数 $(1,0,1)$ で $5_8$ となるため、この符号はしばしば「(7,5)符号」と呼ばれます。

出力される2ビット $(v_k^{(1)}, v_k^{(2)})$ は、送信時にはインターリーブ(交互配置)されて $v_k^{(1)}, v_k^{(2)}, v_{k+1}^{(1)}, v_{k+1}^{(2)}, \ldots$ という1つのビット列としてPSK変調器に渡されます。これがこれまでの回で扱ってきたPCM/PSK/PMのビット列 $\{b_k\}$ の正体、つまり畳み込み符号化後のビット列であるという位置づけです。

状態と状態遷移図

拘束長 $K$ の符号器の「内部状態」は、シフトレジスタに保持されている過去 $K-1$ ビットの入力履歴で決まります。今回の例($K=3$)では、状態は

$$s_k = (u_{k-1}, u_{k-2}) \in \{00, 01, 10, 11\}$$

の4通りです(一般に状態数は $2^{K-1}$)。時刻 $k$ に新しい入力 $u_k$ が来ると、出力 $(v_k^{(1)}, v_k^{(2)})$ が確定すると同時に、状態は

$$s_{k+1} = (u_k, u_{k-1})$$

に遷移します。つまり畳み込み符号器は、入力ビット列によって状態が遷移していく有限状態機械(オートマトン)であり、各遷移に出力ビットのラベルが付いた状態遷移図として描けます。先ほどの $(7,5)$ 符号について、全4状態・各状態からの2通りの遷移(入力0または1)を書き下すと次のようになります。

現在の状態 $(u_{k-1},u_{k-2})$	入力 $u_k$	出力 $(v^{(1)},v^{(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)**の方が扱いやすくなります。トレリスでは、時刻 $k=0,1,2,\ldots$ ごとに $2^{K-1}$ 個の状態ノードを縦に並べ、上の表で定義した遷移を、時刻 $k$ のノードから時刻 $k+1$ のノードへの枝(ブランチ)として描きます。各枝には対応する出力ビット対がラベルとして付き、慣習として入力0の枝は実線、入力1の枝は破線で描かれます。

符号器は通常、送信開始時にシフトレジスタをオール0にリセットしておく(状態00からスタートする)ため、時刻0では状態00のみが存在し、時刻が進むにつれて枝分かれしながら $2^{K-1}$ 個の状態すべてに到達し、以降は定常的な格子構造(トレリス)が時間方向に繰り返されます。1つの入力系列 $u_0, u_1, \ldots, u_{N-1}$ は、このトレリス上で状態00から始まる1本のパス(経路)に1対1で対応し、そのパスに沿って読んだ枝ラベルの並びが符号化出力系列そのものになります。

ビタビ復号アルゴリズム: 動的計画法としての最尤系列推定

受信側の仕事は、雑音の乗った受信系列 $r_0, r_1, \ldots$ から、送信された入力系列 $u_0, u_1, \ldots$ を推定することです。検出理論の回で見た通り、AWGN通信路・等確率事前分布のもとでの最適な推定は最尤系列推定(MLSE: Maximum Likelihood Sequence Estimation)、すなわち送信され得るすべての系列の中から、受信系列との距離(尤度)が最も近いものを選ぶことです。

問題は、長さ $N$ の入力系列に対して候補となる符号語系列が $2^N$ 通り存在することです。すべてを愚直に比較すると計算量が入力長に対して指数的に爆発してしまい、実用的な系列長(数百〜数千ビット)ではとても計算できません。ここで威力を発揮するのがビタビアルゴリズムで、これはトレリス構造が持つ「部分問題の最適性」を利用した**動的計画法(DP)**にほかなりません。

ブランチメトリックとパスメトリック

トレリス上の1本のパスの「良さ」を測る指標として、各枝(ブランチ)に対するブランチメトリック $\lambda(s' \to s)$ を定義します。ハード判定(受信ビットを一旦0/1に判定してから復号する方式)の場合、ブランチメトリックは受信ビット対と枝ラベルとのハミング距離

$$\lambda_k(s' \to s) = d_H\big((r_k^{(1)}, r_k^{(2)}),\ (v^{(1)}_{s'\to s}, v^{(2)}_{s'\to s})\big)$$

で与えられ、BSC通信路のもとでは、ハミング距離が最小になる経路がまさに最尤系列に一致します(これは検出理論の回で見た「最も近い信号点を選ぶことがML判定である」という議論の、系列版にあたります)。ソフト判定(受信信号の振幅情報をそのまま使う方式)の場合は、BPSKマッピング後の受信サンプルと枝ラベルとの相関(あるいはユークリッド距離)をメトリックに使い、こちらはハード判定よりおよそ2 dB程度優れた性能を示すことが知られています(詳細は実務での使われ方を参照)。

時刻0から時刻 $k$ までの1本のパス全体の良さは、そのパスが通った各ブランチのメトリックの総和であるパスメトリック

$$\Gamma_k(s) = \sum_{i=0}^{k-1} \lambda_i(s_i \to s_{i+1})$$

で測られ、ハード判定の場合、最尤系列は $\Gamma_N(s)$ を最小にするパス(ハミング距離の総和が最小のパス)です。

動的計画法による効率化: Add-Compare-Select

ここでベルマンの最適性原理(Bellman’s principle of optimality)を使います。「時刻0から時刻 $k$ まで状態 $s$ に至る大局的な最尤パスの一部分は、それ自身が時刻0から時刻 $k$ で状態 $s$ に至る局所的な最小パスメトリックのパスでなければならない」という単純な事実です。なぜなら、もしその部分パスより小さいパスメトリックで状態 $s$ に至る別の部分パスが存在すれば、それに乗り換えることで全体のパスメトリックをさらに小さくできてしまうからです。

この原理により、時刻 $k$ の各状態 $s$ について、そこに至るすべての部分パスを保持する必要はなく、パスメトリックが最小の1本(生き残りパス, survivor path)だけを覚えておけば十分だと分かります。これにより、次の漸化式で逐次的にパスメトリックを更新できます。

$$\Gamma_{k+1}(s) = \min_{s' : s' \to s} \Big[\, \Gamma_k(s') + \lambda_k(s' \to s) \,\Big]$$

この更新は、実装上は3つのステップの繰り返しとして知られています。

1. Add(加算): 各状態 $s$ に合流し得るすべての枝(通常2本)について、合流元のパスメトリック $\Gamma_k(s')$ とブランチメトリック $\lambda_k(s'\to s)$ を加算する。
2. Compare(比較): 合流する複数(通常2本)の候補値を比較する。
3. Select(選択): 最小値を与える方を新しいパスメトリック $\Gamma_{k+1}(s)$ として採用し、その合流元の状態を「生き残りパス」のポインタとして記録し、負けた方の部分パスは以後の探索から完全に捨てる。

これを**ACS演算(Add-Compare-Select)**と呼びます。各時刻において、状態数 $2^{K-1}$ 個それぞれについてこのACS演算を行うだけでよいため、系列長 $N$ に対する計算量は $O(N \cdot 2^{K-1})$ となり、愚直な全数探索の $O(2^N)$ から指数的に削減されます。これがビタビアルゴリズムの本質です。

トレースバック

系列の終端(あるいは十分な時間が経過した時点)まで生き残りパスの更新を続けたら、最終的にパスメトリックが最小の状態を選び、そこから記録しておいた生き残りパスのポインタを時間を遡ってたどる(トレースバック, traceback)ことで、最尤入力系列を復元します。実際の系統では、符号器の末尾に $K-1$ ビットの既知の「テールビット」(通常オール0)を付加して、必ず状態00に強制終端させることでトレースバックの終点を明確にする設計がよく使われます(この分だけわずかに実効符号化率が下がりますが、系列長が十分長ければ無視できる程度です)。また無限に系列を遡ってメモリを消費しないよう、実装上はトレースバック長を拘束長の5倍程度($5K$〜$6K$)に打ち切っても、実用上ほぼ最適解と変わらない性能が得られることが経験的に知られています。

自由距離とビット誤り率の上界

畳み込み符号の誤り訂正性能を特徴づける最も重要な量が 自由距離 (free distance) $d_{free}$ です。これは、全0系列(正解パス)から一度分岐し、後で再びトレリス上で合流する、すべての「誤りパス」の出力系列のハミング重みの最小値として定義されます。

$$d_{free} = \min_{\substack{u \neq 0 \\ u \text{ が有限重み}}} w_H\big(\, \text{Enc}(u) \,\big)$$

先ほどの $(7,5)$ 符号で具体的に確認してみましょう。状態00から入力系列 $u = (1,0,0,\ldots)$ を与えると、トレリス上のパスは

$$00 \xrightarrow[\;11\;]{u=1} 10 \xrightarrow[\;10\;]{u=0} 01 \xrightarrow[\;11\;]{u=0} 00$$

と状態00に戻ってきます(出力の重みはそれぞれ2, 1, 2)。この誤りパス全体の出力重みは $2+1+2=5$ で、これが $(7,5)$ 符号における最小重みの誤りパスであることが知られており、したがって $d_{free}=5$ です。

自由距離が重要なのは、これが復号誤りの起きやすさを直接支配するからです。正解パスと自由距離だけ離れた誤りパスにビタビ復号が誤って乗り換えてしまう確率(ペアワイズ誤り確率)は、ソフト判定・BPSK・AWGN通信路のもとで

$$P_2(d) = Q\!\left(\sqrt{2\, R_c\, d\, \frac{E_b}{N_0}}\right)$$

で与えられます。トレリス上には自由距離以上の重みを持つ誤りパスが(重み $d$ ごとに一定の個数)無数に存在するため、これらすべてを合算する**ユニオン限界(union bound)**によって、ビット誤り率の上界は

$$P_b \;\lesssim\; \sum_{d=d_{free}}^{\infty} \beta_d\, Q\!\left(\sqrt{2\, R_c\, d\, \frac{E_b}{N_0}}\right)$$

と評価できます。ここで $\beta_d$ は、重み $d$ の誤りパスすべてについて、それが引き起こす情報ビットの誤り数を数え上げた係数で、符号器の状態遷移図から信号流グラフ(Masonのゲイン公式)を使って解析的に求められる重み分布(weight enumerating function)から導出されます。$E_b/N_0$ が高いレジームでは指数関数的に減衰するQ関数の性質上、和の中で $d=d_{free}$ の項が支配的になり、近似的に

$$P_b \approx \beta_{d_{free}}\, Q\!\left(\sqrt{2\, R_c\, d_{free}\, \frac{E_b}{N_0}}\right)$$

とみなせます。無符号化BPSKのビット誤り率 $P_b = Q(\sqrt{2E_b/N_0})$ と見比べると、Q関数の引数の中で実効的な $E_b/N_0$ が $R_c\, d_{free}$ 倍されていることが分かります。これは「同じビット誤り率を達成するのに必要な $E_b/N_0$ が、符号化によって $R_c\, d_{free}$ 分の一で済む」ことを意味し、これをdBに直したものが**漸近符号化利得(asymptotic coding gain)**です。

$$G_a \;[\text{dB}] = 10\log_{10}\big(R_c\, d_{free}\big)$$

先ほどの $(7,5)$ 符号($R_c=1/2$, $d_{free}=5$)であれば、

$$G_a = 10\log_{10}(0.5 \times 5) = 10\log_{10}(2.5) \approx 3.98\ \text{dB}$$

と計算できます。ただし、この値はあくまで $E_b/N_0$ が十分大きい漸近的な極限での上界であり、実際の運用点(たとえば目標ビット誤り率 $10^{-5}$付近)では、和の中の $d>d_{free}$ の項の寄与が無視できず、ユニオン限界自体もやや緩いため、実測される符号化利得はこれよりいくらか小さくなる点には注意が必要です。

実務での使われ方

畳み込み符号とビタビ復号は、深宇宙通信における誤り訂正符号の歴史の出発点です。1977年に打ち上げられたボイジャー1号・2号は、拘束長 $K=7$、符号化率 $R_c=1/2$ の畳み込み符号(生成多項式は8進数表記で $g_1 = 171_8$, $g_2 = 133_8$、自由距離 $d_{free}=10$)を搭載し、これは今日でも「NASA標準畳み込み符号」として広く知られています。$K=7$ なので状態数は $2^6=64$ となり、地上局のビタビ復号器は64状態のトレリス全体でACS演算を毎シンボル実行し続けます。

この符号の漸近符号化利得は

$$G_a = 10\log_{10}(0.5 \times 10) = 10\log_{10}(5) \approx 6.99\ \text{dB}$$

と計算されますが、実際の運用でよく引用される値は、目標ビット誤り率 $10^{-5}$付近でソフト判定ビタビ復号を用いた場合でおよそ5 dB前後です。漸近値との差は、前節で触れた通りユニオン限界が中程度のSNRでは緩いことに起因します。それでも「送信電力(あるいはアンテナ口径)を変えずに5 dB近い符号化利得を得る」ことのインパクトは絶大で、同じ受信 $E_b/N_0$ でデータレートを数倍に引き上げられることを意味します。ハード判定復号(受信ビットを一旦0/1に丸めてからビタビ復号する方式)はこれより2 dB程度性能が劣るため、実際の深宇宙受信機では受信サンプルの振幅情報をそのまま使うソフト判定ビタビ復号が標準的に採用されています。

この $(K=7, R_c=1/2)$ 畳み込み符号は、CCSDSの標準にも規定されており(伝統的には CCSDS 101.0-B Telemetry Channel Coding、現行では CCSDS 131.0-B TM Synchronization and Channel Coding に統合)、さらにこれとリード・ソロモン符号を組み合わせた「連接符号(concatenated code、いわゆるOdenwalder連接符号)」も同時に標準化されました。畳み込み符号は単発のビット誤りには強い一方、ビタビ復号が誤った経路に乗り換えると出力にバースト状の誤りが発生しやすいという弱点があり、この弱点を外側のリード・ソロモン符号(バースト誤りの訂正を得意とする)で補うのが連接符号の設計思想です。この組み合わせは、シャノン限界の回でも触れた通り、1990年代のターボ符号・LDPC符号の登場までの約20年間、深宇宙通信における誤り訂正の事実上の標準であり続けました。

畳み込み符号化率 $R_c=1/2$ は、そのまま使うと元のデータレートを半分にしてしまいますが、実務では**パンクチャリング(puncturing)**と呼ばれる技法で、あらかじめ決められたパターンに従って出力ビットの一部を規則的に間引くことで、$R_c=2/3, 3/4, 7/8$ といった、より高い実効符号化率を同じ64状態の符号器・復号器のまま作り出す設計もCCSDS標準に含まれています。これにより、リンクの $E_b/N_0$ に余裕があるパス(たとえば地球に近い運用フェーズ)ではより高いデータレートを、余裕のないパス(外惑星探査など)ではより強い誤り訂正能力を、同じハードウェアで柔軟に選択できます。

演習問題

1. 生成多項式 $g_1(D) = 1+D+D^2$, $g_2(D) = 1+D^2$ の $(7,5)$ 畳み込み符号器に、入力系列 $u = (1,1,0,1)$(その後は0が続くとする)を与えたとき、出力される符号化ビット列を、本文の状態遷移表を使って時刻ごとに求めてください。
2. 本文中の状態遷移表を使って、状態00から出発し状態00に戻ってくる誤りパスのうち、出力重みが本文で示した $d_{free}=5$ のパス(入力 $1,0,0$)以外に、重み5または6の別の誤りパスが存在するか探してみてください(トレリスを2〜4ステップ先まで手で展開して探索すること)。
3. CCSDSのNASA標準畳み込み符号($K=7$, $R_c=1/2$, $d_{free}=10$)について、漸近符号化利得 $G_a = 10\log_{10}(R_c\, d_{free})$ をdBで計算し、本文中に挙げた実測値(約5 dB)との差がなぜ生じるのかを、ユニオン限界の性質に触れながら説明してください。
4. なぜビタビ復号は、系列長 $N$ に対して指数的な計算量 $O(2^N)$ を要する全数探索を、線形な計算量 $O(N \cdot 2^{K-1})$ にまで削減できるのか、本文で述べたベルマンの最適性原理とAdd-Compare-Select演算の役割に触れながら、自分の言葉で説明してください。

まとめと次回予告

畳み込み符号は、シフトレジスタと生成多項式によって現在の入力と過去の入力履歴を線形結合し、冗長な出力ビットに畳み込む符号化方式です。その構造は状態遷移図・トレリス線図として可視化でき、ビタビアルゴリズムはこのトレリス上でベルマンの最適性原理に基づくAdd-Compare-Select演算を繰り返す動的計画法として、最尤系列推定を効率的に実現します。そして自由距離 $d_{free}$ とユニオン限界から導かれる符号化利得 $G_a = 10\log_{10}(R_c\, d_{free})$ という式が、「冗長ビットを足すことでどれだけ $E_b/N_0$ の要求を下げられるか」を定量的に結び付けています。ボイジャー以来の深宇宙通信は、この畳み込み符号とビタビ復号の組み合わせによって、送信電力を増やすことなく通信性能を大きく引き上げてきました。

次回は、畳み込み符号がバースト状の誤りに弱いという弱点を補うために連接されたリード・ソロモン符号を扱います。有限体(ガロア体)上の代数的な構造を使ってシンボル単位の誤りを訂正するこの符号が、畳み込み符号とどう組み合わさって「連接符号」という強力な誤り訂正システムを作り上げるのかを見ていきます。

参考文献

• A. J. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm,” IEEE Transactions on Information Theory, 1967
• J. G. Proakis, M. Salehi, Digital Communications, 5th ed., McGraw-Hill (Convolutional Codes and Viterbi Decoding の章)
• B. Sklar, Digital Communications: Fundamentals and Applications, 2nd ed., Prentice Hall
• CCSDS 131.0-B, TM Synchronization and Channel Coding
• J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76