System and method for decoding automatic identification system signals

ES 2 448 867 T3

DESCRIPTION

System and method for decoding signals of an automatic identification system

Countryside

The embodiments described herein relate to systems and methods for decoding automatic identification system signals. More specifically, the embodiments described herein relate to systems and methods for monitoring ships sending automatic identification system signals by receiving the signals with a low-Earth orbit satellite and decoding the signals using correlation techniques.

Background

Automatic Identification System (AIS) is a maritime communications system designed for short-range ship-to-ship and ship-to-shore communications (typically 20-30 nautical miles). The AIS system uses narrow band (i.e. 25 kHz bandwidth) and very high frequency (VHF) channels centered on 161.975 MHz and 162.025 MHz, with a possible additional channel at 157.375 MHz, and a communication method called access Self-Organizing Time Division Multiple (SOTDMA).

The AIS system supports a number of different signal types. The main AIS signal sent by a ship is a position report that provides information regarding the ship's identification, position, heading, speed, and other details. AIS also includes the use of a receiver, which allows a ship to receive AIS signals emitted by ships located around it. Every minute, each VHF channel is divided into 2,250 time slots, each of which can accommodate a 26.67 ms AIS transmission (ie AIS signal). The time slots are exactly synchronized to Coordinated Universal Time (UTC), typically using the Global Positioning System (GPS), and each AIS unit reserves time slots for future AIS transmissions from the ship. Therefore, other AIS units within range can maintain a map of reserved slots and avoid transmission during these slots. This self-organizing feature prevents signal collisions in the short ranges involved in surface transmissions.

The use of AIS is now mandatory on all ships over 300 tonnes making international voyages, and it is also being extended to other ships. It was originally intended as a safety and navigation aid, and also has potential safety applications for monitoring maritime traffic. Detection of AIS signals could be achieved using shore / shore stations, but the limited range of VHF signals would require such shore / shore stations to be located at many positions along the shoreline, and even then they could only monitor the immediate coastal region.

US 6,512,720 B1 describes a method for Doppler compensation in a phase coherent underwater communication system. WO 20071143378 describes a space based system for simultaneously tracking and monitoring one or more ocean ships at any point on earth, the system including a number of satellites. Ole Fredrik Haakonsen Dahl: “Space-Based AIS Receiver for Maritime Traffic Monitoring Using Interference Cancellation”, Norwegian University of Science and Technology, Master of Science in Communications Technology, June 2006, pages 1-107, XP002581810, examines receiver solutions to reduce the problem of interference between messages from different ships.

Resume

The invention is defined in the independent claims to which reference is now made. Preferred features are set forth in the dependent claims.

According to a first aspect of the invention, a method is provided for producing validated decoded Automatic Identification System (AIS) message segments from a plurality of AIS signals where a plurality of AIS signals are received in one or more satellites in the space and pre-processed to produce digital input data corresponding to the plurality of received AIS signals, including the method: processing the input digital data by correlating the input digital data with a plurality of predefined signals having different Doppler shifts to calculate a plurality of corresponding correlation signals, where the plurality of predefined signals are generated by applying Doppler shifts to a predetermined sequence of codes AIS, and scanning the plurality of correlation signals for amplitude peaks that exceed contiguous amplitude peaks by a predetermined amount in order to identify one or more candidate AIS message signals based on the correlation signals; determining Doppler deviation estimates and time of arrival estimates for the one or more candidate AIS message signals; decoding the one or more candidate AIS message signals in the input digital data to obtain corresponding message segments; and validating the decoded message segments for appropriate AIS formatting to produce validated decoded AIS message segments.

In some embodiments, before decoding the one or more candidate AIS message signals in the data

ES 2 448 867 T3 digital input, the method further includes refining the group of one or more candidate AIS message signals to obtain a refined group of candidate AIS message signals and performing decoding on the refined group of candidate AIS message signals , and where refining the candidate message signals includes: determining whether any of the one or more candidate AIS message signals repeats at a different Doppler shift estimate; and remove all duplicate candidate AIS message signals. In some embodiments, before decoding the one or more candidate AIS message signals in the input digital data, the method further includes refining the group of one or more candidate AIS message signals to obtain a refined group of candidate AIS message signals. and performing decoding on the refined group of candidate AIS message signals, and where refining the candidate message signals includes: classifying the one or more candidate AIS message signals by their corresponding time of arrival estimates; and removing all remaining candidate AIS message signals that are overlapped on their high time side by a stronger candidate AIS message signal. In some embodiments, prior to decoding, the method further includes re-filtering the one or more candidate AIS message signals by applying narrow-band filtering centered on the Doppler offset estimate that corresponds to the one or more candidate AIS message signals.

The method may further include employing at least two antennas configured to receive the plurality of AIS signals, the at least two antennas differing from one another in at least one in a spatial and polarizing manner, and prior to the decoding step the method may further include combining the one or more candidate AIS message signals received by one of the antennas with one or more corresponding candidate AIS message signals received by at least one of the other antennas using an offset of phase that maximizes the amplitude of the one or more candidate AIS message signals combined relative to any overlapping signals, and performing decoding on the one or more combined candidate AIS message signals.

The method may further include de-mapping the validated decoded message segments to obtain modified input digital data, and performing the processing, determining and decoding steps on the modified input digital data. In some embodiments, prior to decoding, the method includes determining a more accurate Doppler shift estimate and time of arrival estimate for the one or more candidate message signals.

At least one decoded message segment may be associated with a given ship, and after decoding, the method may return to the processing step which may further include: correlating the input digital data with a plurality of predefined signals corresponding to a subset of the at least single decoded message segment associated with the given ship; and determining whether the input digital data is a candidate AIS message signal associated with the given ship.

According to a second aspect of the invention, a system is provided for producing validated decoded Automatic Identification System (AIS) message segments from a plurality of AIS signals where a plurality of AIS signals are received at one or more satellites in the space and pre-processed to produce digital input data corresponding to the plurality of received AIS signals, including the system: a processing module configured to process the input digital data by correlating the input digital data with a plurality of predefined signals having different Doppler shifts to calculate a plurality of corresponding correlation signals, where the processing module is further configured to generate the plurality of predefined signals applying Doppler shifts to a predetermined sequence of AIS codes, and to scan the plurality of correlation signals for amplitude peaks that exceed contiguous amplitude peaks by a predetermined amount in order to identify one or more candidate AIS message signals based on the correlation signals; a processing module configured to determine corresponding Doppler shift estimates and time of arrival estimates for the one or more candidate AIS message signals; a decoder configured to decode the one or more candidate AIS message signals in the input digital data to obtain corresponding message segments; and a validation module configured to validate the decoded message segments for appropriate AIS formatting to produce validated decoded AIS message segments.

One of the processing modules may further be configured to generate the plurality of predefined signals by applying Doppler shifts to a predetermined AIS code sequence and to scan the plurality of correlation signals for amplitude peaks that exceed contiguous amplitude peaks in a predetermined quantity in order to identify the one or more candidate AIS message signals. The predetermined sequence of AIS codes can include at least one training sequence of an AIS signal. The system may further include a refinement module configured to refine the one or more candidate AIS message signals to obtain a refined group of candidate AIS message signals and the decoder module may be configured to perform decoding on the refined group of message signals. AIS candidate and refinement module may be configured to refine the one or more candidate AIS message signals by classifying the one or more AIS message signals candidates for their corresponding arrival time estimate; and removing all remaining candidate AIS message signals that are overlapped on their high time side by a stronger candidate AIS message.

The system may further include a refinement module configured to refine the one or more signal signals.

ES 2 448 867 T3 candidate AIS message signals to obtain a refined group of candidate AIS message signals and the decoder module may be configured to perform decoding on the refined group of candidate AIS message signals and the refinement module can be configured to refine the one or more candidate AIS message signals determining whether any of the one or more candidate AIS message signals repeats at a different Doppler shift estimate; and remove all duplicate candidate AIS message signals. The processing module may further be configured to re-filter the one or more candidate AIS message signals by applying narrow-band filtering centered on the Doppler offset estimate that corresponds to the one or more candidate AIS message signals.

