変調・符号化#25

ターボ符号 — 並列連接畳み込み符号と反復復号でシャノン限界に迫る

1993年にBerrouらが発表し符号化理論に衝撃を与えたターボ符号。2つの再帰的組織畳み込み符号器(RSC)をインターリーバで並列連接し、対数尤度比(LLR)による外部情報の交換とBCJR(MAP)アルゴリズムで反復的に復号することで、なぜシャノン限界からわずか1dB足らずまで迫れるのかを数式で理解する。

前提知識: convolutional-viterbi

ターボ符号反復復号BCJRアルゴリズムCCSDS誤り訂正符号

この回で学ぶこと

前回、畳み込み符号とその最尤復号アルゴリズムであるViterbiアルゴリズムを学びました。深宇宙通信の歴史では、この畳み込み符号を単独で使うだけでなく、外側にReed-Solomon符号を置き、内側に畳み込み符号を置いて**直列に連接(serial concatenation)**する方式が長く標準でした。ボイジャーやガリレオが使った RS(255,223) + 畳み込み符号(拘束長7、符号化率1/2)の組み合わせがその代表例です。この直列連接符号は、Viterbi復号が出しやすい「バースト的な誤り」をインターリーブとRS符号の強力なバースト誤り訂正能力で後始末する、という一方向の情報の流れ(内側→外側)に基づいています。

1993年、Claude Berrou、Alain Glavieux、Punya Thitimajshimaの3人がICC(IEEE International Conference on Communications)で発表した論文 “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes” は、この常識を覆しました。彼らが提案したのは、2つの畳み込み符号器を直列ではなく並列に連接し、しかも復号側で2つの復号器が互いの推定結果を反復的に交換し合うという、まったく新しい発想の符号でした。その性能は衝撃的で、符号化率1/2、情報ブロック長 $N=65536$ ビットのターボ符号は、ビット誤り率 $10^{-5}$ を達成するのに $E_b/N_0 \approx 0.7$ dB しか必要とせず、これは同じ符号化率でのシャノン限界(理論上0 dB付近)からわずか0.7 dBという、当時の符号化理論の常識(直列連接符号でシャノン限界から3〜4 dB程度が精一杯とされていた)を根底から覆す結果でした。この一撃で、符号化理論の研究の中心は「良い符号語をどう設計するか」から「反復的に情報を交換しながらどう賢く復号するか」へと大きく舵を切ることになります。

この回では、ターボ符号を構成する並列連接畳み込み符号(PCCC: Parallel Concatenated Convolutional Code)の仕組み、2つの復号器が対数尤度比(LLR)を交換しながら推定を改善していく反復復号(iterative decoding)の原理、そしてその心臓部であるBCJRアルゴリズム(MAP復号)の考え方を、数式を追いながら理解します。あわせて、実務上避けて通れないターボクリフとエラーフロアという2つの性能特性、そしてCCSDS標準ターボ符号の実装と、それが後にLDPC符号へ置き換えられていった理由も見ていきます。

直感的な全体像 — 「並列」と「反復」という2つの発想の転換

直列連接符号とターボ符号(並列連接符号)の違いを、まず図式的に捉えましょう。

直列連接符号では、情報ビット列 $\mathbf{u}$ がまずRS符号器を通り、その出力がさらに畳み込み符号器を通ります。復号側では、受信信号をまずViterbi復号器にかけ、その出力(まだ誤りが残っている)をRS復号器に渡して最終訂正する、という一方向のパイプラインです。

ターボ符号のPCCC構成はまったく発想が異なります。

同じ情報ビット列 $\mathbf{u} = (u_1, u_2, \dots, u_N)$ を、そのままの順序で1つ目の再帰的組織畳み込み符号器(RSC1)に通し、パリティ系列 $\mathbf{p}^{(1)}$ を得ます。
同じ情報ビット列 $\mathbf{u}$ を、インターリーバ $\pi$ でビット順序をランダムにかき混ぜてから、2つ目の再帰的組織畳み込み符号器(RSC2)に通し、パリティ系列 $\mathbf{p}^{(2)}$ を得ます。
送信するのは、系統(systematic)ビット $\mathbf{u}$ 、パリティ $\mathbf{p}^{(1)}$ 、パリティ $\mathbf{p}^{(2)}$ の3つを組み合わせたものです。

