距離スペクトラムとユニオンバウンド — 符号の性能解析を統一的に理解する

この回で学ぶこと

畳み込み符号とビタビ復号の回では、正解パスと誤りパスのハミング距離の最小値である自由距離 $d_{free}$ が符号化利得を決めることを見ました。トレリス符号化変調(TCM)の回では、まったく別の指標に見える自由ユークリッド距離 $d_{free}$ が、まったく同じ役割(符号化利得の決定要因)を果たしていました。同じ記号 $d_{free}$ を使いながら、片方はビット列同士の食い違いの個数を数え、もう片方は信号空間上の幾何学的な隔たりを測っている。この2つは偶然同じ名前が付いているだけなのでしょうか。

そうではありません。この回で示すのは、**「符号語(あるいは信号点列)の間にどんな距離尺度を使おうとも、誤り率解析の骨組みそのものは1つの一般理論に集約できる」という事実です。この一般理論の核が、符号語間の距離の分布を数え上げた距離スペクトラム(distance spectrum)と、その分布から誤り率の上界を導くユニオンバウンド(和集合上界, union bound)**です。畳み込み符号のハミング距離ベースの解析も、TCMのユークリッド距離ベースの解析も、この一般理論に特定の距離尺度を代入しただけの特殊ケースにすぎません。

この回では、(1) 距離スペクトラムという考え方を一般的に定式化し、(2) ユニオンバウンドが確率論のごく基本的な不等式から導かれることを示し、(3) 両者を組み合わせて誤り率の一般公式を導出し、(4) なぜ高SNR領域では自由距離の項だけで誤り率がほぼ決まってしまうのか、という近似の妥当性を数式で確認します。個々の符号の自由距離の具体的な数値(NASA標準 $(7,5)$ 符号の $d_{free}=10$ や、4状態8PSK-TCMの $d_{free}^2=4.0$ など)は前2回ですでに求めているので再導出はせず、「なぜその数値が誤り率を決めるのか」という一般理論の側に焦点を絞ります。

直感的導入: 同じ枠組みの中の2つの「距離」

まず、なぜハミング距離とユークリッド距離が「同じ枠組み」だと言えるのか、直感からおさらいします。

畳み込み符号の復号(ハード判定・BSC通信路)では、受信ビット列と候補の符号語ビット列との近さを、食い違うビットの個数=ハミング距離で測りました。一方TCMでは、送信信号点列と別の符号語が対応する信号点列との幾何学的な近さを、ユークリッド距離で測りました。どちらも本質的にやっていることは同じです。「正解の系列」と「まぎらわしい別の系列」がどれだけ離れているかを、何らかの距離関数 $d(\cdot,\cdot)$ で測り、その距離が小さい系列ほど、雑音によって取り違えられやすい、という構図です。

違いはただ1つ、距離関数として何を採用するかだけです。

• ハード判定・BPSK/BSC通信路では、受信側がまず0/1に判定してしまうため、残っている情報はビットの一致・不一致だけになり、自然な距離はハミング距離 $d_H$ になります。
• ソフト判定・AWGN通信路(振幅情報をそのまま使う場合)では、受信信号と信号点との近さが直接ユークリッド距離 $d_E$ で測れるため、こちらのほうが本来の受信機の判定基準に近くなります(実際畳み込み符号の回でも、ソフト判定の方がハード判定よりおよそ2dB優れると述べました)。

つまりハミング距離とユークリッド距離は、**「AWGN通信路上でどれだけ厳密に受信機の物理的な判定基準に忠実であるか」が異なるだけの、同じ「符号語間の距離」という概念の2つの計量(メトリック)**なのです。実際、後で数式的に示す通り、ハミング距離ベースの誤り率公式は、BPSKマッピングを経由してユークリッド距離に変換したうえで得られる特殊ケースにすぎません。この回では、この「距離」を一般の記号 $d$ で表し、それが何であっても成立する誤り率解析の枠組みを構築します。

