# Time Delay Estimation of AIS Signal Based on Three-Order Cumulant

Authors: Xin Meng; Dawei Zhao; Shexiang Ma; Jianfu Teng
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

A time delay estimation algorithm based on three-order cumulant with the different symmetry of modulation signal between training sequence and information sequence of AIS (Automatic Identification System) is presented, which aims to overcome the large time delay and strong noise in the receiver side of AIS. Theoretical analysis and simulation results show that this algorithm successfully suppresses the influence of Gaussian noise. Moreover, under non-Gaussian and correlative noise, it can also obtain a fine estimated performance. Simulation results show that this algorithm is superior to the correlative and data-aided time delay estimation ones.


---

## Body

## 1. Introduction

In AIS (Automatic Identification System), the channel varies quickly with time, and the signal noise ratio (SNR) is low [1]. The performance of time delay estimation will greatly affect the detection and separation of AIS signal. So how to achieve the accurate estimation of time delay in low SNR has become an urgent problem. For MSK and GMSK base-band signal, [2] presents a high-order autocorrelation algorithm based on the front feedback structure. It is a widely used algorithm of time delay estimation at present, but the estimation performance is affected by the autocorrelation step; [3] designs a self-correlation time delay estimation algorithm based on one-bit difference with the use of the prior information of frame structure of AIS signal. This algorithm can overcome the influence of frequency offset and phase shift, but it is sensitive to noise; [4] proposes a two-order self-correlation algorithm and it extracts the cosine function which contains time delay from the autocorrelation function of received signal, but the computation burden is large, and estimation accuracy is relatively low. Besides the estimated range is only half of the symbol period; In [5], there is a time-phase-combined estimation algorithm based on the principle of maximum likelihood. Time delay can be obtained by the joint likelihood function of the delay and the phase of the received signal. The algorithm has a certain improvement in the estimation accuracy, but it relies on high-precision frequency offset correction. When the error exceeds 5, time delay estimation accuracy will deteriorate rapidly; [6] proposes a time delay estimation algorithm based on digital phase-locked loop, but the estimation performance is not fit for GMSK modulation signal; [7] deduces the relationship between phase information of power spectrum and autocorrelation function from frequency domain, and then the phase spectrum of the regression straight line is weighted averagely, but the estimation performance of the algorithm is greatly affected by the power spectrum method; a delay difference estimation algorithm based on one-dimensional slice of three-order cumulant is proposed in [8]. This algorithm needs two sensors to deal with two receipt signals, which is not in conformity with the requirements of AIS receiver; [9, 10] present maximum likelihood algorithms of time delay estimation. This algorithm requires that the conditional probability density should be known, so as to construct a delay probability density function to estimate the time delay by the peak. But in actual communication, the probability density of signal is so difficult to obtain, that it is hard to achieve in application; [11] presents an adaptive time delay estimation algorithm based on high-order cumulant. But this algorithm needs the design of high-order filter and the repeated iteration. The complex computation is not conducive to the realization of AIS receiver hardware.The algorithm in this paper makes use of the different symmetry of modulation signal between training sequence and information sequence of AIS. Then define the delay measurement function based on three-order cumulant and estimate the time delay by minimization. As a result, it successfully restrains the influence of noise on the time delay estimation of AIS signal and the accurate estimation is achieved.


## 2. AIS Signal Model

AIS signal mainly uses the protocol of SO-TDMA. According to HDLC high-level data link control procedures, AIS signal uses grouped-structure. There is 256 bits per message. The message frame is shown in Table1 [12]Table 1
Message structure of AIS.
8 bits 24 bits 8 bits 168 bits 16 bits 8 bits 24 bits RU TF SF Data Fcs EF BufferThe modulation of AIS is GMSK. The binary information of the ship is represented asai. After coding of NRZI (No Return Zero-Inverse), ai take on the value ±1. The base-band signal of GMSK is shown as follows:(1)st=ejψai;t(2)ψai;t=π∑iaiqt-iTb(3)qt=∫-∞tgτdτ(4)gt=12TbQ2πBln⁡2t-L+12Tb(5)Qt=12π∫t∞e-τ2/2dτ,where q(t) is the phase pulse response, g(t) is the rectangular impulse response of Gaussian filter, L is the correlation length, B is the band-width of 3 dB, and Tb is symbol period.Rectangular impulse response of Gaussian filter is infinite in theory. In order to put Gaussian filter into practice,g(t) is truncated with correlation length L=3.(6)qt=0,t<-L-1Tb212Tb∫-∞tgτ-12Tb1dτ,-L-1Tb2≤t≤L+1Tb212t>L+1Tb2.


