Galileo HAS（high accuracy service）その2

category: gnss

はじめに

欧州のGalileo測位衛星が放送するメッセージHAS（ハス、high accuracy service）の復号にチャレンジしています。

私には、HASの仕様書Galileo High Accuracy Service Signal-in-Space Interface Control Document (HAS SIS ICD)（以下、仕様書と略します）を読んでもわからないところがありました。

そこで、ソフトウェア定義無線Pocket SDRを用い、実際に手を動かして復号してみます。あと一歩でHASメッセージを解読できそうです。

E14 HASS=Operational(1) MT=1 MID=25 MS= 2 PID=117 -> A new page for MID=25
E15 Dummy page (0xaf3bc3)
E03 HASS=Operational(1) MT=1 MID=25 MS= 2 PID= 47
------ HAS decode with the pages of MID=25 MS=2 ------
0x8ef2012050099f95c32b0000ab06cbf260ba0d4ff3ff56096f9a8437cfe103fa97807b0ff5f0ab
fd7801dfd080079d40141b50148153f4204efd87eb00bdffbfd9013403a046fec83b7fd406ffe182
dbf99fedfd801cbf3caaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Time of hour TOH: 2287 s
Mask            : off
Orbit correction: off
Clock full-set  : on
Clock subset    : off
Code bias       : off
Phase bias      : off
Mask ID         : 9
IOD Set ID      : 0
E34 HASS=Operational(1) MT=1 MID=25 MS= 2 PID=207 -> Enough pages for MID=25
E05 Dummy page (0xaf3bc3)

HASのリードソロモン符号利用は誤り訂正のためではない

一般に、リードソロモン符号（Reed-Solomon code、以下RS符号と略します）は、伝送路にて発生した受信語の誤りを訂正するために用いられます。これは、多元記号（例えば8ビットをひとかたまりとした256状態を表す256元記号）からなるメッセージ伝送の複数誤りを訂正できるので、通信や放送などに広く用いられています。

誤り訂正は、冗長情報の伝送により達成されます。送信側では、メッセージに加え、そのメッセージを一定の規則で要約した冗長情報も伝送します。一方、受信側では、その冗長情報を含む受信語を要約するシンドロームの計算と、シンドロームを用いた誤り位置計算から、誤った受信語を訂正します。

しかしながら、HAS情報が伝送されるE6B信号には、たたみ込み符号（convolutional code）とインターリーブによる誤り訂正がすでに適用されているので、さらに誤り訂正として、RS符号を適用する理由はありません。HASで用いられるRS符号の生成行列（G: generator matrix）が、256行32列と、巨大である理由がわかりませんでした。また、仕様書のHAS復号例にあるPID（encoded page identification）の役割や、また、続くメッセージのPID値が不連続になる理由が、わかりませんでした。

実は、HASメッセージ伝送は、秘密分散の原理にて、メッセージを最大256「ピース」（正式な用語はHASページです）に分割し、これらを複数衛星（空間軸）と連続する複数時間スロット（時間軸）を用いて、時空間で異なる複数ピースを伝送します。ひとつの衛星は、1秒間に1ピースを放送します。受信機は、複数衛星から放送される異なるピースを同時受信します。受信機にてそのヘッダに記されたMS（message size、424ビットからなるピース数）だけピースが集まれば、これらのピースに生成行列の逆行列をかけて、HASメッセージを復号します。この復号方法は、MSを超えるピースを扱いませんので、誤り訂正を行いません。もちろん、受信機は、MSを超えるピースを集めれば、理論的には誤り訂正を行えますが、そのような誤り訂正を行う動機はないでしょう。

例えば、MS=6で、3秒間にわたる5衛星でのメッセージ伝送を考えると、送信側で用意するピース数は15であり、受信側ではそのうちの6ピース受信できればメッセージ復号可能です。このとき、3衛星からの信号を同時受信できれば、2秒間でHASメッセージが復号できます。また、2衛星からの信号しか受信できなくても、3秒間でメッセージ復号が可能です。受信できる衛星は場所依存ですが、最大32までのMSに比べて、候補となる全ピース数は最大255と潤沢にあるので、メッセージ長と伝送に必要な最大時間を決めれば、すべての衛星に異なるピースを割り当てることができます。

