変調・符号化#176

BICM — 符号化と変調を疎結合のまま反復で結び直す

TCMのように符号と変調を一体設計する代わりに、符号化→インターリーブ→マッピングという単純な直列パイプラインで構成するBICM(Bit-Interleaved Coded Modulation)を扱う。グレイマッピングとビット単位LLR、そして復号器とデマッパーの間でLLRを交換するBICM-IDの反復構造を数式で追い、DVB-S2/S2XやCCSDSでの採用理由を見る。

前提知識: LDPC符号 — 疎な検査行列とメッセージパッシングでシャノン限界に迫る、APSK — 高次変調と非線形増幅器を両立させる同心円配置

BICMLLR反復デマッピンググレイマッピングDVB-S2

この回で学ぶこと

TCM(トレリス符号化変調)の回では、Ungerboeckが1982年に示した衝撃的な発想——符号化と変調を別々の段階として設計するのではなく、セット分割によって信号点集合とトレリスの枝を一体で設計することで、帯域幅を増やさずに符号化利得を得る——を学びました。TCMは電話回線モデムや帯域制限の強い衛星回線で大きな成功を収めましたが、そこには代償がありました。符号化率を変えたければトレリス構造とセット分割を設計し直す必要があり、変調多値数を変えればまたゼロから設計し直しです。符号と変調が密結合しているということは、片方を変えればもう片方も一緒に作り直さねばならないということです。

一方、LDPC符号の回で見たように、1990年代半ば以降の誤り訂正符号の主役はターボ符号・LDPC符号のような、シャノン限界に迫る強力な符号化に移りました。これらの符号は数千〜数万ビット規模の長い符号語を使い、 $E_b/N_0$ をできるだけ低く抑えて動作させることを目的として設計されています。TCMのように「符号化と変調を同じトレリス上で一体設計する」というアプローチは、こうした長く複雑な現代符号と組み合わせようとすると設計空間が爆発的に複雑になり、実務上ほとんど現実的ではありません。

この回で扱う BICM (Bit-Interleaved Coded Modulation, ビット交番符号化変調) は、この問題に対する実務的な解答です。発想はTCMとは正反対で、符号化・インターリーブ・マッピングをあえて疎結合な3段の直列パイプラインとして構成することにあります。

\underbrace{\text{情報ビット}}_{} \;\xrightarrow{\ \text{符号化}\ }\; \underbrace{\text{符号化ビット}}_{} \;\xrightarrow{\ \text{インターリーブ}\ }\; \underbrace{\text{並べ替え後のビット}}_{} \;\xrightarrow{\ \text{マッピング}\ }\; \underbrace{\text{多値シンボル}}_{}

一見すると、これはTCM以前の「符号化と変調を独立に設計する」古い枠組みへの単純な先祖返りに見えます。しかし実際にはBICMは、(1) ldpc.mdで学んだLLRベースの反復復号器にそのまま接続できるビット単位の対数尤度比(LLR)計算という橋渡しの仕組み、(2) 復号器からの事後情報を使ってデマッパーの精度を反復的に高める**BICM-ID(反復デマッピング)**という仕組みを備えることで、密結合設計であるTCMに劣らない性能を、はるかに柔軟な設計自由度で実現します。この回では、なぜ「疎結合」がむしろ実務上の強みになるのか、そしてビット単位LLRと反復デマッピングという2つの数式的な柱を順に見ていきます。

直感的導入 — なぜ疎結合が「手抜き」ではなく強みになるのか

TCMを振り返ると、その設計プロセスは次のようなものでした。目標の符号化利得・多値数・トレリス状態数を決め打ちし、Ungerboeckのセット分割規則に従って信号点とトレリス枝の対応表を作り、その対応表全体をビタビ復号器に埋め込みます。符号化率を $R_c=2/3$ から $R_c=3/4$ に変えたい、あるいは変調を8PSKから16APSKに変えたいとなれば、この対応表を作り直すところからやり直しです。つまり**「どの誤り訂正符号を使うか」と「どの変調方式を使うか」という2つの設計選択が、1つの結合したトレリスの中に溶け込んでしまっている**のです。

BICMはこの2つの選択を、パイプラインの中の独立した2つの部品として切り離します。