## 3. Time Delay Estimation Algorithm Based on Third-Order Cumulants

### 3.1. Symmetry Analysis of AIS Signal

The symmetry of signal can be expressed by the skewness [12]. If the skewness is greater than zero, positive deviation value is larger and probability density function drags the long tail on the right. To the contrary, negative deviation value is larger, the long tail is on the left. The more close to 0 the value of skewness is, the more close to the symmetrical distribution the signal will be. If signal obeys normal distribution, the skewness is equal to the three-order center distance where value is 0.From Table1, training sequence of AIS signal is composed of 24 bits alternate codes between 0 and 1. After it, the start flag is made up of 01111110. Then the feature sequence is made up by training sequence and the first two codes of start flag, where the length of feature sequence is N, N=26. Through the modulating by GMSK, the modulation signal of feature sequence is denoted by s(k) and the skewness of s(k) is named as J. Then J is defined as(7)J=Esk-Eskvarsk3,where varsk is variance of the signal and Es(k) is average.According to the definition of (7), the skewness value of feature sequence modulation signal is 6.9244×10-6. Similarly, skewness of 100 groups of modulation signal of AIS information sequence is calculated. Then get the mean of them to be 1.1669×10-4. Based on the comparison of two values, it is clear that the symmetry of modulation signal of feature sequence is much stronger than the information sequence. At the same time, three-order cumulant of symmetric distribution is 0, and the more close to the symmetric distribution the signal is, the smaller third-order cumulants will be. So, third-order cumulant can achieve accurate time delay estimation by different symmetry between the modulation signal of feature sequence and information sequence. Meanwhile it can also restrain the influence of Gaussian noise.


### 3.2. Principle of Time Delay Estimation Algorithm

Assumeh1,h2,…,hn is n-dimensional random variable; its r order joint cumulant is denoted by Cr:(8)Cr=1jr∂Ψω1,ω2,…,ωn∂ω1r1∂ω2r2⋯∂ωnrnω1=ω2=⋯=ωn=0,where the order r=r1+r2+⋯+rn, and Ψ(ω1,ω2,…,ωn) is described by(9)Ψω1,ω2,…,ωn=ln⁡Eejω1h1+ω2h2+⋯+ωnhn.Preset the receipt signal:(10)yt=xt-τ+nt,where x(t) is the sending signal and n(t) is the noise. τ is time delay. Assume that τd is normalized time delay; then τd=τ/Tb.After discretization, the receipt signal is shown as follows:(11)yk=xk-D+nk,where D is the discrete time delay.As is known to all, AIS signal can be approximated as stationary random signal. So the three-order cumulant ofy(k) can be expressed by the joint one- of three-dimensional random variable y(k),y(k-λ1),y(k-λ2) and denoted as C3y(λ1,λ2). If joint three-order cumulant is represented as symbol cum(·), then (12)C3yλ1,λ2=cumyk,yk+λ1,yk+λ2.In a similar way, the cumulant of sending signal can be noted as follows: (13)C3xλ1,λ2=cumxk,xk+λ1,xk+λ2.When the time delayτ is an integer multiple of symbol period, y(k) is the sampled signal of y(t). Sample period is T, and the total of sampling point in each symbol period is Nb, where Nb=Tb/T. Then it is obvious that the time delay D is an integer multiple of Nb. Now according to the length of the modulation signal of the feature sequence, gradually slide and intercept the corresponding part of y(k). Then define the delay measurement function in accordance with three-order cumulant. Finally, the time delay is estimated by minimization.Sliding valued is given as follows: d∈0,1,…,M, where M=τm·Nb and τm is the largest normalized time delay of AIS with its value being an integer and larger than τd.The truncation signal can be described by(14)ydk=yk+d,k=0,1,…,Nt,where Nt=N·Nb.Set time delay measurement functionP(d):(15)Pd=C3ydλ1,λ2.Let λ1=0, λ2=0. According to (14) and the character of three-order cumulant, (15) can be expanded as follows:(16)Pd=C3xd0,0+C3nd0,0=cumxdk-D,xdk-D,xdk-D+cumndk,ndk,ndk,where xd(k)=x(k+d), nd(k)=n(k+d), k=1,2,…,Nt.Ifnk is Gaussian noise, the value of three-order cumulant of n(k) is 0; if n(k) is non-Gaussian and correlative noise with high SNR, just ignore the influence of noise. Then P(d) can be simplified as follows:(17)Pd=C3xd0,0.From (17), when xd(k) represents the modulation signal of the feature sequence, P(d) obtains minimum value. So, assume (18)D^=argmindPd.Then the time delay is estimated as follows: (19)τ^=D^T.When the normalized time delay τd is a decimal, Nb should satisfies the following:(20)Nb=ξ·10υ,where υ is the order of magnitude of τd and ξ is an integer larger than zero.From (20), this algorithm relies too much on the sampling frequency and therefore fits the sample signal with cubic spline interpolation algorithm. Assume there are Ns interpolating points in each sample period T; the interval of interpolation is Ts, where Ts=T/Ns. Then Nb just needs to satisfy the following:(21)Nb×Ns=ξ·10υ.Same as the previous estimate algorithm in this paper, if the normalized time delay is a decimal, the time delay can be estimated by(22)τ^=D^Ts.


