測距符号の設計 — Gold符号と相互相関の数理

この回で学ぶこと

再生測距の回では、探査機がPN(擬似雑音)測距符号を復調・再構成してから送り返すことで、往復分の雑音の重畳を回避できることを学びました。そこではPN符号の自己相関が「原点で鋭い三角ピークを持ち、それ以外ではほぼゼロ」という性質を持つことを前提として使い、測距精度がチップレート・積分時間・SNRでどう決まるかを導きました。

この回では一歩踏み込んで、その符号自体をどう設計するかという問題を扱います。実はこれは、シフトレジスタと有限体 $\mathrm{GF}(2)$ 上の多項式が主役を務める、深宇宙通信の中でもとりわけ数論的・組合せ論的な色彩の濃いテーマです。

問題意識はこうです。探査機が1機だけなら、自己相関の鋭いM系列(マキシマル長系列)を1本用意すれば済みます。しかし現実には、火星周回機が同時に何機も運用され、DSNの1つのアンテナが複数探査機を同時受信し(MSPA運用)、GNSSでは30機以上の衛星が同じ周波数で同時に送信しています。このとき各符号は、自分自身との自己相関が鋭いだけでなく、他の符号との相互相関(cross-correlation)も一様に低いことが要求されます。この「自己相関と相互相関を同時に良くする」という要求は互いに綱を引き合う関係にあり、どこまで両立できるかには数学的な限界(Welch限界)が存在します。その限界の近くを達成する古典的傑作が、この回の主役 Gold符号 です。

直感的な導入 — 全員が同じ部屋で同時に話すには

パーティ会場で、複数のペアが同時に会話している状況を考えてみましょう。周波数分割は「ペアごとに別の部屋に分かれる」方式、時分割は「順番に話す」方式です。それに対して符号分割(CDMA)は、全員が同じ部屋で同時に話すが、ペアごとに異なる「言語」を使う方式に例えられます。自分の相手の言語だけを聞き取る訓練(=自分の符号との相関)をしておけば、他の言語の会話は意味を成さない雑音として聞き流せる、という理屈です。

ただしこの例えには続きがあります。もし2つの言語がたまたま似ていたら――多くの単語が共通していたら――他人の会話の断片が、自分宛のメッセージとして「誤って聞き取れてしまう」ことが起きます。符号の言葉で言えば、2つの符号の相互相関が大きいと、他の探査機の信号が自分の相関器に疑似的なピークを作り、測距値を汚したり、最悪の場合は他機の信号に誤ってロックしてしまうのです。

したがって符号族の設計問題とは、「どの2つを取っても十分に似ていない言語の集合を、できるだけたくさん作る」という組合せ論の問題にほかなりません。以下でこれを数式にしていきます。

相関特性の定式化

周期 $N$ の2値系列 $u = (u_0, u_1, \dots, u_{N-1})$, $u_i \in \{0, 1\}$ を考え、送信時にはチップ $u_i$ を $(-1)^{u_i} \in \{+1, -1\}$ にマッピングして使うものとします。2つの系列 $u, v$ の周期的相互相関関数を次で定義します。

$$\theta_{u,v}(\tau) = \sum_{i=0}^{N-1} (-1)^{u_i}\,(-1)^{v_{i+\tau}} = \sum_{i=0}^{N-1} (-1)^{u_i + v_{i+\tau}}$$

(添字は $\bmod N$ で巡回させます。)$u = v$ の場合が自己相関 $\theta_u(\tau) = \theta_{u,u}(\tau)$ です。相関器が受信信号と符号レプリカを突き合わせるとき、その出力の期待値はまさにこの $\theta$ に比例するのでした。

M系列の自己相関(復習と精密化)

$n$ 段の線形帰還シフトレジスタ(LFSR)の帰還多項式に $\mathrm{GF}(2)$ 上の原始多項式を選ぶと、周期が最大値 $N = 2^n - 1$ に達するM系列が得られます。M系列の自己相関は、次のきれいな2値性を持ちます。

$$\theta_u(\tau) = \begin{cases} N & \tau \equiv 0 \pmod N \\ -1 & \tau \not\equiv 0 \pmod N \end{cases}$$

ピーク $N$ に対してサイドローブは $-1$、規格化すれば $-1/N$ です。$n = 10$ なら $N = 1023$ で、サイドローブはピークの $1/1023 \approx -30$ dB。単独運用の測距符号として、これ以上を望むのが難しいほど理想的な特性です。実際、再生測距で仮定した「原点以外でほぼゼロ」の正体はこの $-1/N$ でした。

