変調・符号化#17

フレーム同期とASM — ビット列の海から「フレームの先頭」を掘り当てる

地上局に届くのは区切りのない連続ビット列だけ。各フレームの先頭に埋め込まれた既知パターンASMを相関検出で見つけ出す仕組みを、誤検出・見逃し確率のQ関数評価とCCSDS式の同期状態機械とともに定式化する。

フレーム同期ASM相関検波CCSDS状態機械

この回で学ぶこと

前回まで、変調・符号化・PLLによる搬送波追尾・スクランブリングによるビット統計の均一化と、探査機から届くビット列を正しく復調・復号するための技術を積み上げてきました。しかし、まだ大きな穴が1つ残っています。地上局の復調器が最終的に手にするのは、区切りのない連続したビットのストリーム $\{c_k\}$ だけです。この中のどこからどこまでが1つの「フレーム」(テレメトリの1パケット分のまとまり、通常は数百〜数千ビット)なのか、受信機はまだ何も知りません。

フレームの境界が分からなければ、その後段のあらゆる処理——Reed-Solomon復号やビタビ復号のブロック区切り、デスクランブリングのLFSRリセットタイミング、テレメトリパケットのヘッダ解釈——はすべて成立しません。1ビットでも境界がずれれば、そこから先のフレーム全体が意味不明のゴミになります。この「ビット列の海の中から、フレームの先頭という1点を確実に掘り当てる」仕事を担うのが**フレーム同期(Frame Synchronization)であり、その中核的な道具がアタッチド同期マーカー(Attached Sync Marker, ASM)**です。この回では、ASMを使った相関検出の仕組みを、誤検出確率・見逃し確率というQ関数を使った統計的な評価、そしてCCSDSが定める同期状態機械という2つの軸で定式化します。

直感的な導入: 既知のパターンを目印に埋め込む

発想はとてもシンプルです。各フレームの送信データの先頭に、送信側と受信側があらかじめ合意した既知のビットパターン(たとえばCCSDSで標準的に使われる32ビットの $\text{1ACFFC1D}_{16}$ )を毎回必ず付け加えて送信します。受信機は、届いた連続ビット列の中から「このパターンにそっくりな部分」を探し続け、それを見つけた位置を「ここがフレームの先頭だ」と判定します。

\underbrace{10101100\,11001111\,11111100\,00011101}_{\text{ASM (32 bit, 既知パターン)}} \; \Big| \; \underbrace{\cdots}_{\text{フレーム本体(ペイロード, スクランブル済み)}}

言葉にすると単純ですが、実際にはいくつもの困難が絡みます。まず、ASMがどこに来るか受信機は事前に知らない(だから探索しなければならない)。次に、探索は膨大な数の候補位置に対して行う必要があり、ノイズによってたまたまASMに似たビット列が非マーカー部分に現れてしまう可能性もゼロではない(誤検出)。逆に、本物のASM位置でもチャネル雑音によってビット誤りが発生し、完全一致しないために見逃してしまうこともある(見逃し)。この「探す」「見分ける」「確信を持つ」という一連のプロセスを、統計的な裏付けとともに設計するのがフレーム同期の理論です。

なお、前回学んだスクランブリングは、実はこのフレーム同期の前提条件そのものでもあります。ペイロード部分がスクランブルされていれば、そこに含まれるビットは統計的に0と1がほぼ等確率でランダムに現れる系列とみなせます。これにより、「ASM以外の位置にたまたまASMそっくりのパターンが出現する確率」を、以下で見るように単純な二項分布・正規近似で扱えるようになります。逆にスクランブルがかかっていないと、ペイロードの統計的な偏り(長い0の連続など)が誤検出確率の見積もりを歪め、フレーム同期の信頼性設計そのものが崩れてしまいます。

相関検出: ハミング距離によるパターンマッチング

受信機の内部では、既知のASMパターンを $L$ ビットの系列 $\{m_1, m_2, \dots, m_L\} \in \{0,1\}^L$ として保持しています。受信ビット列 $\{c_k\}$ の中で、位置 $k$ を起点とする $L$ ビットの窓 $\{c_k, c_{k+1}, \dots, c_{k+L-1}\}$ を切り出し、これとASMパターンとのハミング距離(異なるビットの個数)

D_k = \sum_{i=1}^{L} \big(m_i \oplus c_{k+i-1}\big)

を計算します。 $D_k = 0$ ならば完全一致、 $D_k$ が大きいほど不一致が多いことを意味します。この $D_k$ を、受信ビットが1つ届くたびに位置 $k$ を1つずつスライドさせながら逐次計算し続ける操作を**スライディング相関(sliding correlation)**と呼びます。 $D_k$ があらかじめ決めたしきい値 $d$ 以下になった位置 $k$ を「フレーム先頭の候補」として検出します。