つまり同じ情報を、異なる並び順で2回、独立に畳み込み符号化するというのがPCCCの本質です。この「並列」構成が持つ意味は、復号側で初めて明らかになります。RSC1のパリティから見て「怪しい」と判定されたビット位置が、インターリーバでかき混ぜられた後のRSC2のパリティからは「怪しくない」と判定されることがあります。なぜなら、ある符号器にとって区別しづらい(低重み誤りを生みやすい)入力パターンが、インターリーバによってビット順序が入れ替わった別の符号器にとっても同様に区別しづらいパターンになる確率は、インターリーバが情報ビット列を十分にランダム化していれば非常に低いからです。この「片方の弱点をもう片方が補う」性質こそが、並列連接符号がシャノン限界に迫れる本質的な理由です。

そして復号側では、この構造を活かして2つの復号器が互いの出力を交換しながら反復的に精度を上げていくという仕組みが使われます。これが「ターボ」の名前の由来で、ターボチャージャーが排気ガス(エンジンの「出力」)を吸気側に戻して燃焼効率を上げるのと同じように、ターボ復号器は一方の復号器の出力を他方の復号器の入力として再利用し、それを繰り返すことで全体の推定精度を高めていきます。

構成要素1: 再帰的組織畳み込み符号器 (RSC)

ターボ符号の構成符号(constituent code)には、普通の畳み込み符号ではなく再帰的組織畳み込み符号 (RSC: Recursive Systematic Convolutional code) が使われます。「組織的(systematic)」とは入力ビットがそのまま出力の一部として現れること、「再帰的(recursive)」とは出力の一部が符号器内部にフィードバックされることを意味します。

教科書でよく使われる、拘束長3(記憶長 $m=2$ 、4状態)のRSC符号器を例にとりましょう。生成多項式を八進数表記で $(g_0, g_1) = (7, 5)$ とすると、 $g_0(D) = 1 + D + D^2$ (フィードバック側)、 $g_1(D) = 1 + D^2$ (パリティ出力側)です。2つの記憶素子の内容を $m_k^{(1)}, m_k^{(2)}$ とすると、動作は次の3本の式で表せます。

a_k = u_k \oplus m_k^{(1)} \oplus m_k^{(2)} \qquad \text{(フィードバック信号)}

m_{k+1}^{(1)} = a_k, \qquad m_{k+1}^{(2)} = m_k^{(1)} \qquad \text{(シフトレジスタ更新)}

x_k = u_k \ (\text{系統出力}), \qquad p_k = a_k \oplus m_k^{(2)} \ (\text{パリティ出力})

普通の(非再帰的な)畳み込み符号との決定的な違いは、 $a_k$ が単なる入力 $u_k$ ではなく、状態にフィードバックされた値だという点です。この結果、状態遷移図(トレリス)は非再帰的な符号と同じ形をしていますが、**入力ビット系列と出力符号語の対応関係が非線形的に「絡み合う」**という重要な性質を持ちます。特に、全ビットが1という無限長の入力(あるいはインターリーバを介した特定の入力パターン)に対して出力の重みが小さくなる、という現象が起きにくくなり、これが後述する反復復号の収束特性やエラーフロアの議論に効いてきます。

一般に、拘束長 $\nu$ (記憶長 $m=\nu-1$ )のRSC符号器は $2^m$ 個の状態を持つトレリスとして表現でき、次節のBCJRアルゴリズムはこのトレリス上で動作します。

構成要素2: インターリーバとPCCC全体の符号化率

PCCC全体の構成を整理すると、送信されるのは次の3つの系列です。

\mathbf{x} = \{x_k\}_{k=1}^N = \{u_k\}, \qquad \mathbf{p}^{(1)} = \{p_k^{(1)}\}, \qquad \mathbf{p}^{(2)} = \{p_k^{(2)}\}

系統ビット1つに対しパリティビットが2つ付くので、パンクチャリング(間引き)をしない「母符号(mother code)」の符号化率は

R_{\text{mother}} = \frac{1}{1+1+1} = \frac{1}{3}

です。実務ではこれをパンクチャリングして符号化率を上げます。たとえば $\mathbf{p}^{(1)}$ と $\mathbf{p}^{(2)}$ を1ビットおきに交互に間引く(奇数番目の情報ビットではRSC1のパリティだけを送り、偶数番目ではRSC2のパリティだけを送る)と、パリティビットの本数が実質半分になり、

R = \frac{1}{1 + 1/2 + 1/2} = \frac{1}{2}

の符号化率1/2のターボ符号が得られます。同様の考え方で、パリティをさらに強く間引けば1/2より高い符号化率(例: 2/3、3/4)を、逆にRSC1・RSC2からより多くのパリティビットを出力させれば1/3より低い符号化率(1/4、1/6など)を作ることができ、これがCCSDS標準ターボ符号が複数の符号化率をサポートしている理由です。

