変調・符号化#27

CCSDS符号化標準の変遷 — 畳み込み符号からLDPCまで、符号化利得半世紀の軌跡

畳み込み符号・RS符号・連接符号・ターボ符号・LDPC符号をここまで個別に学んできた総まとめ回。CCSDS標準の変遷を時系列で振り返り、各世代の符号化利得(dB)を無符号化BPSKを基準に整理し、その数dBがリンクバジェットの数式を通じて実際の通信距離・データレートにどれだけの違いを生んだかを定量的に確認する。

前提知識: concatenated-codes、turbo-codes、ldpc

CCSDS符号化利得リンクバジェット誤り訂正符号深宇宙通信史

この回で学ぶこと

ここまでの回で、私たちは深宇宙通信の誤り訂正符号を一つずつ個別に学んできました。畳み込み符号の格子構造とビタビ復号、リード・ソロモン(RS)符号の非二元有限体上の代数的な訂正能力、畳み込み符号とRS符号を組み合わせた連接符号、反復復号によってシャノン限界へと肉薄するターボ符号、そして現在の標準であるLDPC符号。それぞれの回では、各符号の内部構造(トレリス、生成多項式、インターリーブ、Tannerグラフ、Belief Propagationなど)を数式で追うことに集中してきました。

この回は、それらを新たに導出する回ではありません。代わりに、これらの符号がCCSDSの標準の中でどういう順序で登場し、旧世代を置き換え、あるいは共存してきたのかを時系列で俯瞰し、「結局、半世紀にわたる符号化技術の進歩は、通信をどれだけ良くしたのか」という問いに、符号化利得(コーディングゲイン)という単一の数値のものさしで答えを与えます。そして、その数dBから10dB程度の符号化利得という一見地味な数字が、抽象的な理論値ではなく、実際のミッションが飛べる距離や送れるデータレートにどれだけ具体的な違いを生んだのかを、リンクバジェットの数式を使って定量的に確かめます。最後に、シャノン限界にほぼ到達した現在でも、なぜ一部のミッションが今なお「古い」符号を使い続けているのかという、実務上の興味深い逆説も扱います。

直感的導入

半世紀にわたる符号化技術の歴史を、まず言葉で俯瞰してみましょう。

雑音の多い部屋の向こうにいる人に声を届けたいとします。最も原始的な方法は、ただ大声で叫ぶことです(無符号化)。しかし喉には限界があるので、次に考えるのは「同じことを2回言う」「聞き取りにくい単語は言い換える」といった工夫でしょう。これが誤り訂正符号の本質です。声の大きさ(送信電力)を上げずに、言葉の構成の工夫だけで、相手に正しく伝わる確率を上げるわけです。

CCSDSの符号化標準の歴史は、まさにこの「工夫」がどんどん洗練されていった記録です。1960〜70年代のパイオニアや初期ボイジャーは、まだ「叫ぶだけ」に近い無符号化、あるいは単純な畳み込み符号のみの時代でした。1980年代には、畳み込み符号(内符号)とRS符号(外符号)を組み合わせた連接符号が標準化され、ボイジャーの天王星・海王星接近時にはさらに強力な符号へと進化しました。1990年代後半から2000年代にかけては、Berrouらが1993年に発表したターボ符号が登場し、その論文タイトルどおり”シャノン限界に近い”符号化を実現します。そして2000年代後半以降は、1960年代にGallagerが提案しながら長らく忘れられていたLDPC符号が再発見・実用化され、現在のCCSDS標準の主力になっています。

重要なのは、これらの符号の進化がバラバラの改良の寄せ集めではなく、一貫して同じ目標――無符号化に対する符号化利得を、より少ない演算量・より短い符号長で、シャノン限界にどこまで近づけるか――を追いかけ続けた歴史だという点です。以下では、この「利得」を数式の言葉で定義し、各世代を横並びに比較していきます。

符号化利得という共通のものさし

PCM/PSK/PMの回で見たように、無符号化BPSKのビット誤り率は

P_b = Q\!\left(\sqrt{\frac{2E_b}{N_0}}\right)