なお、次数 $n$ の原始多項式は複数存在し、M系列は全部で $\phi(2^n - 1)/n$ 本あります($\phi$ はオイラーのトーシェント関数)。$n = 10$ では $\phi(1023)/10 = 600/10 = 60$ 本です。「60本もあるなら、60機の探査機にそれぞれ1本ずつ配ればいいのでは?」——これが自然な発想ですが、ここに落とし穴があります。

M系列どうしの相互相関 — 楽園の終わり

同じ周期 $N$ を持つ2本の異なるM系列 $u, v$ の相互相関 $\theta_{u,v}(\tau)$ は、残念ながら自己相関のようには行儀よく振る舞いません。ペアの選び方によっては、$\theta_{u,v}(\tau)$ がピーク $N$ に対して無視できないほど大きな値を取ることが知られています。

代表的な数値を挙げると、$n = 10$($N = 1023$)の60本のM系列から任意にペアを選ぶと、最悪のペアでは相互相関の最大値が $383$ に達します。規格化すれば $383/1023 \approx 0.37$、デシベルで約 $-8.5$ dB です。つまり、他の探査機の信号が自分の信号よりわずか8.5dB強いだけで、疑似相関ピークが本物のピークと同じ高さになってしまうのです。深宇宙運用では探査機ごとの距離もアンテナ利得も大きく異なるため、受信電力に数十dBの差がつくことは珍しくなく(いわゆる遠近問題、near-far problem)、これでは符号分割は成立しません。

しかも厄介なことに、M系列ペアの相互相関の振る舞いは $n$ に対して単調に改善するわけではなく、ペアごとにばらばらです。「M系列をたくさん集めただけでは、相互相関の保証が何も得られない」——これがM系列の限界であり、次に述べるGold符号の出発点です。

プリファードペア — 例外的に行儀のよいペア

ところが、M系列のペアの中には例外的に相互相関が小さく抑えられる組が存在します。プリファードペア(preferred pair) と呼ばれるこの特別なペア $(u, v)$ は、相互相関がたった3値しか取りません。

$$\theta_{u,v}(\tau) \in \{\, -1,\; -t(n),\; t(n) - 2 \,\}, \qquad t(n) = \begin{cases} 2^{(n+1)/2} + 1 & (n \text{ 奇数}) \\ 2^{(n+2)/2} + 1 & (n \text{ 偶数}) \end{cases}$$

この $t(n)$ が以後の議論全体を支配する量です。$t(n)$ は $\sqrt{N} \approx 2^{n/2}$ のオーダーであり、規格化相互相関 $t(n)/N$ は $n$ を増やせば $2^{-n/2}$ のオーダーで指数的に小さくできます。$n = 10$ なら $t(10) = 2^6 + 1 = 65$ で、先ほどの最悪値 $383$ とは対照的です。

プリファードペアの片割れ $v$ は、$u$ からデシメーション(間引き) $v_i = u_{qi}$ によって構成できます。$q = 2^k + 1$ または $q = 2^{2k} - 2^k + 1$ の形の整数で、$\gcd(n, k)$ に関する一定の条件を満たすものを選ぶ、というのが古典的な構成法です(詳細はSarwate–Pursleyのサーベイに譲ります)。ひとつ重要な注意として、$n$ が4の倍数のときはプリファードペアが存在しないことが知られており、これが後述するGPSの設計($n = 10$)にも影を落としています。

Gold符号 — ペアから族へ

プリファードペアは2本しかありません。数十機に符号を配るには、この「行儀のよさ」を保ったまま本数を増やす必要があります。R. Gold(1967)の洞察は、プリファードペアの一方を巡回シフトしながらもう一方とXORするだけで、性質の保証された大家族が作れる、というものでした。

$T$ を1チップの巡回シフト演算子として、Gold符号族を次で定義します。

$$G(u, v) = \{\, u,\; v,\; u \oplus v,\; u \oplus Tv,\; u \oplus T^2 v,\; \dots,\; u \oplus T^{N-1} v \,\}$$

$\oplus$ はチップごとの $\mathrm{GF}(2)$ 上の加算(XOR)です。族の要素数は、シフト $N$ 通りの合成系列に元の2本を加えて

$$|G(u, v)| = N + 2 = 2^n + 1$$

となります。$n = 10$ なら1025本。ハードウェア的には、プリファードペアを生成する2本のLFSRを並べ、初期位相(シフト量)を変えてXORするだけで族の任意のメンバーが得られるという、実装上も極めて経済的な構成です。

