変調・符号化#125

インターリーバ設計論 — ブロック型・畳み込み型・疑似ランダム型を使い分ける

連接符号のバースト誤り分散に使ったブロックインターリーバは、インターリーバ設計の一断面に過ぎない。畳み込みインターリーバのメモリ・遅延トレードオフ、ターボ符号のSランダムインターリーバがエラーフロアを下げる理由、CCSDS標準のパラメータを数式で整理する。

前提知識: 連接符号 — 畳み込み符号とリード・ソロモン符号を直列につなぐ古典アーキテクチャ、ターボ符号 — 並列連接畳み込み符号と反復復号でシャノン限界に迫る

インターリーバターボ符号SランダムCCSDS符号設計

この回で学ぶこと

連接符号の回で、私たちはブロック(行列型)インターリーバを導入しました。RS符号語を $I$ 個束ねて $I \times n$ の行列に書き込み、列方向に読み出すことで、ビタビ復号器が残す塊状の誤りを $I$ 個の符号語に均等にばら撒く——という仕組みでした。あの回では、深さ $I$ を大きくすればバースト耐性が $I$ 倍に線形拡大するところまで、具体的な入出力対応式とともに確認しました。

しかし、あれは「インターリーバ」という設計対象のごく一部でしかありません。実際にCCSDS標準やターボ符号の実装を見渡すと、インターリーバには行列型以外にも畳み込みインターリーバ、擬似ランダムインターリーバ、Sランダムインターリーバといった多様な設計があり、それぞれ全く異なる動機と数理を持っています。特にターボ符号の回では「並列連接畳み込み符号にインターリーバ $\pi$ を挟む」と述べましたが、あそこで使われているインターリーバは、連接符号のブロックインターリーバとは目的そのものが違う道具です。

この回では、インターリーバという設計対象を一段階抽象化し、(1) インターリーバが果たしうる役割を整理し直し、(2) 畳み込みインターリーバとブロックインターリーバのメモリ・遅延のトレードオフを数式で比較し、(3) ターボ符号で使われる擬似ランダムインターリーバ・Sランダムインターリーバがなぜ性能(特にエラーフロア)を左右するのかを見ていきます。

直感的な導入 — インターリーバは「並べ替え」以上の設計対象

インターリーバの動作そのものは単純です。入力シンボル(あるいはビット)の列 $\{c_k\}_{k=1}^{N}$ に対して、ある全単射(置換) $\pi: \{1,\dots,N\} \to \{1,\dots,N\}$ を適用し、

t_k = c_{\pi(k)}

という並べ替えられた列 $\{t_k\}$ を作って伝送する。受信側では逆置換 $\pi^{-1}$ を使って元の順序に戻す。原理はこれだけです。

しかし「 $\pi$ をどう選ぶか」という一点に、驚くほど多様な設計思想が詰め込まれています。ブロックインターリーバの $\pi$ は「行列に書いて列で読む」という規則的な写像でしたが、これから見るように、 $\pi$ を規則的な写像にするか、擬似ランダムな写像にするかで、達成できる目的そのものが変わってきます。まずはインターリーバが果たしうる役割を、これまで学んだ2つの文脈に沿って整理し直しましょう。

インターリーバの2つの役割の再整理

役割1: バースト誤りの分散(拡散)

連接符号の回で見た役割です。伝送路上、あるいは内符号の復号後に生じる時間的に集中した誤りの塊を、複数の符号語に均等に分配し直すことで、1つの符号語が受け取る誤り数を減らします。ここで重要なのは、 $\pi$ に求められる性質が「近接していたシンボルを、伝送順あるいは符号語割り当て上、互いに遠ざける」という、決定論的かつ規則的な保証だという点です。ブロックインターリーバの列読み出しは、この保証を厳密な数式( $k \bmod I$ の周期性)で与えてくれるからこそ、 $L_{\max}=I\cdot t$ というバースト耐性の下限を確定的に導出できました。ここではランダム性は不要で、むしろ規則性のほうが解析しやすく好都合です。

