Transmission of satellite navigation message into multiple pages encoded for optimal retrieval at receiver in a fully interchangeable way

Abstract

Described herein is a method for improving the reception of a satellite navigation message divided in several pages and transmitted by one or several satellites. A satellite navigation message M of k pages is encoded inn pages, and any k retrieved pages from any satellite enables decoding of the original satellite navigation message M. An implementation of the method uses parallel block encoding for a binary erasure channel with high parity and zero overhead, where symbols at a fixed position of all pages are encoded in parallel into shorter codes. This method achieves full page interchangeability in the message transmission, optimizes message reception and reduces decoding cost.

Claims

1. A method of generating an encoded satellite navigation message, in the form of a number of pages, for transmission to at least one user receiver via a plurality of satellites, the method comprising the steps of: a) dividing, at a ground station, a satellite navigation message M into k pages; b) dividing, at the ground station, each page into j symbols, the satellite navigation message M being divided into k×j symbols; c) for each symbol position, encoding the symbols of the k pages at the ground station by encoding each column of the symbols of the pages separately for a total of j block codes, wherein each of n pages comprises symbols from the j block codes, n being larger than k; d) generating, at the ground station, an encoded satellite navigation message M′ for the n pages; e) allocating, at the ground station, at least a subset of the n pages of the encoded satellite navigation message to each of the plurality of satellites; f) transmitting, by the ground station, the allocated pages to respective ones of the plurality of satellites; and g) transmitting the allocated pages by the plurality of satellites to the at least one user receiver.

2. The method according to claim 1, wherein step c) further comprises using a block coding scheme which allows any k symbols of the n pages to be used in retrieval of the original satellite navigation message.

3. The method according to claim 1, wherein the block codes comprise Reed-Solomon codes.

4. The method according to claim 1, wherein step d) further comprises attaching a cyclic redundancy check to each page to simulate a binary erasure channel.

5. The method of claim 1 further comprising: decoding the encoded satellite navigation message at at least one user receiver, the encoded satellite navigation message being generated in accordance with the decoding comprising the steps of: i) receiving, at each one of the at least one user receiver, pages transmitted by the plurality of satellites within the field of view of said each one of the at least one user receiver; and ii) decoding, at said each one of the at least one user receiver, the encoded satellite navigation message from the pages received from the plurality of satellites by recursively applying a decoding process thereto by decoding each column separately for a total of j block codes.

6. The method according to claim 5, wherein the block codes comprise Reed-Solomon codes.

7. The method according to claim 5, wherein step i) further comprises receiving different pages from different ones of the plurality of satellites.

8. The method according to claim 5, wherein step i) further comprises receiving the pages sequentially over time.

9. A user receiver configured for decoding an encoded satellite navigation message transmitted as different pages from a plurality of satellites in its field of view, the encoded satellite navigation message being generated and transmitted in accordance with the method of claim 1, the user receiver being configured for: receiving pages transmitted by the plurality of satellites within its field of view; and decoding the encoded satellite navigation message from the pages received from the plurality of satellites by recursively applying a decoding process thereto by decoding each column separately for a total of j block codes.

10. The user receiver according to claim 9, wherein the block codes comprise Reed-Solomon codes.

11. A satellite navigation system for generating, transmitting and decoding an encoded satellite navigation message in the form of a number of pages, the system comprising: a plurality of satellites; at least one user receiver; and a ground station configured for generating an encoded satellite navigation message, in the form of a number of pages, for transmission to the plurality of satellites, the encoded satellite navigation message being generated by: dividing a satellite navigation message M into k pages; dividing each page into j symbols, the satellite navigation message M being divided into k×j symbols; for each symbol position, encoding the symbols of the k pages by encoding each column of the symbols of the pages separately for a total of j block codes; generating an encoded satellite navigation message M′ for n pages, n being larger than k, wherein each of the n pages comprises symbols from the j block codes; allocating at least a subset of the n pages of the encoded satellite navigation message to each of the plurality of satellites; and transmitting the allocated pages to respective ones of the plurality of satellites, wherein the plurality of satellites comprises means for transmitting the allocated pages to the at least one user receiver.