そしてGold符号族の核心が、次の一様な相関上限の保証です。族から任意に選んだ2本 $x, y \in G(u,v)$ について、

$$|\theta_{x,y}(\tau)| \le t(n) = 2^{\lfloor (n+2)/2 \rfloor} + 1 \qquad (x \ne y \text{ のすべての } \tau, \; x = y \text{ の } \tau \not\equiv 0)$$

が成り立ちます。つまり相互相関だけでなく、各符号の自己相関サイドローブも同じ $t(n)$ で一様に抑えられるのです。「最悪ケースが保証されている」ことは、ミッションの成立性をリンクバジェットで事前に証明しなければならない宇宙システム設計において決定的に重要です。M系列60本の寄せ集めには最悪ケースの保証がなく、Gold符号1025本にはある——これが両者を分ける本質です。

代償もあります。合成系列 $u \oplus T^k v$ はもはやM系列ではないため、自己相関サイドローブは $-1$ から $t(n)$ オーダーまで悪化しています。単独運用ならM系列が最良、複数運用ならGold符号——という棲み分けは、このトレードオフの直接の帰結です。

どこまで良くできるのか — Welch限界

Gold符号は「十分良い」のでしょうか、それとも「まだ改善の余地がある」のでしょうか。この問いに答えるのがWelch(1974)の下界です。周期 $N$ の系列 $M$ 本からなる任意の族について、自己相関サイドローブと相互相関の最大値 $\theta_{\max}$ は

$$\theta_{\max} \ge N \sqrt{\frac{M - 1}{MN - 1}} \;\approx\; \sqrt{N} \qquad (M \gg 1)$$

を下回れません。どんなに符号設計を工夫しても、$\sqrt{N}$ オーダーの相関は原理的に避けられないのです。Gold符号の $t(n)$ は、$n$ が奇数のとき約 $\sqrt{2}\,\sqrt{N}$、偶数のとき約 $2\sqrt{N}$ ですから、この理論限界から高々小さな定数倍しか離れていません。なお $n$ が偶数のときは、Kasami系列(small set) が $2^{n/2} + 1 \approx \sqrt{N}$ を達成してWelch限界にほぼ到達しますが、族の大きさが $2^{n/2}$ 本(Goldの $2^n+1$ 本に対して)と小さいという別のトレードオフを抱えます。「相関の低さ」と「族の大きさ」もまた綱引きの関係にあるわけです。

相互相関が悪いと何が起きるか — 疑似ピークと測距誤差

相互相関の悪さが測距に及ぼす影響を定式化しておきます。所望探査機の信号(振幅 $A$、遅延 $\tau$)と干渉探査機の信号(振幅 $A_I$、遅延 $\tau_I$、符号 $v$)が重なって受信されるとき、符号 $u$ に対する相関器出力は

$$\Lambda(\Delta) = A\,\frac{\theta_u(\Delta - \tau)}{N} + A_I\,\frac{\theta_{u,v}(\Delta - \tau_I)}{N} + n(\Delta)$$

となります。第2項が符号間干渉です。影響は2つの形で現れます。

(1) 誤捕捉。 捕捉(アクイジション)段階では $\Lambda(\Delta)$ が閾値を超える遅延を探します。干渉項の疑似ピークの高さは最大 $A_I\, t(n)/N$ ですから、

$$\frac{A_I}{A} \cdot \frac{t(n)}{N} \gtrsim 1$$

すなわち干渉信号が所望信号より $20\log_{10}(N/t(n))$ dB以上強いと、他機の符号の疑似ピークに誤ってロックし、まったく別の(そして誤った)距離を報告する危険が生じます。GPS C/Aコードの場合この余裕は $20\log_{10}(1023/65) \approx 23.9$ dBで、屋内受信や干渉環境ではこの限界が実際に問題になります。

(2) 測距バイアス。 正しくロックしている場合でも、干渉項は真のピーク近傍で有限の傾きを持つため、ピーク位置(あるいは早遅相関器のゼロクロス点)をずらします。三角ピークの傾きが $1/T_c$ オーダーであることから、遅延誤差のオーダー評価は

$$|\delta\tau| \lesssim \frac{A_I}{A} \cdot \frac{t(n)}{N} \cdot T_c$$