D_k \le d \quad \Longrightarrow \quad \text{位置 } k \text{ をフレーム先頭候補とする}

これは双極性表現( $a_i = 2m_i - 1$ , $r_j = 2c_j - 1$ )を使った相関和 $C_k = \sum_i a_i r_{k+i-1}$ とも等価で、 $C_k = L - 2D_k$ の関係にあります(一致ビットは $+1$ 、不一致ビットは $-1$ に寄与するため)。以下ではより直感的な「許容ビット誤り数 $d$ 」という形でハミング距離ベースの定式化を進めます。

統計的評価: 2つの仮説とQ関数

$D_k$ の振る舞いは、位置 $k$ が本物のフレーム先頭かどうかで大きく異なります。これを2つの仮説として整理します。

仮説 $H_1$ (整合仮説): 位置 $k$ が真のASM開始位置である場合。 送信されたASMのビットに対し、チャネル(復調後のビット誤り率 $p_b$ )がランダムに誤りを与えます。各ビットが独立に確率 $p_b$ で反転すると仮定すれば、不一致ビット数は二項分布に従います。

D_k \,\big|\, H_1 \sim \text{Binomial}(L, p_b)

$L$ が十分大きければ中心極限定理により正規分布で近似でき、平均・分散は

\mathbb{E}[D_k \mid H_1] = L p_b, \qquad \text{Var}[D_k \mid H_1] = L p_b(1-p_b)

仮説 $H_0$ (非整合仮説): 位置 $k$ がASMとは無関係な、ペイロード中のたまたまの位置である場合。 ここで前節の議論が効いてきます。ペイロードはスクランブルされているため、各ビット $c_{k+i-1}$ は既知のマーカービット $m_i$ と独立に、確率 $1/2$ で一致・不一致すると近似できます。したがって

D_k \,\big|\, H_0 \sim \text{Binomial}(L, 1/2), \qquad \mathbb{E}[D_k \mid H_0] = \frac{L}{2}, \qquad \text{Var}[D_k \mid H_0] = \frac{L}{4}

この2つの分布は、 $L$ が数十ビット程度でもかなり離れた位置(平均 $Lp_b$ 付近と平均 $L/2$ 付近)に分布します。しきい値 $d$ をこの中間のどこかに置くことで、両者を識別する2値検定を構成できます。

誤検出確率(False Alarm Probability) $P_{FA}$ は、非整合位置( $H_0$ )なのにたまたま $D_k \le d$ となってしまい、誤ってフレーム先頭だと判定してしまう確率です。正規近似を使うと、

P_{FA} = \Pr(D_k \le d \mid H_0) \approx Q\!\left(\frac{L/2 - d}{\sqrt{L/4}}\right) = Q\!\left(\frac{L - 2d}{\sqrt{L}}\right)

見逃し確率(Miss Detection Probability) $P_{MD}$ は、整合位置( $H_1$ )なのにチャネル誤りが多すぎて $D_k > d$ となり、正しいフレーム先頭を見逃してしまう確率です。

P_{MD} = \Pr(D_k > d \mid H_1) \approx Q\!\left(\frac{d - L p_b}{\sqrt{L p_b(1-p_b)}}\right)

ここで $Q(\cdot)$ はPCM/PSK/PMの回で導入した標準正規分布の裾の確率関数です。この2つの式が、フレーム同期設計の心臓部です。しきい値 $d$ を小さくする(厳しくマッチを要求する)と $P_{FA}$ は下がりますが $P_{MD}$ は上がります。逆に $d$ を大きくする(甘くマッチを許す)と $P_{MD}$ は下がりますが $P_{FA}$ が上がります。 $P_{FA}$ と $P_{MD}$ はしきい値 $d$ を介してトレードオフの関係にあり、この構造は検波理論で扱う一般的な2値仮説検定とまったく同じ形をしています。

しきい値設計と系列長 $L$ の効果

実務上のしきい値設計は、「チャネルのビット誤り率 $p_b$ が想定される最悪値のときでも見逃し確率を十分小さく保ちつつ、ペイロード中の誤検出も許容範囲に収める」という制約付き最適化として行われます。典型的な設計手順は次の通りです。

リンク設計から想定される最悪ケースのビット誤り率 $p_b$ を決める(たとえば $E_b/N_0$ の運用マージン込みで $p_b = 10^{-2}$ 程度)。
$P_{MD}$ を許容値(たとえば $10^{-3}$ 以下)に抑えるための $d$ の下限を、見逃し確率の式から逆算する。
その $d$ における $P_{FA}$ を確認し、フレーム長あたりに生じる誤検出の期待回数(1フレーム分の探索候補位置の数 $\times P_{FA}$ )が運用上許容できる水準か検証する。

