Galileo HAS（high accuracy service）part 2

Introduction

I am trying to decode the message HAS (high accuracy service) broadcast by the European Galileo navigation satellites.

Even after reading the HAS specification Galileo High Accuracy Service Signal-in-Space Interface Control Document (HAS SIS ICD) (hereinafter abbreviated as the specification), there was something I did not understand.

Therefore, using Pocket SDR, a software-defined radio, I will actually try to decode HAS message by hand. It looks like I am one step closer to decode HAS messages.

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)

Use of Reed-Solomon code in HAS is not for error correction

In general, Reed-Solomon code (RS code) is used to correct errors in received words that occur on transmission lines. It is widely used in communications and broadcasting because it can correct multiple errors in message transmissions consisting of multi-element symbols (for example, a 256-element symbol that represents 256 states in a group of 8 bits).

Error correction is achieved by transmitting redundant information. In addition to the message, the sender also transmits redundant information that summarizes the message according to certain rules. On the other hand, the receiving side corrects erroneous received words by calculating a syndrome that summarizes the received words including the redundant information and by calculating the error position using the syndrome.

However, since the E6B signal carrying the HAS information already has error correction by convolutional code and interleaving applied, there is no reason to apply the RS code for additional error correction. I didn’t understand why the RS code generator matrix G used in HAS is huge, 256 rows and 32 columns. Also, I didn’t understand the role of PID (encoded page identification) in the HAS decoding example in the specification, and the reason why the PID values of subsequent messages are discontinuous.

In fact, HAS message transmission uses the principle of secret sharing to divide a message into a maximum of 256 “pieces” (the formal term is the HAS page), which are divided into multiple satellites (spatial domain) and multiple continuous time slots (time domain). A HAS message is divided into and broadcast different pieces in time and space domains. One satellite broadcasts one piece per second. The receiver receives different pieces broadcast from multiple satellites at the same time. After completed the piece collection that the number of pieces is MS (message size, the number of pieces consisting of 424 bits) written in the header, the receiver start decoding the HAS message by multiplying the pieces and the inversion matrix of the generator matrix. Because the decoding method does not handle pieces beyond MS, it does not perform error correction. Of course, a receiver could theoretically correct errors if it collected more pieces than MS, but it would have no incentive to do so.

For example, when MS=6 and a message is transmitted by 5 satellites for 3 seconds, the number of pieces prepared on the transmitting side is 15, and the message can be decoded by the receiving side if 6 pieces are received. At this time, if signals from 3 satellites can be received simultaneously, the HAS message can be decoded in 2 seconds. In addition, even if signals from only two satellites can be received, message decoding is possible in 3 seconds. The number of visible satellites is site-dependent, but compared to MS, which has a maximum of 32, the total number of possible pieces is 255 at maximum, and a different piece can be assigned for each satellite.

The total number of pieces does not necessarily have to be 255. When MS is small, it is possible to reduce the total number of pieces, say 20 pieces. Reducing the total number of pieces reduces the number of pieces in the time domain, and it leads to quick transmission of messages, but it also tends to fail in decoding message in an environment with a small number of visible satellites. The total number of pieces determined by the operator is a trade-off between message transmission efficiency and message delivery rate.

This RS code is used only for this pseudo-randomized multi-piece creation. PID represents the row number of the RS code generator matrix randomly determined by the operator (at page 49 in the specification).

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.

This method of message transmission is called High Parity Vertical Reed-Solomon (HPVRS). The key idea of this HPVRS is to create many redundant pieces by using the feature of RS code that allows free code design, and to perform efficient parallel transmission of information by secret sharing.

This generator matrix G consists of the identity matrix from the 1st to 32nd rows and the RS code parity matrix from the 33rd to 256th rows. It means that a message with PID ranging from 1 to 32 is transmitted as it is. At this time, however, I have not found pieces with such PID. In other words, Galileo HAS does not seem to transmit messages as is.

The receiver collects the piece’s PID and the received word W_PID. After collecting the MS pieces, the receiver obtains the matrix D created by cutting out multiple PID rows from G, calculates the inverse matrix D^-1 on the Galois field, and multiply the inverse matrix by W to get the HAS message. Since D^-1 cannot be obtained unless MS pieces are collected, it is not possible to sequentially decode the message each time one piece is received. I wonder the expression “only one inverse matrix calculation is sufficient” in the specifications at page 39 may be confusing.

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.

