連接符号 — 畳み込み符号とリード・ソロモン符号を直列につなぐ古典アーキテクチャ

この回で学ぶこと

前々回は畳み込み符号とビタビ復号を学びました。ビタビ復号器は、トレリス上の最尤パスを追跡することでランダムな(互いに独立に散らばった)ビット誤りに強い訂正能力を発揮します。しかし復号後の誤りをよく観察すると、それは決してランダムには散らばっていません。ビタビ復号器が誤ったパスを選んでしまうと、その誤りは拘束長程度の期間にわたって尾を引き、数ビットから十数ビットが固まった誤りイベント (error event) として現れます。つまりビタビ復号後の出力は、「誤りは少ないが、残った誤りは塊になっている」という独特の性質を持っています。

前回はリード・ソロモン(RS)符号を学びました。RS符号はビット単位ではなくシンボル(バイト)単位で誤りを数えるため、1シンボルの中で何ビット誤っていようと「1シンボル誤り」としてしか数えません。これはまさに、バースト的に固まった誤りに強いという性質でした。

この2つの事実を並べると、自然な発想が浮かびます。「ビタビ復号器が残す誤りはバースト的な塊である」「RS符号はバースト的な塊にめっぽう強い」——ならばこの2つを直列につなげば、互いの弱点を補い合う理想的な誤り訂正システムができるのではないか。この発想を実際に工学として作り込んだものが、この回で扱う 連接符号 (concatenated code) です。畳み込み符号を内符号 (inner code)、RS符号を外符号 (outer code) とし、その間にインターリーバ (interleaver) と呼ばれる並べ替え装置を挟むことで、ボイジャーからガリレオ、そして現代の多くのミッションに至るまで、深宇宙通信の誤り訂正の「標準構成」であり続けてきたアーキテクチャです。

直感的な全体像

連接符号のデータの流れを、送信側と受信側でそれぞれ追ってみましょう。

送信側(符号化): 元データのビット列は、まず外符号であるRS符号器に通されます。RS符号はここで冗長シンボルを付加します。次にその出力をインターリーバで並べ替えます(中身の理由は後述します)。そして最後に、並べ替えられたビット列を内符号である畳み込み符号器に通し、変調・送信します。

受信側(復号): 受信機はまず内符号から復号します。復調されたビット列(あるいは軟判定値)をビタビ復号器に通し、畳み込み符号の誤りを訂正します。次にデインターリーバでビットの並びを元に戻します。最後にRS復号器に通し、外符号の誤りを訂正して元データを取り出します。

つまり、符号化の順序は「外符号 → インターリーブ → 内符号」、復号の順序はその逆で「内符号(ビタビ)復号 → デインターリーブ → 外符号(RS)復号」です。内符号が物理的なチャネル(無線伝搬路)に一番近い側に置かれるため、こう呼ばれます。

なぜこの順序なのか、そしてなぜ間にインターリーバが要るのか。これがこの回の中心的な問いです。答えを一言で言えば、「ビタビ復号器が吐き出す誤りの塊の大きさと、RS符号が扱いやすい誤りの塊の大きさの間には、まだギャップがある。インターリーバはそのギャップを埋める道具である」ということです。以下、これを数式で追っていきます。

内符号の出力: なぜ誤りは塊になるのか

畳み込み符号(拘束長 $K$、符号化率 $r$)をビタビ復号したときの復号後ビット誤り率(BER)を $p$ とします。チャネルのEb/N0がある程度以上あれば $p$ は非常に小さい値に抑えられますが、その残った誤りの時間的な分布が問題です。

ビタビ復号は、トレリス上で正しいパスと誤ったパスの距離(ハミング距離、あるいは軟判定ならユークリッド距離)を比較しながら、生き残りパスを選び続けるアルゴリズムでした。復号器が雑音によって一時的に誤ったパスを選んでしまうと、そのパスは正しいパスに合流するまでの間、正解のビット列とずれ続けます。この「一時的な誤選択から合流するまで」の区間が1回の誤りイベントであり、その典型的な長さは拘束長 $K$ のオーダー(標準的な $K=7$ の符号ではおおむね数ビット〜十数ビット)になります。

これを大まかにモデル化すると、復号後のビット誤り列は次のようなバースト誤りモデルで近似できます。