符号化器は、多値シンボルのことなど何も知らずに、単に情報ビット列に対して符号化率 $R_c$ のLDPC符号(なりターボ符号なり)をかけるだけです。
マッパーは、符号化ビット列がどんな符号から来たかなど気にせず、単にビットを $M=2^m$ 点のコンステレーションのシンボルに割り当てるだけです。
両者の間に挟まるインターリーバは、単に符号化ビットの並び順をランダムに(あるいは擬似ランダムに)シャッフルするだけです。

この分離のおかげで、符号化率 $R_c$ と変調多値数 $m=\log_2 M$ は、互いに独立な2つのパラメータとして自由に選べるようになります。DVB-S2の規格書を見ると、符号化率だけで1/4から9/10まで11通り、変調方式もQPSK・8PSK・16APSK・32APSKと4通りあり、実質的にその組み合わせの多くがそのまま使用可能です。これをTCMのように一体設計しようとすれば、組み合わせの数だけトレリス構造を作り直す必要があり、標準規格として現実的な選択肢ではありません。BICMは「符号化と変調をあえて疎結合のまま」にすることで、この設計の組み合わせ爆発を避け、モジュール化された実装を可能にしているのです。

もっとも、疎結合にしただけでは代償もあります。符号化ビットの並び順をインターリーバでシャッフルしてしまうと、TCMが利用していた「符号化ビットの依存構造と信号点配置の幾何構造を同時に最適化する」という情報が失われ、単純な「符号化して、独立にマッピングするだけ」では、TCMほどの利得を引き出せません。この失われた性能を取り戻すのが、次節以降で見るグレイマッピングと**反復デマッピング(BICM-ID)**です。

数式定式化1: グレイマッピングとビット単位LLR

$M=2^m$ 点のコンステレーションでは、各シンボル $s$ に長さ $m$ のビットラベル $b_1 b_2 \cdots b_m$ が割り当てられます。APSKの回で見たような多値変調では、1つのシンボル誤り(隣接点への取り違え)が、ビットラベルの上で何ビットの誤りを引き起こすかは、ラベルの割り当て方によって変わります。グレイ符号(Gray code)マッピングとは、コンステレーション上で隣接する(ユークリッド距離が最小の)信号点同士のビットラベルが、常にちょうど1ビットだけ異なるように設計されたラベル割り当てです。

雑音によって受信点が最近傍の誤った信号点へずれてしまう「最も起こりやすい誤り方」を考えると、グレイマッピングのもとではこの誤りは常に1ビットのハミング距離しか生みません。これに対し非グレイなマッピング(たとえば単純な2進数順)では、隣接点同士のラベルが2ビット以上異なることがあり、1回のシンボル誤りが複数ビットの誤りに波及してしまいます。BICMでは符号化ビットが後段のインターリーバでバラバラの位置に散らされるため、TCMのように「特定のビットの誤りやすさをトレリス構造で吸収する」余地がありません。したがってグレイマッピングによってビット単位の誤りやすさをできるだけ均一かつ最小に抑えておくことが、BICMの受信性能を左右する重要な設計原則になります。

次に、この多値シンボルから各ビットのLLRを取り出す仕組みを定式化します。 $M=2^m$ 点のコンステレーション $\mathcal S = \{s_0, \dots, s_{M-1}\}$ があり、シンボル $s$ が受信雑音 $n \sim \mathcal N(0,\sigma^2)$ (複素AWGNの場合は各軸独立に分散 $\sigma^2$ )を受けて

r = s + n

として受信されるとします。ビットラベルの $k$ 番目の位置( $k=1,\dots,m$ )の値を $b_k \in \{0,1\}$ とし、 $\mathcal S_k^{(0)}, \mathcal S_k^{(1)}$ をそれぞれ「 $k$ 番目のビットラベルが0であるような信号点の部分集合」「1であるような部分集合」とします( $\mathcal S = \mathcal S_k^{(0)} \cup \mathcal S_k^{(1)}$ 、各部分集合は $M/2$ 点)。ldpc.mdで導入したLLRの定義と同じ形で、ビット $b_k$ のLLRは

L(b_k) \;=\; \ln \frac{P(b_k=0 \mid r)}{P(b_k=1 \mid r)}