役割2: 疑似ランダム化による復号器間の相関除去

ターボ符号の回で扱った文脈です。並列連接畳み込み符号(PCCC)では、同じ情報ビット列 $\mathbf{u}$ を2つの再帰的組織畳み込み符号器(RSC1, RSC2)にそれぞれ異なる順序で通します。RSC1には $\mathbf{u}$ をそのまま、RSC2には $\pi(\mathbf{u})$ を通す、という構成でした。

このときインターリーバに求められる性質は、役割1とはまったく異なります。目的は「バーストを分散させる」ことではなく、「RSC1にとって訂正しづらい(低重み出力を生みやすい)入力パターンが、RSC2にとっても同時に訂正しづらいパターンになる確率を下げる」ことです。RSC1とRSC2は同じ構造の符号器なので、もし $\pi$ が単純な規則的写像(たとえば行列型)だったら、周期的な入力パターンに対して両方の符号器が同時に低重み出力を出してしまう「相性の悪いケース」が、規則性ゆえにむしろ系統的に発生しやすくなります。これを避けるには、 $\pi$ が入力の周期的・規則的な構造を徹底的に崩す、すなわち擬似ランダムであることが本質的に重要になります。

まとめると、同じ「インターリーバ」という名前の道具でも、

	役割1(連接符号)	役割2(ターボ符号)
目的	バースト誤りの分散	復号器間の相関除去
求められる $\pi$ の性質	規則的・周期的でよい	疑似ランダムであるべき
設計の主眼	深さ $I$ の最適化	距離制約・ランダム性の質

という、目的と設計原理が根本的に異なる2つの問題であることを、まず明確にしておきます。以下ではこの2つの役割それぞれについて、代表的な実装を数式で見ていきます。

畳み込みインターリーバ — 役割1をより少ないメモリで実現する

ブロックインターリーバは実装が単純である一方、 $I \times n$ 行列全体を書き込んでから読み出す構造上、行列1枚分をまるごと溜め込んでから動かすという無駄があります。これに対し G. D. Forney が示した**畳み込みインターリーバ(convolutional interleaver)**は、シフトレジスタの段数を系統的にずらすことで、同等のバースト耐性をより少ないメモリ・遅延で達成する構成です。

構造

$J$ 本の枝(ブランチ)を持つシフトレジスタ群を用意し、枝 $j$ ( $j = 0, 1, \dots, J-1$ ) には長さ $jB$ シンボル分の遅延素子を並べます( $B$ は基本遅延単位、枝ごとに $B$ シンボルずつ遅延段数が増えていく設計)。入力側のコミュテータ(回転スイッチ)は、シンボルが1つ来るたびに枝を $0 \to 1 \to \cdots \to J-1 \to 0 \to \cdots$ と順に切り替えながら送り込みます。

\text{時刻 } k \text{ の入力シンボル } c_k \ \longrightarrow\ \text{枝 } j = k \bmod J \ \text{へ投入}

枝 $j$ に入ったシンボルは $jB$ シンボル時間分だけ遅延され、出力側の(入力側と同期して回転する)コミュテータによって読み出されます。つまり枝番号が大きいほど長く足止めされるわけです。受信側のデインターリーバはこれと相補的な構造を持ちます——枝 $j$ の遅延を $(J-1-j)B$ とした、いわば「遅延が逆順」の同じ仕組みを置くことで、トータルの(インターリーバ+デインターリーバの)遅延をどの枝についても揃え、元の順序を復元します。

バースト分散の効果

この構成により、伝送順で隣り合う2つのシンボル $c_k, c_{k+1}$ は異なる枝(遅延量が $B$ シンボル分違う)を通るため、送出されるタイミングが引き離されます。枝の遅延差が $B$ シンボルずつ規則的に増えていく設計により、元の時系列上で近接していたシンボルほど、伝送列上では大きく引き離されて現れる、というブロックインターリーバと同種の分散効果が得られます。

メモリ・遅延のトレードオフ