$$e(t) = \sum_{k} \mathbb{1}_{[\tau_k,\ \tau_k + L_k)}(t)$$

ここで $\tau_k$ は $k$ 番目の誤りイベントの発生時刻、$L_k$ はそのイベントの長さ(ビット数)で、$L_k$ はおおむね拘束長 $K$ のオーダーの分布に従い、イベント同士の間隔 $\tau_{k+1}-\tau_k$ はEb/N0が十分高ければ非常に長い(=誤りイベントは疎にしか起きない)というのがビタビ復号後のBERの実態です。平均誤り率は低いが、誤りが起きるときは固まって起きる——これが内符号の出力の本質的な性質です。

外符号: RS符号のシンボル訂正能力(復習)

前回学んだ通り、$(n,k)$ RS符号は $\mathrm{GF}(2^m)$ 上で構成され、1シンボルが $m$ ビットからなります。CCSDSで標準となっている構成は

$$(n, k) = (255, 223), \qquad m = 8 \ \text{(1シンボル = 1バイト)}$$

で、1符号語あたり訂正できるシンボル誤り数は

$$t = \left\lfloor \frac{n-k}{2} \right\rfloor = \frac{255-223}{2} = 16$$

です。ここで決定的に重要なのは、RS符号が数えるのはシンボル単位の誤りであってビット単位の誤りではないという点です。1シンボル(8ビット)のうち1ビットだけ誤っていても、8ビット全部が誤っていても、RS復号器から見ればどちらも等しく「1シンボル誤り」でしかありません。符号語の誤り訂正が失敗する条件は、シンボル誤り数 $e$ が $t$ を超えることで、その確率はシンボル誤り率 $p_s$ を使って

$$P_{\text{block fail}} \;\approx\; \sum_{e=t+1}^{n} \binom{n}{e}\, p_s^{\,e}\,(1-p_s)^{\,n-e}$$

と近似できます(RS符号は独立なランダムシンボル誤りに対して常にこの2項分布型の評価が有効です)。

連接のかみ合わせ: なぜ内符号の出力が外符号にとって”扱いやすい”のか

ここで内符号と外符号の性質を重ね合わせてみましょう。ビタビ復号後の誤りが「$L$ ビットの塊」として発生したとき、これをそのままRS符号器が扱う8ビット単位のシンボル列に割り当てるとどうなるでしょうか。

$L$ ビットの塊が1つのシンボル境界の中に収まるなら、それは1シンボル誤りとして処理されます。仮に $L=8$ ビット全部が誤っていたとしても、RS符号から見ればコストは「1シンボル」分だけです。もしこれが逆に、同じ8個のビット誤りが8個の別々のシンボルに1ビットずつ散らばっていたら、RS符号にとっては「8シンボル誤り」となり、$t=16$ という限られた訂正能力を一気に半分も消費してしまいます。

つまり、誤りが塊になっていることは、シンボル単位で誤りを数える符号にとってはむしろ好都合なのです。同じ量のビット誤りでも、少数のシンボルに凝縮されているほうが、多数のシンボルに薄く広がっているよりもRS符号の訂正能力を消費しません。これが「畳み込み符号を内符号、RS符号を外符号にする」という組み合わせが理にかなっている核心的な理由です。ビタビ復号器はビット誤り率そのものは十分低くできなくても、誤りを少数の塊に押し込めることが得意であり、RS符号はまさにその塊を安く処理できる符号だからです。

インターリーバ: 塊の”かたより”を均す

しかし、これだけではまだ不十分です。ビタビ復号器の誤りイベントの発生自体はEb/N0が低下する局面(信号が弱まる、太陽合による雑音増加、姿勢変化によるアンテナ利得低下など)で頻発しやすく、複数の誤りイベントがたまたま同じRS符号語の範囲内(255シンボル = 2040ビット)に集中して発生してしまう可能性があります。個々のイベントは短くても、運悪く同じ符号語に3つも4つも重なれば、合計シンボル誤り数が $t=16$ を超えて復号失敗を招きかねません。