The system can further include at least two antennas configured to receive the plurality of AIS signals, the at least two antennas differing from each other in at least one in a spatial and polarizing manner, and one of the processing modules may further be configured to combine the one or more candidate AIS message signals received by one of the antennas with one or more corresponding candidate AIS message signals received by at least one of the other antennas using an offset phase that maximizes the amplitude of the one or more candidate AIS message signals combined relative to any overlapping signals, and the decoder may be configured to perform decoding on the one or more candidate AIS message signals combined. The system may further be configured to de-correlate the validated decoded message segments to obtain modified input digital data, and the processing module may be further adapted to process the modified input digital data.

One of the processing modules may further be configured to determine a more accurate Doppler shift estimate and time of arrival estimate for the one or more candidate AIS message signals prior to decoding. The method may further include the step of employing, or the decoder may further include, a Viterbi decoder configured to decode GMSK modulated signals. The system may further be configured to associate at least one decoded message with a given ship, correlate the input digital data with a plurality of predefined signals that correspond to a subset of the at least one decoded message associated with the given ship, and determine whether the Digital input data is a candidate signal message associated with the ship.

Brief description of the drawings

For a better understanding of the various embodiments described herein, and to show more clearly how they can be put into practice, reference will now be made, by way of example only, to the accompanying figures in which:

Figure 1 is a general schematic diagram of an AIS processing system including a LEO satellite and a ground station.

Figure 2 is a block diagram of an exemplary embodiment for the LEO satellite and ground station of Figure 1.

Figure 3 is a block diagram of an alternative exemplary embodiment for the LEO satellite and ground station of Figure 1.

Figure 4 is a flow chart of an exemplary embodiment of a method for detecting and decoding AIS signals.

Figure 5 is a diagram illustrating the data structure of an AIS message signal.

Figure 6 is a flow chart of another exemplary embodiment of a method for detecting and decoding AIS message signals.

Figure 7 is a flow chart of an exemplary embodiment of a method for processing input digital data to identify candidate message signals.

Figure 8 is a flow chart of an exemplary embodiment of a method for refining candidate message signals.

Figures 9A, 9B and 9C are graphical illustrations of correlation signals.

And Figures 10A, 10B and 10C are graphical illustrations of correlation signals.

Detailed description of exemplary embodiments

It will be appreciated that, for the sake of simplicity and clarity of illustration, where appropriate, reference numerals may be repeated between the figures to indicate corresponding or analogous elements or steps.

ES 2 448 867 T3

In addition, numerous specific details are set forth in order to provide a complete understanding of the exemplary embodiments described herein. However, those skilled in the art will understand that the embodiments described herein can be practiced without these specific details. In other instances, known methods, procedures, and components have not been described in detail as these are known to those of skill in the art. Furthermore, it should be noted that this description is not intended to limit the scope of the embodiments described herein, but rather to simply describe one or more exemplary implementations.

AIS signals can also be detected using Low Earth Orbit (LEO) satellites, since AIS signals are strong enough to be detected by a satellite. LEO satellites also provide coverage for areas that are outside the range of shore / ground stations. However, the large field of view (FOV) of a LEO satellite means that the LEO satellite can receive signals from a large number of ships at the same time, particularly when the LEO satellite passes over high volume ship areas, thus which typically results in large numbers of AIS signals colliding or overlapping one another. Furthermore, the large FOV of a LEO satellite means that the ships in the FOV can be very far from each other and at great distances the SOTDMA communication method is not effective in avoiding signal collisions. Propagation delays also affect the exact timing.

Therefore, an inherent problem with LEO satellite-based AIS detection is that many of the AIS signals sent by ships will collide or overlap each other. For example, it is estimated that there may be more than 2,000 ships in the FOV of a LEO satellite in high traffic areas. Each ship will typically send 10 AIS position reports per minute, so for 2,000 ships a LEO satellite will receive 20,000 AIS signals per minute. This is a very large number compared to the number of time slots available (ie 4,500 across both VHF channels) and as a result many AIS signals will collide with each other. Therefore, although the detection of AIS signals by a LEO satellite can provide a means of monitoring a large area of ​​maritime traffic, the feasibility of this approach depends largely on its being able to decode AIS signals in the presence of large numbers of vehicles. signs of overlap.

Reference is first made to FIG. 1, which depicts a general diagram of an AIS processing system 10 including a LEO satellite 12 and a ground station 14 for receiving and decoding AIS signals. Figure 1 illustrates numerous ships 16 that have an AIS 18 to transmit AIS signals that are received by the LEO 12 satellite. However, as described above, due to the large FOV of the LEO 12 satellite, many of the received AIS signals are they overlap with each other. Accordingly, the embodiments described herein relate to methods and systems for effectively detecting and decoding AIS signals when many of these signals can overlap one another and can also be corrupted with noise or interference.

Typically, a given ship 16 will transmit AIS signals on two narrowband (ie 25 kHz) VHF channels. Examples of VHF AIS channels include AIS1 at 161.975 MHz, AIS2 at 162.025 MHz, and USAIS at 157.375 MHz. To transmit the signal, the AIS 18 transmitter unit employs a Gaussian minimum shift modulation (GMSK) of 9.6 kbps, which is commonly known to imply that the AIS signal will be contained within a 14 kHz bandwidth. The LEO satellite 12 is equipped with at least one VHF antenna (see Figures 2 and 3) and receives the AIS signal transmitted by the ship 16. The LEO satellite 12 is moving at a high speed, such as 7,500 m / s for example, and consequently the AIS signal received by the LEO 12 satellite experiences a Doppler shift of up to +/- 3.5 kHz.

The AIS signals received by the LEO 12 satellite will have a range of amplitudes, depending on the position of the ship 16 and its angular position as seen by the LEO 12 satellite. Generally, the transmitting antenna used in the AIS 18 of a given ship 16 does not radiate straight up, and this creates a reception hole directly below the LEO 12 satellite. However, in most of the FOV of the LEO 12 satellite, the radiation patterns of the transmitting antenna of the AIS 18 tend to balance the reduced signal intensity produced by the increased range, and the range of the received signal amplitudes is relatively modest, and is most likely less than 10 dB for most of the LEO 12 satellite FOV. Unfortunately, the differential amplitude between overlapping AIS signals has to be quite large for conventional decoding to be successful (> 10 dB). However, in some circumstances, comparatively small differential amplitudes between overlapping signals can still provide a reasonable means of distinguishing them.

All the received AIS signals are pre-processed in the LEO satellite 12 to create input digital data, which is subsequently processed by a processor unit (see Figures 2 and 3) so that the detected AIS signals can be decoded to extract the segment of message they contain. In some embodiments, the processing takes place at LEO satellite 12 and the extracted message segments are then sent to ground station 14, as will be explained with reference to Figure 2. In other embodiments, the input digital data is sent. to ground station 14 where processing takes place to produce the extracted message segments, as will be explained with reference to FIG. 3.

In alternative embodiments there may be more than one LEO satellite 12 that receives and preprocesses, and possibly detects and decodes, the AIS signals. Additionally, or alternatively, one or more ground stations 14 may be used to decode the pre-processed AIS signals. In another alternative, the processing required for detection and

ES 2 448 867 T3 decoding can be separated between the LEO satellite 12 and the ground station 14; This scheme can also be extended to cases where there is more than one LEO 12 satellite and one ground station 14, one LEO 12 satellite and more than one ground station 14, or more than one LEO 12 satellite and more than one ground station 14. Accordingly, in these cases, data can be transmitted between the LEO satellite (s) and the ground station (s) for processing in various ways. For the sake of simplicity, the embodiments described here refer to a system with a LEO satellite 12 and a ground station 14, but the processing methodology can be extended to several LEO satellites and / or several ground stations. It is also conceivable that inter-satellite links (ISL) could be employed between a constellation of LEO satellites. However, this is a very expensive and complex approach and, in practice, data distribution over a terrestrial network is more likely to be employed.

Referring now to Figure 2, there is shown a block diagram of an exemplary embodiment for the LEO satellite 12 and the ground station 14 of the AIS processing system 10. In general, the LEO satellite 12 includes a receiver 20, a control unit 22, a processing unit 24, and a transmitter unit 26. The receiver 20 includes a first receiver channel 28, and a second receiver channel 30. The first receiver channel 28 includes a first receiver antenna 32, an RF front end 34, including a front end filter and a low noise amplifier, a filter stage 36, an amplifier stage 38, a mixing stage 40, an ADC 42 and a filter bank 44. The second receiver channel 30 includes similar components numbered 46 to 58. In some embodiments, the second receiver channel 30 is not used, as will be described in more detail below. Also, in some embodiments, mixing stages 40 and 54 are not used if the ADC 42 and 56 are operating at a sufficiently adequate sample rate. The processing unit 24 includes a processing module 60, a refinement module 62, a decoder 64, and a validation module 66. In some embodiments the refinement module 62 is not used, as will be described in more detail below. Transmitter 26 generally includes a modulator 68, a transmitter unit 70, and a transmitter antenna 72.