ここが畳み込みインターリーバの核心的な利点です。インターリーバ単体が保持しなければならない遅延素子の総数(メモリ量)は、各枝の遅延段数の総和で決まります。

M_{\text{conv}} = \sum_{j=0}^{J-1} jB = B\cdot\frac{J(J-1)}{2}

一方、深さ $I$ でシンボル長 $n$ の行列を使うブロックインターリーバは、行列そのものを1枚まるごと保持する必要があるため、

M_{\text{block}} = I \cdot n

のメモリを要します(さらに、受信側で元に戻すデインターリーバにも同量のメモリが要る点は両方式で共通です)。両者を、同程度のバースト誤り分散能力が得られるようにパラメータを揃えて比較すると(目安として $J \approx I$ 、 $B \approx n/I$ と選んだとき)、

M_{\text{conv}} \approx B\cdot\frac{J(J-1)}{2} \approx \frac{n}{I}\cdot\frac{I(I-1)}{2} = \frac{(I-1)n}{2} \approx \frac{M_{\text{block}}}{2}

すなわち畳み込みインターリーバは、同等の性能をおよそ半分のメモリで達成できるというのが、Forneyによって示された古典的な結果です。処理遅延についても同様の比が成り立ち、ブロックインターリーバは行列を1枚まるごと埋めてから読み出す必要があるため往復で $2In$ シンボル時間程度の遅延が生じるのに対し、畳み込みインターリーバは枝ごとに遅延が分散しているため、往復の総遅延がおよそ半分の $(J-1)B \approx (I-1)n/I$ 程度に収まります。

この差は、搭載機器のメモリ・電力資源が限られる探査機や、往復遅延が数十分〜数時間に及ぶ深宇宙リンクにおいて処理遅延そのものを詰めたい場合に、無視できない実務的価値を持ちます。一方でブロックインターリーバには「行列という構造が直感的で、深さ $I$ を可変にする設計変更が容易」「バースト耐性 $L_{\max}=I\cdot t$ の導出が単純明快」という実装・解析上の利点があるため、CCSDSの連接符号標準では歴史的にブロック型が採用されています。畳み込みインターリーバは、メモリ・遅延を切り詰めたい通信システム(地上の光ファイバー伝送や一部の衛星通信規格など)でしばしば選ばれる、もう一つの古典的選択肢と位置づけられます。

疑似ランダムインターリーバとSランダムインターリーバ — 役割2を実現する

続いて、ターボ符号の文脈で必要になる「疑似ランダム化」の設計に移ります。単純に乱数表を1つ引いて $\pi$ を作るだけでも、規則的な写像よりはずっとましですが、それだけでは不十分です。純粋にランダムな置換は、確率的にはまれであっても「隣接していた2つのビットが、インターリーブ後も依然として近くに来てしまう」という配置を許してしまいます。これがなぜ問題なのかを見てみましょう。

なぜ「近接ビットが近接のまま」だと困るのか

RSC符号器は有限状態機械であり、その出力重み(パリティに現れる1の個数)は、入力パターンの局所的な構造——特に、孤立した少数の1が互いにどれだけ近い間隔で現れるか——に強く依存します。重みの小さい入力パターン(たとえば「0が続く中に1が2つだけ、近い間隔で現れる」パターン)は、RSC1にとって低重みの出力を生みやすい、いわば「相性の悪い」入力です。

もしインターリーバ $\pi$ が、この2つの近接した1をインターリーブ後もやはり近接させたままにしてしまうと、RSC2から見た入力(すなわち $\pi(\mathbf{u})$ )でも同じ低重みパターンが再現され、RSC1とRSC2が同時に低重みの出力を出してしまうという最悪の事態が起こります。ターボ符号の回で触れたエラーフロアの主因は、まさにこの「両方の構成符号が同時に騙される」低重み誤り事象でした。したがって、インターリーバ設計の目標は明快です——入力列上で近接していたビット対は、インターリーブ後も近接させないことです。

Sランダムインターリーバ