と定義されます。ベイズの定理により $P(b_k=i\mid r) \propto P(r\mid b_k=i)\,P(b_k=i)$ なので、事前確率が等確率( $P(b_k=0)=P(b_k=1)=1/2$ )であれば

L(b_k) = \ln \frac{P(r \mid b_k=0)}{P(r \mid b_k=1)}

となります。ここで $P(r\mid b_k=i)$ は、ラベルの $k$ 番目が $i$ であるという条件のもとで、その部分集合 $\mathcal S_k^{(i)}$ に属する各信号点からの尤度をすべて足し合わせた(周辺化した)ものです。

P(r \mid b_k=i) = \sum_{s \in \mathcal S_k^{(i)}} P(s)\, p(r\mid s) = \frac{1}{M/2}\sum_{s \in \mathcal S_k^{(i)}} \frac{1}{2\pi\sigma^2}\exp\!\left(-\frac{|r-s|^2}{2\sigma^2}\right)

これらをまとめると、ビット単位LLRの厳密な(exactな)表式が得られます。

\boxed{L(b_k) = \ln \frac{\displaystyle\sum_{s \in \mathcal S_k^{(0)}} \exp\!\left(-\dfrac{|r-s|^2}{2\sigma^2}\right)}{\displaystyle\sum_{s \in \mathcal S_k^{(1)}} \exp\!\left(-\dfrac{|r-s|^2}{2\sigma^2}\right)}}

この式が、多値シンボルという「密な」表現から、ビットごとに独立した「疎な」LLR表現への変換を担っています。1つの受信シンボル $r$ から $m$ 個のLLR $L(b_1),\dots,L(b_m)$ が計算され、これがそのままldpc.mdのSum-Product復号アルゴリズムにおける通信路LLR $L_{\mathrm{ch},i}$ の入力列(インターリーブを逆順に戻した上で)になります。まさにここが「マッピング(信号空間側)」と「符号化(ビット領域側)」という疎結合な2つの世界を橋渡しする、BICMの中核の数式です。

実務上、この和の形の厳密なLLR計算は $M$ が大きくなると指数関数の和が必要になり計算量が増えるため、max-log近似がよく使われます。指数関数の和は最大項が支配的であるという近似 $\ln\sum_i e^{x_i} \approx \max_i x_i$ を使うと、

L(b_k) \approx \frac{1}{2\sigma^2}\left(\min_{s\in \mathcal S_k^{(1)}} |r-s|^2 \;-\; \min_{s\in \mathcal S_k^{(0)}} |r-s|^2\right)

となり、和の計算が「部分集合内で最も近い信号点を探す」という単純な最小値探索に置き換わります。この近似は性能劣化がわずか(典型的に0.1〜0.3 dB程度)である一方、ハードウェア実装の負荷を大きく下げるため、実際のBICM受信機の多くがこのmax-log LLRを採用しています。

数式定式化2: 反復デマッピング(BICM-ID)の仕組み

前節のLLR計算は、シンボルの各ビットについて「他のビットが0/1のどちらであるか全く分からない」という前提(等確率の事前分布)を置いていました。しかし実際には、 $k$ 番目以外のビット $b_1,\dots,b_{k-1},b_{k+1},\dots,b_m$ についても、復号器が生成する事後LLRという形で、ある程度の確信度を持つ情報が存在します。この情報をデマッパーに「フィードバックして使い回す」ことで、LLR計算の精度を反復的に改善しようというのが BICM-ID (BICM with Iterative Decoding, 反復復号付きBICM) です。

これは構造として、LDPC符号の回で見たチェックノード・変数ノード間のメッセージ交換や、等化器と復号器の間でLLRを交換する turbo-equalization(ターボ等化) の考え方と全く同じ形をしています。turbo-equalizationでは「等化器」と「復号器」という2つのモジュールがLLRをやり取りしましたが、BICM-IDではこの片方が「シンボルデマッパー」に置き換わるだけで、情報をやり取りする構造そのものは同一です。

事前情報を使ったLLR計算式

まず、 $k$ 番目以外のビット $b_j$ ( $j\neq k$ )それぞれについて、復号器側から得られた事前LLR $L_a(b_j)$ があるとします。ここから、 $b_j$ の事前確率を