Receiver 20 receives a plurality of AIS signals and preprocesses these signals to obtain input digital data. The processing unit 24 processes the input digital data to identify and decode one or more candidate AlS message signals. After the candidate AIS message signals are decoded to determine message segments contained therein, these decoded message segments are modulated by modulator 68 and transmitted via transmitting antenna 72 as transmitted decoded message segments 74 to the ground station. 14.

Ground station 14 is equipped with a control unit 76, a receiver 78, and a data memory 80, such as a database stored on a suitable storage medium. Receiver 78 includes receiving antenna 82 and demodulator 84 to demodulate transmitted decoded message segments 74 that are received by ground station 14. Control unit 76 controls the operation of ground station 14, and can be used to retrieve the decoded message segments from demodulator 84, store these decoded message segments in data memory 80, and later reclaim the message segments. decoded message stored. Ground station 14 may also include a transmitter (not shown) to send decoded message segments to interested parties. For example, various security and intelligence organizations may be interested in reviewing all validated decoded message segments, and as such must be stored in data memory 80 for later retrieval. For example, decoded messages can be distributed in encrypted form over the Internet.

Receiver 20 includes two receiver channels 28 and 30, one for each receiver antenna 32 and 46. However, in some embodiments only one receiver channel is used. Accordingly, for the sake of simplicity of explanation, only the components of a reception path will be described. The receiving antenna 32 is a very high frequency (VHF) antenna that is configured to receive AIS signals transmitted on the AIS1, AIS2, and USAIS channels. In embodiments with two receiver channels, receiver antennas 32 and 46 are polarized differently, to provide additional processing gain for detecting and decoding AIS signals. For example, the receiving antenna 32 may have a right circular polarization, and the receiving antenna 46 may have a left circular polarization. Typically, the transmitting antenna used by the AIS 18 of a given ship 16 transmits AIS signals with a vertical linear polarization, which generally implies that the transmissions from particular positions have very well defined polarizations. In embodiments with two receiver channels, this polarization manifests as a phase shift between the AIS signals received by the two receiver antennas 32 and 46. That is, the AIS signal received by receiver 46 will be a lagged version of the corresponding AIS signal received by receiver 32. This phase shift may provide a mechanism to distinguish between overlapping AIS signals, as better explained below regarding to figure 6. Furthermore, due to the vertical linear polarization of the AIS transmitting antenna 18 of a given ship 16, the AIS signals that are received by the receiving antennas 32 and 46 and correspond to one another generally have similar amplitudes.

In general, receiver 20 is configured to receive an AIS signal in the radio frequency (RF) range and convert it to a baseband digital signal (ie, digital input data). This preprocessing and conversion performed by receiver 20 can be accomplished in a number of ways and incorporates standard operations in signal processing. For example, according to the exemplary embodiment shown in Figure 2, considering the receiving channel 28, an AIS signal is first received by the receiving antenna 32 and processed by the end

ES 2 448 867 T3 RF front end 34. The RF front end 34 includes filtering and amplifying components. The filtering components provide a first level of filtering to remove interfering signals, including intermodulation products produced by out-of-band carriers, as well as other noise. Filters that are generally used have only modest selectivity, but preferably have very low loss since any loss at this stage comes directly from the overall system noise figure. At this stage, the filtering components can include a VHF filter, which can be an LC type filter, and the amplification components include a low noise amplifier after the first level of filtering to boost the signal to a reasonable level.

The RF leading end output 34 is then processed by filter stage 36 which provides another level of more selective filtration. Filter stage 36 includes a broadband channel filter with a passband to transmit the three AIS channels (ie, AIS1 at 161.975 MHz, AIS2 at 162.025 MHz, and USAIS at 157.375 MHz). Alternatively, two combined filters can be used, one filter for the AIS1 and AIS2 channel and one filter for the USAIS channel, which can eliminate some interference between the two channels (ie AIS1 / AIS2 and USAIS). Filter stage 36 generally employs a surface acoustic wave filter that can provide the sharp filtration needed.

The received signals are further processed by the amplifier stage 38 for signal amplitude adjustment so that the entire quantization range of the ADC 42 can be utilized during digitization. Accordingly, amplification stage 38 includes variable-gain amplifiers and feedback can be provided from mixing stage 40 so that an automatic gain control (AgC) block (not shown) in amplifier stage 38 or the mixing stage 40 can regulate the amount of gain, or alternatively the attenuation, that is provided by amplifier stage 38. Alternatively, in other embodiments, control unit 22 may include an AGC component to control the amount of gain, or attenuation, provided by amplifier stage 38.

In this regard, receiver channel 28 employs distributed amplification and filtering using various amplification and filtering components to reduce the operating load on any of the components and avoid any non-linearities that may otherwise be encountered. How the amplification is distributed throughout this entire RF processing chain is a matter that depends on detailed considerations of power consumption, noise figure, and intermodulation products.

The output of the amplifier stage 38 is further processed by the mixing stage 40, and digitized by the ADC 42. The mixing stage 40 converts the VHF signals to an intermediate frequency (IF) band such as 25 MHz, which means that a lower sampling rate can be employed to reduce the requirements of the ADC 42. The ADC 42 then samples the data. If a sufficiently fast ADC is available, with sample rates above 400 MHz for example, then conversion to an intermediate frequency can also be omitted and digitization can take place at this point. For example, the ADC 42 may be a band pass sigma delta ADC. In this case, filter bank 44 provides downconversion to shift the frequency content of the data to the baseband as explained below. Alternatively, if an I and Q mixer were used, then the mixing stage 40 may provide baseband output data. In any of these embodiments, the mixing stage 40 also generally includes filters and amplifiers to provide further filtering and amplification or buffering. For example, filtering is employed at the output of mixing stage 40 to remove image bands and local oscillator leakage. For example, mixing stage 40 may include a post-mixer IF filter which may be an LC type filter.

The digitized data is then processed by filter bank 44. For the case where the data is sampled in IF, filter bank 44 includes means for downconversion to baseband, and narrow band filters to remove all data. out-of-band signals. For example, a 20 kHz bandwidth linear phase digital filter can be used for each AIS channel to account for the expected range in possible Doppler shifts. A component to perform decimation (not shown) can also be included at this point to reduce the output sample rate. In some embodiments, a digital signal processor (DSP) can be used to implement filter bank 44. In this case, the DSP can down-convert digitized data to baseband, perform narrow-band filtering, and perform decimation for produce digital input data. The AD6620 digital receive signal processor is an example of a DSP that can be used to produce input digital data that includes I and Q baseband data for each of the AIS channels.

In each of these embodiments, the receiver 20 preprocesses the received AIS signals to produce input digital data. This preprocessing includes fairly standard signal processing operations that can be performed with standard commercial hardware. The organization of hardware and processing can be modified in a number of ways as is generally known to those of skill in the art. Accordingly, the embodiments discussed herein are simply for the purpose of providing exemplary illustrations for performing such pre-processing. For example, in another embodiment, the RF front end output 34 can be digitized with an ADC and then passed to a DSP that can provide baseband downconversion, narrowband filtering, and decimation.

ES 2 448 867 T3

The input digital data is then supplied to the processing unit 24 for detecting and decoding the AIS message segments. Processing unit 24 may provide parallel processing capability to potentially reduce computational time, as is commonly understood by those of ordinary skill in the art. Once the processing unit 24 has received the input digital data, it supplies it to the processing module 60 for processing. The processing module 60 processes the input digital data to identify one or more candidate message signals and determine a corresponding Doppler shift estimate and time estimate for each candidate message signal. The processing module 60 generally processes the input digital data using correlation techniques. For example, the processing module 60 can process the input digital data with a plurality of predefined signals that correspond to Doppler shifts from a predetermined AIS code sequence (for example, a flag start sequence can be used in a field of flag start 126 shown in FIG. 5) to compute a plurality of correlation signals.