で与えられます。誤り訂正符号を使うと、同じ $E_b/N_0$ のもとで $P_b$ が改善されます(あるいは同じ $P_b$ を、より低い $E_b/N_0$ で達成できます)。この効果を数値化するのが符号化利得 $G_c$ で、ある目標ビット誤り率 $P_b^\ast$ を達成するために必要な $E_b/N_0$ を、無符号化の場合と符号化した場合とで比較して定義します。

G_c(\text{dB}) \equiv \left(\frac{E_b}{N_0}\right)_{\text{uncoded, dB}}^{P_b = P_b^\ast} - \left(\frac{E_b}{N_0}\right)_{\text{coded, dB}}^{P_b = P_b^\ast}

つまり「同じ誤り率を達成するのに、符号化によって何dB分の $E_b/N_0$ を節約できたか」という差分です。符号化率が違う符号同士でも、変調方式が同じ(BPSKやQPSK)である限り、この $G_c$ 一本で横並びに比較できるのが便利な点です。ここでの $E_b$ は情報ビット1ビットあたりのエネルギーであり、符号化によって追加される冗長ビットの分だけ1情報ビットに配分できる送信エネルギーが実質的に薄まる効果(符号化率 $r<1$ による損失)も、この $G_c$ の中にすでに織り込まれています。

基準点として、目標ビット誤り率 $P_b^\ast = 10^{-5}$ における無符号化BPSKの必要 $E_b/N_0$ を計算しておきます。 $Q^{-1}(10^{-5}) \approx 4.265$ より、

\sqrt{\frac{2E_b}{N_0}} = 4.265 \ \Longrightarrow\ \frac{E_b}{N_0} \approx 9.09 \ \Longrightarrow\ \left(\frac{E_b}{N_0}\right)_{\text{dB}} \approx 9.6\ \text{dB}

これが本稿を通じて使う「符号化利得ゼロ」の基準点です。

CCSDS符号化標準の変遷 — 年表と符号化利得の推移

以下の表は、各世代の代表的な符号構成について、目標ビット誤り率における必要 $E_b/N_0$ と、無符号化BPSKに対する符号化利得の目安をまとめたものです(実際の数値は符号長・フレームサイズ・復号アルゴリズムの実装によって変動するため、あくまで代表値として扱ってください)。

年代	CCSDS標準(概略)	符号構成	符号化率	目標BER	$E_b/N_0$ (目安)	符号化利得 $G_c$
〜1970年代	(無符号化 / 単体畳み込み)	無符号化BPSK	1	$10^{-5}$	9.6 dB	0 dB (基準)
1970年代	(単体畳み込み符号運用)	畳み込み符号 $K=7$ , $r=1/2$ (ビタビ軟判定)	1/2	$10^{-5}$	約4.5 dB	約5.1 dB
1980年代	CCSDS 101.0-B系	連接符号: 畳み込み( $K=7,r=1/2$ )+RS(255,223)+インターリーブ	実質約0.437	$10^{-6}$	約2.5 dB	約8.0 dB
1980年代末	(ボイジャー改良符号)	連接符号: 畳み込み( $K=15,r=1/6$ )+RS(255,223)	実質約0.146	$10^{-6}$	約0.4 dB	約10.1 dB
1990年代後半〜2000年代	CCSDS 131.0-B系(ターボ追加)	ターボ符号(フレーム長 $k\approx 8920$ )	1/2	$10^{-5}$	約0.8 dB	約8.8 dB
2000年代後半〜現在	CCSDS 131.0-B-3等	LDPC符号(AR4JA等)	1/2	$10^{-5}$	約0.5 dB	約9.1 dB

いくつか注意点を補足します。

目標BERが世代によって揃っていない理由。 連接符号は、外符号のRSが持つ「訂正しきれる誤りバイト数を超えると急激に破綻する」という崖(cliff)効果の性質上、内符号(畳み込み符号)出力のBERがある閾値を下回った瞬間に、RS復号後のBERが桁違いに改善します。そのため実務上、連接符号の性能は $10^{-6}$ 程度の低いBERで評価するのが慣例です。一方、単体の畳み込み符号やターボ符号・LDPC符号は $10^{-5}$ 前後で評価されることが多く、表中のBERはこの慣例に合わせています。世代間の $G_c$ を厳密に比較する際は、この目標BERの違いに注意する必要があります。