数式定式化1: 距離スペクトラム(重み分布)の定義

ある通信路符号化方式(畳み込み符号でもTCMでも、あるいはブロック符号でも構いません)において、正解の符号語(あるいは信号点系列)を基準にとり、そこから距離 $d$ だけ離れた別の符号語(信号点系列)がいくつ存在するかを数え上げた数を $A_d$ と書きます。

$$A_d = \#\{\, c' \neq c \;:\; d(c, c') = d \,\}$$

この $A_d$ を $d$ の関数として並べたもの、あるいはそれを母関数(生成関数)としてまとめたもの

$$A(X) = \sum_{d} A_d\, X^{d}$$

を、その符号の**距離スペクトラム(distance spectrum)または重み分布(weight distribution / weight enumerating function)**と呼びます。線形符号(畳み込み符号を含む)では、全0系列からの距離はそのまま符号語の「重み」(1の個数)に一致するため、重み分布という呼び方が使われます。

畳み込み符号の回で $\beta_d$ という記号で導入した係数は、実はこの $A_d$ を「情報ビット誤り数」で重み付けした変種であり、トレリス符号化変調の回では自由ユークリッド距離 $d_{free}$ だけに着目していましたが、その背後には $d_{free}$ 以上のすべての $d$ について $A_d$ が(有限または無限に)存在する、完全な距離スペクトラムが控えていました。この回で見る一般公式は、$d_{free}$ 付近の1項だけでなく、この分布全体 $\{A_d\}$ を使い切ります。

距離スペクトラムのうち、最小の(0でない)$d$ を

$$d_{free} = \min\{\, d > 0 \;:\; A_d > 0 \,\}$$

と定義すれば、これがまさに畳み込み符号の自由距離、TCMの自由ユークリッド距離のいずれにも共通する一般的な定義になります。前2回で扱った2つの「自由距離」は、それぞれ距離関数 $d(\cdot,\cdot)$ にハミング距離、ユークリッド距離を代入した、この一般定義の特殊ケースだったわけです。

畳み込み符号の場合、この $A_d$(正確には情報ビット重み付き版)は状態遷移図を信号流グラフとみなし、Masonのゲイン公式を使って解析的に求められることを前々回で触れました。状態00を除去し他の全状態を通る閉路のゲインの和として、重み分布を係数に持つ有理関数(伝達関数) $T(X, Y)$ が得られ、これを $X$ のべき級数に展開すると、その係数がちょうど $A_d$ に対応します。

数式定式化2: ユニオンバウンドという確率論の基本不等式

次に、この距離スペクトラムから誤り率の上界を導くための道具、ユニオンバウンドを確認します。これは符号理論に限らず成り立つ、確率論のごく基本的な不等式です。

事象 $E_1, E_2, \ldots, E_n$ (あるいは可算無限個)が与えられたとき、そのうち少なくとも1つが起こる確率は、各事象の確率の単純な和を超えることはありません。

$$P\left(\bigcup_{i} E_i\right) \;\le\; \sum_{i} P(E_i)$$

これをブールの不等式(Boole’s inequality)、通信・符号理論の文脈ではユニオンバウンドと呼びます。証明は測度論的加法性の初等的な帰結です。事象の和集合 $\bigcup_i E_i$ を、互いに排反(disjoint)な部分に分割し直すと

$$\bigcup_i E_i = E_1 \cup (E_2 \setminus E_1) \cup (E_3 \setminus (E_1\cup E_2)) \cup \cdots$$

となり、確率の加法性(排反事象の確率は単純に足せる)から

$$P\left(\bigcup_i E_i\right) = \sum_i P\big(E_i \setminus (E_1\cup\cdots\cup E_{i-1})\big) \;\le\; \sum_i P(E_i)$$