After calculating the plurality of correlation signals, the processing module 60 scans the correlation signals for correlation peaks (i.e., amplitude peaks) that exceed other peaks by a predetermined amount in order to identify the single or more candidate message tokens. Generally, the correlation peak should exceed the amplitude of any subsequent peaks that are within a signal length (ie, 26.67 ms) of the data segment being analyzed. The correlation peak associated with a candidate message signal provides an estimate of its time Dopplery shift, as will be explained in more detail later. The processing module 60 can be implemented using a group of processing components, described in more detail below, to calculate the correlation signals, using the predefined signals that correspond to Doppler deviations from a predetermined sequence of AIS codes, in parallel to reduce processing time.

In some embodiments, after identifying one or more candidate message signals, the processing module 60 sends this group of candidate message signals to the refinement module 62. The refinement module 62 refines the group of candidate message signals by classifying the signals candidate messages in this group by their corresponding time estimate. Refinement module 62 can then determine if any of these candidate message signals repeat at a different Doppler shift estimate; if so, refinement module 62 removes all repeated candidate message signals from the group. Finally, refinement module 62 removes all candidate message signals that are overlapped on their high time side by a stronger candidate message signal. This operation ensures that no time is wasted trying to decode questionable signals. In this case, it is unlikely that a signal can be decoded if its message segment is overlapped by an equally strong or stronger signal, regardless of the Doppler shift. The remaining candidate message signals include a group of refined candidate message signals that refinement module 62 sends to decoder 64. Refinement module 62 will typically alleviate the computation time required to decode all candidate message signals that are identified by processing module 60, since the group of refined candidate message signals is generally (much) smaller in size than the group of candidate message signals identified by the processing module 60.

Decoder 64 decodes one or more candidate message signals to obtain (or extract) the AIS message segment they contain. In some embodiments, decoder 64 receives the one or more candidate message signals from processing module 60. In other embodiments, decoder 64 receives the one or more candidate message signals from refinement module 62. In both cases, there are no predetermined code sequences within the message segment, so correlation techniques may not be useful in decoding a candidate message signal. In some circumstances, candidate message signals may contain specific identification numbers, such as a Maritime Mobile Service Identity, or specific locations. As such, in some cases, there may be some fixed known code sequences within the message segment, which can be used to employ correlation techniques. However, in cases where such fixed known code sequences do not exist, decoder 64 may employ various decoding procedures to extract message segments from the single or more candidate message signals. For example, decoder 64 may perform Viterbi decoding (or more generally dynamic programming), as explained in more detail below. In any case, prior to decoding, a more accurate Doppler shift estimate and time estimate are obtained for the candidate message signals, as will be explained later, regardless of whether the candidate message signals have been previously refined.

After decoder 64 extracts message segments from the one or more candidate message signals, the message segments are sent to validation module 66. Validation module 66 validates the decoded message segments for proper formatting of message messages. AIS signal by checking each decoded message segment for valid bit stuffing and then removing all bit stuffing. Bit stuffing is required by the AIS signal specification, where a 0 must be inserted into the message segment after any sequence of five successive 1s in the message and the frame check sequence portion of the message segment. This is done to avoid the appearance of start and stop flags.

ES 2 448 867 T3 spurious. The validation module 66 then verifies the frame check sequence field of the decoded message segment. If a decoded message segment passes these checks, it is temporarily stored in a list of decoded message segments that have been validated.

The decoded message segments are then supplied to modulator 68, which digitally modulates the decoded message segments for transmission to ground station 14. Modulator 68 may employ various digital modulation techniques such as a digital shift manipulation modulation scheme. phase (PSK) (that is, it modulates the phase of a signal). Examples include quadrature PSK or higher order PSK such as 8-PSK. The digital modulated decoded message segments are then received by transmitter unit 70 which includes circuitry to generate analog signals corresponding to the digital modulated decoded segments, upconverts these analog signals to the frequency range required for transmission, and amplifies these signals. so that they have the required signal strength that is necessary for transmission to ground station 14. These signals are then supplied to transmitting antenna 72 for transmission to ground station 14. Transmitting antenna 72 on LEO satellite 12 and receiving antenna 78 at ground station 14 may be configured for operation, for example, in the S band or X band. In an alternative embodiment, processing unit 24 may include modulator 68.

Furthermore, since the decoded message segments can be considered to include classified information that must be kept secure, encryption can also be employed prior to modulation. In these cases, the transmission unit 26 or the processing unit 24 includes an encryption module (not shown) to encrypt the decoded message segments before the modulator 68 modulates these message segments. In this case, the ground station 14 includes a corresponding decryption module (not shown) for decrypting the received data, after demodulation, to recover the original decoded message segments.

LEO satellite 12 also includes a memory component (not shown) so that it has the ability to store input digital data until it is sent to ground station 14. For example, LEO satellite 12 may not always be in the FOV of ground station 14 and thus it may be necessary to store the input digital data until the LEO satellite 12 enters the FOV of ground station 14, at which point the data can be sent.

Referring now to Figure 3, a block diagram of an alternate embodiment of a LEO satellite 12 'and a ground station 14' is depicted. The components of the general system are analogous to those represented in figure 2. However, in this embodiment, the ground station 14 'includes a processing unit 24', similar to the processing unit 24, and the LEO satellite 12 ' does not have the processing unit 24. In this case, the control unit 22 receives the digital input data from the receiver 20, and provides this data to the transmitter 26 which possibly encrypts, then modulates and transmits this data as transmitted digitized signal data 74 'to the ground station 14 '. Receiver 78 at ground station 14 'receives the transmitted digitized signal data 74', and demodulates this data by demodulator 84 to produce received digital input data that is supplied to processing unit 24 'in order to detect and decoding candidate AIS message signals.

In some embodiments, the processing unit 24 'can be a computing group and can be implemented as a parallel processing system using standard components such as a server (local or remote), a plurality of processors (for example Xeon 5140 2.33 processors GHz), dual-core, random access memory, virtual memory, several redundant series of independent drives (including a networked file system), a hard disk, and a software operating system (eg Linux). These components are linked by a dedicated network connection and although contained within a single ground station 14 'are illustrated, several components may be located locally or remotely from ground station 14.

The specifics of the downlink path is not described in detail, since it largely depends on the frequency assignments obtained from the regulatory entities. However, when detection and decoding are carried out at ground station 14 ', system 10' may be configured such that the downlink path accommodates a data rate transmission of around 3 Mbps. Otherwise, the components of the LEO satellite 12 'and the ground station 14' operate analogously to the components of the LEO satellite 12 and the ground station 14.

It should be noted that the control units 22 and 76 and the processing units 24 and 24 'can be implemented using a processor. Also, in some embodiments, the control unit 22 and the processing unit 24 can be implemented with the same processor. Likewise, in some embodiments, the control unit 76 and the processing unit 24 'can be implemented with the same processor. Additionally, in some embodiments, transmitter 26 and receiver 78 may also employ a processor. Furthermore, it should be noted that the various embodiments of LEO 12 and 12 'and ground station 14 and 14' generally employ a combination of hardware and software. For example, the components of the processing unit 24 and 24 ', the modulator 68 and the demodulator 84 can be implemented using software. Furthermore, it should be understood that there may be embodiments in which these components are arranged differently but performing the same functionality.

ES 2 448 867 T3

Furthermore, while the embodiments depicted in Figures 2 and 3 illustrate two particular system configurations, those skilled in the art should understand that many other system configurations can be employed. For example, some components of the processing unit can be implemented in a LEO satellite, such as the processing module, while other components, such as the decoder or the validation module, can be implemented in a ground station.

Referring now to Figure 4, there is depicted a flow chart of an exemplary embodiment of a method 100 for detecting and decoding AIS signals. In step 102, a plurality of AIS signals transmitted by a plurality of ships are received by the LEO satellite 12 and pre-processed to obtain digital input data. As explained above, generally the preprocessing converts the received AIS signals to a digital baseband form using filtering, amplification, and mixing, for example. In step 104, the input digital data is processed to identify one or more candidate message signals, along with a corresponding Doppler shift estimate and time estimate for each candidate message signal. The time estimate is the time of arrival of the AIS signal in question at the LEO 12 satellite. The time position of some particular marker within the signal can be considered, for example the start of a training sequence. The underlying approach to processing input digital data is to rely on the fact that AIS signals contain predetermined code sequences as depicted in Figure 5.