## 3.1. Symmetry Analysis of AIS Signal

The symmetry of signal can be expressed by the skewness [12]. If the skewness is greater than zero, positive deviation value is larger and probability density function drags the long tail on the right. To the contrary, negative deviation value is larger, the long tail is on the left. The more close to 0 the value of skewness is, the more close to the symmetrical distribution the signal will be. If signal obeys normal distribution, the skewness is equal to the three-order center distance where value is 0.From Table1, training sequence of AIS signal is composed of 24 bits alternate codes between 0 and 1. After it, the start flag is made up of 01111110. Then the feature sequence is made up by training sequence and the first two codes of start flag, where the length of feature sequence is N, N=26. Through the modulating by GMSK, the modulation signal of feature sequence is denoted by s(k) and the skewness of s(k) is named as J. Then J is defined as(7)J=Esk-Eskvarsk3,where varsk is variance of the signal and Es(k) is average.According to the definition of (7), the skewness value of feature sequence modulation signal is 6.9244×10-6. Similarly, skewness of 100 groups of modulation signal of AIS information sequence is calculated. Then get the mean of them to be 1.1669×10-4. Based on the comparison of two values, it is clear that the symmetry of modulation signal of feature sequence is much stronger than the information sequence. At the same time, three-order cumulant of symmetric distribution is 0, and the more close to the symmetric distribution the signal is, the smaller third-order cumulants will be. So, third-order cumulant can achieve accurate time delay estimation by different symmetry between the modulation signal of feature sequence and information sequence. Meanwhile it can also restrain the influence of Gaussian noise.


## 3.2. Principle of Time Delay Estimation Algorithm