となります。雑音による誤差(再生測距の $\sigma_\tau$)が積分時間を延ばせば平均化で減るのに対し、この符号間干渉によるバイアスは決定論的で、積分では消えない点が重要です。低相互相関の符号族を使うことは、この消せない系統誤差の上限を設計段階で保証する行為にほかなりません。

CCSDS 414.1-B の合成符号 — もう一つの数論的設計

深宇宙測距の現行標準 CCSDS 414.1-B (Pseudo-Noise and Regenerative Ranging) の符号は、Gold符号とはまた別の数論的アイデアで作られています。再生測距の末尾で触れた「コンポジット符号」の中身をここで開いてみましょう。

規格の符号は、周期がそれぞれ

$$L_1 = 2,\quad L_2 = 7,\quad L_3 = 11,\quad L_4 = 15,\quad L_5 = 19,\quad L_6 = 23$$

の6本の短い成分系列 $C_1, \dots, C_6$ を、チップごとの重み付き多数決で1本に合成したものです。成分の周期がどの2つも互いに素であることから、合成符号の周期は積

$$L = 2 \cdot 7 \cdot 11 \cdot 15 \cdot 19 \cdot 23 = 1{,}009{,}470 \text{ チップ}$$

になります。そして**中国剰余定理(CRT)**により、各成分の位相 $(\tau \bmod L_1, \dots, \tau \bmod L_6)$ の組が分かれば、全体の位相 $\tau \bmod L$ が一意に復元できます。受信機は約100万チップの符号全体と相関を取る必要はなく、成分ごとに(高々 $2 + 7 + \dots + 23 = 77$ 通りの)短い相関を取り、CRTで貼り合わせるだけでよいのです。符号長 $L$ に対して捕捉計算量が $\sum L_i$ で済む——これが合成符号の組合せ論的な妙味です。

規格には2つの変種があります。$C_1$(周期2の矩形波、レンジクロック)に大きな多数決重みを与えて総電力の約9割をレンジクロック成分に集中させ、チップレベルの測距精度を最優先する T4B と、重みを均して残り5成分の捕捉SNRを稼ぎ、捕捉時間を短縮する T2B です。精度(クロック成分の電力)と捕捉の速さ(サブ符号成分の電力)の綱引きを、多数決の重みという1つのパラメータで調停しているわけです。

符号長と一意距離範囲のトレードオフもこの数値で再訪できます。代表的なチップレート約 $2.068$ Mchip/s では符号1周期は $L\,T_c \approx 0.488$ 秒、2-way測距の一意距離範囲は

$$R_{amb} = \frac{c \, L \, T_c}{2} \approx \frac{(3.0 \times 10^8)(0.488)}{2} \approx 7.3 \times 10^4 \text{ km}$$

と、探査機の軌道予測誤差を十分カバーする約7.3万kmに達します。GPS C/Aコード(周期1ms、距離換算300km)と比べると、深宇宙測距がいかに長い符号を必要とし、それを捕捉可能に保つために合成符号という構造を選んだかが見て取れます。

実務での使われ方

• GPS C/Aコードは、Gold符号の最も有名な実使用例です。$n = 10$($N = 1023$、チップレート1.023 Mchip/s、周期1ms)のGold族1025本から、自己相関・相互相関特性の良い符号を選抜してPRN番号として各衛星に割り当てています。相互相関は3値 $\{-65, -1, +63\}$ に限定され、最悪でも $-23.9$ dBが保証されます。30機以上の衛星が同一周波数L1で同時送信するというシステム成立性そのものが、Gold符号の相関上限保証の上に立っています。近代化信号(L5、Galileo E1など)では、より長い符号やレジスタ生成によらないメモリコードを使ってこの余裕をさらに広げています。
• 深宇宙の再生測距では、CCSDS 414.1-BのT4B/T2B合成符号が標準です。NASA/JPLのDSNとESAのESTRACKが対応し、BepiColomboやJUICEなどのトランスポンダに実装されています。DSNのMSPA(Multiple Spacecraft Per Aperture)運用——火星に複数機が集まる時代に、1基の34mアンテナで複数探査機のダウンリンクを同時受信する運用——では、探査機ごとの信号の分離性が符号・サブキャリア設計に直接依存します。
• 符号分割の思想そのものは、直接拡散スペクトラム拡散(DSSS)の回で扱った通信への応用と地続きです。測距符号設計は「通信のためのCDMA」と同じ数学(低相互相関系列族)を「距離の物差し」に転用したものと言えます。また、探査機側がGNSS信号を受信して自律航法を行うGNSSオンボード航法は、まさにGold符号の相関特性を月遷移軌道の彼方で使い倒す応用です。