この「局所的な偏り」を平坦にならすのがインターリーバの役割です。考え方は単純です。連続する1つのRS符号語に属するシンボルを、伝送順では互いに大きく離れた位置に散らばらせておけば、伝送路上の1回の誤りバースト(あるいは近接した複数の誤りイベント)が、1つの符号語に集中的にダメージを与えることを防げます。

ブロックインターリーバの数式的な入出力対応

CCSDSで標準的に使われるブロック(行列型)インターリーバを定式化しましょう。深さ(depth) $I$ のインターリーバは、$I$ 個のRS符号語を1つの $I \times n$ 行列に束ねて操作します。

書き込み(RS符号化直後): $i$ 番目の符号語($i = 0, 1, \dots, I-1$)の $j$ 番目のシンボル($j = 0, 1, \dots, n-1$)を、行列の $(i,j)$ 成分として行ごとに書き込みます。

$$M[i][j] = c_i(j), \qquad i = 0,\dots,I-1,\quad j = 0,\dots,n-1$$

読み出し(伝送順): 行列を列方向に読み出して伝送します。伝送順のインデックス $k$ に対応する行列の位置は

$$i = k \bmod I, \qquad j = \left\lfloor \frac{k}{I} \right\rfloor, \qquad t_k = M[i][j]$$

で与えられます。この読み出し方によって、伝送順で隣り合うシンボル $t_k, t_{k+1}$ は($k$ が $I$ の倍数をまたがない限り)必ず異なる符号語($i$ が1ずつ増える)に属することになります。$I$ シンボル進むごとにちょうど1周し、$I$ 個すべての符号語から1シンボルずつ均等に取り出された状態になっています。

受信側(デインターリーブ)は逆の操作です。受信シンボル列 $r_k$ を、$i=k\bmod I,\ j=\lfloor k/I\rfloor$ の対応で行列 $M'[i][j]=r_k$ に書き戻し、今度は行ごとに読み出せば、元の $i$ 番目のRS符号語が復元され、RS復号器に渡せます。

バースト訂正能力の拡大

このインターリーバによって、系全体としてどれだけ長いバースト誤りに耐えられるかを計算してみましょう。伝送路上で $L$ シンボル分の連続したバースト誤りが起きたとします。深さ $I$ のインターリーバでデインターリーブすると、この $L$ シンボルは $I$ 個の符号語に分配され、1つの符号語が受け取る誤りシンボル数は最大で

$$e_{\max} = \left\lceil \frac{L}{I} \right\rceil$$

です。RS復号が保証つきで成功するための条件は $e_{\max} \le t$ なので、これを解くと、確実に訂正可能な最大バースト長(シンボル数)は

$$L_{\max} = I \cdot t$$

ビット数に換算すれば($1$ シンボル $=m$ ビット)、

$$L_{\max}^{\text{(bit)}} = I \cdot t \cdot m$$

たとえば標準的な $(255,223)$ RS符号($t=16$, $m=8$)にインターリーブ深さ $I=4$ を組み合わせると、

$$L_{\max}^{\text{(bit)}} = 4 \times 16 \times 8 = 512\ \text{ビット}$$

もの連続バースト誤りを確実に訂正できる計算になります。インターリーブなし($I=1$)なら $L_{\max}^{\text{(bit)}}=128$ ビットに過ぎないことと比べると、インターリーバがバースト耐性を線形に($I$ 倍に)引き上げていることが分かります。実際のミッション設計では、想定される最悪ケースのフェード継続時間や誤りイベントの集中度を見積もり、それに見合う $I$(CCSDSでは典型的に $I=1,2,3,4,5,8$ 等)を選定します。

符号化利得の積み上げ

最後に、内符号と外符号を連接することで全体としてどれだけの符号化利得(coding gain)、すなわち同じ目標BERを達成するために必要なEb/N0を無符号系に対してどれだけ下げられるか、を見てみましょう。

符号化利得は一般に

$$G_{\text{code}}\ [\text{dB}] = \left(\frac{E_b}{N_0}\right)_{\text{無符号,dB}}\bigg|_{\text{目標BER}} \;-\; \left(\frac{E_b}{N_0}\right)_{\text{符号化,dB}}\bigg|_{\text{目標BER}}$$