P(b_j = 0) = \frac{e^{L_a(b_j)}}{1+e^{L_a(b_j)}}, \qquad P(b_j=1) = \frac{1}{1+e^{L_a(b_j)}}

と表せます(LLRの定義から直接導かれるロジスティック関数の形です)。信号点 $s$ に対応するビットラベル $(b_1,\dots,b_m)$ の各ビットが独立であると仮定すると、その信号点の事前確率は

P(s) = \prod_{j\neq k} P(b_j)

で与えられます。これを使って、前節の等確率を仮定した式を一般化し、事前確率で重みづけしたLLR計算式が得られます。

\boxed{L_D(b_k) = \ln \frac{\displaystyle\sum_{s \in \mathcal S_k^{(0)}} P(s)\, \exp\!\left(-\dfrac{|r-s|^2}{2\sigma^2}\right)}{\displaystyle\sum_{s \in \mathcal S_k^{(1)}} P(s)\, \exp\!\left(-\dfrac{|r-s|^2}{2\sigma^2}\right)}}

事前情報が全くない( $L_a(b_j)=0$ 、すなわち $P(b_j)=1/2$ )場合、この式は前節の等確率の式にちょうど一致します。 $|L_a(b_j)|$ が大きい(確信度が高い)ほど、その部分集合内で $b_j$ の値と矛盾する信号点の重みが小さくなり、デマッパーはより「絞り込まれた」精度の高いLLRを出力できます。

復号器とデマッパーの間のLLR交換ループ

このLLR計算をターボ等化と同じ形の反復ループに組み込みます。 $b_k$ 自身の事前情報 $L_a(b_k)$ (その反復で復号器から返ってきた値)を差し引いた外部情報だけを次段に渡すのがポイントで、LDPC符号のチェックノード・変数ノード更新式で「自分自身の情報を除く」ことで自己参照を避けたのと全く同じ理由によります。

L_e(b_k) = L_D(b_k) - L_a(b_k)

この $L_e(b_k)$ を、インターリーバの逆順(デインターリーブ)を経て符号語のビット順に並べ直し、LDPC(あるいはターボ)復号器への通信路LLR入力とします。復号器は自身の反復(たとえばLDPCのSum-Product復号)を何回か回した後、各符号化ビットについての事後LLRを出力し、そこから復号器自身が使った入力(外部情報の原則により)を差し引いた事後-事前の外部情報を、今度はインターリーブし直してデマッパーに事前情報 $L_a(b_j)$ として送り返します。

反復デマッピングの手順をまとめると、次のようになります。

初回反復: 事前情報なし( $L_a=0$ )でLLR $L_D(b_k)$ を計算し、デインターリーブして復号器へ渡す。
復号器が(たとえばLDPCなら数回のSum-Product反復を経て)各ビットの外部情報を出力する。
復号器の出力をインターリーブし直し、デマッパーへの事前情報 $L_a(b_j)$ として供給する。
デマッパーが $L_D(b_k)$ を式のとおり再計算し(今回は事前情報つき)、外部情報 $L_e(b_k) = L_D(b_k)-L_a(b_k)$ をデインターリーブして再び復号器へ渡す。
あらかじめ定めた反復回数に達するか、復号が収束するまでステップ2〜4を繰り返す。

各反復で復号器がより確信度の高い外部情報をデマッパーに供給できるようになると、デマッパーはコンステレーション上の「怪しい部分集合」をより正確に絞り込めるようになり、 $L_D(b_k)$ の精度が上がります。これがまた復号器の入力精度を上げ……という好循環がBICM-IDの反復構造です。特に、グレイマッピングでない(あえて非グレイに設計した)コンステレーションを使うと、初回反復でのビット間の誤りやすさは劣化する代わりに、反復が進むにつれてビット間の相関構造をより強く利用できるようになり、十分な反復回数の後にはグレイマッピングを上回る性能に達することがある——という設計上のトレードオフも知られています。ただし多くの実用システムでは、実装の単純さと初回反復での性能の良さを優先し、グレイマッピング+わずかな反復(あるいは反復なし)という構成が広く使われています。

なぜBICMがTCMより柔軟か

ここまでの数式を踏まえて、BICMとTCMの設計自由度の違いを整理します。