12. The satellite navigation system according to claim 11, wherein the block codes comprise Reed-Solomon codes.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) For a better understanding of the present disclosure, reference will now be made, by way of example, to the accompanying drawings in which:

(2) FIG. 1 illustrates a conventional satellite navigation message transmission scheme in which a given satellite navigation message is divided in blocks (termed as “message splitting”);

(3) FIG. 2 illustrates a conventional satellite navigation message transmission scheme based on page offsetting in which each satellite transmits the same satellite navigation message with a different offset;

(4) FIG. 3 illustrates a transmission method in which all the symbols in a given position in a page are encoded in a separate code;

(5) FIG. 4 illustrates the reception process in fading channels in which a 4-page satellite navigation message is encoded into 12 pages and transmitted by 3 satellites, and the user receiver recomposes the satellite navigation message by receiving only 4 pages.

(6) FIG. 5 illustrates Reed-Solomon implementations of the present disclosure;

(7) FIG. 6 illustrates a comparison between the decoding cost of the method of the present disclosure and the decoding cost of conventional methods;

(8) FIGS. 7a, 7b and 7c respectively illustrate a comparison between the reception time of the method of the present disclosure (indicated by asterisks “*” in black) and the reception time of a standard method (indicated by crosses “+” in grey) for and “Open Sky” scenario, a “Soft Urban” scenario and a “Hard Urban” scenario;

(9) FIG. 8 illustrates a scheme for defining the page ID of the satellite navigation message based on the satellite ID of the transmitting satellite and the time, both of which are known a priori by the user receiver; and

(10) FIG. 9 is a flow chart that illustrates a method of the present disclosure.

DETAILED DESCRIPTION

(11) The present disclosure will be described with respect to particular embodiments and with reference to certain drawings but the invention is not limited thereto. The drawings described are only schematic and are non-limiting. In the drawings, the size of some of the elements may be exaggerated and not drawn on scale for illustrative purposes.

(12) It is to be noted that the present disclosure is directed to solving specific problems associated with the field of satellite navigation and which may not occur in the field of satellite communications. In particular, satellite navigation data, as encoded in accordance with the present disclosure, is generally more difficult to receive than pure satellite communication signals. Generally, satellite communication signals are received at a much higher power (where satellite navigation signals are received at about −155 dBW, that is, below the thermal noise level). Due to this, the typical data rate of satellite navigation signals is in the order of a 100 bps (50 bps for GPS L1C/A), which is much lower than usual data rates used in satellite communication systems. In addition, satellite communication messages are generally transmitted from a single source, and satellite navigation signals and data have to be available at said low power to both static and dynamic users in all environments, including air, sea, and terrestrial, the latter including tree canopy and urban canyons.

(13) With low data reception rates in satellite navigation systems, the present disclosure solves the problem of transmitting long messages, for example, of the order of thousands or tens of thousands of bits, with these signals needing to be received in degraded environments through a very high data redundancy yet at no overhead and low decoding complexity, which cannot otherwise achieved with state-of-the-art methods. RS (or similar) standard code implementations provide a very low parity with respect to what is required for to solve the problem of the present disclosure. Typically, the present disclosure requires a parity/data ratio between 1/10 and 1/6, for an already long message. While this may be achieved with RS (or similar) codes with longer symbols, for example, 16 bits, these implementations are not standard and are more difficult to decode at the user receiver. In particular, the method of the present disclosure is applied to long messages with a high parity/data ratio as required to solve the specific satellite navigation problem of transmitting long messages with weak signals in degraded environments, that is, with potentially very high error rates.

(14) Moreover, a fundamental difference over the prior art is that the method of the present disclosure utilizes parallel processing at an “inter-symbol”level, that is, for several symbols, not at an “intra-symbol” level, that is, at bit level. By acting at full symbol level, it is possible to parallelize as many codes as necessary. The method of the present disclosure utilizes a parallelization of 54, that is, (448−16)/8 vectors, which is not viable with methods known from the prior art.