ここで系列長 $L$ (マーカーのビット長)が本質的な役割を果たします。 $P_{FA}$ の式 $Q\big((L-2d)/\sqrt{L}\big)$ を見ると、 $d/L$ の比率(相対的な許容誤り率)を一定に保ったまま $L$ を大きくすると、引数 $(L-2d)/\sqrt{L}$ は $\sqrt{L}$ のオーダーで大きくなり、 $Q$ 関数は指数的に急減します。つまりマーカーを長くするほど、誤検出確率は劇的に下がる。 これがCCSDSをはじめ多くの規格が32ビットやそれ以上の長いマーカーを採用する理由です。一方で、マーカーはペイロードではなくオーバーヘッドですから、フレーム全体の長さ $N$ に対する比率 $L/N$ がそのまま伝送効率の損失になります。フレーム長が数千ビットあれば32ビットのオーバーヘッドは1%未満で無視できますが、低レートミッションのように短いフレームを使う場合には無視できない比率になり得ます。「マーカーを長くして信頼性を上げる」ことと「マーカーを短くしてオーバーヘッドを減らす」ことは、真正面から対立するトレードオフであり、この回のテーマそのものです。

フレーム同期状態機械: 未同期・検索・確認・ロック

これまでの議論は「1回のスライディング相関でどう判定するか」という静的な話でした。しかし実際の受信機は、時間とともに探索・確認・追尾という異なるモードを行き来する必要があります。ノイズによる偶発的な誤検出やたまたまの見逃しに対して頑健であるために、多くの実装(CCSDS 131.0-Bが規定する同期戦略、および B. Sklarの教科書で解説される一般的なフレーム同期回路)は、次のような状態機械として設計されます。

未同期(SEARCH)状態: フレームの先頭位置がまったく分かっていない状態。受信ビットが1つ届くたびにスライディング相関を実行し、 $D_k \le d$ となる位置を探し続ける。候補が見つかったら CHECK 状態に遷移する。
確認(CHECK)状態: 候補位置が見つかったら、そこから1フレーム分(既知のフレーム長 $N$ ビット)先に進んだ位置に、再び同じ許容誤り数 $d$ 以内でASMが現れるかを確認する。この「次のフレーム周期でも同じ相対位置にマーカーが現れるか」という確認を、あらかじめ決めた回数(たとえば連続2〜3フレーム)成功するまで繰り返す。途中で一度でも確認に失敗すれば、その候補は偶発的な誤検出だったとみなし、SEARCH状態に戻って探索をやり直す。
ロック(LOCK)状態: CHECK状態での確認を規定回数連続で通過すると、フレーム同期が確立したとみなしLOCK状態に入る。以降はビットごとの全面探索をやめ、既知のフレーム長 $N$ だけ離れた予測位置だけを毎フレーム確認する軽量な追尾モードに切り替わる。

LOCK状態にはさらに重要な工夫があります。LOCK中に1回や2回、予測位置でのハミング距離が一時的にしきい値を超えても、即座にSEARCH状態へ戻ることはしません。 これは「フライホイール(flywheel)」的な振る舞いと呼ばれ、あらかじめ決めた連続ミス許容回数(たとえば連続3〜5フレーム)を超えて初めて同期喪失と判断し、SEARCH状態に戻ります。この設計により、一時的な深いフェード(信号レベルの落ち込み)による偶発的なミスマッチで、せっかく確立した同期を無駄に失うことを防いでいます。逆に言えば、この許容回数を大きくしすぎると、本当にリンクが切れた場合の検知が遅れるという別のトレードオフも生じます。

     [誤検出/雑音]
   ┌─────────────┐
   ▼             │
 SEARCH ──候補発見──▶ CHECK ──確認失敗──▶ SEARCH
                       │
                  確認成功(規定回数)
                       ▼
                     LOCK ──ミス許容回数超過──▶ SEARCH
                       │
                  毎フレーム予測位置を確認
                       ▼
                     LOCK (継続)

この探索→確認→ロックという3段構えは、単発のしきい値判定だけでは避けられない「偶発的な誤検出でロックしてしまう」「一時的な雑音でロックを失う」という2つの実運用上の弱点を、時間方向の冗長性によって補うものです。

実務での使われ方

CCSDSの CCSDS 131.0-B (TM Synchronization and Channel Coding) は、テレメトリのアタッチド同期マーカーとして、伝統的に32ビットのマーカー

\text{ASM} = \text{1ACFFC1D}_{16} = \texttt{0001 1010 1100 1111 1111 1100 0001 1101}

を規定しています。この32ビットパターンは、自己相関特性(パターン自身をずらして重ねたときの一致度)が低くなるように設計されており、たまたまASM自身の内部でずれた位置に重ねてもよく一致してしまう、という「疑似ロック」を起こしにくい性質を持っています。