Assumeh1,h2,…,hn is n-dimensional random variable; its r order joint cumulant is denoted by Cr:(8)Cr=1jr∂Ψω1,ω2,…,ωn∂ω1r1∂ω2r2⋯∂ωnrnω1=ω2=⋯=ωn=0,where the order r=r1+r2+⋯+rn, and Ψ(ω1,ω2,…,ωn) is described by(9)Ψω1,ω2,…,ωn=ln⁡Eejω1h1+ω2h2+⋯+ωnhn.Preset the receipt signal:(10)yt=xt-τ+nt,where x(t) is the sending signal and n(t) is the noise. τ is time delay. Assume that τd is normalized time delay; then τd=τ/Tb.After discretization, the receipt signal is shown as follows:(11)yk=xk-D+nk,where D is the discrete time delay.As is known to all, AIS signal can be approximated as stationary random signal. So the three-order cumulant ofy(k) can be expressed by the joint one- of three-dimensional random variable y(k),y(k-λ1),y(k-λ2) and denoted as C3y(λ1,λ2). If joint three-order cumulant is represented as symbol cum(·), then (12)C3yλ1,λ2=cumyk,yk+λ1,yk+λ2.In a similar way, the cumulant of sending signal can be noted as follows: (13)C3xλ1,λ2=cumxk,xk+λ1,xk+λ2.When the time delayτ is an integer multiple of symbol period, y(k) is the sampled signal of y(t). Sample period is T, and the total of sampling point in each symbol period is Nb, where Nb=Tb/T. Then it is obvious that the time delay D is an integer multiple of Nb. Now according to the length of the modulation signal of the feature sequence, gradually slide and intercept the corresponding part of y(k). Then define the delay measurement function in accordance with three-order cumulant. Finally, the time delay is estimated by minimization.Sliding valued is given as follows: d∈0,1,…,M, where M=τm·Nb and τm is the largest normalized time delay of AIS with its value being an integer and larger than τd.The truncation signal can be described by(14)ydk=yk+d,k=0,1,…,Nt,where Nt=N·Nb.Set time delay measurement functionP(d):(15)Pd=C3ydλ1,λ2.Let λ1=0, λ2=0. According to (14) and the character of three-order cumulant, (15) can be expanded as follows:(16)Pd=C3xd0,0+C3nd0,0=cumxdk-D,xdk-D,xdk-D+cumndk,ndk,ndk,where xd(k)=x(k+d), nd(k)=n(k+d), k=1,2,…,Nt.Ifnk is Gaussian noise, the value of three-order cumulant of n(k) is 0; if n(k) is non-Gaussian and correlative noise with high SNR, just ignore the influence of noise. Then P(d) can be simplified as follows:(17)Pd=C3xd0,0.From (17), when xd(k) represents the modulation signal of the feature sequence, P(d) obtains minimum value. So, assume (18)D^=argmindPd.Then the time delay is estimated as follows: (19)τ^=D^T.When the normalized time delay τd is a decimal, Nb should satisfies the following:(20)Nb=ξ·10υ,where υ is the order of magnitude of τd and ξ is an integer larger than zero.From (20), this algorithm relies too much on the sampling frequency and therefore fits the sample signal with cubic spline interpolation algorithm. Assume there are Ns interpolating points in each sample period T; the interval of interpolation is Ts, where Ts=T/Ns. Then Nb just needs to satisfy the following:(21)Nb×Ns=ξ·10υ.Same as the previous estimate algorithm in this paper, if the normalized time delay is a decimal, the time delay can be estimated by(22)τ^=D^Ts.


## 4. Simulation Results