ボイジャー改良符号の位置づけ。 1980年代末、ボイジャー2号の天王星・海王星接近に向けて、JPLは拘束長 $K=15$ 、符号化率 $r=1/6$ というきわめて長い拘束長の畳み込み符号(通称 Big Viterbi Decoder, BVD)を開発しました。これは標準的な $K=7, r=1/2$ 符号に対して約2.1 dBの追加利得をもたらすことが実測・報告されており、RS符号との連接と合わせて表中のような大きな符号化利得を実現しています。この符号は同じ「連接符号」という枠組みの中での内符号の強化にあたり、次のターボ符号への橋渡し的な位置づけとして興味深い事例です。

ターボ・LDPCがシャノン限界にどれだけ迫っているか。 シャノン限界の回で導いた、スペクトル効率 $\eta$ の関数としての最小必要 $E_b/N_0$ の式

\frac{E_b}{N_0} > \frac{2^\eta - 1}{\eta}

に、符号化率 $r=1/2$ に対応するスペクトル効率 $\eta \approx 0.5$ bit/s/Hz(BPSKベースで1シンボルに1符号化ビット、符号化率1/2なので1シンボルあたり0.5情報ビット)を代入すると、

\frac{E_b}{N_0} > \frac{2^{0.5}-1}{0.5} = \frac{0.4142}{0.5} \approx 0.828 \ \Longrightarrow\ \left(\frac{E_b}{N_0}\right)_{\text{dB}} > -0.82\ \text{dB}

これが符号化率1/2におけるシャノン限界です。表のターボ符号(約0.8 dB)は限界からわずか 約1.6 dB、LDPC符号(約0.5 dB)は 約1.3 dB しか離れていません。1970年代の畳み込み符号単体(約4.5 dB)がこの限界から5 dB以上離れていたことを思えば、この50年間の符号化研究がいかにシャノン限界という「動かない壁」に肉薄してきたかが、この一本の数直線上に凝縮されていることが分かります。

符号化利得をリンクバジェットに翻訳する

符号化利得が何dBかという数字自体は抽象的です。これを、実際のミッション設計で意味を持つ通信距離やデータレートに翻訳してみましょう。

受信電力 $P_R$ は、送信電力 $P_T$ 、送受信アンテナ利得 $G_T, G_R$ 、波長 $\lambda$ 、距離 $d$ を使った自由空間伝搬の関係式で与えられます(シャノン限界の回でも触れた自由空間損失の考え方です)。

P_R = \frac{P_T G_T G_R}{L_{\text{other}}}\left(\frac{\lambda}{4\pi d}\right)^2

ここで $L_{\text{other}}$ は大気減衰や実装損失などをまとめた損失項です。 $E_b/N_0$ は、この受信電力を雑音電力スペクトル密度 $N_0$ とビットレート $R_b$ で正規化したものでした。

\frac{E_b}{N_0} = \frac{P_R}{N_0 R_b} \ \propto\ \frac{1}{d^2 R_b}

つまり $E_b/N_0$ は距離の2乗に反比例し、データレートに反比例します。符号化利得 $G_c$ (線形値では $G \equiv 10^{G_c(\text{dB})/10}$ )は「必要な $E_b/N_0$ を $1/G$ 倍にできる」ということなので、この余裕を2通りの方法で使い切ることができます。

(a) データレートを固定し、距離を伸ばす場合。 $E_b/N_0 \propto 1/d^2$ なので、必要 $E_b/N_0$ を $1/G$ 倍にできる余裕は、距離を

\frac{d_{\text{new}}}{d_{\text{old}}} = \sqrt{G} = 10^{\,G_c(\text{dB})/20}

倍まで伸ばすことに使えます。

(b) 距離を固定し、データレートを上げる場合。 $E_b/N_0 \propto 1/R_b$ なので、同じ余裕は

\frac{R_{b,\text{new}}}{R_{b,\text{old}}} = G = 10^{\,G_c(\text{dB})/10}

倍のデータレートに使えます。