と定義されます。連接符号の場合、この利得は単純な足し算にはなりません。RS復号器は、入力されるシンボル誤り率(=内符号+インターリーバ通過後のビタビ出力の質)がある閾値を下回ると、ブロック誤り率が急激に(ほぼ崖のように)ゼロに近づくという**しきい値効果(threshold effect)**を持つからです。つまりRS符号が追加でもたらす利得 $\Delta G_{\text{outer}}$ は、内符号がすでにどれだけ誤りを塊に押し込められているかに強く依存する非線形な効き方をします。

とはいえ、目安として全体の符号化利得を

$$G_{\text{concat}} \approx G_{\text{inner}} + \Delta G_{\text{outer}}$$

の形で捉えることは実務上有用です。CCSDS標準の $(K=7, r=1/2)$ 畳み込み符号+ビタビ軟判定復号は、単体でBER $=10^{-5}$ を達成するのに必要なEb/N0を、無符号BPSKの約9.6 dBから約4.5 dBまで引き下げます。すなわち

$$G_{\text{inner}} \approx 9.6 - 4.5 = 5.1\ \text{dB}$$

ここにインターリーブ深さ $I=5$ 前後の $(255,223)$ RS符号を外符号として連接すると、文献でよく引用される目安の値として、さらに 2 dB前後の追加利得($\Delta G_{\text{outer}} \approx 2$–$2.3$ dB)が得られ、全体として

$$G_{\text{concat}} \approx 7\text{–}7.5\ \text{dB}$$

程度の総符号化利得が、より低いBER(RSの後段検査によりブロック誤りをほぼ払拭できるため、実効的にBER $=10^{-6}$ 程度でも安定動作)で得られることが知られています。数dBの差は些細に聞こえるかもしれませんが、リンクバジェットの世界では意味が違います。3 dBはほぼ「送信電力を2倍にする」「アンテナ開口面積を2倍にする」「距離を約$1/\sqrt2$倍に縮める」のと等価な効果を持つため、2 dBの追加利得は、探査機の重量・電力予算を増やすことなくデータレートを引き上げたり、より遠方のミッションを可能にしたりする、実務上非常に大きな価値を持ちます。

実務での使われ方

連接符号がミッション設計に初めて本格的に組み込まれた歴史的な例が、ボイジャー2号の木星・土星探査から天王星・海王星探査への移行です。当初のボイジャーの誤り訂正は $(K=7, r=1/2)$ 畳み込み符号+ビタビ復号のみでした。しかし木星・土星より遥かに遠い天王星(1986年)・海王星(1989年)フライバイでは、信号がさらに減衰し、同じデータレート・画質を維持するにはリンクマージンが不足することが判明しました。JPLはここで地上局のソフトウェア更新と探査機側の符号化方式変更により、$(255,223)$ RS符号とインターリーバを追加した連接符号へ切り替え、約2 dBの追加符号化利得を確保することで、天王星・海王星の高解像度画像データを実現しました。

ガリレオ探査機はさらに劇的な例です。高利得アンテナ(HGA)が展開に失敗し、代替の低利得アンテナ(LGA)での通信を強いられたため、リンクマージンが当初計画から大幅に不足する事態に陥りました。JPLはこれを補うため、標準の $K=7$ よりもさらに強力な、実験的な拘束長 $K=15$ の畳み込み符号を専用の「ビッグ・ビタビ・デコーダ (Big Viterbi Decoder, BVD)」で復号し、これをRS符号と連接するという、当時としては極限的な符号化構成を採用しました。連接符号の柔軟性(内符号を強化しても外符号の役割は変わらない)がこの危機的な状況を救った代表例としてよく引用されます。

これらの実績を踏まえ、CCSDSは CCSDS 131.0-B (TM Synchronization and Channel Coding) において、$(K=7, r=1/2)$ 畳み込み符号(生成多項式 $G_1=171_8,\ G_2=133_8$)+$(255,223)$ RS符号+ブロックインターリーバ(深さ $I=1,2,3,4,5,8$ から選択)という組み合わせを、深宇宙・地球周回ミッション共通の標準チャネル符号化方式として規定しています。この構成は打ち上げから数十年を経た現在も、多くのミッションでヘリテージ(実績のある枯れた技術)として使われ続けています。