インターリーバ $\pi$ の設計もまた性能を大きく左右します。単純な行列型(ブロック)インターリーバでも動作はしますが、実用のターボ符号では、隣接するビットが極端に近い位置に再配置されない(最小距離が保証される)よう設計された擬似ランダムインターリーバや、行列型と乱数を組み合わせたインターリーバが好んで使われます。インターリーバ長 $N$ が大きいほど、統計的に「RSC1とRSC2が同時に苦手とする入力パターン」が起きにくくなり、性能(特に後述するターボクリフの位置)が改善しますが、その代償として復号に必要なブロック長・遅延が増大するというトレードオフが生じます。

反復復号の原理 — 対数尤度比と外部情報の交換

復号側の構成は、送信側のPCCCを鏡写しにしたような形をしています。受信信号から、系統ビットの尤度 $\mathbf{y}^s$ 、RSC1のパリティの尤度 $\mathbf{y}^{p_1}$ 、RSC2のパリティの尤度 $\mathbf{y}^{p_2}$ (こちらはインターリーブされた順序に対応)が得られます。これらをもとに、2つのソフト入力・ソフト出力(SISO)復号器 DEC1、DEC2 が交互に動作します。

議論の基本単位は対数尤度比 (LLR: Log-Likelihood Ratio) です。ビット $u_k$ に関するLLRを

L(u_k) \equiv \ln \frac{P(u_k = 1 \mid \cdot)}{P(u_k = 0 \mid \cdot)}

と定義します。 $L(u_k) > 0$ なら $u_k=1$ の方がもっともらしく、 $L(u_k)<0$ なら $u_k=0$ の方がもっともらしいと解釈でき、符号(sign)を取れば硬判定(ハード判定)、絶対値の大きさは判定の確信度を表します。

DEC1がトレリス上のBCJRアルゴリズム(次節で詳述)によって計算する事後LLRは、次の3つの寄与に分解できます。

L_1(u_k) = \underbrace{L_c\, y_k^{s}}_{\text{チャネルLLR(系統)}} + \underbrace{L_a(u_k)}_{\text{事前情報(DEC2から)}} + \underbrace{L_{e,1}(u_k)}_{\text{外部情報(extrinsic)}}

ここで $L_c = 4E_s/N_0$ はAWGNチャネルのLLRスケール係数、 $y_k^s$ は受信した系統シンボル、 $L_a(u_k)$ はDEC2から渡された(このビットに関する)事前情報、そして $L_{e,1}(u_k)$ がDEC1が符号の構造(トレリスの制約とパリティ $\mathbf{y}^{p_1}$ )だけから新たに引き出した情報です。反復復号の1回目では $L_a(u_k)=0$ (まだ相手の情報がない)からスタートします。

ここで重要な設計判断があります。DEC1が計算した完全な事後LLR $L_1(u_k)$ をそのままDEC2に渡してはいけません。なぜなら $L_1(u_k)$ にはすでにチャネルLLR $L_c y_k^s$ が含まれており、これをそのままDEC2に渡すと、DEC2は自分自身が持っている同じ系統チャネル情報を「二重に」使ってしまい、両復号器の推定が互いに正のフィードバックで過信し合う(相関が発散する)という問題(しばしば「情報の近親相姦(information incest)」と呼ばれます)が起きてしまいます。そこで、DEC1は外部情報 $L_{e,1}(u_k)$ だけを抽出してインターリーブし、DEC2への事前情報として渡します。

L_{a,2}(u_k) = \pi\big(L_{e,1}(u_k)\big)

DEC2はこれをトレリス上の事前確率として使い、自分のパリティ $\mathbf{y}^{p_2}$ と系統チャネルLLR(インターリーブされた順序で)を組み合わせて、同様に