具体的に数字を入れてみましょう。畳み込み符号単体( $G_c \approx 5.1$ dB)からLDPC符号( $G_c \approx 9.1$ dB)への進化がもたらした追加利得は $\Delta G_c = 9.1 - 5.1 = 4.0$ dBです。これをデータレートに換算すると、

10^{4.0/10} = 10^{0.4} \approx 2.51

同じ距離・同じ送信電力のまま、データレートを約2.5倍に増やせるということです。あるいは距離に換算すると、

10^{4.0/20} = 10^{0.2} \approx 1.58

同じデータレート・同じ送信電力のまま、通信できる距離を約1.6倍に伸ばせることになります。無符号化からLDPC符号までの全利得 $G_c \approx 9.1$ dBで同じ計算をすると、データレートで約8.1倍、距離で約2.85倍という、探査機の運用可能な範囲を一変させる数字になります。太陽系内での探査機と地球の距離は軌道運動によって数倍程度変動しますが、符号化技術の進歩だけで、送信電力やアンテナサイズを一切変えずにこれに匹敵するマージンを生み出せる、という事実が、なぜCCSDSがこれほど熱心に符号化標準を更新し続けてきたかの答えです。

実務での使われ方

現在運用中・計画中の深宇宙ミッションでは、CCSDS 131.0-B-3(TM Synchronization and Channel Coding)に規定されたターボ符号(符号化率1/2, 1/3, 1/6)またはLDPC符号(AR4JA符号族など)が、新規開発のダウンリンク(探査機→地球)テレメトリの標準的な選択肢です。たとえば近年の火星探査機の多くは、限られた送信電力の中でできるだけ多くの画像・科学データを持ち帰るため、ターボ符号やLDPC符号を用いた高効率なリンクを採用しています。

一方で、興味深いことにすべてのミッションが最新の符号に移行しているわけではありません。たとえば2006年に打ち上げられ、2015年の冥王星フライバイを経て現在もカイパーベルトで運用が続くニュー・ホライズンズは、設計凍結時期の制約から連接符号(畳み込み+RS)を使い続けています。数十年単位で飛び続ける探査機にとって、打ち上げ後に符号化方式そのものを変更することは(搭載ソフトウェアの改修余地がない限り)事実上不可能であり、「その時点での最良の、しかし枯れた」符号を選ばざるを得ないという制約があります。また多くのCubeSat・小型衛星ミッションでも、コストと開発リスクを抑えるため、飛行実績のあるIPコア・トランスポンダに内蔵された単純な畳み込み符号やRS+畳み込みの連接符号がいまだに広く使われています。

さらに本質的な非対称性が、アップリンク(地球→探査機、コマンド送信) に存在します。CCSDS 231.0-B(TC Synchronization and Channel Coding)に規定されるコマンドアップリンクでは、現在でもBCH符号や単純な畳み込み符号が標準的に使われ続けており、ターボ符号やLDPC符号への移行はダウンリンクほど進んでいません。理由は明快です。

復号を担う側の資源が非対称。 ダウンリンクのLDPC・ターボ復号は、電力にほぼ制約のない地上局側(DSNの大型アンテナ局)が担います。しかしアップリンクの復号は探査機側が行わねばならず、探査機の限られた電力・質量・放熱能力の中で、反復復号(ターボ・LDPC)特有の演算量と復号遅延を負担することになります。
コマンドの性質上、低遅延・高信頼な「枯れた」実装が優先される。 姿勢制御やクリティカルフェーズでのコマンド送信は、多少のデータレート損失より、確実かつ即座に正しく復号できることの方が重要です。反復復号は原理的に高い符号化利得を持ちますが、復号に要する遅延や、実装の検証・飛行実績の蓄積という点では、単純な畳み込み符号やBCH符号に一日の長があります。
後方互換性とヘリテージ(実績)の重み。 新しい符号化ASIC・FPGA IPコアを採用するには、放射線耐性試験・熱真空試験・EMI試験などの再認証コストとスケジュールリスクが伴います。すでに飛行実績のあるトランスポンダ設計を複数ミッションで使い回す方が、開発コストとリスクの両面で合理的な場合が多く、これが「新しい符号があるのに古い符号が生き残る」最大の実務的理由です。
DSN側の後方互換性維持義務。 地上局(DSN)は、1970年代打ち上げのボイジャーから最新鋭のミッションまで、同時に多世代にわたる符号化方式をサポートし続ける必要があります。新しい符号の追加は既存符号のサポート終了を意味しないため、DSNの受信機・復号系は年々「対応フォーマットの博物館」のように多様化していきます。