一方で、1993年のターボ符号の発明、およびその後のLDPC(低密度パリティ検査)符号の実用化は、連接符号の世界に大きな転機をもたらしました。RS+畳み込みの連接符号は、シャノン限界に対しておおよそ2〜3 dB程度のギャップを残す設計であるのに対し、ターボ符号やLDPC符号は反復的な軟判定復号によってこのギャップを1 dB未満まで詰めることができます。CCSDSは後にターボ符号(CCSDS 131.0-B改訂版)、さらに長尺LDPC符号を標準に追加し、現代の多くの新規ミッションではこれらがRS+畳み込みの連接符号に取って代わりつつあります。それでも連接符号が完全に姿を消したわけではなく、実装の単純さや長年の運用実績、後方互換性の要求から、今なお現役の選択肢であり続けています。

演習問題

1. $(255,223)$ RS符号($t=16$、$m=8$ ビット/シンボル)にインターリーブ深さ $I=8$ を組み合わせたとき、確実に訂正できる最大の連続バースト誤り長 $L_{\max}^{\text{(bit)}}$ をビット数で求めてください。また、これが $I=4$ の場合と比べて何倍になるか答えてください。

2. インターリーバの伝送順インデックス $k=53$、インターリーブ深さ $I=5$ のとき、この伝送シンボルが行列上のどの位置 $(i,j)$ に対応するか($i=k\bmod I$, $j=\lfloor k/I\rfloor$ を用いて)計算し、これが元のどのRS符号語(何番目)の何シンボル目に相当するか答えてください。

3. ある区間で、ビタビ復号器が8ビットの誤りを出したとします。(a) この8ビットが1つのRSシンボル境界内に完全に収まる場合と、(b) 8個の別々のシンボルに1ビットずつ均等に散らばる場合とで、RS符号の訂正能力 $t=16$ に対する消費量(シンボル誤り数)をそれぞれ求め、どちらがRS符号にとって”安く”つくか説明してください。

4. 畳み込み符号単体で得られる符号化利得を $G_{\text{inner}} \approx 5.1$ dB、RS符号+インターリーブの追加によって $\Delta G_{\text{outer}} \approx 2.2$ dB が上乗せされるとします。この連接符号による総利得 $G_{\text{concat}}$ をリンクバジェット上の「等価な効果」(送信電力比、あるいは通信距離比)に換算して説明してください(3 dBがおおよそ電力2倍、距離 $1/\sqrt2$ 倍に相当することを使ってよい)。

まとめと次回予告

この回では、前々回の畳み込み符号(ビタビ復号後にバースト的な誤りイベントを残す)と、前回のRS符号(シンボル単位でバースト誤りに強い)を、内符号・外符号として直列に連接するアーキテクチャを学びました。ビタビ復号器の誤りが塊になっているという性質そのものはRS符号にとってむしろ好都合であること、しかし局所的な誤りの偏りを均すためにインターリーバが不可欠であること、そしてブロックインターリーバの深さ $I$ がバースト訂正能力を $I$ 倍に線形拡大する仕組みを、それぞれ数式で確認しました。CCSDS標準の $(K=7,r=1/2)$畳み込み+$(255,223)$RS+インターリーブという組み合わせが、ボイジャーの天王星・海王星探査やガリレオのアンテナ故障克服といった歴史的なミッションを支えてきたこと、そして総符号化利得がおよそ7〜7.5 dBに達することも見ました。

しかし連接符号にも限界があります。RS+畳み込みの構成はシャノン限界に対して依然として2〜3 dB程度のギャップを残しており、このギャップを詰めるために1993年に登場したのがターボ符号 (turbo code) です。次回は、2つの畳み込み符号器を並列に組み合わせ、軟判定情報を繰り返し交換しながら復号を洗練させていく「反復復号」という全く新しい発想を、連接符号との対比で見ていきます。

参考文献

• CCSDS 131.0-B, TM Synchronization and Channel Coding
• CCSDS 130.1-G, Overview of Space Communications Protocols (Green Book)
• G. D. Forney Jr., Concatenated Codes, MIT Press, 1966
• J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76
• S. B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice Hall
• B. Sklar, Digital Communications: Fundamentals and Applications, 2nd ed., Prentice Hall
• DSN Telecommunications Link Design Handbook, DSN No. 810-005(Channel Codingに関するモジュール)