が成り立ちます(各項で $P(E_i \setminus \cdots) \le P(E_i)$ であることを使いました)。等号が成立するのは、すべての事象が互いに排反な場合(同時には決して起こらない場合)に限られ、事象同士が重なり合う(複数の $E_i$ が同時に成立し得る)ほど、この上界は実際の確率より緩くなります。

この不等式を符号の復号誤りに当てはめます。送信された正解の符号語を $c$ とし、復号器が誤って別の符号語 $c'$ を選んでしまう事象を $E_{c'}$(ペアワイズ誤り事象)と定義すると、「復号誤りが起きる」という事象は、$c$ 以外のどれかの符号語が選ばれてしまうという事象の和集合そのものです。

$$P_e = P\left(\bigcup_{c' \neq c} E_{c'}\right) \;\le\; \sum_{c' \neq c} P(E_{c'})$$

これがユニオンバウンドの符号理論への応用の第一歩です。実際にはビタビ復号のように、ある1つの誤り事象が起きれば他の(距離の大きい)誤り事象は同時に起こりにくいという排他性がある程度働くため、この不等式は特に低SNRで緩くなりがちですが、高SNR領域では良い近似になることを後の節で確認します。

数式定式化3: ユニオンバウンドによる誤り率の一般公式

$\sum_{c' \neq c} P(E_{c'})$ を、距離スペクトラム $A_d$ を使って整理します。$c$ からの距離が $d$ の符号語は $A_d$ 個存在し、その各々についてのペアワイズ誤り確率 $P_2(d)$ は(距離が同じであれば)ほぼ等しいとみなせるので、

$$\sum_{c' \neq c} P(E_{c'}) = \sum_{d} A_d\, P_2(d)$$

とまとめられます。あとはペアワイズ誤り確率 $P_2(d)$ を具体的に求めれば完成です。AWGN通信路上でのML検出(最尤判定)では、2つの符号語(あるいは信号点系列)が距離 $d$ だけ離れているとき、雑音がそれを覆い隠して誤って判定させる確率は、検出理論の回で見た「最も近い信号点を選ぶ」ML判定の直接の帰結として、次のQ関数で厳密に与えられます。

$$P_2(d) = Q\!\left(\frac{d}{2\sigma}\right), \qquad \sigma^2 = \frac{N_0}{2}$$

（$\sigma^2$ は1次元あたりのAWGN雑音分散です。）ここで、符号語間の距離 $d$ を、実際の物理的な信号エネルギー $E$(ビットあたり、あるいはシンボルあたり)で正規化されたスケールで測ることにすると、$d^2$ にエネルギー $E$ を乗じた量が実際の(2乗)ユークリッド距離に対応し、

$$P_2(d) = Q\!\left(\sqrt{\frac{d^2 E}{2N_0}}\right)$$

という形に整理できます。これを距離スペクトラムの和と組み合わせると、符号の種類、距離尺度、変調方式によらず成立する誤り率の一般公式が得られます。

$$\boxed{\;P_e \;\le\; \sum_{d} A_d\, Q\!\left(\sqrt{\frac{d^2 E}{2N_0}}\right)\;}$$

この式こそが、この回の中心となるユニオンバウンドによる誤り率上界の一般公式です。前2回で見た2つの式は、いずれもこの一般公式の特殊ケースです。

