トレリス符号化変調 (TCM) — 符号化と変調を一体設計して帯域を増やさず利得を得る

この回で学ぶこと

畳み込み符号とビタビ復号の回では、情報ビットに冗長ビットを足すことで符号化利得 $G_a = 10\log_{10}(R_c\, d_{free})$ を得られることを見ました。しかしそこには見過ごせない代償がありました。符号化率 $R_c = k/n < 1$ で冗長ビットを足すということは、同じ情報ビット列を送るのに、変調前のビット列そのものが $1/R_c$ 倍に膨れ上がるということです。QPSK/OQPSKの回で確認した通り、変調方式が同じである限り占有帯域幅はシンボルレートに比例するので、ビットレートが膨れればシンボルレートも膨れ、帯域幅も $1/R_c$ 倍に膨張します。あるいは帯域幅を変えたくなければ、その分だけ情報のデータレートを犠牲にするしかありません。

つまりこれまでの枠組みでは、「符号化(誤り訂正)」と「変調(信号点配置)」は完全に独立な2段階の設計でした。まず符号化率 $R_c$ の誤り訂正符号でビット列に冗長性を足し、できあがった(元より長い)ビット列を、QPSKなり8PSKなり決まった変調方式に渡す。この2段階設計である限り、「誤り訂正能力を上げる」ことと「帯域幅を節約する」ことは常にトレードオフの関係にありました。

1982年、Gottfried Ungerboeckはこの前提そのものを覆しました。 符号化と変調を別々の段階として設計するのではなく、符号器と変調器を1つの一体システムとして同時に設計するという発想です。具体的には、冗長ビットをビット列の「時間軸上の水増し」として扱う代わりに、変調の多値数(信号点数)を増やすことでその冗長ビットを「信号空間」側に吸収してしまう。たとえば2ビット/シンボルの情報を送りたいとき、QPSK(4点)をそのまま使うのではなく、8PSK(8点、3ビット/シンボルの容量を持つ)を使い、余った1ビット分の容量を畳み込み符号的な冗長性に割り当てる。シンボルレートも占有帯域幅も、無符号化QPSKと全く変わりません。それでいて、トレリス構造を持つ符号化のおかげで、無符号化8PSKや無符号化QPSKよりも高い符号化利得が得られる——これが TCM (Trellis-Coded Modulation, トレリス符号化変調) の核心です。

この回では、なぜこの「発想の転換」が数式的に成立するのかを、(1) 帯域幅を増やさずに冗長ビットを吸収する仕組み、(2) Ungerboeckのセット分割 (set partitioning) による信号点とトレリス枝の対応付け、(3) その結果として符号化利得を支配する 自由ユークリッド距離 (free Euclidean distance) という指標、の3段階で理解します。ビタビ復号のアルゴリズム自体は前回ですでに導出済みなので再導出はせず、「変調と符号化を統合設計する」という新しい視点に絞ります。

直感的導入: 冗長ビットをどこに「隠す」か

具体的な数字で比較してみましょう。ビットレート $R_b$ の情報を送りたいとします。

方式A(従来の2段階設計): 情報ビットに符号化率 $R_c = 1/2$ の畳み込み符号をかけ、符号化後のビット列をQPSK($M=4$、2ビット/シンボル)で送る。符号化後のビットレートは $R_b/R_c = 2R_b$ となり、QPSKのシンボルレート $R_s = (2R_b)/2 = R_b$ が必要です。無符号化のQPSKで同じ情報レート $R_b$ を送るときのシンボルレートは $R_s = R_b/2$ でしたから、符号化によってシンボルレート(したがって占有帯域幅)が2倍に膨張しています。

方式B(TCM): 情報ビット2ビットのうち1ビットはそのまま(無符号化)、もう1ビットを簡単な畳み込み符号器に通して2つの冗長ビットにする…のではなく、変調方式を8PSK($M=8$、3ビット/シンボル)に切り替え、3ビット目という「新しく空いた容量」に冗長性を担わせます。1シンボルには相変わらず2ビット分の情報が乗っており、シンボルレートは無符号化QPSKと全く同じ $R_s = R_b/2$ のままです。帯域幅は無符号化QPSKから一切変わっていません。 それでいて、8PSKの8つの信号点への符号化ビットの割り当て方(トレリス構造)を工夫することで、無符号化QPSKよりも優れた耐雑音性能を実現できます。