Simulation parameter setting is shown in Table2. All the simulation parameters are set according to AIS protocol. There is an assumption that the transmitter and receiver are UTC synchronization.Table 2
Simulation parameter.
System parameter settings Symbol rate R = 9600 bit/s Symbol period T b = 1 / R Modulation system GMSK Normalized maximum time delay 12 T b  Time delay estimation under Gaussian noise  Case 1: integral normalized time delay Case 2: decimal normalized time delay  Time delay 2 T b, 4Tb, 8Tb Time delay 0.221 T b, 1.414Tb, 8.331Tb Sample period (T) T b / 10 Sample period (T) T b / 10 Interpolation period (Ts) T / 100  Time delay estimation under non-Gaussian and correlative noise  Case 3: integral normalized time delay Case 4: decimal normalized time delay  Time delay 2 T b, 4Tb, 8Tb Time delay 0.221 T b, 1.414Tb, 8.331Tb Sample period (T) T b / 10 Sample period (T) T b / 10 Interpolation period (Ts) T / 100 Interpolation period (Ts) T / 100Normalization in this paper is achieved withTb. There are four cases of simulation in this table. In Case 1, because time delay is an integral multiple of the symbol period, the signal does not need to be interpolated. But in Case 2/3/4, the interpolation can make estimation more accurate. The simulation results are as follows.(1) Time Delay Estimation under Gaussian NoiseCase 1. When normalized time delay τd is an integer, simulation results are shown in Figures 1 and 2. In the simulation, frequency offset is set to be zero.Figure 1
Normalized time delay and its estimation with different SNR.Figure 2
Standard deviation of normalized time delay estimation with different SNR.By the graph under different SNR (Signal-to-Noise Ratio), this algorithm can get completely accurate estimation. The estimation performance is not affected by the value of SNR or time delay.Case 2. When normalized time delay τd is a decimal, set frequency offset to be zero, too. The simulation results are shown in Figures 3 and 4. From the graph, when the number of interpolation points is large enough, the signal estimation performance is the same as the normalized time delay being an integer. Besides it is also not affected by the value of time delay or SNR.Figure 3
Normalized time delay and its estimation with different SNR.Figure 4
Standard deviation of normalized time delay estimation with different SNR.In Figure5, the time delay estimation proposed in this paper is compared with those presented in [3, 4]. For the sake of simplicity, let “1-bit-difference algorithm” denote the algorithm from [3] and “M&M algorithm” denote the one from [4]. According to the fact that the range of estimation of algorithm from literature [4] is [-0.5Tb,0.5Tb], let τ=0.375Tb. From the graph, the estimated performance in this paper is much better than others, especially under the lower SNR.Figure 5
Comparison among different algorithms.From Figure6, different SNR do not affect the performance of time delay estimation with the same frequency offset. But the performances will drop rapidly with the increase of frequency deviation. As the frequency offset is 5 Hz, normalized MSE is larger than 10-3. Therefore, this algorithm needs higher frequency deviation correction accuracy.Figure 6
Influence of frequency offset.(2) Time Delay Estimation under Non-Gaussian and Correlative Noise. In this subsection, the noise is set as follows:(23)nk=xk×wk,where w(k) is Gaussian noise. The relationship between intensity κ of Gaussian noise and SNR is shown in Table 3.Table 3
Noise Intensity and SNR.
κ −30 −29 −28 −27 −26 −25 −24 −23 −22 −21 SNR 60.03 57.95 56.03 53.99 52.07 50.02 47.99 46.08 43.91 42.00 κ −20 −19 −18 −17 −16 −15 −14 −13 −12 −11 SNR 40.03 38.00 35.95 34.01 31.92 30.00 27.93 26.09 23.86 22.01 κ −10 −9 −8 −7 −6 −5 −4 −3 −2 −1 SNR 20.03 18.00 16.13 14.01 11.98 10.06 8.02 6.02 3.96 1.97 κ 0 1 2 3 4 5 6 7 8 9 SNR −0.04 −1.91 −3.98 −5.90 −7.99 −10.08 −11.97 −13.99 −15.82 −18.00By Table3, the SNR is decreasing with the increase of the intensity of Gaussian noise.Because the noise is not additive Gaussian one and it is related to the signal, the three-order cumulant cannot completely suppress the influence of noise to the signal symmetry. The frequency offset is set to be zero.Case 3. When normalized time delay τd is an integer, simulation results are shown in Figure 7.Figure 7
Normalized time delay estimation MSE with integral time delay.Case 4. When normalized time delay τd is a decimal, the simulation results are shown in Figure 8.Figure 8
Normalized time delay estimation MSE with decimal time delay.From Figures7 and 8, the algorithm has obvious noise threshold at 0 dB, but when SNR is larger than 0 dB, the normalized time delay estimation can still achieve 10-5.


## 5. Conclusion

In this paper, under Gaussian noise, the algorithm can accurately estimate the time delay. Its performance is more accurate than the 1-bit-difference algorithm and M&M algorithm. It is nearly not affected by the SNR, even if SNR is −30 dB. Furthermore when the noise is non-Gaussian and correlative, the normalized time delay estimation MSE can achieve10-5 with SNR being larger than 0 dB. These two are the main contributions of this paper. Besides the algorithm has the same performance for all signals with similar characteristics and is not limited to AIS signals. However, this algorithm needs to know the order of magnitude of the delay in the received signal, so that we can set the Sample Frequency and the Interpolation Frequency. Otherwise the algorithm cannot get the perfect results.



---

*Source: 1349702-2018-05-10.xml*