演習問題

1. $n = 10$ のGold符号族について、(a) $t(10)$ の値、(b) 規格化最悪相互相関 $t(10)/N$ をdB表示した値、(c) 族に含まれる符号の本数、をそれぞれ計算してください。また、GPSの運用衛星数(30機強)に対してこの本数がどの程度の余裕を持つか述べてください。

2. Welch限界 $\theta_{\max} \ge N\sqrt{(M-1)/(MN-1)}$ に $N = 1023$, $M = 1025$ を代入して下界を数値で求め、Gold符号の $t(10) = 65$、およびKasami系列(small set)の $2^5 + 1 = 33$ と比較してください。Kasami系列がWelch限界に対してどの程度「最適」に近いか、またその代償(族の大きさ $2^{n/2} = 32$ 本)について、Gold符号と対比して論じてください。

3. CCSDS 414.1-Bの合成符号について、(a) 成分周期 $2, 7, 11, 15, 19, 23$ がどの2つも互いに素であることを確認し(素因数分解を書き出す)、中国剰余定理が全体位相の一意復元を保証する理由を1〜2文で説明してください。(b) チップレート $2.068$ Mchip/s のときの符号周期(秒)と2-way一意距離範囲(km)を計算してください。(c) 仮に成分を使わず周期 $1{,}009{,}470$ の符号全体を総当たりで捕捉する場合と、成分ごとに捕捉してCRTで合成する場合とで、試すべき相関位相数の比を概算してください。

4. 探査機Aの測距信号を受信中、同じ周波数帯で探査機Bの信号が20dB強く受信されているとします(遠近問題)。両機の符号の規格化相互相関の最大値が (a) $-8.5$ dB(相性の悪いM系列ペア)の場合、(b) $-23.9$ dB(Gold符号)の場合のそれぞれについて、Bの信号が作る疑似相関ピークの高さをAの真のピークと比較し、誤捕捉の危険があるかどうかを判定してください。また、本文の式 $|\delta\tau| \lesssim (A_I/A)(t(n)/N)\,T_c$ を使い、(b) の場合のチップ周期に対する測距バイアスの上限を見積もってください。

まとめと次回予告

測距符号の設計は、「自己相関の鋭さ」「相互相関の低さ」「族の大きさ」「符号長(一意距離範囲)と捕捉計算量」という互いに綱を引き合う要求を、有限体上の数論で調停する仕事です。単独運用ならM系列の2値自己相関($N$ と $-1$)が理想的ですが、複数探査機の同時運用ではM系列ペアの相互相関に保証がないことが致命傷になります。プリファードペアのXORから生まれるGold符号族は、$2^n + 1$ 本という大きな族のすべてのペアに $t(n) = 2^{(n+1)/2} + 1$ オーダーの一様な相関上限を保証し、Welch限界が示す理論限界 $\sqrt{N}$ に定数倍まで迫ります。GPS C/Aコードはこの保証の上に30機以上の同時送信を成立させ、CCSDS 414.1-Bは互いに素な成分符号と中国剰余定理という別の数論で、100万チップ級の長周期と現実的な捕捉時間を両立させていました。

次回は視点を大きく変えて、TLE(2行軌道要素)の精度と限界を扱います。測距や追跡で得た観測をもとに軌道を配布する最も普及した形式であるTLEが、どんなモデル(SGP4)を前提とし、どの程度の精度を持ち、なぜ深宇宙探査機や精密な衝突回避には使えないのか——「軌道情報の流通フォーマット」という実務的な側面から軌道決定を見直します。

参考文献

• CCSDS 414.1-B, Pseudo-Noise and Regenerative Ranging
• CCSDS 414.0-G, Pseudo-Noise (PN) Ranging Systems(Green Book、T4B/T2B符号の設計解説)
• R. Gold, “Optimal Binary Sequences for Spread Spectrum Multiplexing,” IEEE Transactions on Information Theory, vol. 13, no. 4, 1967
• D. V. Sarwate and M. B. Pursley, “Crosscorrelation Properties of Pseudorandom and Related Sequences,” Proceedings of the IEEE, vol. 68, no. 5, 1980
• L. R. Welch, “Lower Bounds on the Maximum Cross Correlation of Signals,” IEEE Transactions on Information Theory, vol. 20, no. 3, 1974
• IS-GPS-200, NAVSTAR GPS Space Segment/Navigation User Segment Interfaces(C/Aコード仕様)
• J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76