(15) By utilizing inter-symbol parallelization, a more flexible method of decoding satellite navigation messages or signals can be obtained.

(16) Furthermore, in comparison with satellite communication systems, satellite navigation systems need to transmit messages with a very high redundancy rate to address high error rates and to transmit those messages from more than one source or satellite.

(17) The term “Open Sky” as used herein refers to an environment where signals from four transmitting satellites are received with a page error rate of 0.5% for each satellite.

(18) The term “Soft Urban” as used herein refers to an environment where signals from four transmitting satellites are received with page error rates of 0.5%, 1%, 10% and 20% respectively for the four satellites.

(19) The term “Hard Urban” as used herein refers to an environment where signals from two transmitting satellites are received with a page error rate of 10% and 20% respectively for the two satellites.

(20) The term “fading channel” refers to a communication that experiences a variation in the attenuation of a signal with multiple variables, such as, time, geographical position and radio frequency.

(21) The term “C/NAV” refers to the commercial navigation messages broadcast by Galileo satellites on frequency E6.

(22) The term “I/NAV” refers to the integrity navigation messages broadcast by Galileo satellites on frequencies E1 and E5.

(23) The term “parity/data ratio” refers to the amount of parity bits versus the amount of information bits in the encoded message.

(24) The terms “block codes” or “block coding schemes” refer to codes or coding schemes in which parallelization can be achieved. The present disclosure is described with reference to Reed-Solomon codes but is not limited thereto. For example, the Bose-Chaudhuri-Hocquengem (BCH) coding scheme may also be implemented.

(25) The term “binary erasure channel” or “BEC” refers to a common communications channel model in which a transmitter sends a bit (a “0” or a “1”) and the receiver either receives the bit or it receives a message that the bit was not received or “erased”. In reality, packets of bits are transmitted by the transmitter and the receiver either receives the packet or the packet is erased, in the present method, the C/NAV page CRC is checked and the page is discarded if the CRC fails.

(26) The approach proposed in the article “European GNSS (Galileo) Open Service Signal In Space Interface Control Document, (OS SIS ICD V1.3)” is shown in FIG. 1. In FIG. 1, a satellite navigation system 10 comprising a user receiver 12 and three satellites 14, 16, 18 is shown. As shown, each satellite 14, 16, 18 transmits a satellite navigation message to the user receiver 12 in two four-page chunks. This is known as message splitting. The two four-page chunks are indicated as 14a and 14b, 16a and 16b, and, 18a and 18b from respective ones of satellites 14, 16 and 18. Here, the block data is encoded interchangeably so that any page contributes to it; however, due to channel impairments, the user receiver 12 only receives the blocks shown in grey. In this example, the user receiver 12 would not be able to receive all of the chunks 14a, 14b, 16a 16b, 18a and 18b from any one of satellites 14, 16, 18, and, therefore would not be able to decode the satellite navigation message. However, if the pages were fully interchangeable as described below, it would be possible to decode the satellite navigation message as will be described in more detail below.

(27) As described above, page offsetting does not allow optimal recovery of the satellite navigation message. FIG. 2 illustrates a satellite navigation system 20 which is similar to the system 10 of FIG. 1 and comprises a user receiver 22 and three satellites 24, 26, 28. However, in this case, each satellite 24, 26, 28 transmits a 4-page satellite navigation message with a page offsetting of 0, 1, 2 respectively. In this example, the user receiver receives only half of the pages (shown in grey) from each of the satellites, and, therefore would not be able to receive the full satellite navigation message. As mentioned above with reference to FIG. 1, if all pages are interchangeable, the satellite navigation message could be received in 2 seconds.

(28) However, page offsetting alone does not allow reception as the user receiver should wait for the re-broadcast of the satellite navigation message, if possible, with its associated delay. The system cannot control which satellites are seen by each user receiver and there will always be users receiving a combination of pages which does not allow for a successful decoding or demodulation of the satellite navigation message.