Referring now to Figure 5, a diagram illustrating the data structure of an AIS message signal 120 is depicted therein. The AIS message signal 120 includes an ascending ramp field 122, a training sequence 124, a field start flag 126, and a message segment field 128 including a ship ID field 130, a longitude field 132, a latitude field 134, and various other fields 136. The AIS message signal 120 also includes a Frame Check Sequence (FCS) field 138, an end flag field 140, and a buffer field 142. The up ramp field 122 generally matches the transmitter power of the AIS 18 of a given ship 16. The training sequence field 124 is included to allow the receiver of a conventional AIS 18 to perform carrier recovery. Start flag field 126 is a predetermined AIS code sequence that is generally used by various embodiments described herein to process input digital data to identify one or more candidate message signals, as will be explained. The message segment field 128 contains information regarding the ship 16 from which the AIS signal was sent, such as the ship ID 130 and the longitude 132 and latitude 134 of the ship's position. The other fields 136 also include information related to the ship including navigation status, rate of turn, true heading, etc., as well as other information such as a time stamp indicating when the information was obtained. The frame check sequence field 138 is used for error detection, and can be used to determine if some AIS message signal data has been lost or altered during transmission. End flag field 140 is another predetermined sequence of AIS codes that can be used during decoding, as will be explained in more detail later. Buffer field 142 can be changed in length so that, although bit stuffing is required, the overall length of the AIS message signal remains constant.

Referring back to FIG. 4, at step 104, the input digital data is processed based on the fact that the AIS message signals contain predetermined code sequences such as the training sequence and start flag field. 124 and 126 and the end flag field 140. There may also be other fixed known code sequences within the AIS message signal that can also be used, but, for the sake of simplicity, the processing in this exemplary method 100 will use at least the data in the training sequence field 124, i.e. in some cases the predefined signals are based on the training sequence field 124, while in other cases the predefined signals are based on both the training sequence and start flag fields 124 and 126 (ie, a combination of the training sequence and the start flag sequence). In other cases, a portion of the message segment can also be used since the first byte of message segment 128 is also reasonably predictable. Typically, step 104 employs correlation techniques by correlating the training sequence and start flag fields 124 and 126 with predetermined code sequences at a plurality of different Doppler shifts to produce a plurality of correlation signals (which are also can be called correlation functions). The generated correlation signals can then be used to identify one or more candidate message signals contained within the input digital data. Generally, a peak in the amplitude of the correlation signal (i.e., a correlation peak) is used to identify a candidate message signal along with an estimate of its time, using the position of the amplitude peak and an estimate of its Doppler shift which will be the Doppler shift associated with the predefined signal that was used in the correlation. Other details about an exemplary implementation of the processing in step 104 are explained later with reference to FIG. 7.

The method 100 may then decode the candidate message signals identified in step 108 to extract the message segments they contain. Optionally, method 100 may include step 106 in which the candidate signal messages identified in step 104 are refined to produce a refined (and typically smaller) set of candidate message signals that can then be decoded in step 116. An exemplary implementation of the refinement step is described in relation to Figure 8. The underlying approach

ES 2 448 867 T3 to the refinement step is that a large number of candidate message signals will generally be identified in step 104, but due to the overlapping signals, it may be difficult to decode the candidate message signals. Therefore, for computational efficiency, refinement can be performed to remove and / or replace overlapping and repeated candidate message signals so that decoding is carried out on a smaller group of candidate message signals.

In step 108, the group of candidate message signals is decoded to extract the message segment it contains. As explained above, in general, there are no fixed known code sequences within the message segment, so correlation techniques may not be useful for decoding the candidate AIS message signal. However, other techniques can be employed to decode candidate AIS message signals, such as dynamic scheduling techniques, or more specifically Viterbi decoding. Furthermore, prior to decoding, a more accurate Doppler shift estimate and time estimate are obtained for the candidate message signals, as previously mentioned.

Fine tuning of the correlation signals is carried out in order to obtain a more accurate determination of time and Doppler shift for each of the candidate message signals. This fine-tuning procedure is based on the Schwarz inequality (see equation (5) below), which shows that the maximum overlap integral is obtained when the two correlated functions are identical. This fine-tuning procedure uses the same predetermined AIS code sequences used to generate the predefined signals in the correlation step. The time and Doppler deviation estimates of the predefined signals are then adjusted slightly to maximize the overlap integral with respect to the candidate message signal, using the initial Doppler deviation estimate and the time estimate as a starting point. The resulting fine-tuning values ​​typically represent the best achievable estimates of time, phase, and Doppler shift, that is, an exact Doppler shift, time, and phase for the identified candidate message signal. Maximizing the overlap integral implies maximizing a function of two variables given a good starting point. This can be done using a standard mathematical optimization routine, such as Newton's method, for example.

When decoding a candidate AIS message signal, Viterbi decoding uses the Viterbi algorithm to decode a stream of bits, or in this case a message segment. However, during the decoding process, numerous sub-message segments are generated (i.e., partial routes as better explained below) and then the best message segment has to be selected from this group of possible sub-message segments. . This selection of the best message segment is done in the absence of any specific knowledge about the message segment contained within the candidate AIS message signals, since it is assumed that nothing is known about the content of the message segment in order to use a broader decoding implementation. To select the best message segment, the decoding may include determining which sub-message segment (of the group of sub-message segments) gives the closest match possible with the candidate AIS message signal. Many possible proximity measures can be used; an example is choosing the sub-message segment that minimizes the least squares error estimate.

In general, at any point the Viterbi decoding can be considered to be in one of a number of possible states. The operation of the Viterbi algorithm can be understood with the help of a trellis diagram (not shown), which illustrates the possible states and paths. The Viterbi decoder will start at a starting point (or start state) and as the decoder advances in time, each state may transition to one or more later states. This generates a number of possible routes through the Trellis (ie the sub-message segments mentioned above). Depending on the number of states and the length of the message segment to be decoded, the number of possible routes can be very large.

In the context of decoding AIS message signals, a suitable starting point (or state) for the Viterbi decoder may be the predetermined code sequence at the start of the AIS message signal, namely the start flag field 126. From this starting point, the Viterbi decoder will transition to one or more of the subsequent states, generating a number of possible routes (ie, the sub-message segments listed above) before terminating. An AIS message signal contains another predetermined code sequence that will help terminate a route, specifically the end flag field 140. Therefore, the Viterbi decoder continues to advance in time to generate a number of routes (ie, sub-message segments) until the content of the end flag field 140 is detected on a specific route. When the content of the end flag field 140 is detected, that specific route will terminate.

In order to determine the Viterbi decoder configuration in the context of AIS message signals, the properties of the AIS message signal can be considered. As explained above, AIS signals are transmitted using GMSK modulation, where the message segment (ie, the sequence of bits) is transformed into waveforms (which make up the AIS signal) for transmission. Considering simple baseband MSK (manipulation with minimal offset) first, the signal waveform corresponding to each bit period is in one of two forms (generally opposite) depending on whether the bit is a 0 or a 1 Each bit advances or retards the phase of the π / 2 signal depending on whether it is a 1 or a 0 respectively. The preceding bits only affect the current bit insofar as they set the start phase, which can take one of four values

ES 2 448 867 T3 possible: 0, π / 2, π, and 3π / 2. Therefore, a Viterbi decoder with four states is appropriate for this type of decoding where, at each time step (i.e. bit interval), the states are defined by the four possible start phases set by the preceding bits. (for example 0, π / 2, π, 3π / 2).

In GMSK modulation, each bit produces a total phase shift of ± π / 2, but the effect of each bit is spread over several steps in time. However, as an approximation, this effect can be neglected beyond the nearest contiguous intervals. In other words, to determine the waveform associated with a particular bit, such as a 0 for example, the bits that precede and follow the particular bit are necessary. For an approximation, the waveform in any bit interval will have one of eight possible shapes, rather than the two required for simple MSK. In this approach, a Viterbi decoder for GMSK modulation requires 16 rather than 4 states, where the state at an inter-bit boundary is defined by the preceding bit, the next bit, and the four possible phase states (i.e. 0, π / 2, π, and 3π / 2) produced by the other preceding bits. However, if the phase state at any point is 0 or π, then the decoder can only go to phase states of π / 2 or 3 π / 2 in the next step and vice versa. In addition, all routes on the Trellis begin in a start state, determined by a predetermined code sequence, such as the data in the start flag field 126. Therefore, only 8 of the 16 possible states can be active. in any subsequent step. Therefore, the Viterbi decoder for decoding AIS message signal segments effectively has 8 states.