符号化率と変調多値数が独立: BICMでは符号化器・インターリーバ・マッパーが完全に独立したモジュールなので、符号化率 $R_c$ を変えたければ符号化器だけを差し替え、変調多値数 $m$ を変えたければマッパーだけを差し替えれば済みます。TCMでは符号化率と多値数の組み合わせごとにセット分割とトレリス割り当てを再設計する必要があり、 $R_c$ と $m$ が事実上一体化しています。
強力な現代符号との親和性: BICMのビット単位LLRは、ldpc.mdで見たSum-Product復号やターボ復号のような、LLRを入力とする現代の反復復号器にそのまま接続できます。TCMのビタビ復号はユークリッド距離をブランチメトリックとする専用構造であり、LDPC・ターボ符号のような長い符号語との統合は現実的ではありません。
符号化率の刻みの自由度: LDPC符号は符号化率をパンクチャリング(一部のパリティビットを間引く)や複数の検査行列の用意によって、1/4から9/10まで細かく刻めます。BICMではこの符号化率の刻みが、マッパー側の設計を一切変えずにそのまま活かせます。
適応符号化変調(ACM)との相性: リンク品質(受信SNR)の変動に応じて符号化率や変調方式をリアルタイムに切り替えるACM(Adaptive Coding and Modulation)は、BICMの「符号化率と変調が独立」という性質があって初めて実用的に成立します。TCMのように符号化率と変調が一体化した構造では、切り替えのたびにトレリス全体を再構成する必要があり、ACMの実装は非現実的です。

代償として、BICMは前節で触れたように理想的な密結合設計(TCM)に比べ、単純な設計(グレイマッピング・反復なし)では理論的な最適性からわずかに劣ります。しかし現代の強力な誤り訂正符号(LDPC・ターボ符号)そのものがシャノン限界に迫る性能を持つため、変調側で追加の符号化利得を無理に稼ぐ必要性自体が薄れており、「多少の最適性を犠牲にしても、モジュール化と実装の単純さを取る」というBICMの設計思想が、実務上は圧倒的に優位になっています。

実務での使われ方

BICMの実務上の代表例は DVB-S2(ETSI EN 302 307、APSKの回で扱った衛星デジタル放送規格)です。DVB-S2は、BCH符号を外符号、LDPC符号を内符号とする連接符号を、QPSK・8PSK・16APSK・32APSKの4つの変調方式のいずれかと自由に組み合わせる、まさにBICMのアーキテクチャを採用しています。符号化率はLDPC符号側で1/4刻みから9/10まで11通りが規定されており、変調方式との組み合わせは合計28通り(ModCod、Modulation and Codingの略)にのぼります。この規格上の柔軟性は、BICMが符号化率と変調多値数を独立に選べるという性質そのものの実務的な現れです。後継規格の DVB-S2X(ETSI EN 302 307-2)では、さらに細かい符号化率の刻みと、より高次の変調(64APSK、128APSKなど)が追加され、ModCodの組み合わせ数は100を超えます。DVB-S2/S2Xはさらに、リンク品質(受信側から報告されるSNR推定値)に応じてModCodをフレーム単位で切り替える**ACM(Adaptive Coding and Modulation)**運用を標準の中核機能として持ち、これはBICMが持つモジュール性があって初めて実用的に成立する運用形態です。

CCSDSにおいても、APSKの回で触れた CCSDS 131.2-B (Flexible Advanced Coding and Modulation Scheme for High Rate Telemetry Applications) が、近地球ミッションの高速テレメトリ向けにLDPC符号と8PSK・16APSK・32APSKを組み合わせたBICM的な構成を規定しています。この規格もDVB-S2と同様、符号化率と変調方式の多数の組み合わせを1つの共通したパイプライン構造の中で規定しており、ミッションごとの要求データレート・リンク余裕に応じて柔軟に選択できるようになっています。反復デマッピング(BICM-ID)そのものは、標準規格上は受信機の実装オプションとして扱われることが多く、必須要件としてではなく、追加の実装コストに見合うだけの性能向上(典型的に0.1〜0.5 dB程度、コンステレーションと反復回数に依存)が見込める場合に、受信機設計者の判断で導入される技術という位置づけです。

演習問題