つまり、符号化利得という観点だけを見ればLDPC・ターボ符号への統一移行が合理的に見えますが、実際のミッション設計は「利得」「実装の枯れた信頼性」「復号側の資源制約」「後方互換性」という複数の軸のトレードオフの上に成り立っており、これが今日でも複数世代の符号がCCSDS標準の中に併存し続けている理由です。

演習問題

目標ビット誤り率 $10^{-5}$ において、無符号化BPSKが $E_b/N_0 = 9.6$ dB、ターボ符号( $r=1/2$ )が $E_b/N_0 = 0.8$ dB を必要とするとき、ターボ符号の符号化利得 $G_c$ を計算してください。またこの結果を、符号化率 $1/2$ におけるシャノン限界 $-0.82$ dB と比較し、ターボ符号がシャノン限界から何dB以内に迫っているか求めてください。
問1の符号化利得 $G_c$ (dB)を用いて、データレートを変えずに探査機との通信距離を何倍まで伸ばせるか、 $d_{\text{new}}/d_{\text{old}} = 10^{G_c/20}$ の式で計算してください。
あるミッションが畳み込み符号単体( $G_c \approx 5.1$ dB)からLDPC符号( $G_c \approx 9.1$ dB)にアップグレードしたとします。距離を変えずに、データレートを何倍に増やせるか、 $R_{b,\text{new}}/R_{b,\text{old}} = 10^{\Delta G_c/10}$ の式で計算してください。
なぜ探査機へのコマンドアップリンクでは、ダウンリンクのテレメトリほどにはターボ符号・LDPC符号への移行が進んでいないのでしょうか。この回で扱った「復号を担う側の資源の非対称性」という観点から、自分の言葉で説明してください。

まとめと次回予告

この回では、これまで個別に学んできた畳み込み符号・RS符号・連接符号・ターボ符号・LDPC符号を、CCSDS標準の歴史的変遷という軸で串刺しにし、符号化利得という単一のものさしで整理しました。1970年代の畳み込み符号単体(約5.1 dB)から、1980年代の連接符号(約8〜10 dB)、そして現代のターボ・LDPC符号(約9 dB、シャノン限界から1〜2 dB以内)へと、半世紀かけて着実に理論限界へ近づいてきた軌跡を確認し、その数dBの差がリンクバジェットの数式を通じて、実際の通信距離やデータレートに数倍単位の実質的な違いをもたらすことも見ました。また、符号化利得だけでは説明できない実務上の理由(復号側の資源制約、実装の枯れた信頼性、後方互換性)から、最新の符号と旧世代の符号が今なお併存していることも確認しました。

これで変調・符号化に関する一連のテーマはひと区切りです。次回からは、受信機がビット列・シンボル列そのものをどうやって正しいタイミングで切り出しているのかというシンボル同期の話に軽く触れていきます。ここまで学んできたPLLによる搬送波位相の追尾とはまた別に、「シンボルの境界がどこにあるか」を推定する仕組みが必要であり、それがなければ、どんなに優れた符号化利得を持つ符号も宝の持ち腐れになってしまいます。

参考文献

CCSDS 131.0-B-3, TM Synchronization and Channel Coding
CCSDS 101.0-B-6, Telemetry Channel Coding (Historical, superseded)
CCSDS 130.1-G-3, TM Synchronization and Channel Coding — Summary of Concept and Rationale (Green Book)
CCSDS 231.0-B, TC Synchronization and Channel Coding
C. Berrou, A. Glavieux, P. Thitimajshima, “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes,” Proc. IEEE ICC, 1993
R. G. Gallager, “Low-Density Parity-Check Codes,” IRE Transactions on Information Theory, 1962
S. Dolinar, F. Pollara, et al., JPL TDA Progress Report series on the Voyager Big Viterbi Decoder and concatenated coding performance
J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76
DSN Telecommunications Link Design Handbook, DSN No. 810-005