(29) The problem which is solved by the present disclosure can be mathematically defined as follows: Let there be a high accuracy service (HAS) satellite navigation message M composed of k pages (M.sub.1, . . . , M.sub.k) which has to be transmitted by several navigation satellites at a given time through a binary erasure channel, the BEC assuming that a C/NAV page is either received correctly or is discarded. The BEC is modelled by checking the C/NAV page CRC and discarding the page is the CRC fails.

(30) The satellite navigation message M is encoded into a coded satellite navigation message C, of n pages, (C.sub.1, . . . , C.sub.n) where n>k, and transmitted at the same time by multiple satellites so that any k retrieved pages of C received from any satellite enables decoding of the original satellite navigation message M, allowing full page interchangeability in the satellite navigation message reception. The method must be valid for different message lengths, and the decoding process must be affordable in a user receiver.

(31) The method of the present disclosure is based on the following steps and uses parallel processing at an inter-symbol level so that there is no restriction: Divide a satellite navigation message M into k pages (M.sub.1, . . . , M.sub.k) Divide each page into j symbols so that the full satellite navigation message M is divided into k×j symbols (w.sub.1,1, . . . , w.sub.k,j) For each symbol position c=1, . . . , j, encode the symbols of the k pages (w.sub.1,c, . . . , w.sub.k,c) into (w′.sub.1,c, . . . , w′.sub.n,c) with a block coding scheme having the property that any k symbols of the n encoded symbols can be used to retrieve the original satellite navigation message Generate a full encoded satellite navigation message M′ (w′.sub.1,1, . . . , w′.sub.n,j), of n pages, where each page is composed of symbols from j parallel codes Attach a CRC or similar check to each page so that page reception is treated as in a binary erasure channel Allocate the n pages of M′, or a subset of them, to different satellites, and transmit the satellite navigation message through the satellites, so that each satellite transmits different pages At the user receiver side, when k pages of M′ are successfully received from any of the visible satellites, decode satellite navigation message M by applying the decoding process recursively j times

(32) An encoding and message-to-satellite allocation process is shown in FIG. 3 where n pages (C.sub.1, . . . , C.sub.n) are encoded in symbols w.sub.1,1 to w.sub.n,j with j being the total number of symbols in a C/NAV page. For example, j may be 52 for 448 bits minus the 16-bit header. Instead of using the same RS code for all symbols in the satellite navigation message, each column (w.sub.1,1, . . . , w.sub.n,1; w.sub.1,2; . . . , w.sub.n,2; etc.) is encoded and decoded separately for a total of j RS codes. The pages C.sub.i=1,n, or a subset thereof, are transmitted sequentially over time by different satellites which allows the user receiver to identify each C.sub.i. When the user receiver receives k pages, j codes will be decoded to provide the satellite navigation message using parallelization at the inter-symbol level.

(33) The reception process in fading channels is shown in FIG. 4, where a 4-page satellite navigation message is encoded into 12 pages and transmitted by 3 satellites, and the receiver recomposes the satellite navigation message by receiving only 4 pages. In FIG. 4, a satellite navigation system 100 is shown which comprises a user receiver 110 and three satellites 120, 130, 140. Each satellite 120, 130, 140 transmits four pages to the user receiver 110. However, due to fading channels, only the pages indicated in grey are received by the user receiver 110 and these pages are used to decode and recompose the original 4-page satellite navigation message.

(34) Reed-Solomon codes have the property of allowing the recovery of a satellite navigation message with any k symbols out of the n transmitted symbols. Therefore, one embodiment of the present disclosure is based on Reed-Solomon coding. In order to achieve full page interchangeability with multiple satellites, n has to be much bigger than k, that is, the satellite navigation message has to be coded with a lot of parity data so different satellites do not transmit the same pages. This is described by Westall et al. in “An introduction to Galois Fields and Reed-Solomon Coding”, School of Computing Clemson University, SC (2010): 29634-1906.

(35) Based on current estimations of the maximum message size for a precise point positioning (PPP) message transmitted in the Galileo E6B signals at 448 bps, it can be assumed that: A maximum satellite navigation message length (k.sub.max) of 20 pages, or 8640 bits, or 1080 bytes (e.g. an iono message), where each page can provide 432 bits (54 bytes), plus 16 bits for a header used to identify the information contained in the page, for a total of 448 bits. A maximum of 20 transmitting satellites, as per Galileo constellation capabilities, which would require a parity/data ratio of 20/1.