L_2(u_k') = L_c\, y_k'^{s} + L_{a,2}(u_k') + L_{e,2}(u_k')

を計算し、外部情報 $L_{e,2}$ をデインターリーブして次のイテレーションのDEC1への事前情報 $L_{a,1} = \pi^{-1}(L_{e,2})$ とします。この「DEC1 → インターリーブ → DEC2 → デインターリーブ → DEC1 → …」というサイクルを、あらかじめ決めた回数(実務では8〜18回程度)繰り返し、最終的に $L_1(u_k)$ (または $L_2$ をデインターリーブしたもの)の符号を取って最終的なビット判定 $\hat u_k = \text{sign}(L(u_k))$ とします。

BCJRアルゴリズム(MAP復号)の仕組み

各SISO復号器の内部で、パリティと事前情報からビットごとの事後LLRを計算するアルゴリズムがBCJRアルゴリズム(Bahl, Cocke, Jelinek, Raviv, 1974年、通称MAP復号)です。前回学んだViterbiアルゴリズムがトレリス上で「最も尤もらしい1本のパス(符号語全体)」を求めるのに対し、BCJRは「各時刻のビットごとの事後確率(周辺分布)」を求める点が本質的に異なります。ターボ復号ではビットごとの信頼度(LLR)そのものが次のイテレーションの入力になるため、Viterbiではなくビット単位の事後確率を出せるBCJRが必要になります。

トレリスの状態を $s_k \in \{0, 1, \dots, 2^m-1\}$ とし、次の3つの量を定義します。

前向き変数(forward metric) $\alpha_k(s)$ : 時刻1から $k$ までの観測 $\mathbf{y}_1^k$ が得られたもとで、状態が $s_k=s$ である結合確率(に比例する量)。

後向き変数(backward metric) $\beta_k(s)$ : 状態が $s_k=s$ であるという条件のもとで、時刻 $k+1$ から末尾までの観測 $\mathbf{y}_{k+1}^N$ が得られる条件付き確率(に比例する量)。

枝メトリック(branch metric) $\gamma_k(s', s)$ : 状態が $s_{k-1}=s'$ から $s_k=s$ へ遷移する際の、その遷移に対応する入力ビットの事前確率と、その遷移が生成する出力シンボルに対する観測尤度の積。

$\alpha$ と $\beta$ は、トレリスをそれぞれ前向き・後向きに1回ずつ走査するだけで、次の再帰式で効率的に計算できます。

\alpha_k(s) = \sum_{s'} \alpha_{k-1}(s')\, \gamma_k(s', s), \qquad \beta_{k-1}(s') = \sum_{s} \gamma_k(s', s)\, \beta_k(s)

境界条件は、符号器が既知の状態(通常はゼロ状態)から始まり、末尾に数ビットのターミネーションビット(トレイルビット)を付加して強制的にゼロ状態へ戻す設計が一般的なので、 $\alpha_0(0)=1$ (他の状態は0)、 $\beta_N(0)=1$ (他の状態は0)とします。

この $\alpha, \gamma, \beta$ が揃うと、時刻 $k$ でビット $u_k=i$ ( $i\in\{0,1\}$ )であった事後確率は、そのビット値に対応する全ての遷移 $(s',s)$ について和を取ることで得られます。

P(u_k = i \mid \mathbf{y}) \ \propto\ \sum_{(s', s):\, u_k = i} \alpha_{k-1}(s')\, \gamma_k(s', s)\, \beta_k(s)

したがって求めたいLLRは

L(u_k) = \ln \frac{\displaystyle\sum_{(s', s):\, u_k = 1} \alpha_{k-1}(s')\, \gamma_k(s', s)\, \beta_k(s)}{\displaystyle\sum_{(s', s):\, u_k = 0} \alpha_{k-1}(s')\, \gamma_k(s', s)\, \beta_k(s)}

となります。ここから外部情報 $L_e(u_k)$ を得るには、枝メトリック $\gamma_k(s',s)$ をあらかじめ「事前確率の項」と「系統チャネル尤度の項」と「パリティチャネル尤度の項」に因数分解しておき、上式のLLRから事前情報 $L_a(u_k)$ とチャネル系統項 $L_c y_k^s$ を差し引けば求まります。つまり $L_e(u_k) = L(u_k) - L_a(u_k) - L_c y_k^s$ という関係が、先ほどの分解式 $L(u_k)=L_c y_k^s + L_a(u_k)+L_e(u_k)$ の裏返しとして成り立っています。

実装上は、確率の積 $\alpha\gamma\beta$ をそのまま計算すると桁あふれ(アンダーフロー)を起こしやすいため、すべてを対数領域で扱うLog-MAPアルゴリズムが標準的に使われます。対数領域での和 $\ln(e^a+e^b)$ は、ヤコビ対数(Jacobian logarithm)

\max^*(a,b) \equiv \ln\!\left(e^{a}+e^{b}\right) = \max(a,b) + \ln\!\left(1+e^{-|a-b|}\right)

を使って乗算・指数演算なしに計算できます。補正項 $\ln(1+e^{-|a-b|})$ を省略して単純に $\max^*(a,b)\approx \max(a,b)$ とする近似はMax-Log-MAPと呼ばれ、わずかな性能劣化と引き換えに演算量をさらに削減できるため、演算資源が限られる搭載機器での実装によく使われます。

ターボクリフとエラーフロア

ターボ符号のビット誤り率(BER)対 $E_b/N_0$ の曲線は、他の符号にはない独特の2段構えの形をしています。

まず、ある $E_b/N_0$ のしきい値付近で、BERがごくわずかな $E_b/N_0$ の増加に対して桁違いに(場合によっては1 dBの変化で3桁以上)急落する領域が現れます。これをターボクリフ(turbo cliff)、あるいは(反復復号がうまく収束する領域という意味で)ウォーターフォール領域と呼びます。反復のたびに2つの復号器が交換する外部情報の信頼度が雪だるま式に高まり、ある点を境に一気に収束することが、この急峻な落ち込みの理由です。インターリーバ長 $N$ を大きくするほど、この崖の位置はシャノン限界に近づいていきます。

しかし、BERが $10^{-5}$ 〜 $10^{-6}$ 程度まで下がったあたりから、曲線の傾きが急に緩やかになり、それ以上 $E_b/N_0$ を上げてもBERがなかなか下がらなくなる領域が現れます。これがエラーフロア(error floor)です。これは、反復復号が収束しないという問題ではなく、ターボ符号そのものが持つ有効最小距離(effective minimum distance)が小さいことに起因します。RSC符号器の構造上、ごく少数の「1」が離れた位置に孤立して現れる特定の入力パターン(たとえば重み2の入力)に対して、たまたまインターリーバによる並べ替え後もRSC2側で低重みの出力になってしまう「相性の悪い」ケースが、確率は低いながらも避けられずに残ります。この少数の低重み誤り事象が、ウォーターフォール領域を過ぎた低BER領域では支配的になり、床(フロア)のように誤り率が張り付いてしまうわけです。

実務設計では、この2つの特性は独立にチューニングする必要があります。ウォーターフォール領域(ターボクリフの位置)はインターリーバ長 $N$ と反復回数で主に決まり、エラーフロアの高さはインターリーバの詳細設計(S-ランダムインターリーバなど、低重み入力パターンが再構成されにくい配置規則)で主に決まります。反復回数についても、最初の数回のイテレーションで性能が大きく改善する一方、それ以降は改善が急速に頭打ちになる(収穫逓減)ため、実装では復号遅延・消費電力とのトレードオフから8〜15回程度で打ち切るのが一般的です。

実務での使われ方

CCSDSはターボ符号を CCSDS 131.0-B (TM Synchronization and Channel Coding) の中で標準化しています。CCSDS標準ターボ符号は16状態(拘束長5)の再帰的組織畳み込み符号器2つを構成符号として用い、情報ブロック長は1784、3568、7136、8920ビットの4種類、符号化率は1/2、1/3、1/4、1/6の4種類がサポートされています。この構成符号のパラメータは、Berrouらのオリジナルの提案(16状態RSC)の系譜を直接引き継いだものです。NASAの火星探査機(たとえばマーズ・リコネッサンス・オービター)をはじめ、2000年代以降の数多くの深宇宙・近地球ミッションのダウンリンクで、CCSDS標準ターボ符号が採用され、それ以前の直列連接符号(RS+畳み込み)と比べて1〜2 dB以上のリンクマージンの改善をもたらしました。

一方で、2000年代後半以降、多くの新規ミッションはターボ符号に代えて**LDPC符号(低密度パリティ検査符号)**を採用する方向に移行しています。CCSDSもAR4JA符号族などのLDPC符号を131.0-Bに追加標準化しました。この移行の背景には、性能そのものだけでなく、実装上の理由が大きく関わっています。

復号遅延(レイテンシ)の違い。 BCJRアルゴリズムは、ブロック全体を受信し終えてから前向き再帰 $\alpha$ と後向き再帰 $\beta$ をそれぞれ端から端まで走査する必要があり、本質的に**逐次的(シーケンシャル)**です。ブロック長が数千ビットに及ぶターボ符号では、1回の反復ごとにこの前向き・後向き走査が発生し、それを8〜15回繰り返すため、総復号遅延がブロック長と反復回数の積にほぼ比例して増大します。
並列実装のしやすさ。 これに対しLDPC符号の復号(確率伝播法、Belief Propagationやサムプロダクトアルゴリズム)は、疎なタナーグラフ上のすべての変数ノード・チェックノードを、原理的に同時並行して更新できます。これは高速な専用ハードウェア(ASIC/FPGA)への実装に非常に向いており、近地球ミッションのKaバンド高速リンク(数百Mbps〜Gbpsクラス)のような高スループットが要求される場面で、ターボ符号のBCJR復号よりも有利になります。
高い符号化率への拡張性。 LDPC符号は検査行列の設計次第で高い符号化率(たとえば0.9以上)まで柔軟に対応でき、エラーフロアも構造的な設計(不整脈的でないグラフ構造)によって深宇宙用途でも十分に低く抑えられることが分かってきました。

このため、現在では低データレートで極めて弱い信号を扱う一部の深宇宙ミッションを除き、多くの新規ミッションではLDPC符号がターボ符号に代わる標準選択肢になりつつあります。とはいえ、ターボ符号は多くの既存機体・地上局設備に組み込まれた実績のある方式として、CCSDS標準の中に今も現役の選択肢として残っています。

演習問題

本文で示した拘束長3、生成多項式 $(g_0,g_1)=(7,5)$ のRSC符号器について、ゼロ状態からスタートし入力系列 $u = (1,0,1,1)$ を与えたときの、各時刻の状態 $(m^{(1)}_k, m^{(2)}_k)$ 、系統出力 $x_k$ 、パリティ出力 $p_k$ を表にして求めてください。
PCCC母符号(符号化率1/3、系統1本+パリティ2本)から、パリティを1ビットおきに交互に間引くパンクチャリングによって符号化率1/2を得る手順を説明し、さらに符号化率2/3を得るにはどのようなパンクチャリングパターンが必要か、間引き後のビット構成を示しながら求めてください。
あるビット $u_k$ について、DEC1のBCJR復号が出した事後LLRが $L_1(u_k) = 2.3$ 、チャネルLLR(系統)が $L_c y_k^s = 0.8$ 、DEC2から受け取った事前情報が $L_a(u_k) = 0.5$ であったとします。DEC2へ渡すべき外部情報 $L_{e,1}(u_k)$ を計算し、なぜ $L_1(u_k)$ をそのまま渡してはいけないのかを、情報の二重利用という観点から説明してください。
ターボクリフとエラーフロアはそれぞれ何に起因する現象か、そしてなぜインターリーバ長を伸ばすだけではエラーフロアを十分に下げられないのかを、この回で学んだ内容にもとづいて説明してください。また、CCSDSがターボ符号からLDPC符号へ標準の軸足を移した最大の実装上の理由を、BCJR復号とBelief Propagation復号の構造的な違いに触れながら述べてください。

まとめと次回予告

ターボ符号は、2つの再帰的組織畳み込み符号器をインターリーバで並列に連接するというPCCCの構造と、2つのソフト入力・ソフト出力復号器が対数尤度比の外部情報だけを交換しながら反復的に精度を高めていく復号アルゴリズムという、2つの発明の組み合わせによって、シャノン限界からわずか1 dB足らずまで迫るという1993年当時の常識を覆す性能を実現しました。その心臓部であるBCJR(MAP)アルゴリズムは、Viterbiアルゴリズムと同じトレリス構造の上で、前向き・後向きの2方向の再帰によってビットごとの事後確率を計算します。一方で、ターボクリフとエラーフロアという2つの実務上の性能特性、そしてBCJR復号が本質的に持つ逐次性による復号遅延の大きさが、後にCCSDSがLDPC符号へと標準の軸足を移していく動機になりました。

次回は、このターボ符号の後継として現在の主流になりつつある**LDPC符号(低密度パリティ検査符号)**を扱います。疎なパリティ検査行列とタナーグラフ上の確率伝播法(Belief Propagation)によって、ターボ符号に匹敵する、あるいはそれを上回る性能を、より並列性の高い復号アルゴリズムで実現する仕組みを見ていきます。

参考文献

C. Berrou, A. Glavieux, P. Thitimajshima, “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes,” Proc. IEEE International Conference on Communications (ICC), 1993.
L. R. Bahl, J. Cocke, F. Jelinek, J. Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” IEEE Transactions on Information Theory, vol. 20, no. 2, 1974.
CCSDS 131.0-B, TM Synchronization and Channel Coding
S. Lin, D. J. Costello, Error Control Coding, 2nd ed., Prentice Hall
B. Vucetic, J. Yuan, Turbo Codes: Principles and Applications, Kluwer Academic Publishers
J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76