この目標を明示的な制約として組み込んだ設計がSランダムインターリーバ(S-random interleaver)です。長さ $N$ の置換 $\pi$ が距離パラメータ $S$ に関してSランダムであるとは、任意の2つの入力位置 $i \neq j$ について、

|i - j| \le S \ \Longrightarrow\ |\pi(i) - \pi(j)| > S

が成り立つことを言います。つまり「元の列で $S$ 以内に近接していたどの2ビットも、インターリーブ後は必ず $S$ より遠く離れる」という条件です。この条件を満たす $\pi$ は、次のような貪欲アルゴリズムで構成できます。

位置 $1, 2, \dots, N$ を順に埋めていく。位置 $k$ の割り当て候補としてランダムに $\pi(k)$ の値を1つ選ぶ。
既に確定済みの $\pi(k-S), \dots, \pi(k-1)$ (直近 $S$ 個)のいずれとも、候補値との差が $S$ を超えているかを確認する。
条件を満たさなければ候補を引き直す。満たすまで繰り返し、満たしたら確定して次の位置に進む。

$S$ を大きく取るほど「近接ビットを遠ざける」保証は強くなりますが、 $N$ が有限である以上 $S$ には上限があります。値を大きくしすぎると、上記アルゴリズムのステップ3で条件を満たす候補がなかなか見つからず、構成そのものが破綻(デッドロック)しやすくなるため、実用上は

S \sim \sqrt{\frac{N}{2}}

程度が目安として使われます。たとえば $N=8920$ ビット(CCSDSターボ符号の最大情報ブロック長の1つ)であれば $S \sim \sqrt{4460} \approx 67$ 程度が一つの目安になります。

Sランダムインターリーバは、あらゆる低重み入力パターンに対する保証を与えるわけではありませんが、少なくとも距離の近い低重みパターン(実務上、支配的なエラーフロア要因となることが多いクラス)を体系的に排除できるため、単純な一様乱数インターリーバよりも一貫してエラーフロアを下げる効果が確認されています。インターリーバ長 $N$ が大きいほど、ターボクリフの位置(ウォーターフォール領域が始まる $E_b/N_0$ )がシャノン限界に近づくことは前回見た通りですが、それとは独立に、エラーフロアの高さは主にこのSランダム性(あるいはそれに準じた距離制約の質)によって決まる、という役割分担を押さえておくことが重要です。

実務での使われ方

CCSDSにおけるブロックインターリーバの深さ

連接符号の回で見た通り、CCSDS 131.0-Bの $(255,223)$ RS符号+畳み込み符号の連接方式では、ブロックインターリーバの深さとして $I=1,2,3,4,5,8$ が規定されています。ミッション設計者は、想定される最悪ケースのフェード継続時間(太陽合、アンテナのマスク角通過、姿勢変化によるアンテナパターン null 通過など)から必要なバースト耐性 $L_{\max}=I\cdot t\cdot m$ を見積もり、それを満たす最小の $I$ を選びます。インターリーブ深さを上げるほどバースト耐性は線形に向上しますが、行列を埋めてから読み出す構造上、処理遅延(往復で概ね $2In$ シンボル時間)も比例して増大します。深宇宙探査機のテレメトリのように片道遅延がすでに数分〜数時間ある回線では、この追加遅延は相対的には無視できることが多い一方、近地球のリアルタイム運用(有人ミッションの音声・映像通信やクリティカルコマンドの応答確認など)では、インターリーブ深さの選択がそのまま体感遅延に直結するため、深さは必要最小限に抑える設計判断がなされます。

CCSDSターボ符号のインターリーバ