(36) However, in order to reduce the amount of parity/data ratio of 20/1, it can be assumed that satellites in an opposite slot of an orbit cannot be observed by the same user receiver. This already reduces the redundancy by half (from 20 to 10). Other assumptions are that satellites can be evenly distributed in the sky, and that, with a clean sky, a receiver on Earth can see at most ⅓ of the 20 Galileo connected satellites. In this case, a RS message may have a 6/1 parity/data ratio for a total (data+parity) of 7560 bytes. However, most standard RS coding approaches are based on GF(2.sup.m), where m=8, which implies that no more than 256 bytes can be encoded. Other implementations with m=16 or m=32 are possible, but they complicate Galois field arithmetic (especially polynomial multiplication for m=32), increasing receiver decoding cost and storage requirements.

(37) Some examples with different message lengths, up to 20 pages, are provided in FIG. 5. In the first example, a 20-page message is transmitted at a code rate of 1/5, that is, guaranteeing page interchangeability for up to 5 satellites in view of the user receiver. 100 8-bit symbol messages are encoded, with 20 data symbols and 80 parity symbols, fitting well in many RS codes, as for example, RS(255,161,8) as described by Cheung et al. in “End-to-end system consideration of the Galileo image compression system” (International Geoscience and Remote Sensing Symposium, Vol. 2, Institute of Electrical & Electronics Engineers, INC (IEE), 1996). The excess information symbols would be filled with zeros (for example, in the 20-page example, out of the 161 data symbols, only 20 would be used, and 141 would be filled with zeros) as described by B. E. Schotsch in “Specification of Outer Reed-Solomon Encoding of the CED in the Galileo E1 I/NAV Message”, 2017.

(38) In the second example, a 16-page satellite navigation message is transmitted at a code rate of 1/6. 96 8-bit symbol messages are encoded with 16 data symbols and 80 parity symbols with excess information symbols being filled with zeros. In the third example, a 10-page satellite navigation message is transmitted at a code rate of 1/8. 80 8-bit symbol messages are encoded with 10 data symbols and 70 parity symbols with excess information symbols being filled with zeros.

(39) In the fourth example with less redundancy, as proposed in the article by Schotsch mentioned above, a 18-page satellite navigation message is transmitted at a 1/4 code rate with an I/NAV RS code, RS(255,195,8), which provides 60-symbol parity.

(40) One of the advantages of the method of the present disclosure, compared to a standard RS coding in a single code, is the significantly lower decoding cost. Repeating j times the decoding process linearly increases decoding cost with respect to a single decoder iteration, but as the satellite navigation message is much shorter, decoding cost exponentially decreases. The decoding cost is estimated as the cost of inverting a k×k matrix and the cost of solving a linear k×k system. The matrix inversion cost is usually estimated as O(k.sup.3), which is the cost of the Gaussian Elimination method. The cost of solving the linear system is estimated as O(k.sup.2).

(41) A comparison with standard methods is shown in FIG. 6. The comparison is based on a data page length of 432 bits and message sizes of k=20 and k=4. Three implementations are selected: A single RS code for the whole satellite navigation message. m=8 for a short message (n=216<2.sup.8), and m=16 for a long message (2.sup.8<n<2.sup.16). This is termed “Standard1”. An implementation based on splitting the satellite navigation message into 5 chunks of 4-pages, where each chunk is encoded separately. This is termed “Standard2”. The method of the present disclosure is termed “MRSC” (multiple RS coding).

(42) In FIG. 6, m represents the symbol size (GF size is 2.sup.m), “max pages/code” represents the number of C/NAV pages that are (totally or partially, in the MRSC case) encoded with a RS code; “parallel codes/msg” is the number of RS codes that encode a given satellite navigation message in parallel; “chunks” is the number of RS codes that encode a given satellite navigation message; “codes” is the total number of codes for the satellite navigation message, “k” is the total number of bytes encoded per code; and “dec. ops/code” is the number of decoding operations per code (O(k.sup.3)+O(k.sup.2)). As shown, the implementation of the present disclosure (MRSC) has a much lower decoding cost than the other implementations (“Standard1” and “Standard2”) for the same satellite navigation message.