フレーム長とマーカー長の比率: CCSDSのTMトランスファフレームは、典型的には数百〜数千バイト(たとえば1024バイト = 8192ビット程度)のペイロードを持つことが多く、この場合32ビットのASMが占める割合は1%未満とごくわずかです。一方、低データレートの深宇宙リンクや、セーフモード時の縮退したテレメトリでは、より短いフレーム長が使われることもあり、その際にはマーカーのオーバーヘッド比率が相対的に大きくなるため、マーカー長を短くするか、あるいはより効率の良いフレーム設計とのバランスが検討されます。
符号化方式との関係: 畳み込み符号やターボ符号など、強力な誤り訂正符号と組み合わされた高レートリンクでは、フレーム(コードブロック)自体が非常に長くなる傾向があり、探索すべき候補ビット位置の総数も増えるため、誤検出確率を十分低く保つ目的で、より長いマーカーやマーカー設計の見直しが行われることがあります。
マーカーは意図的にスクランブル対象外とする: 前回触れた通り、ASM自体は固定パターンとして送信され、スクランブラの対象からは除外されます。これにより受信機は、スクランブルされたペイロードの手前で確実にマーカーを検出し、そこを起点にデスクランブル用LFSRを既知の初期状態にリセットできます。マーカー検出とデスクランブルの開始点は、常にワンセットで設計されます。
DSN(Deep Space Network)の受信機でも、この階層的な状態機械によるフレーム同期がテレメトリ処理チェーンの一部として実装されており、ロック状態の可否がテレメトリデータのリアルタイム可用性を左右する重要な運用パラメータとして監視されています。

演習問題

マーカー長 $L = 32$ 、想定ビット誤り率 $p_b = 0.05$ のとき、しきい値 $d = 4$ ビットでの見逃し確率 $P_{MD}$ を正規近似の式 $P_{MD} \approx Q\big((d - Lp_b)/\sqrt{Lp_b(1-p_b)}\big)$ を用いて計算してください。
同じ $L=32$ , $d=4$ のとき、誤検出確率 $P_{FA} \approx Q\big((L-2d)/\sqrt{L}\big)$ を計算してください。この2つの結果から、 $d=4$ という設計が「見逃しに厳しく誤検出に甘い」設計か、その逆かを議論してください。
マーカー長を $L=32$ から $L=64$ に倍増させ、許容誤り数の比率 $d/L$ を一定(すなわち $d=8$ )に保った場合、 $P_{FA}$ の式の引数 $(L-2d)/\sqrt{L}$ がどう変化するかを計算し、誤検出確率が改善する理由を、 $Q$ 関数の単調減少性を踏まえて説明してください。あわせて、この変更がフレーム全体の伝送効率に与える影響についても述べてください。
LOCK状態において、予測位置でのハミング距離が1フレームだけしきい値を超えても即座にSEARCH状態に戻さない「フライホイール」的設計が採用される理由を、この回で学んだ内容(特にリンクの一時的なフェードと $P_{MD}$ の関係)をもとに説明してください。また、この連続ミス許容回数を極端に大きく設定した場合に生じうる別の問題点についても考察してください。

まとめと次回予告

フレーム同期は、区切りのない連続ビット列の中から「フレームの先頭」という1点を確実に見つけ出すための技術です。既知のビットパターンであるASM(アタッチド同期マーカー)を各フレームの先頭に付与し、受信機がスライディング相関(ハミング距離)でそれを探索します。整合仮説 $H_1$ と非整合仮説 $H_0$ の下でのハミング距離の分布を二項分布・正規近似で評価することで、誤検出確率 $P_{FA}$ と見逃し確率 $P_{MD}$ をそれぞれQ関数で定式化でき、両者はしきい値 $d$ を介したトレードオフの関係にあることを見ました。またマーカー長 $L$ を伸ばすほど誤検出確率は指数的に改善する一方、フレームのオーバーヘッドが増えるという、この回のもう1つのトレードオフも確認しました。さらに、単発の判定だけに頼らず、SEARCH・CHECK・LOCKという時間方向に冗長性を持たせた状態機械によって、偶発的な誤検出や一時的なフェードに対して頑健な同期を実現する設計思想も見てきました。

次回は変調方式の話に戻り、限られた帯域の中でより多くのビットを1シンボルに詰め込む**高次変調(APSK: Amplitude and Phase Shift Keying)**を扱います。BPSKやQPSKよりも信号点配置が複雑になる一方で、電力効率と帯域効率のトレードオフをどう最適化するかという、通信路容量に近づくための工夫を見ていきます。

参考文献

CCSDS 131.0-B, TM Synchronization and Channel Coding
J. L. Massey, “Optimum Frame Synchronization,” IEEE Transactions on Communications, vol. 20, no. 2, 1972
B. Sklar, Digital Communications: Fundamentals and Applications, 2nd ed., Prentice Hall
J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76
DSN Telecommunications Link Design Handbook, DSN No. 810-005