• 畳み込み符号の回の $P_b \lesssim \sum_{d=d_{free}}^{\infty} \beta_d\, Q(\sqrt{2 R_c d\, E_b/N_0})$ は、$d$ にハミング距離を、$E$ に符号化ビットエネルギー $E_c = R_c E_b$ を代入したケースに相当します。BPSKの対蹠(±1)マッピングでは、ハミング距離1のビット反転が実際のユークリッド距離の2乗を4だけ増やすため($(\sqrt{E_c}-(-\sqrt{E_c}))^2 = 4E_c$)、正規化ハミング距離 $d_H$ とユークリッド距離の2乗は $d_E^2 = 4 E_c d_H$ という関係で結ばれ、これを一般公式に代入すると $Q(\sqrt{4E_c d_H/(2N_0)}) = Q(\sqrt{2 R_c d_H E_b/N_0})$ となって、前々回の式に一致します。
• TCMの回では、符号化と変調が最初から一体設計されているため、$d$ はすでに信号空間上のユークリッド距離そのものであり、$E$ はシンボルエネルギー $E_s$ です。ビットマッピングを介した変換が不要な分、一般公式にそのまま $d = d_{free}$(ユークリッド距離)、$E=E_s$ を代入するだけで、前回のペアワイズ誤り確率の議論と一致します。

つまり両者の違いは「$d$ という記号に何を代入するか」という距離尺度の選び方だけであり、誤り率が距離スペクトラムの和として上から抑えられるという構造そのものは共通の一般理論だった、ということがここで初めて明らかになります。

数式定式化4: 高SNR極限と自由距離の支配性

一般公式 $P_e \le \sum_d A_d Q(\sqrt{d^2 E/(2N_0)})$ は無限個(あるいは非常に多数)の項の和ですが、実務では「自由距離の項だけ見ればよい」としばしば近似されます。これがなぜ正当化されるのかを数式で確認します。

Q関数は、大きな引数に対して次のガウス型の漸近評価(Chernoff型の上界、および漸近的に厳密な評価)を持ちます。

$$Q(x) \sim \frac{1}{x\sqrt{2\pi}}\, e^{-x^2/2} \qquad (x \to \infty)$$

つまりQ関数は引数の2乗に対して指数関数的に減衰します。これを一般公式の各項に当てはめると、距離 $d$ の項は

$$Q\!\left(\sqrt{\frac{d^2 E}{2N_0}}\right) \sim \exp\!\left(-\frac{d^2 E}{4N_0}\right)$$

の形で減衰することが分かります。したがって、隣り合う2つの距離 $d_{free}$ と $d > d_{free}$ の項の比は、

$$\frac{A_d\, Q(\sqrt{d^2 E/(2N_0)})}{A_{d_{free}}\, Q(\sqrt{d_{free}^2 E/(2N_0)})} \;\sim\; \frac{A_d}{A_{d_{free}}}\exp\!\left(-\frac{(d^2 - d_{free}^2)E}{4N_0}\right)$$

となり、$E/N_0$(SNR)を大きくしていくと、$A_d/A_{d_{free}}$ が有限である限り、この比は指数関数的にゼロへ近づきます。距離スペクトラムの係数 $A_d$ は一般に $d$ とともに増加しますが(距離が離れるほど、そこに存在する符号語の「候補数」は組合せ的に増える)、その増加は多くとも指数関数的であり、Q関数側の指数的減衰の「肩」の傾き($E/N_0$)を十分大きく取れば、必ずQ関数側の減衰が $A_d$ の増加を凌駕します。したがって高SNR極限では和全体が最小距離の項だけで近似的に決まります。

$$P_e \;\approx\; A_{d_{free}}\, Q\!\left(\sqrt{\frac{d_{free}^2\, E}{2N_0}}\right) \qquad (E/N_0 \to \infty)$$

これが、畳み込み符号の回やTCMの回で「自由距離が大きい符号ほど良い」と単純化して語ってきたことの、厳密な理論的根拠です。自由距離を大きくすることは、この支配項のQ関数の引数を大きくすること、すなわち指数関数的な減衰の傾きを急にすることに直結します。逆に言えば、この近似はあくまで漸近的なものであり、$E/N_0$ が小さい(SNRが低い)領域では、$d > d_{free}$ の項の寄与が無視できず、上界としてのユニオンバウンド自体も緩くなるという限界も同時に見えてきます。この点は次節の実務でさらに具体的に確認します。

実務での使われ方