(43) Another advantage of the method of the present disclosure is the improved reception capabilities under fading conditions. The reception of a 20-page satellite navigation message through MRSC compared to an equivalent conventional method in five 4-page chunks is shown in FIGS. 7a to 7c. Each of FIGS. 7a to 7c were modelled using a Monte-Carlo simulation run with 5000 instances, measuring the time to decode the satellite navigation message in each case.

(44) FIG. 7a illustrates a comparison between the reception time in the method of the present disclosure, indicated as “*” in black, and the reception time of a 4-page/5-chunk method, indicated as “+” in grey, for an “open sky” case with four satellites in view of the user receiver. In the conventional method, the chunk sequence is optimized so that the satellites transmit complementary chunk sequences for the user receiver. A page error rate of 0.5% was obtained for each of the four satellites.

(45) FIG. 7b is similar to FIG. 7a but for a “soft urban” case with four satellites in view of the user receiver. Page error rates of 1%, 5%, 10% and 20% were obtained for respective ones of the satellites.

(46) FIG. 7c is similar to FIGS. 7a and 7b but for a “hard urban” case with only two satellites in view of the user receiver. Page error rates of 10% and 20% were obtained for respective ones of the satellites.

(47) As shown in FIGS. 7a to 7c, the method of the present disclosure improves significantly the message reception robustness and the satellite navigation message is received much more quickly.

(48) A specific implementation of the method of the present disclosure can based on every page including a header, with a message ID field, a message length field, and a Page ID field.

(49) Another specific implementation, in which the header size is reduced, can be based on defining a satellite/time matrix for a given number of satellites and time, so that the Page ID field can be defined from the matrix, instead of occupying space in the header, thereby allowing the possibility to have long encoded satellite navigation messages. This is illustrated in FIG. 8.

(50) FIG. 8 illustrates how to identify the pages of a message composed of at most (n+1)*T pages by just identifying the satellite identification (n) and time (between 1 and T) without necessarily having to transmit this information in the header.

(51) Another specific implementation may include a page header where the coding scheme that is encoding the satellite navigation message is defined in the header, thereby allowing multiple schemes.

(52) Another specific implementation includes the encoding of a high accuracy message based on grouping message subtypes in 3 messages: one message for the satellite mask, orbit corrections, biases and user ranging accuracy (URA); one message for ionospheric corrections; and one message for the satellite clock corrections composed of 1 to 3 pages, depending on the amount of satellites in the satellite mask.

(53) Another implementations include other block codes different than RS, or other symbol lengths different than 8-bits (e.g. 16 bits or 32 bits, as both are available for RS).

(54) In another implementation, the satellite navigation message encoded is not a high accuracy message, but another common satellite navigation message transmitted by a GNSS constellation, such as a digital signature or an almanac.

(55) Another implementation allows for the interleaving of several different satellite navigation messages from different satellites in time. This means that, instead of transmitting one message at a given time interval, the system can transmit several messages during that time interval, and, the header of a particular message identifies that message with a particular message ID.

(56) FIG. 9 is a flow chart that illustrates a method of the present disclosure performed at a ground station. The method includes, at step 902, dividing, at a ground station 900, a satellite navigation message M into k pages; at step 904, dividing, at the ground station, each page into j symbols, the satellite navigation message M being divided into k×j symbols; at step 906, for each symbol position, encoding the symbols of the k pages at the ground station by encoding each column of the symbols of the pages separately for a total of j block codes, wherein each of n pages comprises symbols from the j block codes, n being larger than k; at step 908, generating, at the ground station, an encoded satellite navigation message M′ for the n pages; at step 910, allocating, at the ground station, at least a subset of the n pages of the encoded satellite navigation message to each of the plurality of satellites; and at step 912, transmitting, by the ground station, the allocated pages to respective ones of the plurality of satellites.