CCSDS標準ターボ符号(CCSDS 131.0-B)は、情報ブロック長 $N=1784,\ 3568,\ 7136,\ 8920$ ビットの4種類をサポートすることを前回見ました。これらの各ブロック長に対して、CCSDS標準は個別に定義された疑似ランダムインターリーバ(ブロック長ごとに固定された置換規則)を規定しています。単純な一様乱数表ではなく、Sランダム的な距離制約に類する規則性を織り込んだ構成的なアルゴリズムによって生成されており、これにより標準に準拠する送信機・受信機の双方が、同じ置換を再現可能な形で(乱数表を送受信間で共有する必要なく)実装できるようになっています。ブロック長が大きいほど(すなわち $N=8920$ に近いほど)ターボクリフの位置がシャノン限界に近づく一方、復号に必要なブロック全体を受信し終えるまでの待ち時間(BCJRアルゴリズムの逐次性に起因する遅延、前回参照)も比例して増大するため、ミッションのデータレートと許容遅延に応じてブロック長が選択されます。

演習問題

畳み込みインターリーバにおいて $J=6$ 本の枝、基本遅延 $B=20$ シンボルとしたとき、インターリーバ単体が必要とするメモリ量 $M_{\text{conv}}$ (遅延素子の総数)を求めてください。また、同程度の性能を狙う深さ $I=6$ のブロックインターリーバ(シンボル長 $n$ は $B\approx n/I$ の関係から逆算)のメモリ量 $M_{\text{block}}$ を求め、両者の比を確認してください。
Sランダムインターリーバの定義 $|i-j|\le S \Rightarrow |\pi(i)-\pi(j)|>S$ について、長さ $N=10$ 、 $S=2$ の短い置換の一部として $\pi(3)=7$ が既に決まっているとします。次に位置 $\pi(4)$ を決めようとするとき、候補値のうちどの範囲の値が禁止されるか(Sランダム条件に違反するか)を、 $\pi(3)$ との関係から求めてください。
ターボ符号のインターリーバに、もし単純な行列型(ブロック)インターリーバをそのまま流用したとします。RSC1にとって低重み出力を生みやすい周期的な入力パターン(たとえば一定間隔で1が現れるパターン)があったとき、行列型インターリーバの規則性がなぜRSC2でも同種の低重みパターンを再現しやすくしてしまうのか、この回で学んだ内容をもとに説明してください。
深宇宙探査機のテレメトリ回線(片道遅延が数分〜数時間)と、有人ミッションの近地球音声通信回線(片道遅延が1秒未満であることが望ましい)とで、ブロックインターリーバの深さ $I$ の選び方の方針がどう変わるべきか、処理遅延とバースト耐性のトレードオフの観点から論じてください。

まとめと次回予告

この回では、連接符号の回で扱ったブロックインターリーバが、インターリーバ設計というより大きな問題の一断面に過ぎないことを出発点に、インターリーバが果たしうる2つの異なる役割——バースト誤りの分散(連接符号)と、疑似ランダム化による復号器間の相関除去(ターボ符号)——を整理しました。前者に対しては、ブロックインターリーバよりも少ないメモリ・遅延で同等の性能を達成できる畳み込みインターリーバの構造とトレードオフを、後者に対しては、近接ビットがインターリーブ後も近接し続けることを明示的に禁じるSランダムインターリーバが、なぜターボ符号のエラーフロアを下げるのかを数式で確認しました。CCSDS標準では、連接符号ではブロック深さ $I=1,2,3,4,5,8$ が、ターボ符号ではブロック長ごとに固定された疑似ランダムインターリーバが、それぞれ異なる設計原理のもとで規定されていることも見ました。

次回は視点を少し変え、有人ミッションにおける音声通信という、これまでのテレメトリ・データ中心の議論とは異なる制約(超低遅延・可変レート・人間の聴覚特性)を持つ通信の話題に触れていきます。

参考文献

G. D. Forney Jr., “Burst-Correcting Codes for the Classic Bursty Channel,” IEEE Transactions on Communications, vol. 19, no. 5, 1971.
J. L. Ramsey, “Realization of Optimum Interleavers,” IEEE Transactions on Information Theory, vol. 16, no. 3, 1970.
S. Dolinar, D. Divsalar, “Weight Distributions for Turbo Codes Using Random and Nonrandom Permutations,” TDA Progress Report 42-122, JPL, 1995.
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