As explained above, each path in the trellis corresponds to a particular sequence of bits, which can be a message segment when the path is terminated. However, considering that an AIS message segment, including the data in frame check sequence field 138, is at least 184 bits long and that the Viterbi decoder effectively has 8 states, the total number of possible routes ( i.e. sub-message segments) can be quite large. Therefore, an operable Viterbi decoder should attempt to terminate most of these routes at intermediate points and not follow them all the way through the Trellis, as explained above. By reducing the number of routes, the number of possible decoded message segments from the candidate AIS message signal is in turn reduced. This can be done using what is sometimes called in dynamic programming the BeIlman optimality principle. This requires that when two or more routes join in the same state at a particular point in time, only the partial route (ie the sub-message segment) with the best performance measure is retained. The path with the best performance measure is the path that is closest to the actual signal, at that point, based on the chosen performance measure. The basis of this procedure is that any route that progresses from that state and time point will have a better overall performance measure if it is associated with the surviving route (that is, a previously held route) rather than with any of the routes that were scrapped. It also ensures that the number of active routes at any point in time cannot exceed the number of states (since only one route is selected whenever two or more routes meet in the same state).

Many techniques can be used to determine which partial path has the best performance measure. However, the technique used to select the best partial route should be capable of selecting the best partial route in the absence of any specific knowledge about the message segment contained within the candidate AIS message signal. An exemplary technique that can be used to choose the best partial path minimizes the least squares error estimate. For example, the least squares error estimate can be expressed as:

N τ i-lo where s (t) represents the candidate AIS message signal, and a¡ (t) represents the theoretical waveform associated with a partial path in the i-th bit interval, T is the duration of an interval bit (1/9600 s), and N is the number of bit intervals in the candidate message signal. The least squares technique then selects the a¡ (t) that minimizes the previous equation.

The least squares error estimate can also be expressed as:

N τ

E = 2 - 2R «a¿t) s (t + (z - 1) T)) + | s (r + (i - l) T) fa (2) rl 0 where s * (t) is the conjugate complex of s (t). Many performance measures can be employed. Normally the measure would be some positive number that is zero only when the two functions are identical. A typical option would be an Lp standard, which has the form

ES 2 448 867 T3

<img file="ES2448867T3_D0001.tif" />

The current option corresponds to p = 2. This is by far the most common option, since it is generally the simplest mathematically, and has theoretical justification in many cases. The options p = 1 and p = ~ are also quite popular; you can use p = 1. Other p-values ​​can also be used in some cases.

Factoring now that the theoretical waveform (that is, the waveform representation of the partial path) is phase modulated only, then | a, (t) | is a constant, and thus minimizing E is equivalent to maximizing P, where P is expressed as:

Ν T ϊ-lo

In order to use the technique described by equation (1), a specific value must be set for | a¡ (t) | at the beginning of decoding. This would normally be estimated from the amplitude of the predetermined code sequence at the start of the AIS message signal, namely the amplitude of the data in the start flag field 126. Such a specific amplitude estimate does not have to use equation (3). The i-th interval is a bit period, which in this case is 1/9600 s.

As noted above, generally the data in AIS message segment field 128 and frame check sequence field 138 are at least 184 bits long (message segment field 128 is 168 bits long and the frame check sequence field 138 adds another 16 bits). In addition, the AIS specification requires bit stuffing such that a 0 is inserted after any sequence of five successive 1s in the message and the frame check sequence portions of the code. This is done to avoid spurious start and stop flags. There can be up to four of these bit stuffing bits, increasing the overall length of the message segment field 128 and the frame check sequence field 138 to a maximum of 188 bits.

Therefore, a message segment will be between 184-188 bits and so in this context the Viterbi decoder will terminate a route if a valid stop flag is found after between 184-188 bits have been extracted. In very rare cases more than one route is found with a valid stop flag for a given candidate AIS message signal. Even though this happens, all the extracted message segments are passed to step 118 for validation.

In step 110, the decoded candidate message signals are validated to ensure they have proper AIS formatting. This may involve checking the decoded candidate message segments for a valid bit padding format, as explained above. The bit stuffing bits are then removed and the frame check sequence field 138 is checked. If a list of validated decoded message segments is desirable (i.e. for later storage and retrieval), then all decoded message segments that pass this validation step can be added to a list of validated decoded message segments and stored in step 104. In general, if a message segment is partially correct it will not pass the validation step. However, alternative embodiments may use these partially extracted message segments for further message segment extraction. At step 104, all decoded message segments can be stored for later reclaim. Alternatively, there may be embodiments where only the list of validated decoded message segments is stored.

An optional extension of method 100 is to de-map all decoded message segments from the input digital data (ie, subtract the best match signal representation corresponding to the extracted message segments from the initial input data). This can be done after validation step 110. The method 100 can then go back to step 104 and reprocess the modified input digital data in an attempt to identify additional candidate AIS message signals, which can then be decoded to extract more message segments.

Another optional extension to this method 100 recognizes that AIS message signals sent from a single ship 16 will have substantial common message segments. Therefore, repeated messages from any given ship 16 can provide another mechanism to improve detection and decoding. For example, a previously detected message segment from a given ship 16 can be used to generate the predefined signal used in obtaining the correlation signals. Additionally, previously decoded message segments can provide the option of using correlation techniques when decoding message signals.

ES 2 448 867 T3 candidates. In such an embodiment, decoder 64 is also configured to employ correlation techniques using the previously decoded message segments when decoding the candidate AIS message signals. If parts of the message sequence are known, such as the MMSI (ie ship id), then these can also be used as part of the fixed code sequences used in the mapping procedure in step 104. A longer fixed code sequence discriminates better against other signals and gives a higher probability of detection. For example, when extracting the message sequence by a Viterbi decoder, the presence of known code sequences predefines path segments and improves the overall probability of successful decoding.

Referring now to FIG. 6, a flow chart of another exemplary embodiment of a method 150 for detecting and decoding AIS message signals is depicted. Method 150 is similar to method 100. However, method 150 includes step 152, which corresponds to LEO satellite embodiments in which two or more receiver channels are used. In these embodiments, in step 152, candidate message signals that correspond to one another, but have different polarizations (i.e., AIS signals received by receiving antennas 32 and 46), are combined with a phase shift that maximizes the amplitude of the resulting combined candidate AIS message signal relative to that of any overlap signal.

As explained above, a given AIS signal received by both receiving antennas 32 and 46 gives rise to two corresponding candidate AIS message signals with two different polarizations, where one candidate AIS message signal is an out-of-date version of the other message signal. Candidate AIS and both have comparable amplitudes. This phase shift could be anywhere in the range of 0 to 360 °. The two corresponding message signals are identified from corresponding correlation peaks (essentially equal time) identified in step 104. The phases of the two correlation functions at their corresponding peaks determine the phase difference between the corresponding messages. One or both of the candidate AIS message signals may be overlapped by another message signal.

However, applying a phase shift to one or both of the two corresponding candidate AIS message signals and then combining these signals can cancel out any unwanted overlapping signals, or at least reduce the intensity of these unwanted signals. Furthermore, this step attempts to maximize the amplitude of the combined candidate AIS message signal (relative to any overlapping signals), to produce a stronger signal for decoding. The combined candidate AIS message signal can then be substituted for the two corresponding candidate AIS message signals and decoded in step 116. In alternative embodiments, step 152 can be carried out by detection and decoding methods that do not employ the step of refinement 106.

Alternatively, in step 152, the two corresponding candidate AIS message signals are simply combined using a variety of fixed offsets to create a subset of combined candidate AIS message signals. If a candidate AIS message signal is overlapped by an unwanted signal with a different polarization, then it may be desirable to combine the candidate AIS message signal with the corresponding candidate AIS message signal (received by the other receiving antenna) using a phase shift. cancel the overlapped unwanted signal. In this case, to determine the optimal phase shift, a variety of fixed offsets can be used, such as 8 different offsets starting at 0 ° and advancing in steps of 45 °, for example. The underlying strategy is to find an offset that best cancels one or more of the unwanted overlap signals giving a better chance of successful decoding. This strategy is computationally more expensive than the one previously described because decoding must be attempted on multiple combinations of the signals in the two polarizations. However, in practice, it is somewhat more successful at extracting codes.