全ピース数は、必ずしも255でなくても構いません。MSが小さいときには全ピース数を少なく、例えば20ピース程度にすることも可能です。全ピース数を少なくすると、時間軸方向のピース数が少なくなるのでメッセージを迅速に伝送できますが、受信衛星数が少ない環境ではメッセージ復号に失敗します。運用者が決定する全ピース数は、メッセージ伝送効率とメッセージ到達率とのトレードオフで決定されます。

このRS符号は、この擬似ランダム化した複数ピース作成のためだけに用いられます。そして、PIDは、運用者がランダムに決定したRS符号の生成行列の行番号を表します（仕様書p.49）。

where D is the sub-matrix created from the RS generator matrix using the k rows corresponding to the received PIDs and the first k columns.

このメッセージ伝送方法は、High Parity Vertical Reed-Solomon（HPVRS）と呼ばれます。このHPVRSのキーアイディアは、自由に符号設計ができるRS符号の特長を用いて多くの冗長ピースを作り出し、秘密分散にて効率的な情報並列伝送を行うことにあります。

この生成行列Gは、1行目から32行目までの単位行列と、33行目から256行までのRS符号パリティ行列からなります。このとき、PIDが1から32のメッセージについては、そのメッセージがそのまま伝送されることになりますが、そのようなPIDを持つピースは見当たりませんでした。すなわち、Galileo HASでは、メッセージをそのままの形では伝送しないようです。

受信機は、ピースのPIDと受信語W_PIDを集めます。そして、受信機は、MSのピースを集め終えると、Gから複数PID行を切り出して行列Dを作成し、ガロア体上でその逆行列D^-1を求め、その逆行列にWをかけてHASメッセージを得ます。MSのピースが集まらないとD^-1を求められないので、1ピース受信するたびの逐次的なメッセージ復号はできません。仕様書にある「逆行列計算は1回で良い」（p.39）の表現は誤解を招くような気がします。

Note that only one matrix inversion is required for all vertical words and that Galois Field arithmetic needs to be taken into account for all operations.

ここまでわかって、ようやくHAS復号コードを書く準備ができました。

Pythonのgaloisモジュール

このガロア体（Galois Field）での逆行列を求めるために、Pythonのgaloisモジュールを用いました。PythonがインストールされているPCでは、pip install galoisにて、このgaloisモジュールをインストールできます。Dr. Rui Hirokawaさんが公開されているCSSRlibのHASデコーダコードppp-has.pyも、このgaloisモジュールを用いています。

このgaloisモジュールを利用するためには、バージョン3.7以上、3.11未満の範囲のPythonが必要です。私が普段利用しているPythonバージョン3.11では、galoisモジュールをインストールできませんでした。

$ pip3.11 install galois
Collecting galois
  Using cached galois-0.3.3-py3-none-any.whl (4.2 MB)
... snip ...
        File "/private/var/folders/ls/1jj34q_50k947833j_gt_w5w0000gn/T/pip-install-zpbz5bfl/numba_c911d79cd9fd41a69ba437728aecb9f4/setup.py", line 48, in _guard_py_ver
          raise RuntimeError(msg.format(cur_py, min_py, max_py))
      RuntimeError: Cannot install on Python version 3.11.2; only versions >=3.7,<3.11 are supported.
      [end of output]

そこで、私はPythonのバージョンを3.10にダウングレードしました。モジュールgaloisの利用の際に警告が出ますが、実害はなさそうです。

