Galileo HAS（high accuracy service）part 1
Introduction
Galileo, the European navigation satellite system, broadcasts messages to improve the positioning accuracy (they are often referred to as the augmentation messages) besides the navigation signal. The augmentation message specification is described in Galileo High Accuracy Service Signal-in-Space Interface Control Document (HAS SIS ICD).
Luckily I have a receiver that can receive Galileo E6B signals, and I’m trying to decode this augmentation messages. First, I tried to run the example written in the specification.
Message structure of Galileo HAS
HAS (high accuracy service) on Galileo’s E6B signal is broadcast one message per second and combines multiple messages to achieve augmentation of navigation signals. This transmission method is as same as CLAS (pronounced like Cirrus, centimeter-level augmentation service) messages in L6D signals and MADOCA-PPP (multi-GNSS advanced orbit and clock augmentation - precise point positioning) messages in L6E signals broadcast from Michibiki, the quasi-zenith satellite system (QZSS).
In addition, the message format of Galileo HAS is said to take into account CSSR (compact space state representation) used in Michibiki’s CLAS and MADOCA-PPP.
7.8 Relationship with other formats
The Galileo HAS SIS ICD is a self-standing document defined taking into account the formats of already existing messages for providing high accuracy corrections. In particular, it takes into account QZSS Interface Specification of the Centimeter-Level Augmentation Service (IS- QZSS-L6-001) [RD4], which uses the Specification of Compact State-Space Representation (CSSR) for Satellite-Based Augmentation Messages defined under RTCM-SC-104.
However, I think these message structures are quite different. Galileo HAS is specifically aware that it can self-heal whenever parts of the messages are lost. A countermeasure against partial message loss that may occur in mobile reception is also found in Galileo’s I/NAV (integrity navigation) message. In addition, the type of augmentation information included in the message can only be decoded by reading through the message in Michibiki’s CSSR. On the other hand in Galileo’s CSSR, the type of information is fixedly described in bit image format in the header.
Galileo E6B signals transmit 984 symbols per second. The receiver performs 123-by-8 deinterleaving (it converts burst errors to random errors) and performs Viterbi decoding with a coding rate of 1/2 and a constraint length of 7 (Sect. 2.2 FEC Coding and Interleaving Parameters). The “HAS page” message length is 448 bits out of the 492 bits of a Viterbi-decoded message. This HAS page consists of a 24-bit length header and a 424-bit length (=53 octets) “HAS Encoded Page”. In the header, the total number of pages after decode k (the number of non-encoded pages, 1 to 32) and the page number before decode N (1 to 255) are described (Sect 3 HAS Page Header). HAS messages are decoded by interpreting the HAS Encoded Page based on this header information. HAS automatically repairs partially lost pages by transmitting N pages that consists of k HAS pages plus their redundant pages.
The number of pages after decode is limited to 32 or less. The example in Annex C is page 15. As mentioned above, one page consists of 424 bits, and the remainder of the message is filled with zeros and alternating codes of 0 and 1 (Sect. 4. HAS Message Overview). But I don’t know it is zero padding or alternating padding.
padding bits with a binary sequence of zeroes and ones “010101…” are appended to the message in order to reach a message length which is a multiple of 424 bits.
Also, regarding the notation of N=255 in Fig. 2, I didn’t know whether the total number of pages N before decode is always 255 or can be less than that. If N is always 255, it will take 255 seconds to receive a HAS message in a cycle. (for CLAS and MADOCA-PPP, the cycle is fixed to 30 seconds). I would like to check it with the actual HAS message.
Automatic repair of partial message erasure is achieved by Reed-Solomon encoding. The receiver decodes the message by multiplying the received HAS page sequence by the inverse of the generator matrix. This matrix inversion and product is performed over the Galois field (Sect. 6.4 HAS Reception and Decoding). If the inverse matrix of the generator matrix corresponding to k = 2, k = 3, …, k = 16 is calculated in advance, the HAS message can be decoded only by multiplying the received word with these Galois fields.
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.
Since Reed-Solomon codes are block codes, there is an option to omit this error correction (Sect. 6. HAS Message Encoding and Decoding). However, looking at the example in Annex C. Reed-Solomon Decoding Example, it seems that this Reed-Solomon decoding must be performed because the same message sequence cannot be found before and after this Reed-Solomon decoding.
When any subset C’ of C, of k different pages (C’1, …, C’k), is received without error, the message can be decoded.
Reed-Solomon Decoding Example
Therefore, I tried the Reed-Solomon decoding example written in Annex C using MATLAB. In order to find the inverse matrix in the Galois field, Communications Toolbox is required in addition to MATLAB itself.
In this example, the number of pages before encoding k is 15. At first, therefore, we define a generator matrix D with 15 rows and 15 columns corresponding to k=15. Here we give this element in decimal.
D = [
31 50 155 253 213 220 84 174 239 85 87 105 214 81 160;
113 18 35 135 205 43 156 23 127 169 162 160 15 49 202;
204 239 127 208 89 187 30 192 37 152 221 214 211 49 93;
72 7 24 67 1 245 154 234 84 179 37 96 222 33 64;
253 151 182 118 101 136 118 241 195 26 152 14 225 28 193;
114 171 242 238 47 124 59 125 65 23 39 150 161 226 5;
33 32 3 8 36 151 121 17 218 26 98 82 65 146 162;
37 190 149 41 64 68 119 19 153 51 235 147 203 136 225;
58 217 47 14 1 13 117 8 167 10 105 226 96 158 229;
169 119 204 119 80 22 46 55 120 70 39 68 156 140 150;
145 19 150 65 190 97 199 178 76 115 138 198 136 18 180;
235 120 75 39 150 196 72 209 145 27 180 77 11 2 154;
143 165 24 101 222 187 133 80 114 98 164 11 16 227 43;
15 105 201 161 101 197 235 191 127 28 238 232 231 198 234;
84 157 205 255 217 251 101 194 230 208 26 232 23 201 46
];
Converting this to a Galois field with gf(), we obtain its inverse matrix GFDinv.
GFD = gf(D,8);
GFDinv = inv(GFD)
GFDinv = GF(2^8) array. Primitive polynomial = D^8+D^4+D^3+D^2+1 (285 decimal)
Array elements =
200 5 121 64 146 79 105 195 15 22 150 75 227 167 168
19 123 74 36 87 170 123 139 57 66 117 19 60 150 3
71 178 51 76 147 41 146 222 254 149 82 30 109 52 69
218 100 198 13 145 216 164 119 203 199 219 224 100 198 41
220 215 176 139 91 173 91 109 135 26 12 188 209 164 238
137 243 144 94 235 114 136 177 122 41 132 110 53 186 53
251 142 229 87 112 189 132 245 226 176 21 171 39 199 231
103 219 81 164 107 111 129 192 209 102 161 141 119 23 230
204 204 167 128 199 2 33 60 17 232 124 25 79 159 233
203 113 26 162 49 31 24 40 59 114 219 100 211 120 129
98 15 14 203 1 75 205 94 78 35 41 23 178 107 76
41 152 227 188 201 126 137 5 126 121 55 226 21 41 45
69 107 172 85 239 175 198 249 164 130 179 235 162 58 196
175 7 101 251 240 158 218 225 58 249 193 64 218 17 214
174 231 25 182 215 187 49 97 157 231 127 42 126 221 196
Next, we define a receiving word W consisting of 15 lines. The number of columns is always 53.
W = [
132 123 199 73 235 125 113 116 36 71 136 251 69 70 145 140 0 39 42 235 193 84 146 204 110 181 90 88 128 226 97 186 227 23 26 35 221 11 229 98 252 141 111 216 142 98 41 194 158 125 140 153 223;
52 154 227 99 77 33 11 173 50 147 166 127 182 33 1 233 221 84 48 123 198 121 237 105 155 213 12 174 174 197 100 133 243 248 22 84 12 174 206 164 198 22 146 238 91 24 202 171 181 189 162 121 57;
85 1 29 145 14 230 225 85 194 242 140 77 215 250 214 40 200 226 106 5 171 215 135 151 77 226 225 111 142 246 176 156 0 215 18 228 41 8 34 151 24 174 236 105 28 5 39 243 194 63 128 181 19;
44 163 27 35 21 83 238 106 156 122 59 255 250 132 43 45 12 243 8 9 16 185 194 2 126 136 115 220 237 47 141 167 212 35 164 47 217 206 88 195 238 68 125 44 175 49 177 138 4 213 165 186 120;
55 190 96 216 35 121 141 182 26 28 152 34 238 248 75 122 213 237 99 213 34 61 152 173 145 204 133 143 64 117 119 92 224 76 187 36 160 208 177 95 127 213 58 214 134 44 121 248 82 63 169 191 75;
187 28 69 29 89 4 160 228 22 185 43 88 154 12 86 206 43 199 115 152 40 239 11 192 73 228 145 24 154 41 63 49 40 36 224 176 100 94 31 100 152 109 111 135 185 118 207 58 18 247 59 144 33;
117 25 72 154 251 194 111 69 202 191 253 159 120 178 246 68 171 41 251 163 124 202 254 239 152 25 2 5 204 223 192 231 250 120 193 179 234 80 108 166 166 167 210 195 99 135 159 118 132 143 164 128 36;
143 12 156 52 139 203 193 61 89 3 53 84 14 168 101 194 207 61 113 59 188 39 200 99 26 41 88 222 211 134 178 117 71 15 136 150 150 65 88 124 204 128 23 28 51 166 204 221 251 63 53 44 190;
203 226 36 10 145 27 54 129 243 142 43 63 242 57 243 98 229 59 74 201 41 44 96 199 124 97 197 70 118 78 134 66 106 138 68 197 64 140 187 91 201 10 138 135 16 254 109 113 144 220 128 204 93;
29 55 158 167 195 223 144 158 158 116 87 219 101 36 71 28 189 52 215 17 199 92 176 139 74 132 108 3 25 126 46 191 226 239 14 161 44 70 247 253 202 246 58 36 35 29 77 144 52 14 217 139 221;
122 57 40 21 48 65 99 21 77 50 204 30 233 166 117 3 48 3 115 250 224 78 143 108 245 144 255 199 147 114 161 38 145 41 107 172 132 82 95 202 166 152 75 83 88 143 25 25 186 202 151 159 222;
125 19 56 207 112 92 184 147 239 181 113 209 24 245 173 57 173 51 3 160 148 255 182 92 140 168 146 194 234 61 53 190 137 15 91 228 231 9 111 222 52 62 205 189 90 185 129 222 74 19 154 94 29;
161 204 117 222 253 61 201 66 207 106 21 166 117 149 224 164 249 50 45 172 71 205 29 87 112 81 177 95 215 130 214 162 83 43 182 9 188 112 183 111 5 174 231 176 103 151 117 7 232 167 19 33 234;
207 147 205 21 140 244 31 178 149 173 157 33 161 85 130 130 237 116 136 51 54 137 106 123 126 234 208 57 145 34 116 229 209 226 26 86 63 239 245 210 21 211 61 189 43 85 215 103 160 170 234 163 56;
215 200 167 19 210 166 18 96 224 77 5 145 106 148 222 103 157 196 233 132 109 61 229 187 163 152 17 62 27 210 42 67 181 2 23 108 68 206 189 76 58 39 164 43 254 9 87 41 18 228 135 212 165
];
Similarly, this W is also converted to Galois field, multiplied by D, and the result is expressed in hexadecimal.
GFW = gf(W,8);
GFM = GFDinv * GFW;
compose("%02x", GFM.x)
ans =
15×53 string
column 1 to 14
"00" "0c" "c0" "0b" "20" "ff" "df" "ff" "ff" "00" "81" "00" "f7" "ff"
"ff" "68" "22" "fe" "a2" "18" "07" "c1" "93" "f7" "59" "80" "35" "fd"
"47" "f9" "03" "ff" "9d" "f7" "80" "5c" "15" "ff" "9f" "dc" "ff" "80"
"43" "fd" "b0" "23" "04" "00" "7f" "e5" "03" "0f" "f1" "ac" "40" "02"
"4f" "e1" "ff" "88" "25" "fe" "8f" "fc" "ff" "00" "48" "08" "1f" "e3"
"f0" "0f" "ff" "70" "4b" "f7" "1f" "ff" "fd" "c0" "97" "fb" "40" "0c"
"40" "56" "05" "c0" "88" "04" "00" "44" "03" "01" "2f" "e2" "7f" "ef"
...
This matched the post-decode message in Annex C.
Implementation with Python
When I was wondering how to implement this procedure in Python, Dr. Eric Sibert told me that the HAS Decoder is implemented in CSSRlib.
The implementation of HAS decoding in CSSRlib uses Python’s galois module to compute products and inverses in the Galois field. It will be very helpful to have specific code. I will try to make my own code.
Also, the generator matrix for k=15 is given, but other generator matrices are not written in the specifications HAS SIS ICD, so it seems that I have to derive them.
Related article(s):
- Galileo HAS（high accuracy service）Part 3 27th October 2023
- Galileo HAS（high accuracy service）part 2 20th February 2023