「冗長ビットをどこに置くか」という視点で言えば、方式Aは冗長ビットを時間軸(余分なシンボル)に、方式Bは冗長ビットを信号空間(余分な信号点)に置いている、と整理できます。以下ではこの直感を数式で裏付けていきます。

数式定式化1: 帯域幅を変えずに冗長性を吸収する条件

一般化しましょう。1シンボルあたり $m$ ビットの情報を送りたいとします。従来の無符号化基準方式では、$2^m$ 点の信号点配置(基準コンステレーション)を使い、シンボルレートは

$$R_{s,\text{ref}} = \frac{R_b}{m}$$

です。TCMでは、信号点数を1段階増やした $M = 2^{m+1}$ 点のコンステレーションを使います。1シンボルは $\log_2 M = m+1$ ビットの容量を持ちますが、そのうち実際に運ぶ情報ビットは $m$ ビットのままで、残り1ビット分の容量を符号器が生成する冗長ビットに割り当てます。したがってTCMのシンボルレートは

$$R_{s,\text{TCM}} = \frac{R_b}{m} = R_{s,\text{ref}}$$

基準方式とTCMのシンボルレートは完全に一致します。 変調方式が変わっていない(サブキャリア・パルス整形などの条件を揃えた)限り、占有帯域幅はシンボルレートだけで決まるので、

$$B_{\text{TCM}} = B_{\text{ref}}$$

も成り立ちます。この「符号化率」を明示的に書けば、TCMが $M=2^{m+1}$ 点の信号点に対して実現しているのは符号化率

$$R_c = \frac{m}{m+1}$$

の符号化ですが、この符号化率の低下はシンボルレートの増加としては一切現れず、信号点数の増加としてのみ現れるという点が方式Aとの決定的な違いです。これがTCMの数式的な骨格であり、「符号化利得を、帯域幅を犠牲にせずに得る」ことができる理由です。

数式定式化2: Ungerboeckのセット分割 (set partitioning)

信号点数を増やしただけでは、当然ながら信号点間の距離は縮まり、APSKの回で見たように無符号化での耐雑音性能はむしろ悪化します。実際、半径1の円周上に置いた無符号化8PSKの最小ユークリッド距離は

$$d_0 = 2\sin\frac{\pi}{8} \approx 0.765, \qquad d_0^2 \approx 0.586$$

であり、同じ半径1のQPSKの最小距離 $d_{\text{QPSK}} = 2\sin(\pi/4) = \sqrt2 \approx 1.414$(二乗で $2.0$)より明らかに小さくなっています。単純に8PSKへ拡張しただけでは性能は悪化するわけです。TCMの本質は、この拡張した信号点集合に符号化ビットをどう割り当てるかという設計にあります。ここで使われるのが Ungerboeck のセット分割です。

セット分割とは、信号点の全体集合を、段階を追って2分割していき、各段階で生まれる部分集合(サブセット)内部の最小距離が、分割前より必ず大きくなるようにするという操作です。8PSKで具体的に見てみましょう。

レベル0(分割前): 全8点の集合 $\Omega_0$、集合内最小距離 $d_0 \approx 0.765$($d_0^2\approx0.586$)。

レベル1(1回分割): $\Omega_0$ を、位相が交互になるように2つの4点部分集合 $B_0, B_1$ に分ける(それぞれが90°おきに並ぶQPSK状の配置になる)。各部分集合内の最小距離は

$$d_1 = 2\sin\frac{\pi}{4} = \sqrt2 \approx 1.414, \qquad d_1^2 = 2.0$$

レベル2(2回分割): $B_0$(または $B_1$)をさらに2つの2点部分集合に分けると、各部分集合は円周上で正反対(対蹠点、180°離れた2点)のペアになります。このときの集合内最小距離は

$$d_2 = 2\sin\frac{\pi}{2} = 2, \qquad d_2^2 = 4.0$$

まとめると、分割が進むごとに部分集合内の最小距離は

$$d_0 < d_1 < d_2, \qquad d_0^2 \approx 0.586 \; \to \; d_1^2 = 2.0 \; \to \; d_2^2 = 4.0$$

と単調に増大していきます(この8PSKの場合、$d_1^2/d_0^2 \approx 3.41$、$d_2^2/d_1^2 = 2$)。セット分割の要点は、分割を深く進めるほど、その部分集合の中だけで信号を選ぶ限り、信号点同士は互いに遠く離れているという構造を作り出すことです。

数式定式化3: セット分割をトレリスの枝に割り当てる規則