符号設計の現場では、この距離スペクトラムとユニオンバウンドの一般理論が、具体的にどう使われているかを見てみましょう。

候補符号の絞り込み: 畳み込み符号の生成多項式を設計する際、拘束長 $K$ を固定しても、タップの取り方(生成多項式の組み合わせ)は多数存在します。符号設計者はまず、候補となる各生成多項式についてMasonのゲイン公式などで距離スペクトラム $\{A_d\}$ を計算機で列挙し、自由距離 $d_{free}$ が最大のものをまず絞り込みます。しかし複数の候補が同じ $d_{free}$ を持つことも多く、その場合は自由距離より1つ上、2つ上の距離 $d_{free}+1, d_{free}+2, \ldots$ における係数 $A_d$ が小さいものを優先する、という距離スペクトラム全体を辞書式に比較する設計手法が使われます。これは前節で見た通り、高SNRでは $A_{d_{free}}$ の大きさが誤り率にほぼ線形に効くため(Q関数の引数は同じでも、係数 $A_{d_{free}}$ が小さいほど有利)、また運用SNRが自由距離の近似が崩れる領域にある場合には次項 $A_{d_{free}+1}$ 以降の寄与も無視できないためです。1970年代にJ. Odenwalder や K. Larsen らが行った、拘束長 $K=3$ から $K=9$ 程度までの候補生成多項式の網羅探索とこの距離スペクトラム比較こそが、畳み込み符号の回で扱ったNASA標準 $(K=7, R_c=1/2)$ 符号($d_{free}=10$)が選ばれた経緯そのものであり、CCSDS 131.0-B に採用されている生成多項式は、この種の系統的な距離スペクトラム比較の結果として現在に至るまで使われ続けています。

シミュレーションBERとの照合: 符号設計・リンク設計の現場では、ユニオンバウンドによる理論上界を計算するだけでなく、実際にモンテカルロ・シミュレーション(乱数で符号化・雑音付加・復号を大量に繰り返し、誤りビット数を実測する)でBER曲線を求め、両者を突き合わせる検証作業が不可欠です。典型的な結果として、目標ビット誤り率 $10^{-5}$〜$10^{-6}$程度の**高SNR領域(waterfall region)では、ユニオンバウンドの理論値とシミュレーション実測値は1dB以内で良く一致することが多く、前節で導いた「高SNRでは自由距離の項が支配的」という近似の妥当性を裏付けています。一方、低〜中SNR領域ではユニオンバウンドは大きく緩み、ひどい場合には $d$ の低い項の寄与が積み重なって上界の値が1を超えてしまう(確率の上界として無意味になる)ことすらあります。これはユニオンバウンドが「排反事象の確率の単純和」という粗い評価であり、複数の誤り事象が実際には排他的に(同時には起こりにくく)復号器内部で競合している事実を反映していないためです。この限界を補うため、実務ではDivsalarの簡易上界(simple bound)や球充填限界(sphere-packing bound)などの、より精緻な(だが計算が複雑な)上界も併用されます。ターボ符号やLDPC符号のように、非常に小さい $d_{free}$ を持つ少数の低重み符号語が存在する場合には、この距離スペクトラムの下端(低い $d$)の解析が、高SNRでBER曲線が予想外に下げ止まるエラーフロア(error floor)**現象の予測にも直接使われており、距離スペクトラムという考え方は畳み込み符号・TCMにとどまらず、現代の誤り訂正符号設計全般に共通する基礎解析ツールであり続けています。

演習問題