Now that we know this, we are finally ready to write the HAS decoder.

Python’s galois module

I used Python’s galois module to find the inverse of this Galois field. We can install this galois module with pip install galois on a PC with Python installed. The HAS decoder code ppp-has.py in the CSSRlib published by Dr. Rui Hirokawa also uses this galois module.

In order to use this galois module, Python version 3.7 or higher but less than 3.11 is required. My usual Python version 3.11 did not allow me to install the galois module.

$ 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]

Therefore, I downgraded my Python version to 3.10. A warning is issued when using the module galois, but it seems that there is harmless.

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.
>>>

Observation of Galileo HAS messages using Pocket SDR

I created a Python code pksdr2has.py that decodes HAS message from the E6B signal log file observed by Pocket SDR. This code does not yet have the ability to decode the augmentation values.

This code uses the bitstring, galois and numpy modules, so we need to install them before running.

pip install bitstring galois numpy

The RS code generator matrix can be found in the text file Galileo-HAS-SIS-ICD_1.0_Annex_B_Reed_Solomon_Generator_Matrix.txt which was attached to the specification PDF file. I modified it so that it can be read by Python. Also, an actual decoding example is in Galileo-HAS-SIS-ICD_1.0_Annex_D_HAS_Message_Decoding_Example.txt, which was very helpful. I also referred to ppp-has.py in CSSRlib mentioned above for coding.

Pocket SDR log files do not include the tail bit (6 bits) of the convolutional code of the C/NAV (commercial navigation) message where the Galileo HAS message is present. The tail bit is unnecessary for message decoding. Also, in this log file, 2 bits left over in hexadecimal notation are zero-filled. Therefore, the C/NAV page length in the specification is 492 bits (Table 5 at page 13), while the C/NAV page length in Pocket SDR logs is 61 bytes (488 bits = 492-6+2 bits).

Using Pocket SDR, I observed for about 1 minute from 2023-02-19 13:38:31 UTC. Now, we process the log file 20230219_133831e6b.txt that is extracted from the E6B signal log file. The observation method is in the article, Galileo E6B signal reception with Pocket SDR, a open source software-defined radio.

./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

The satellite number (such as E14) is not included in the HAS message, so it is extracted from the Pocket SDR log. The E15 header contained af3bc3 (in hexadecimal notation) to indicate an invalid message. There were other satellites broadcasting such invalid messages besides E15.

Let us focus on and decode the first message that MID (message ID) is 2. Since the MS of this message is 2, we can decode this message by receiving messages from two satellites, E14 and E03 in this example. The HAS message obtained by decoding the 2-piece 848-bit length received word with D^-1 is as follows.

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

The decoding result of this HAS message header is as follows.

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

We can see that this HAS message contains clock full-set information. The following MID=2 pieces are not needed for message decoding, and the code ignores them.

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

If the code finds a new MID, it repeats the same procedure. Since the transmission duration for one piece is 1 second, the order of MID is not changed. Since previous MIDs may reappear, we may need to keep the mask information for several past MIDs. (updated on 2023-03-09)

HAS message before operational

In the same way, we try to decode the message before HAS is in operation. With Pocket SDR, I extract the E6B signal from the raw data of about 1 minute from 2022-09-30 11:56:17 UTC previously recorded, and process the log file 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)

Surprisingly, valid-looking data was sent. However, the HASS (HAS Status) in the header is Test.

Conclusion

The RS code in the Galileo HAS is not for error correction, but for dividing messages for parallel transmission. CSSR (compact state space representation) in the quasi-zenith satellite system (QZSS, petnamed Michibiki) and HAS in Galileo convey their augmentation messages in completely different ways. It is interesting that the Michibiki CSSR broadcasts messages in a 30-second cycle, while the Galilo HAS does not have a cycle. Both are great and each have their advantages.

It was difficult to create the Michibiki CSSR decoder QZS L6 Tool, but it was also difficult to create the Galileo HAS decoder. In particular, I spent some time learning the idea of the High Parity Vertical Reed-Solomon (HPVRS). I will try to observe how each one packs the message into the payload.

I am currently working on converting CSSR messages to RTCM SSR messages. In the future, QZS L6 Tool will be modified so that we can perform precise point positioning using RTKLIB with Michibiki CSSR and Galileo HAS.

Related article(s):

• Galileo HAS（high accuracy service）Part 3 27^th October 2023
• Galileo HAS（high accuracy service）part 1 7^th February 2023