セット分割で作った部分集合の階層構造を、符号器のトレリス上の枝ラベルに割り当てる際、Ungerboeckは次の経験則(発見的規則)を提案しました。

1. 全ての分割部分集合を、各状態から出る枝・各状態に入る枝として均等に使う。 特定の部分集合だけが偏って使われないようにする。
2. 並行遷移(parallel transition: 同じ状態対の間を結ぶ複数の枝)には、セット分割の最も深いレベルの部分集合を割り当てる。 並行遷移はトレリス上で1ステップしか離れておらず、後から別の経路に「合流」して距離を稼ぐ余地がないため、その1ステップ自体の距離をできるだけ稼いでおく必要があるからです。8PSKの例で言えば、並行遷移には $d_2$(対蹠点ペア、距離2)を割り当てます。
3. 同じ状態から出る(あるいは同じ状態に合流する)複数の枝には、その一段階浅いレベルの部分集合を割り当てる。 これにより、2つの経路がある状態で分岐し数ステップ後に再合流するとき、各ステップで少なくとも $d_1$ 程度の距離を確保できます。

この規則の狙いは単純です。トレリス上で2つの異なる符号語系列が分岐してから再び合流するまでの累積ユークリッド距離を、常にある値以上に保証すること。 特に「並行遷移(同じ状態対を結ぶ最短の分岐)」は無条件に等しく合流してしまう(1ステップで別れて1ステップで戻る)最も危険なケースなので、そこにこそ最大距離 $d_2$ を割り当てて弱点を潰しておく、という設計思想です。

数式定式化4: 具体例 — 4状態8PSKのUngerboeck符号

この規則を実際の符号器に当てはめてみましょう。1シンボルあたり $m=2$ ビットの情報を送る、4状態のトレリスを持つ8PSK-TCM符号を考えます。2つの入力ビットのうち、1ビット($b_1$)を状態数4(メモリ2ビット)の簡単な畳み込み符号器に通して2つの符号化ビットを作り、この2ビットで「どの部分集合 $B_0, B_1, B_2, B_3$(セット分割レベル1の4つの部分集合)を使うか」を選びます。残るもう1ビット($b_2$)は符号化せずそのまま使い、選ばれた部分集合の中の2点(対蹠点のペア、レベル2の分割)のどちらを送るかを決めます。

このトレリスでは、状態遷移(次にどの状態に移るか)は $b_1$ だけで決まり、$b_2$ は状態遷移には関与しません。つまり同じ状態対を結ぶ2本の枝が、$b_2$ の値だけによって区別される並行遷移として必ず存在します。規則2に従い、この並行遷移には部分集合内の最大距離 $d_2$(距離2、$d_2^2=4$)を割り当てます。一方、$b_1$ によって分岐・合流する経路同士は、規則3に従い各ステップで少なくとも $d_1$($d_1^2=2$)の距離を確保するように、生成多項式(符号器のタップ構成)が設計されます。

このとき、この符号の自由ユークリッド距離(次節で正式に定義します)は、次の2種類の「最も紛らわしい誤り方」のうち小さい方で決まります。

• 並行遷移1本だけの誤り: 距離の2乗は $d_2^2 = 4.0$
• 2ステップかけて分岐し再合流する誤り経路: 各ステップで少なくとも $d_1^2=2.0$ ずつ離れているので、合計 $d_1^2 + d_1^2 = 4.0$

両者がちょうど釣り合うように符号器が設計されているため、

$$d_{free}^2 = \min(4.0,\ 4.0) = 4.0$$

となります。これがUngerboeckが1982年の論文で示した最も基本的な4状態8PSK-TCM符号の自由ユークリッド距離です(具体的な生成多項式の係数は文献 Ungerboeck (1982) の表に譲ります)。

数式定式化5: 自由ユークリッド距離と符号化利得

ここで自由ユークリッド距離を一般に定義しておきます。畳み込み符号の回で見た自由距離 $d_{free}$ は、正解パスと誤りパスの符号化ビット列同士のハミング距離の最小値として定義されていました。TCMではビット同士の距離ではなく、トレリス上で異なる2本のパスに対応する送信信号点列そのもののユークリッド距離を直接使います。