Python 3.10.10 (main, Feb 13 2023, 03:30:25) [Clang 14.0.0 (clang-1400.0.29.202)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import galois
>>> GF=galois.GF(256)
OMP: Info #276: omp_set_nested routine deprecated, please use omp_set_max_active_levels instead.
>>>

Pocket SDRを用いたGalileo HASメッセージの観測

Pocket SDRにて観測したE6B信号のログファイルからHASメッセージを復号するPythonコードpksdr2has.pyを作成しました。まだ、このコードには、具体的な補強値を復号する機能はありません。

このコードは、bitstringモジュール、galoisモジュール、numpyモジュールを利用しますので、実行前にこれらのインストールが必要です。

pip install bitstring galois numpy

RS符号の生成行列は、仕様書のPDFファイルに添付されていたテキストファイル Galileo-HAS-SIS-ICD_1.0_Annex_B_Reed_Solomon_Generator_Matrix.txt にあります。これをPythonにて読み込めるように加工しました。また、実際の復号例が、Galileo-HAS-SIS-ICD_1.0_Annex_D_HAS_Message_Decoding_Example.txt にあり、とても参考になりました。上述のCSSRlibにあるppp-has.pyにも、コーディングの参考にさせていたきました。

Pocket SDRのログファイルでは、Galileo HASメッセージが存在するC/NAV（commercial navigation）メッセージのたたみ込み符号の終端ビット（tail bit、6ビット）を含みません。終端ビットはメッセージ解読に不必要です。また、このログファイルでは、16進表記の際に余った2ビットをゼロ詰めしています。したがって、仕様書のC/NAVページ長が492ビットであるのに対して（13ページ、表5）、Pocket SDRログでのC/NAVページ長は61バイト（488ビット=492-6+2ビット）になります。

Pocket SDRを用いて、2023-02-19 13:38:31 UTCから約1分間、観測し、E6B信号を抽出したログファイル20230219_133831e6b.txtを処理します。観測方法は、Pocket SDRを用いたGalileo E6B信号の受信にあります。

./pksdr2has.py < 20230219_133831e6b.txt

E14 HASS=Operational(1) MT=1 MID=25 MS= 2 PID=117 -> A new page for MID=25
E15 Dummy page (0xaf3bc3)
E03 HASS=Operational(1) MT=1 MID=25 MS= 2 PID= 47

衛星番号（E14など）は、HASメッセージに含まれませんので、Pocket SDRのログから抽出しています。E15のヘッダには、無効メッセージを表すaf3bc3（16進数表記）が書かれていました。他にも、このような無効メッセージを放送している衛星は、E15の他にもありました。

この最初のMID（message ID）が2であるメッセージに着目し解読します。このメッセージのMSは2なので、ここでは、E14とE03の2衛星からメッセージが受信により、このメッセージを復号できます。その2ピース848ビット長の受信語をD^-1にて復号して得たHASメッセージは次の通りです。

------ HAS decode with the pages of MID=25 MS=2 ------
0x8ef2012050099f95c32b0000ab06cbf260ba0d4ff3ff56096f9a8437cfe103fa97807b0ff5f0ab
fd7801dfd080079d40141b50148153f4204efd87eb00bdffbfd9013403a046fec83b7fd406ffe182
dbf99fedfd801cbf3caaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

このHASメッセージヘッダの解読結果は次の通りです。

Time of hour TOH: 2287 s
Mask            : off
Orbit correction: off
Clock full-set  : on
Clock subset    : off
Code bias       : off
Phase bias      : off
Mask ID         : 9
IOD Set ID      : 0

このHASメッセージには、clock full-set情報が含まれていることがわかります。その後に現れるMID=2のピースはメッセージ復号に不要ですので、このコードではこれらを無視しています。

E34 HASS=Operational(1) MT=1 MID=25 MS= 2 PID=207 -> Enough pages for MID=25
E08 HASS=Operational(1) MT=1 MID=25 MS= 2 PID= 77 -> Enough pages for MID=25
E14 HASS=Operational(1) MT=1 MID=25 MS= 2 PID=118 -> Enough pages for MID=25
E03 HASS=Operational(1) MT=1 MID=25 MS= 2 PID= 48 -> Enough pages for MID=25
E34 HASS=Operational(1) MT=1 MID=25 MS= 2 PID=208 -> Enough pages for MID=25
E08 HASS=Operational(1) MT=1 MID=25 MS= 2 PID= 78 -> Enough pages for MID=25

新しいMIDを発見したら、同様の操作を繰り返します。~~一つのピースの伝送時間が1秒間なので、MIDの順序が入れ替わることはありません。~~ 以前のMIDが再び現れることもあるので、過去のいくつかのMIDに対するマスク情報を保持する必要があるかもしれません。(2023-03-09訂正)

運用開始前のHASメッセージ

同様に、HAS運用開始前のメッセージを復号してみます。Pocket SDRにて、以前に収録した2022-09-30 11:56:17 UTCから約1分間の生データからE6B信号を抽出して、そのログファイル20220930_115617e6b.txtを処理します。

./pksdr2has.py < 20220930_115617e6b.txt

E21 HASS=Test(0) MT=1 MID=11 MS=18 PID= 76 -> A new page for MID=11
E27 HASS=Test(0) MT=1 MID=11 MS=18 PID=152
E19 Dummy page (0xaf3bc3)
E21 HASS=Test(0) MT=1 MID=11 MS=18 PID= 75
E27 HASS=Test(0) MT=1 MID=11 MS=18 PID=151
E19 Dummy page (0xaf3bc3)
E21 HASS=Test(0) MT=1 MID=16 MS= 2 PID=199 -> A new page for MID=16
E27 HASS=Test(0) MT=1 MID=16 MS= 2 PID=239
------ HAS decode with the pages of MID=16 MS=2 ------
0xd45200bb5008b40003cdec680006e4129cae0220237e5e01ffd5fccc0f3f0700ffcd3813c91ee5
c003f0b000fc4ffbff4500080040002490008000197ef402affcc00002bfe2ff783040fbfc08007f
5a000042fd98207fee07cfc27ec403407ef7d7dc15555555555555
Time of hour TOH: 3397 s
Mask            : off
Orbit correction: off
Clock full-set  : on
Clock subset    : off
Code bias       : off
Phase bias      : off
Mask ID         : 5
IOD Set ID      : 27
E19 Dummy page (0xaf3bc3)
E21 HASS=Test(0) MT=1 MID=16 MS= 2 PID=200 -> Enough pages for MID=16
E27 HASS=Test(0) MT=1 MID=16 MS= 2 PID=240 -> Enough pages for MID=16
E19 Dummy page (0xaf3bc3)
E21 Dummy page (0xaf3bc3)

なんと、有効そうなデータが送信されていました。しかしながら、ヘッダのHASS（HAS Status）がTestになっています。

おわりに

Galileo HASのRS符号は、誤り訂正のためではなく、メッセージを分割して並列伝送するためのものです。みちびきのCSSR（compact state space representation）と、GaliloのHASとは、まったく異なる方法でその補強メッセージを伝送します。みちびきCSSRが30秒周期でメッセージ伝送するのに対して、Galilo HASは周期を持たないところが面白いです。どちらも素晴らしく、それぞれに利点があります。

みちびきCSSRデコーダQZS L6 Toolの作成には苦労しましたが、Galileo HASデコーダの作成も大変でした。特に、High Parity Vertical Reed-Solomon（HPVRS）のアイディアを学ぶのに、時間を費やしました。それぞれで、どのようにメッセージをペイロード内に納めているのかを観測してみようと思います。

現在、CSSRメッセージから、RTCM SSRメッセージへの変換に取り組んでいます。将来、みちびきCSSRと、Galileo HASとで、RTKLIBを用いて単独精密測位ができるよう、QZS L6 Toolを修正しています。

Galileo HAS（high accuracy service）その3 27^th October 2023
Galileo HAS（high accuracy service）その1 7^th February 2023