Referring now to Figure 7, an implementation 104 'of the processing step 104 is illustrated in more detail. At step 160, the input digital data, representing the plurality of AIS signals received in one or both polarizations, depending on the number of receiver channels are correlated with a number of predefined signals to produce a plurality of correlation signals. Each of these predefined signals corresponds to a sequence of specific known AIS message signals at a specific Doppler shift. The number of predefined signals is chosen so that there is always a predefined signal with a Doppler shift that is close enough to that of any possible received AIS signal so that the correlation peak can be detected with minimal loss of amplitude. A Doppler shift between the predefined signal and the actual signal will reduce the amplitude of the correlation peak. You have to select a tolerance on the allowable amplitude loss, such as 0.5 dB for example. This then sets the allowable Doppler shift to Af, for example. If the predefined signals are then chosen so that their Doppler shifts are spaced 2Af apart, then any real signal will necessarily be within Af of one of the predefined signals. This correlation operation can be implemented using a bank of adapted filters (or more generally correlators). In some embodiments, the matched filter bank may be selected to allow some mismatch in order to reduce the side lobes of the correlation peak so that they are not confused with other candidate message signals in step 104, as will be better explained. in relation to Figures 9A-9C.

ES 2 448 867 T3

At step 162, each correlation signal is scanned for peaks whose amplitudes exceed those of any subsequent peaks that are within the same signal length (i.e., 26.67 ms) by some specified amount (such peaks are may be referred to here as correlation peaks). Correlation peaks in a correlation signal identify candidate AIS message signals, since it provides an indicator that a signal similar to the predetermined AIS message code sequence used to generate the predefined signal is contained within the digital data segment of entry that is currently being processed.

Identifying correlation peaks in the plurality of generated correlation signals whose amplitudes exceed a predetermined amount provides a rough estimate of the time, Doppler shift of an identified candidate message signal. This principle can be applied to many types of modulation. This is due to the discovery that if a spike occurs in a correlation signal, then the two signals (ie, the identified candidate AIS message signal and the predefined signal) are likely to have similar Doppler shifts. Any spike in a correlation signal will be greatly reduced, or even completely removed, if the two correlated signals (i.e., the identified candidate message signal and the predefined signal) have different Doppler shifts. This will be explained in more detail later with reference to Figures 10A-10C. Accordingly, the estimated Doppler shift will be the Doppler shift used for the predefined signal in correlation signals having an identifiable correlation peak.

To provide a more comprehensive explanation of how the generated correlation signal provides a means of identifying candidate AIS message signals and discriminating between overlapping signals with different Doppler shifts, reference will now be made to Figures 9A-9C and Figures 10A-10C. , which show graphical representations of various correlation signals. Generally speaking, the correlation function provides a measure of how well one signal corresponds to another signal (or a time-shifted version of another signal). The correlation function used to generate the correlation signal for two complex signals can be written as:

oe c (t) = J r (r) s' (τ - t) dr (4)

-X

Those skilled in the art understand that the Schwarz inequality states that:

<img file="ES2448867T3_D0002.tif" />

Therefore:

<img file="ES2448867T3_D0003.tif" />

Generally, autocorrelation is a measure of how well a signal is self-matched. Using the above formulas, an autocorrelation function for a signal can be expressed as:

<img file="ES2448867T3_D0004.tif" />

where equality is valid when t = 0. In equations (4) to (7), c (t) is the correlation function, r (t) is a first complex signal, s (t) is a second complex signal, a (t) and b (t) are arbitrary complex functions, and * denotes a complex conjugate.

Correlating a signal with an identical replica implies that there is a minimum mismatch of 0 dB between the waveforms. However, such a procedure can have significant weaknesses. The correlation signal has its maximum amplitude when the signals exactly overlap each other, but the correlation signal can also have other significant peaks or side lobes. When calculating correlation signals using

As segments of the input digital data, such side lobes can be confused with other candidate message signals, so it is important to ensure that these side lobes are suitably suppressed.

Referring to Figure 9A as an example, a correlation signal resulting from the correlation of a signal with an exact replica of itself is depicted (ie the mismatch loss is 0 dB). The signal corresponds to a known exemplary message AIS signal code sequence that can be used to generate the predefined signals used in step 160. The known code sequence used in this example is 40 bits long and includes a training sequence (24 bits), a start flag (8 bits), and the first byte (8 bits) of a message segment (see figure 5). It can be seen that the side lobes 192 are approximately 4 dB below the correlation peak 190, which is large enough that the side lobes 192 can be confused with other candidate message signals (since they appear to be peaks), when exploring the correlation signal for correlation peaks in step 162. To scan for peaks, a threshold value can be selected empirically. Basically, a very low threshold value will identify many spurious peaks, and a lot of computer time can be spent trying to decode them uselessly. Conversely, a high threshold value can unnecessarily exclude valid peaks. A value of around 4 dB has been found to be a reasonable practical compromise. The vast majority of spurious peaks generated within an AIS signal are more than 4 dB below the main correlation peak (see Figure 10a, for example).

Figure 9B depicts the correlation signal that results from correlating one signal with another signal that is not an exact replica in such a way that there is a minimum 0.5 dB mismatch loss between its waveforms. It can be seen that the side lobes 196 are approximately 7 dB below the main peak 194, which is lower than the side lobes 192 of the correlation signal with 0 dB mismatch in FIG. 9A. It is clear that side lobes 196 are presumably less likely to be confused with other candidate AIS message signals when scanning the correlation signal of Figure 9B for correlation peaks.

Figure 9C depicts the correlation signal that results from correlating one signal with another signal that is not an exact replica in such a way that there is a minimum mismatch loss of 1 dB between its waveforms. It can be seen that the side lobes 200 are approximately 10 dB below the correlation peak 198, which is lower than the side lobes 192 of the 0 dB mismatch correlation signal depicted in FIG. 9A. It is clear that the side lobes 200 are presumably less likely to be confused with other candidate AIS message signals when scanning the correlation signal of Figure 9C for correlation peaks. However, mismatch loss is undesirable because it reduces the margin between the correlation peak and any spurious peaks that may exist, thereby making it more difficult to detect candidate AIS message signals in step 162. On the other hand, the minimum mismatch loss that is consistent with an acceptable level of side lobes should be chosen, so as not to confuse the side lobes with candidate AIS message signals. As depicted in Figure 9B, a 0.5 dB mismatch loss gives a side lobe level reduction of approximately 7 dB from the correlation peak. This is less than the typical spurious peak or sidelobe levels found when calculating the correlation of a received AIS signal with a predefined signal. Accordingly, a 0.5 dB mismatch is a reasonable practical choice, although the exact value is not too critical, and the processing in step 160 may be configured for a 0.5 dB mismatch. There can always be a trade-off between side lobe level and mismatch loss, but the exact mismatch option depends on the particular waveform. If the fixed code sequence within the AIS signals that is used for the correlator is changed, then in general a different mismatch loss option will be appropriate.

As explained above, performing the correlation as described here is an effective way to distinguish between overlapping signals with Doppler shifts. This is due to the fact that a correlation peak in a correlation signal will be greatly reduced, or even completely removed, if the two correlated signals are at different Doppler deviations, whereas if a correlation peak occurs in a correlation signal, then the two signals are likely to have similar Doppler shifts. For example, suppose that the processed input digital data segment contains two overlapping AIS signals with different Doppler shifts. If a predefined signal has a similar Doppler shift to one of the AIS signals, then the correlation signal generated for this input digital data segment will generally contain a correlation peak that will be much larger for the AIS signal that has a similar Doppler shift. compared to the other AIS signal. This is illustrated in Figures 10A-10C.

Figure 10A represents the correlation signal that results from correlating a simulated AIS signal with a signal generated using a known 40-bit AIS code sequence, including a training sequence (24 bits), a start flag (8 bits) , and the first byte of the message sequence (8 bits), with a mismatch loss of 0.5 dB. Referring to FIG. 5, it can be seen that an AIS message signal begins with an 8-bit ascending ramp field 122 of eight zeros, preceding the 40-bit AIS code sequence used to generate the correlation signal. Accordingly, as shown in FIG. 10A, the correlation peak 202 occurs at bit 8, when the 40-bit AIS code sequence begins. Figure 10A illustrates that correlation peak 202 has a significant amplitude margin over any side lobes or other spurious peaks; this is partially due to the allowed 0.5 dB mismatch.