$$d_{free}^2 = \min_{\substack{\{s_k\} \neq \{s_k'\} \\ \text{異なる有限長パス}}} \sum_{k} \big| s_k - s_k' \big|^2$$

ここで $\{s_k\}$, $\{s_k'\}$ はトレリス上の異なる2つのパスがそれぞれ選ぶ信号点の系列です。畳み込み符号のときは「符号化ビット列のハミング距離」→「BPSK/QPSKマッピングを経て初めてユークリッド距離に変換される」という2段階の対応でしたが、TCMでは符号化と信号点選択が最初から一体化した設計になっているため、ブランチメトリック自体が最初からユークリッド距離空間で定義され、余計な変換段を経ません。この一体化こそが、同じ帯域幅の中でより深い符号化利得を引き出せる理由です(ビタビ復号自体は、ハミング距離の代わりにユークリッド距離(またはその2乗)をブランチメトリックとして使うだけで、前回のACS演算がそのまま適用できます)。

符号化利得は、TCMと同じ情報レート・同じ平均シンボルエネルギーを持つ無符号化の基準方式との比較で定義されます。

$$\gamma\ [\text{dB}] = 10\log_{10}\!\left(\frac{d_{free,\text{TCM}}^2 / E_{s,\text{TCM}}}{d_{min,\text{ref}}^2 / E_{s,\text{ref}}}\right)$$

4状態8PSK-TCMの例では、TCMは半径1の8PSK($E_{s,\text{TCM}}=1$)、基準方式は同じく半径1のQPSK($E_{s,\text{ref}}=1$、$d_{min,\text{ref}}^2 = d_1^2 = 2.0$)なので、エネルギー項はちょうど打ち消し合い、

$$\gamma = 10\log_{10}\!\left(\frac{4.0}{2.0}\right) = 10\log_{10}(2) \approx 3.01\ \text{dB}$$

帯域幅を1ビットも増やさずに、無符号化QPSKに対して約3 dBの符号化利得が得られることになります。これがUngerboeckの4状態8PSK-TCM符号のもっとも有名な結果です。状態数を増やす(トレリスをより複雑にする)ほど、セット分割の規則を保ちながらより深い分岐・合流経路を設計でき、自由ユークリッド距離をさらに大きくできます。文献に示されている代表的な数値では、8状態で約3.6 dB、16状態で約4.1 dB、64状態で約4.6 dBと、状態数の増加とともに利得は緩やかに増えていきますが、状態数を無限に増やしても利得はある上限(8PSKと2次元信号空間の幾何的な制約による上限、おおよそ5〜6 dB程度)に漸近し、そこから先は状態数を増やすコストに見合わなくなります。

実務での使われ方

TCMが歴史的に最も広く実用化されたのは、電話回線用モデム規格でした。ITU-T(旧CCITT)の V.32(9.6 kbps、1984年)は、L.-F. Wei による回転不変な32点交差(cross)QAM信号点配置とトレリス符号を組み合わせたTCMを採用し、電話回線という非常に帯域幅の限られたチャネル(音声帯域、約3 kHz)の中で高いデータレートを実現しました。後継の V.32bis(14.4 kbps)、そして V.34(33.6 kbps、1994年)では、さらに多状態のトレリス符号(最大で数百状態規模)、複数のコンステレーション形状の切り替え、シェルマッピング(shell mapping、信号点のエネルギー分布を最適化する技法)などを組み合わせ、シャノン限界にかなり近いスペクトル効率を達成しました。この時代、TCMは「帯域幅が厳しく制限され、かつ回線のSNRが比較的高い(電力制限ではなく帯域制限の)チャネル」において、誤り訂正符号の主流技術でした。

一方、深宇宙通信でのTCMの採用は限定的です。理由はシャノンの通信路容量定理の回やAPSKの回で触れた通り、深宇宙リンクは受信電力が極めて乏しい電力制限領域で動作するのに対し、TCMが本領を発揮するのは帯域幅がボトルネックになる帯域制限領域だからです。電力制限領域では、TCMのような3〜6 dB程度の中程度の符号化利得よりも、ターボ符号やLDPC符号のようなシャノン限界により近づける強力な符号の方が、限られた電力から多くのデータレートを引き出す上で有利です。実際、CCSDSの深宇宙テレメトリ標準は畳み込み符号・リード-ソロモン連接符号からターボ符号・LDPC符号へと進化しており、TCMを主要な標準としては採用していません。

それでも衛星通信の一部、とりわけ帯域幅の割り当てが厳しく制限される静止衛星のトランスポンダ回線(帯域制限領域に近い、比較的高いSNRが確保できるリンク)では、8PSKベースのトレリス符号化変調が業務用衛星モデムで採用されてきた歴史があります。APSKの回で扱った DVB-S2 のような「符号化と変調をセットで規定する」規格の考え方自体、系譜をたどればUngerboeckのTCMが切り開いた「符号化と変調は分離すべきではない」という設計思想の延長線上にあると言えます。

演習問題

1. 半径1の8PSK信号点配置について、セット分割レベル0・1・2それぞれの集合内最小距離 $d_0, d_1, d_2$ を $\sin$ の値から計算し、$d_1^2/d_0^2$ および $d_2^2/d_1^2$ をそれぞれ真数とdBの両方で求めてください。
2. 1シンボルあたり $m=3$ ビットの情報を送りたいとき、TCMでは $M=2^{m+1}=16$ 点の信号点配置(16PSKや16QAMなど)を使うことになります。この場合のシンボルレートが、無符号化の8点配置($m=3$、$2^m=8$)基準方式のシンボルレートと一致することを、本文の式 $R_{s,\text{TCM}} = R_b/m$ を用いて確認してください。
3. 本文で導いた4状態8PSK-TCM符号の自由ユークリッド距離 $d_{free}^2=4.0$ と、無符号化QPSK基準方式の最小距離二乗 $d_{min,\text{ref}}^2=2.0$ から、符号化利得 $\gamma$ をdBで計算してください。さらに、もし同じ4状態のトレリスを使いつつ「並行遷移」に誤ってレベル1の部分集合($d_1^2=2.0$)を割り当ててしまった場合、$d_{free}^2$ がどう変化するか考察し、なぜUngerboeckの規則2(並行遷移には最大距離の部分集合を割り当てる)が重要なのかを説明してください。
4. 畳み込み符号の回で学んだ「符号化率 $R_c$ を下げて誤り訂正能力を上げると帯域幅が広がる」というトレードオフと、この回で学んだTCMの「信号点数を増やして帯域幅を変えずに符号化利得を得る」という発想の違いを、自分の言葉で説明してください。またTCMが深宇宙通信よりも電話回線モデムや衛星トランスポンダ回線で好んで使われてきた理由を、電力制限領域と帯域制限領域という観点から述べてください。

まとめと次回予告

TCMは、「符号化(誤り訂正)」と「変調(信号点配置)」を切り離して設計するのではなく、両者を最初から一体のトレリス構造として設計することで、帯域幅を一切増やさずに符号化利得を得るという、それまでの符号設計の常識を覆すアイデアでした。その鍵は、Ungerboeckのセット分割によって信号点集合を段階的に分割し、各分割レベルの最小距離を、トレリスの枝(特に並行遷移)へ意図的に割り当てるという設計原理にあります。この結果、符号化利得を支配する指標は、ハミング距離ではなく信号空間上のユークリッド距離そのもの、すなわち自由ユークリッド距離 $d_{free}$ になります。4状態8PSK-TCMの例では、無符号化QPSKに対して帯域幅を変えずに約3 dBの利得を得られることを具体的に確認しました。

次回は、この「符号化と変調の統合設計」という考え方をさらに一歩進め、チャネルの状態(受信SNRの変動)に応じて符号化率や変調方式そのものをリアルタイムに切り替える適応符号化変調 (ACM: Adaptive Coding and Modulation) に軽く触れます。TCMが「固定のチャネル条件に対して最適な符号化と変調の組を静的に設計する」技術だったのに対し、ACMは「刻々と変化するリンク品質に対して、その組み合わせを動的に選び直す」という、また一段階異なる設計思想に基づいています。

参考文献

• G. Ungerboeck, “Channel Coding with Multilevel/Phase Signals,” IEEE Transactions on Information Theory, vol. 28, no. 1, 1982
• G. Ungerboeck, “Trellis-Coded Modulation with Redundant Signal Sets, Part I: Introduction; Part II: State of the Art,” IEEE Communications Magazine, vol. 25, no. 2, 1987
• L.-F. Wei, “Rotationally Invariant Convolutional Channel Coding with Expanded Signal Space, Part I & II,” IEEE Journal on Selected Areas in Communications, vol. 2, no. 5, 1984
• ITU-T Recommendation V.32, V.34
• J. G. Proakis, M. Salehi, Digital Communications, 5th ed., McGraw-Hill (Trellis-Coded Modulation の章)
• E. Biglieri, D. Divsalar, P. J. McLane, M. K. Simon, Introduction to Trellis-Coded Modulation with Applications, Macmillan