$M=8$ (8PSK、 $m=3$ )のグレイマッピングされたコンステレーションを考えます。ある信号点のビットラベルが $b_1b_2b_3 = 011$ であるとき、この点の最近傍点(隣接する信号点)のビットラベルはグレイマッピングの定義よりちょうど1ビットだけ異なります。8PSKの信号点を円周上に反時計回りへ $000,001,011,010,110,111,101,100$ の順(標準的なグレイコード順)で配置したとして、ラベル $011$ の点の両隣(反時計回り・時計回り)のラベルを書き出し、それぞれ何ビット異なるか確認してください。
本文のmax-log近似LLR式 $L(b_k) \approx \frac{1}{2\sigma^2}\left(\min_{s\in\mathcal S_k^{(1)}}|r-s|^2 - \min_{s\in\mathcal S_k^{(0)}}|r-s|^2\right)$ を用いて、QPSK( $M=4$ 、 $m=2$ 、信号点 $(\pm1,\pm1)/\sqrt2$ )の同相成分(I軸)に対応するビットのLLRが、受信サンプルのI軸成分に比例する単純な線形関数になることを示してください。(ヒント: QPSKのビットラベルはI軸・Q軸に完全に分離できるグレイマッピングを持つことを利用する。)
BICM-IDの外部情報の式 $L_e(b_k) = L_D(b_k) - L_a(b_k)$ において、なぜ復号器へ渡す情報から「自分自身が最後に受け取った事前情報」を差し引く必要があるのか、LDPC符号のチェックノード・変数ノード更新式で学んだ「自己参照を避ける」という原則と対応づけて説明してください。また、もしこの差し引きを行わずに $L_D(b_k)$ をそのまま復号器へ渡してしまうと、反復を重ねるにつれてどのような問題が起きると予想されますか。
DVB-S2のModCod(変調・符号化率の組み合わせ)が28通り(DVB-S2X ではさらに増加)にも及ぶという事実を踏まえ、もしこれをTCMのような密結合設計で実現しようとした場合にどのような設計上の困難が生じるか、この回で学んだBICMの「符号化と変調の独立性」と対比させながら、自分の言葉で論じてください。

まとめと次回予告

BICMは、符号化・インターリーブ・マッピングという3段の単純な直列パイプラインによって、TCMのような密結合設計を避けながらも、グレイマッピングによるビット単位誤りの均一化と、ビット単位LLRというLDPC符号の反復復号にそのまま接続できる橋渡しの仕組みによって、実用上十分な性能を実現します。さらに、復号器の事後情報をデマッパーに事前情報として送り返すBICM-IDは、turbo-equalizationと同じ構造を復号器とデマッパーの間で実現し、反復のたびにLLRの精度を高めていきます。何より重要なのは、符号化率と変調多値数が独立に選べるというBICMの性質そのものが、DVB-S2/S2Xのような多数のModCod組み合わせを持つ現代の規格や、リンク品質に応じてそれらを動的に切り替えるACM運用を実務上可能にしているという点です。

次回は、変調方式そのものではなく伝送路の使い方に目を向け、電波の偏波という自由度をもう一つの多重化の軸として使う偏波多重による周波数再利用に軽く触れます。偏波の回で見た直線偏波・円偏波の性質が、同じ周波数帯で2つの独立したチャネルを同時に運ぶためにどう使われるかを見ていきます。

参考文献

G. Caire, G. Taricco, E. Biglieri, “Bit-Interleaved Coded Modulation,” IEEE Transactions on Information Theory, vol. 44, no. 3, 1998
X. Li, J. A. Ritcey, “Bit-Interleaved Coded Modulation with Iterative Decoding,” IEEE Communications Letters, vol. 1, no. 6, 1997
A. Guillén i Fàbregas, A. Martinez, G. Caire, Bit-Interleaved Coded Modulation, Foundations and Trends in Communications and Information Theory, 2008
ETSI EN 302 307-1, Digital Video Broadcasting (DVB); Second Generation Framing Structure, Channel Coding and Modulation Systems for Broadcasting, Interactive Services, News Gathering and Other Broadband Satellite Applications (DVB-S2)
ETSI EN 302 307-2, DVB-S2 Extensions (DVB-S2X)
CCSDS 131.2-B, Flexible Advanced Coding and Modulation Scheme for High Rate Telemetry Applications
J. G. Proakis, M. Salehi, Digital Communications, 5th ed., McGraw-Hill