ES 2 448 867 T3

Figure 10B depicts the computed correlation signal by correlating a simulated AIS signal with the same predefined signal used in Figure 10A, except that the predefined signal has received a 100 Hz Doppler shift. Comparing the correlation peak 202 of Figure 10A with At correlation peak 204 in FIG. 10B, it can be seen that the 100 Hz Doppler shift has reduced correlation peak 204 by approximately 4 dB.

Figure 10C represents the correlation signal that results from correlating a simulated AIS signal with the same predefined signal that was used in Figure 10A, except that the predefined signal has received a Doppler shift of 200 Hz. Comparing the correlation peak 202 of Figure 10A with the correlation peak 206 of Figure 10C, it can be seen that the 200 Hz Doppler shift has greatly reduced the correlation peak 206 such that the peak 206 is essentially obscured by noise and is not detectable.

Consequently, at step 162 when the correlation signals are scanned for peaks, if the located peaks have amplitudes that exceed those of any subsequent peaks that are at the same signal length (in this case 26.67 ms, for example) by a certain amount, such as about 4 dB as previously explained for this example, a candidate AIS message has been detected, and the Doppler shift of the predefined signal provide an estimate of the Doppler shift of the candidate AIS message and the time of the localized peak provides a time estimate for the candidate AIS message.

To better illustrate this point, the effects of the Doppler shift on the correlation peak can be roughly explained as follows. Considering the case of zero mismatch for simplicity's sake, from equation (7) the magnitude of a correlation peak is given by:

<img file="ES2448867T3_D0005.tif" />

where T is the duration of the signal (40 bits or 40/9600 = 4.167 ms in this example). In a first order, the Doppler shift will modify the magnitude of the correlation peak to:

7/2

J 5 (r)? (- r) exp (jw_DT) ¿T (9)

-7/2 where Wd is the Doppler shift, giving a mismatch of:

<img file="ES2448867T3_D0006.tif" />

When an AIS signal is transmitted using GMSK modulation, which is a form of phase modulation, the signal has constant amplitude and equation (10) simplifies to:

<img file="ES2448867T3_D0007.tif" />

As a simplified example, assuming the predefined signal is generated using a 40-bit sequence and a 100 Hz Doppler shift, with fDT = 100x40 / 9600 = 0.4167, then equation (11) gives a mismatch of 2.64 dB. The mismatch estimate in equation (11) is generally only strictly valid for a perfectly matched filter, but is still approximately correct for mismatched filters that are used in practice.

Equation (11) can be used to select the Doppler shifts for the predefined signals required in processing step 160. In some embodiments, an additional 0.5 dB mismatch will be

IS 2 448 867 T3 acceptable, and equation (11) then implies that | foT | &lt;0.186. For a 40-bit correlation sequence, this implies that | id) | &lt;44.6 Hz. Therefore, if the predefined Doppler deviations are on a uniformly spaced frequency grid with a spacing of less than 89.2 Hz, then the largest possible mismatch with a real signal will be less than 0.5 dB. If this is combined with the 0.5 dB mismatch typically allowed to reduce side lobe levels, then the maximum overall mismatch is 1 dB, which is a reasonable figure.

In another alternative embodiment, multiple predetermined AIS code sequences can be used to calculate the predefined signals used in processing step 110. In this case, a generalized correlation function can be defined using a weighted linear combination of the individual correlation functions. (w¡> 0):

N c (0 =]? J η (Φ * (τ- t) dr (12) il -®

Given the

<img file="ES2448867T3_D0008.tif" />

where equality is valid at t = 0 if r, = yes, then a mismatch loss can be defined with:

<img file="ES2448867T3_D0009.tif" />

where the minimum loss is assumed to occur at t = 0.

As before, a zero mismatch is achieved if r¡ = s¡ for all i, but, as explained above, r¡ can be designed to allow a slight mismatch (around 0.5 dB for example) in order to reduce the level of side lobes in the generalized correlation function of equation (12). In general, the longer the predefined code sequence used, the better the overall performance. In such an embodiment, the processing module 60 may be configured to generate the predefined signals used in the correlation using a plurality of predetermined AIS code sequences. In the above equations (12) to (14), N is the number of code sequences, r¡ (t) is the first complex signal for the i-th code sequence, s¡ (t) is the second complex signal for the i-th code sequence and c (t) is the generalized correlation function. Also, there is no exact rule for selecting the default code sequences, and the option may vary from case to case. However, such predetermined code sequences must include code segments that are always fixed, or at least are fixed for the vast majority of cases, within the set of desired signals.

Referring now to Figure 8, a flow chart of an exemplary embodiment 106 'of refinement step 106 is depicted. At step 170, all detected candidate AIS message signals (for all Doppler shifts) are classified in ascending time order. At step 172, all repeated candidate AIS message signals where the same message has been detected at more than one Doppler shift are removed. In step 174, messages that overlap in both polarizations are removed by stronger signals on their high time side, to obtain a refined set of candidate message signals. The term "high time side" refers to a given signal overlapped by one or more signals whose correlation peaks occur at a later time than the given signal.

After obtaining a refined set of candidate message signals, optionally in step 176, narrow-band filtering can be applied to the refined set of candidate message signals centered on the known Doppler shift frequency estimate. The bandwidth of this filter is typically 10 kHz. Narrow-band filtering blocks as much spectral energy as possible from overlapping signals with different Doppler shifts, and improves the probability of successful decoding.

For the sake of simplicity, the embodiments described herein have been primarily described in relation to systems and methods with a LEO satellite and a ground station. However, as noted above, it is possible

ES 2 448 867 T3 systems and methods employing multiple LEO satellites and / or one or more ground stations, creating new possibilities for detecting and decoding AIS signals. With multiple LEO satellites, the AIS signals from a given ship can be received by more than one LEO satellite. Correlation techniques can then be used using the data from the multiple LEO satellites. AIS signals received from ground stations can also be used. For example, embodiments can be configured to de-correlate ship-transmitted AIS signals within the FOV of a shore station from input digital data produced by a LEO satellite. This de-correlation removes already detected AIS signals from the input digital data, and in effect, primarily only the AIS signals sent by ships outside the ground station FOV remain in the input digital data for further processing, limiting the detection and decoding of AIS signals to ships outside the FOV of land stations. Furthermore, it should be noted that there may be embodiments in which the steps depicted in at least one of Figures 7 and 8 are combined with the steps depicted in Figures 4 or 6.

Numerous specific details are set forth herein in order to provide a complete understanding of the exemplary embodiments described herein. However, those skilled in the art will understand that these embodiments can be practiced without these specific details. In other cases, the known methods, procedures and components have not been described in detail in order not to obscure the description of the embodiments. Furthermore, this description is not to be construed as limiting the scope of these embodiments in any way, but rather a simple description of the implementation of these various embodiments.

For example, in an alternative embodiment, additional antennas and receiver channels can be used to provide additional directional information, which can help distinguish AIS signals from different regions. If additional spatially separated antennas of any polarization are used, then all antennas receive signals of similar intensity, but with different phases. By combining these signals with appropriate combinations of phase and amplitude, it is possible to discriminate in favor of some spatial directions and against others. This is similar to the concept of a serial antenna in phase, where directivity is achieved by having numerous radiating elements fed by an appropriate combination of phase shifters. The hardware required is a generalization of the embodiment described here for the two antenna arrangement, where each antenna has its own RF chain. In this case, the signal processing involves combining the antenna outputs in various phase combinations in a manner similar to that described for the realization of two antennas described here. In cases where insufficient spatial separation of antennas is achieved on a single LEO satellite, a group of LEO satellites can be used to utilize this spatial differentiation feature of AIS signals received in space. In effect, this can be thought of as increasing the effective antenna size to improve directivity. This hardware and processing structure can be generalized to any number of antennas that can be spatially differentiated using polarization or using these two features. Provided that independent information is available from each antenna, combining the antenna outputs in different phase combinations provides a mechanism to discriminate AIS signals coming in from different directions.