1. ユニオンバウンド $P(\bigcup_i E_i) \le \sum_i P(E_i)$ を、事象を互いに排反な部分に分割し直す方法で証明してください。また、等号が成立するのはどのような条件のときか、本文の議論から説明してください。
2. ある符号の距離スペクトラムが $A_{d_{free}} = 1$, $A_{d_{free}+1} = 4$, $A_{d_{free}+2} = 12$ であるとします(それ以降は無視できるとする)。一般公式 $P_e \le \sum_d A_d Q(\sqrt{d^2E/(2N_0)})$ を用いて、$d_{free}^2 E/N_0 = 10$ の場合と $d_{free}^2 E/N_0 = 20$ の場合それぞれについて、上界の値のうち $d_{free}$ の項が全体に占める割合(パーセント)を計算し、SNRが高くなるほど自由距離の項の支配度が増すことを数値で確認してください。
3. 本文中で、畳み込み符号のハミング距離ベースのペアワイズ誤り確率の式 $Q(\sqrt{2R_c d_H E_b/N_0})$ が、一般公式 $Q(\sqrt{d^2E/(2N_0)})$ に $d_E^2 = 4E_c d_H$($E_c = R_c E_b$)を代入した特殊ケースであることを示しました。同様に、TCMの自由ユークリッド距離ベースの式が一般公式の特殊ケースであることを、TCMの回の符号化利得の式 $\gamma = 10\log_{10}(d_{free}^2/E_{s,\text{TCM}} \div d_{min}^2/E_{s,\text{ref}})$ を踏まえて、自分の言葉で説明してください。
4. 高SNR極限でユニオンバウンドが最小距離の項だけで近似できる理由を、Q関数の漸近評価 $Q(x)\sim e^{-x^2/2}/(x\sqrt{2\pi})$ を使って説明してください。またこの近似が低SNR領域では成り立たない理由と、それが符号設計の実務(距離スペクトラム全体の比較やシミュレーションによる検証)にどう影響するかを述べてください。

まとめと次回予告

畳み込み符号の自由距離(ハミング距離)とTCMの自由ユークリッド距離は、名前も定義の見た目も異なるように見えて、実は「正解の符号語からの距離がいくつなのかを数え上げた距離スペクトラム $A_d$」という共通の枠組みの中の、異なる距離尺度を選んだ特殊ケースにすぎませんでした。この距離スペクトラムと、確率論の基本不等式であるユニオンバウンドを組み合わせることで、$P_e \le \sum_d A_d Q(\sqrt{d^2E/(2N_0)})$ という、符号の種類や変調方式によらない誤り率解析の一般公式が得られます。そして高SNR極限でQ関数の指数関数的減衰が距離スペクトラムの増加を凌駕することから、この和が自由距離の1項だけでほぼ決まることが数式的に正当化され、これが「自由距離が大きい符号ほど良い」という、これまで2回にわたって単純化して語ってきた経験則の理論的な裏付けとなります。

次回は、この回まで暗黙のうちに前提としてきた「AWGN通信路を通った信号は、送信時の波形をそのまま(歪みなく)受信できる」という仮定を疑います。実際のRFフロントエンドやチャネルには帯域制限やマルチパスによる符号間干渉(ISI)が存在し、これを補償するチャネル等化技術が必要になります。距離スペクトラムやユニオンバウンドといったこの回までの解析ツールが、そうした歪みのある通信路のもとでどう修正を受けるのか、という新しい視点にごく軽く触れて次のステップへの橋渡しとします。

参考文献

• A. J. Viterbi, J. K. Omura, Principles of Digital Communication and Coding, McGraw-Hill
• J. G. Proakis, M. Salehi, Digital Communications, 5th ed., McGraw-Hill (Union Bound and Error Probability の章)
• G. C. Clark Jr., J. B. Cain, Error-Correction Coding for Digital Communications, Plenum Press
• G. Ungerboeck, “Channel Coding with Multilevel/Phase Signals,” IEEE Transactions on Information Theory, vol. 28, no. 1, 1982
• J. P. Odenwalder, “Optimal Decoding of Convolutional Codes,” Ph.D. dissertation, UCLA, 1970
• D. Divsalar, “A Simple Tight Bound on Error Probability of Block Codes with Application to Turbo Codes,” TMO Progress Report 42-139, JPL, 1999