# Improved ASM-TER Training Sequence Detection and Fine Doppler Frequency Estimation Methods from a Satellite

Authors: Peixin Zhang; Jianxin Wang; Peng Ren; Shushu Yang; Haiwei Song
Journal: Journal of Sensors
 (2020)

---

## Abstract

To detect terrestrial application-specific messages (ASM-TER) signals from a satellite, a novel detection method based on the fast computation of the cross ambiguity function is proposed in this paper. The classic cross ambiguity function’s computational burden is heavy, and we transform the classic cross ambiguity function to a frequency domain version to reduce the computational complexity according to Parseval’s theorem. The computationally efficient sliding discrete Fourier transform (SDFT) is utilized to calculate the frequency spectrum of the windowed received signal, from which the Doppler frequency could be estimated coarsely. Those subbands around the Doppler frequency are selected to calculate the ambiguity function for reducing the computational complexity. Furthermore, two local sequences with half length of the training sequence are utilized to acquire a better Doppler frequency tolerance; thus, the frequency search step is increased and the computational complexity could be further reduced. Once an ASM-TER signal is detected by the proposed algorithm, a fine Doppler frequency estimation could be obtained easily from the correlation peaks of the two local sequences. Simulation results show that the proposed algorithm shares almost the same performance with the classic cross ambiguity function-based method, and the computational complexity is greatly reduced. Simulation results also show that the proposed algorithm is more resistant to cochannel interference (CCI) than the differential correlation (DC) algorithm, and the performance of fine Doppler frequency estimation is close to that of the Cramér–Rao lower bound (CRLB).


---

## Body

## 1. Introduction

The automatic identification system (AIS) [1] is well recognized and accepted as an important tool for safety of navigation [2]. As the demand for maritime very high frequency (VHF) data communications increases, AIS has become heavily used for maritime safety, maritime situational awareness, and port security [3]. Therefore, the VHF data exchange system (VDES), which integrates the functions of VHF data exchange (VDE), application-specific messages (ASM) [4], and AIS, is developed to extend the existing AIS standard by the International Telecommunication Union (ITU) [5, 6]. In general, VDES has three segments: terrestrial segment, satellite segment for uplink, and satellite segment for downlink. This paper is dedicated to detecting terrestrial ASM (ASM-TER) signals from a satellite.Generally, the key point of signal detection is to detect the training sequence. The training sequence of ASM-TER is mainly composed of a double Barker sequence [3]. The Barker sequence is known for its excellent autocorrelation property [7] which holds only for small Doppler frequency [8]. Since the ASM-TER is designed for ship-to-ship and ship-to-shore communications, the assumption of small Doppler frequency is satisfied under such scenarios. However, when receiving ASM-TER signals from a satellite, two main problems arise: nonnegligible Doppler frequency and cochannel interference (CCI).Although traditional energy detection methods are not sensitive to Doppler frequency, it does not utilize Barker sequence’s excellent autocorrelation property which provides a significant signal-to-noise ratio (SNR) improvement. Therefore, energy detection methods are not discussed in this paper. Considering the excellent autocorrelation property of the Barker sequence, a traditional cross correlation method is the best detection method when there is no Doppler frequency. However, the performance degrades rapidly as the Doppler frequency increases [8]. The differential correlation (DC) [9] is a noncoherent method that is insensitive to Doppler frequency, whereas it is susceptive to CCI. What is more, the differential operation leads to a great performance loss compared with coherent methods, and it also breaks the excellent autocorrelation property of the Barker sequence. A cross ambiguity function-based method is not susceptible to Doppler frequency and CCI. It divides the frequency search range (the interval where the possible Doppler frequency lies) into several subbands, and each subband is shifted to the baseband. Afterwards, the cross correlation method is utilized in each subband, and a peak would occur where the Doppler frequency is compensated within an acceptable margin of error [10]. Due to the multiband frequency compensation, the cross ambiguity function is not sensitive to Doppler frequency. Similarly, it is not sensitive to CCI since the desired signal and the CCI usually have different Doppler frequencies and would be separated in different subbands. Although the cross ambiguity function-based method has so many advantages, its computational complexity is quite intolerable for real-time processing due to its two-dimensional search in both time and frequency domains. Some fast algorithms [11–13] are developed to reduce the computational complexity of the cross ambiguity function. The method in [11] utilizes the fast Fourier transform (FFT) to reduce the computational complexity, and the preweighted zoom-FFT (ZFFT) method in [12, 13] utilizes ZFFT to further reduce the computational complexity of an FFT-based method, but they only work when the oversampling ratio is large.To detect ASM-TER signals from a satellite with excellent performance and acceptable computational complexity, this paper proposes a computational complexity reduced algorithm based on the cross ambiguity function. The idea behind it is to reduce the frequency search range and increase the frequency search step for evaluating the cross ambiguity function. To reduce the frequency search range, the classic cross ambiguity function is transformed to a frequency domain version, in which the frequency spectra of the windowed received signal and the local sequence are used. The frequency spectrum of the windowed received signal is also used to coarsely estimate the Doppler frequency, and the estimation formula is derived. To increase the frequency search step, a short local sequence is required since the shorter local sequence leads to the better Doppler frequency tolerance. To this end, the training sequence is divided into two local sequences with one half-length. The two cross ambiguity functions are calculated separately and then are averaged to overcome the performance degradation. Furthermore, the fine Doppler frequency estimation algorithm is developed from the correlation peaks of the two local sequences; the performance of which is close to that of the Cramér–Rao lower bound (CRLB). It facilitates the carrier synchronization for the subsequent data demodulation.This paper is organized as follows. Section2 introduces the signal model. The classic cross ambiguity function and its shortcomings are introduced in Section 3. The proposed method in this paper is elaborated in Section 4. Section 5 shows the performance comparison and analysis. Some conclusions are drawn in Section 6.


## 2. Signal Model

According to the Recommendation ITU-R M.2092-0 [14], the modulation scheme of ASM-TER is π/4 Quadrature Phase Shift Keying (QPSK), so the received baseband ASM-TER signal could be expressed as
(1)xn=A∑nt=0Ns−1gn−ntsntej2πfdnTs+ϕ0+wn,where A is the amplitude of the received signal, fd is the Doppler frequency, Ts is the sampling interval, ϕ0 is the phase shift during propagation, wn is a complex-valued white Gaussian noise which is subject to N0,σ2 (σ2 is the variance of the noise), gn is the root mean square raised cosine roll-off filter defined in [14], Ns is the sample length of sn, and sn is the zero-padded QPSK symbol sequence:
(2)sn=ejϕn,n=ip,0,n≠ip,where p is the oversampling ratio, ϕnϕn∈0,π/4,2π/4,⋯,7π/4 is the modulated phase, and i∈ℕ.The ASM-TER has a certain packet format as shown in Figure1. This paper is dedicated to detecting ASM-TER signals, so other parts except the training sequence (syncword in Figure 1) are not introduced in detail. The training sequence of ASM-TER is a 27-symbol sequence composed of a 1 followed by a Barker13 sequence (1111100110101, noted as +Barker13) and an inverted Barker13 sequence (0000011001010, noted as -Barker13). In the training sequence, bit 1 maps to π/4 QPSK symbol 311, and 0 maps to π/4 QPSK symbol 000. The π/4 QPSK bit mapping is shown in Figure 2.Figure 1
Terrestrial application-specific messages (ASM-TER) packer format.Figure 2
ASM-TER bit mapping.It should be noted that the initial state of the alternatingπ/4 QPSK bit mapping is defined such that the first symbol of the training sequence is mapped to the constellation defined by green points 1+j/2,−1+j/2,−1−j/2,1−j/2; the next symbol is mapped to the constellation defined by purple points 1+0j,0+j,−1+0j,0−j; and so on [14].


## 3. Classic Cross Ambiguity Function

As mentioned above, the cross ambiguity function is an efficient method in detecting a deterministic local sequence with unknown Doppler frequency, and it can be expressed as(3)Cτ,γ=1ExτEy∑n=ττ+Ny−1xne−j2πfmin+γdfnTsy∗n−τ,in which τ is the delay (τ=0,1,⋯,Nx−Ny); Nx and Ny are the sample length of xn and yn, respectively (assuming Nx>Ny); xn is the received signal; yn is the deterministic local sequence; df is the frequency search step; fmin and fmax are the lower and upper limits of the frequency search range, respectively; γ is the frequency search index determined by the frequency search range fmin,fmax and frequency search step df (γ=0,1,⋯,M−1, M=fmax−fmin/df+1, · denotes ceiling operation); ∗ denotes conjugation operation; ∣·∣ denotes the absolute value operator; and Exτ and Ey are the energy of windowed xn and yn, respectively, i.e.,
(4)Exτ=∑n=ττ+Ny−1xnx∗n,Ey=∑n=0Ny−1yny∗n.It can be seen in Equation (3) that, in subband γ, the frequency fmin+γdf is shifted to 0 Hz. If the Doppler frequency is compensated within an acceptable margin of error in a subband, a peak would occur. Therefore, the cross ambiguity function is not sensitive to Doppler frequency. Similarly, if the desired signal and a CCI collide, the cross ambiguity function could separate them in different subbands when their Doppler frequencies are different. Thus, the cross ambiguity function is insensitive to CCI.Although the cross ambiguity function has so many advantages, the computational complexity is quite high. Unlike some other detection methods’ one-dimensional search in the time domain, the two-dimensional search of the cross ambiguity function in both time and frequency domains results in a high computational complexity. Therefore, the classic cross ambiguity function is not suitable for real-time processing.


## 4. The Proposed Algorithm

It can be seen from Equation (3) that the computational complexity of the cross ambiguity function mainly comes from the search for Doppler frequency, and the frequency search times depend on the frequency search range fmin,fmax and the frequency search step df. Both reducing the frequency search range and increasing the frequency search step can reduce the frequency search times. In this section, the proposed algorithm reduces the computational complexity of the cross ambiguity function in two aspects: one is reducing the frequency search range by estimating the Doppler frequency coarsely, and the other is increasing the frequency search step by utilizing two local sequences with half-length of the training sequence.


### 4.1. Computational Complexity Reduction by Reducing the Frequency Search Range

To reduce the frequency search range, we have to estimate the Doppler frequency of the received signal first. There are many accurate frequency estimation methods [15–17], but the computational burden is heavy. In this paper, we choose a computationally efficient method [18] to estimate the Doppler frequency coarsely. The coarsely estimated Doppler frequency at time instant τ could be expressed as
(5)fdc^τ=∑k=0Ny−1kPkτ∑k=0Ny−1Pkτdf+fmin,where Pkτ (k=0,1,⋯,Ny−1) is the k-th sample of the windowed received signal’s power spectrum at time instant τ. To further reduce the influence of noise when SNR is low, values of the power spectrum under a certain threshold are set to zero before calculating fdc^τ.Pkτ could be simply calculated by
(6)Pkτ=XkτXk∗τ,where Xkτ (k=0,1,⋯,Ny−1) is the k-th sample of the windowed received signal’s discrete Fourier transform (DFT), and it can be realized by the sliding DFT (SDFT) [19] which requires fewer computations than traditional methods. The k-th sample of the DFT can be calculated by
(7)Xkτ=ej2πk/NyXkτ−1+xτ−xτ−Ny.Once thek-th DFT sample at any time instant has been computed, the k-th DFT sample at all successive time instants can be computed recursively. This requires only a single complex multiplication for each sample [19].Similar to the DFT, the energy of the windowed received signal at time instantτ can also be calculated in a sliding way:
(8)Exτ=Exτ−1+xτx∗τ−xτ−Nyx∗τ−Ny.After coarsely estimating the Doppler frequency, the frequency search range could be reduced to a range centered atfdc^τ, and the width of the frequency search range is determined by the accuracy of the coarse Doppler frequency estimation. To evaluate the accuracy of the coarse Doppler frequency estimation, the simulated probability density function (PDF) of the coarse Doppler frequency estimation error fdc^τ−fd and an approximate Gaussian distribution are shown in Figure 3. In this simulation, the energy per bit to noise power spectral density ratio (Eb/N0) is set to 6 dB, and the approximate Gaussian distribution subjects to NEfdc^τ−fd,varfdc^τ−fd (where E· denotes the expectation operator implemented by calculating the average value and var· is the variance operator).Figure 3
Simulated probability density function (PDF) offdc^τ−fd.As can be seen from Figure3, the distribution of fdc^τ−fd can be approximately regarded as a Gaussian distribution. To notice that, the expectation of fdc^τ−fd is not 0. The coarse Doppler frequency estimation method measures the mass center of the power spectrum, and the mass center’s location in the frequency domain is considered the coarse Doppler frequency estimation fdc^τ. Theoretically, the mass center of the source signal’s power spectrum without noise indicates the Doppler frequency fd. However, the practical power spectrum of the received signal is the combination of source signal’s power spectrum and noise’s power spectrum. The practical power spectrum’s mass center can be regarded as a weighted average of the noise power spectrum’s mass center (0 Hz) and the source signal power spectrum’s mass center (fd), and the weight coefficients depend on the “mass” (power) of noise and source signals, which are all positive. As a result, Efdc^τ≠fd, and this method is not strictly an unbiased estimation. Hence, the reduced frequency search range is defined by root mean square error (RMSE) instead of variance, and it is set to fdc^τ−3δ,fdc^τ+3δ (δ is the RMSE of fdc^τ) to guarantee the detection of the true peak with a probability of about 99.7%. Correspondingly, such subbands with indexes within γmin,γmax (γmin=fdc^τ−3δ−fmin/df,γmax=fdc^τ+3δ−fmin/df, · denotes flooring operation) are calculated, and the computational complexity is reduced.


### 4.2. Further Computational Complexity Reduction by Increasing the Frequency Search Step

Another way to reduce the computational complexity is increasing the frequency search step. The frequency search step should be smaller than the Doppler frequency tolerance of the local sequence, and the Doppler frequency tolerance is inversely proportional to the length of the local sequence. Therefore, a shorter local sequence leads to fewer Doppler frequency search times. The impact of the local sequence’s length on the Doppler frequency tolerance is shown in Figure4.Figure 4
Doppler frequency tolerance of different local sequences.As shown in Figure4, the Doppler frequency tolerance of the +Barker13 sequence is about twice that of the whole training sequence. As a result, the frequency search step could be doubled; hence, the computational complexity will be approximately reduced by half.Since the training sequence of ASM-TER is mainly composed of a double Barker sequence, a single +Barker13 sequence could be used to detect the training sequence, and there should be two peaks which indicate the location of the two Barker13 sequences. However, due to theπ/4 QPSK mapping in ASM-TER, the magnitude of the second peak which indicates the location of the -Barker13 sequence will be only about 70% of the first one as shown in Figure 5.Figure 5
Cross correlation coefficient using a single +Barker13 sequence.What is more, compared with a 27-symbol local sequence, a single 13-symbol local sequence leads to a shorter window, and a shorter window results in the accuracy degradation of power spectrum estimation. In order to avoid such performance loss, this paper utilizes two sets of correlators with local sequences of the +Barker13 sequence and -Barker13 sequence, respectively. It should be noted that the -Barker13 set utilizes the windowed received signal at time instantτ, and the +Barker13 set utilizes the windowed received signal at time instant τ−NBK13 (NBK13 is the sample length of the -Barker13 sequence). As a result, Equation (6) is replaced by a smooth estimation, and the k-th sample of the smoothed power spectrum can be expressed as
(9)Pk′τ=XkτXk∗τ+Xkτ−NBK13Xk∗τ−NBK132,k=0,1,⋯,NBK13−1.Equation (6) utilizes one 27-symbol sequence, and Equation (9) utilizes two 13-symbol sequences. Hence, theoretically, the accuracies of Equations (6) and (9) are almost the same, as well as the search ranges. Although utilizing two shorter local sequences does not reduce the computational complexity directly, the shorter local sequences lead to larger Doppler frequency tolerance which is beneficial to reducing the Doppler frequency search times.


### 4.3. A Frequency Domain Version of the Cross Ambiguity Function

Since the DFT of the windowed received signal is obtained and the deterministic local sequence requires no extra computation, it comes naturally to calculate the cross ambiguity function in the frequency domain. According to Parseval’s theorem, the classic cross ambiguity function can be transformed to a frequency domain version:(10)Cτ,γ=∑n=ττ+Ny−1xne−j2πfmin+γdfnTsy∗n−τExτEy=n′=n−τ∑n′=0Ny−1xn′+τyn′ej2πfmin+γdfn′Ts∗ExτEy=∑k=0Ny−1∑n′=0Ny−1xn′+τe−j2πn′k/Ny∑n′=0Ny−1yn′ej2πfmin+γdfn′Tse−j2πn′k/Ny∗ExτEy=∑k=0Ny−1Fxn′+τF∗yn′ej2πfmin+γdfn′TsExτEy,γ=γmin,γmin+1,⋯,γmax,where F· denotes the DFT, Fxn′+τ is the frequency spectrum of the windowed received signal at time instant τ, and F∗yn′ej2πfmin+γdfn′Ts is the conjugation of the frequency-shifted DFT of local sequence yn′. F∗yn′ej2πfmin+γdfn′Ts can be calculated and stored in advance and requires no computation during detection, as well as Ey.The outputs of the two correlator sets in corresponding subbands are averaged to obtain the final output; then, a peak over a certain threshold indicates the existence of an ASM-TER signal. A block diagram of the training sequence detection is shown in Figure6.Figure 6
Block diagram of the training sequence detection.


### 4.4. Computational Complexity Analysis

Given the sample length of the training sequenceNts, the comparison of computational complexity is carried out among direct calculation of the cross ambiguity function, preweighted ZFFT cross ambiguity function [12], and the proposed algorithm. Because complex multiplication is the major burden in digital signal processing, the number of complex multiplications (NCM) is used to measure the computational complexity. The computational complexities of these three algorithms in each window are shown in Table 1.Table 1
Computational complexity comparison.
AlgorithmNCMDirect calculation2NtsMPreweighted ZFFTMNh+M/2log2MThe proposed algorithm2γmax−γmin+3NBK13+1In Table1, Nh is the sample length of segmented data in the preweighted ZFFT method, and the segmentation is based on the assumption that the data could be downsampled without aliasing. If the assumption cannot be satisfied, Nh equals Nts. Assuming that the oversampling ratio p is 4, the number of subbands M without performance loss for the direct calculation of the cross ambiguity function using the whole training sequence is 64; then, Nh=Nts=27×p=108 and NBK13=13×p=52. As can be seen from Figure 4, the Doppler frequency tolerance of the +Barker13 sequence is about half that of the whole training sequence, so the maximum number of subbands when using the proposed algorithm is 32. In such conditions, the NCM of direct calculation, preweighted ZFFT, and the proposed algorithm are 13824, 7104, and 3537, respectively. If the number of subbands in the proposed algorithm is reduced to 1/2 and 1/4 of the maximum number, the NCM of the proposed algorithm is reduced to 1873 and 1041, respectively. Obviously, the proposed algorithm is more computationally efficient than direct calculation and preweighted ZFFT even when the subband number is not reduced, and the NCM of the proposed algorithm keeps decreasing as the subband number decreases.


### 4.5. Fine Doppler Frequency Estimation for Subsequent Data Demodulation

Apart from reducing the computational complexity by increasing the frequency search step, there is another advantage of utilizing two local sequences. After an ASM-TER training sequence is detected using the proposed algorithm, the two peaks of the two correlator sets could be used to finely estimate the Doppler frequency easily. The fine Doppler frequency estimation is based on the phase difference of the two correlator sets’ peak values. Assuming that the peaks occur in subbandγp, the compensated frequency in subband γp is fdp, and the time instant at the beginning of the +Barker13 sequence is 0; then, the peak value of the +Barker13 correlator set’s output without noise is
(11)Vp+=∑n=0NBK13−1ej2πfdnTs∑nt=0NBK13−1gn−nts+nt×e−j2πfdpnTs∑nt=0NBK13−1gn−nts+∗nt=∑n=0NBK13−1∑nt=0NBK13−1gn−nts+nt2ej2πfd−fdpnTs,in which s+n is the zero-padded symbol sequence of the +Barker13 sequence, and the peak value of the -Barker13 correlator set’s output without noise is
(12)Vp−=∑n=NBK132NBK13−1ej2πfdnTs∑nt=0NBK13−1gn−nts−nt×e−j2πfdpn−NBK13Ts∑nt=0NBK13−1gn−nts−∗nt=n′=n−NBK13ej2πfdNBK13Ts∑n′=0NBK13−1∑nt=0NBK13−1gn′−nts−nt2ej2πfd−fdpn′Ts,where s−n is the zero-padded symbol sequence of the -Barker13 sequence. Due to the symmetry of gn and the autocorrelation property of the +/-Barker13 sequence, it is easy to prove that Equation (13) holds for any n∈0,1,⋯,NBK13−1:
(13)∑nt=0NBK13−1gn−nts+nt2=∑nt=0NBK13−1gn−nts−nt2.From Equations (11), (12), and (13), a certain relationship between Vp+ and Vp− could be found:
(14)Vp−Vp+=ej2πfdNBK13Ts,and a fine estimation of the Doppler frequency could be obtained according to Equation (14). However, to avoid ambiguity, the fine Doppler frequency estimation is calculated by
(15)fdf^=fdp+∠Vp−/Vp+e−j2πfdpNBK13Ts2πNBK13Ts,where ∠· denotes the phase.


## 4.1. Computational Complexity Reduction by Reducing the Frequency Search Range

To reduce the frequency search range, we have to estimate the Doppler frequency of the received signal first. There are many accurate frequency estimation methods [15–17], but the computational burden is heavy. In this paper, we choose a computationally efficient method [18] to estimate the Doppler frequency coarsely. The coarsely estimated Doppler frequency at time instant τ could be expressed as
(5)fdc^τ=∑k=0Ny−1kPkτ∑k=0Ny−1Pkτdf+fmin,where Pkτ (k=0,1,⋯,Ny−1) is the k-th sample of the windowed received signal’s power spectrum at time instant τ. To further reduce the influence of noise when SNR is low, values of the power spectrum under a certain threshold are set to zero before calculating fdc^τ.Pkτ could be simply calculated by
(6)Pkτ=XkτXk∗τ,where Xkτ (k=0,1,⋯,Ny−1) is the k-th sample of the windowed received signal’s discrete Fourier transform (DFT), and it can be realized by the sliding DFT (SDFT) [19] which requires fewer computations than traditional methods. The k-th sample of the DFT can be calculated by
(7)Xkτ=ej2πk/NyXkτ−1+xτ−xτ−Ny.Once thek-th DFT sample at any time instant has been computed, the k-th DFT sample at all successive time instants can be computed recursively. This requires only a single complex multiplication for each sample [19].Similar to the DFT, the energy of the windowed received signal at time instantτ can also be calculated in a sliding way:
(8)Exτ=Exτ−1+xτx∗τ−xτ−Nyx∗τ−Ny.After coarsely estimating the Doppler frequency, the frequency search range could be reduced to a range centered atfdc^τ, and the width of the frequency search range is determined by the accuracy of the coarse Doppler frequency estimation. To evaluate the accuracy of the coarse Doppler frequency estimation, the simulated probability density function (PDF) of the coarse Doppler frequency estimation error fdc^τ−fd and an approximate Gaussian distribution are shown in Figure 3. In this simulation, the energy per bit to noise power spectral density ratio (Eb/N0) is set to 6 dB, and the approximate Gaussian distribution subjects to NEfdc^τ−fd,varfdc^τ−fd (where E· denotes the expectation operator implemented by calculating the average value and var· is the variance operator).Figure 3
Simulated probability density function (PDF) offdc^τ−fd.As can be seen from Figure3, the distribution of fdc^τ−fd can be approximately regarded as a Gaussian distribution. To notice that, the expectation of fdc^τ−fd is not 0. The coarse Doppler frequency estimation method measures the mass center of the power spectrum, and the mass center’s location in the frequency domain is considered the coarse Doppler frequency estimation fdc^τ. Theoretically, the mass center of the source signal’s power spectrum without noise indicates the Doppler frequency fd. However, the practical power spectrum of the received signal is the combination of source signal’s power spectrum and noise’s power spectrum. The practical power spectrum’s mass center can be regarded as a weighted average of the noise power spectrum’s mass center (0 Hz) and the source signal power spectrum’s mass center (fd), and the weight coefficients depend on the “mass” (power) of noise and source signals, which are all positive. As a result, Efdc^τ≠fd, and this method is not strictly an unbiased estimation. Hence, the reduced frequency search range is defined by root mean square error (RMSE) instead of variance, and it is set to fdc^τ−3δ,fdc^τ+3δ (δ is the RMSE of fdc^τ) to guarantee the detection of the true peak with a probability of about 99.7%. Correspondingly, such subbands with indexes within γmin,γmax (γmin=fdc^τ−3δ−fmin/df,γmax=fdc^τ+3δ−fmin/df, · denotes flooring operation) are calculated, and the computational complexity is reduced.


## 4.2. Further Computational Complexity Reduction by Increasing the Frequency Search Step

Another way to reduce the computational complexity is increasing the frequency search step. The frequency search step should be smaller than the Doppler frequency tolerance of the local sequence, and the Doppler frequency tolerance is inversely proportional to the length of the local sequence. Therefore, a shorter local sequence leads to fewer Doppler frequency search times. The impact of the local sequence’s length on the Doppler frequency tolerance is shown in Figure4.Figure 4
Doppler frequency tolerance of different local sequences.As shown in Figure4, the Doppler frequency tolerance of the +Barker13 sequence is about twice that of the whole training sequence. As a result, the frequency search step could be doubled; hence, the computational complexity will be approximately reduced by half.Since the training sequence of ASM-TER is mainly composed of a double Barker sequence, a single +Barker13 sequence could be used to detect the training sequence, and there should be two peaks which indicate the location of the two Barker13 sequences. However, due to theπ/4 QPSK mapping in ASM-TER, the magnitude of the second peak which indicates the location of the -Barker13 sequence will be only about 70% of the first one as shown in Figure 5.Figure 5
Cross correlation coefficient using a single +Barker13 sequence.What is more, compared with a 27-symbol local sequence, a single 13-symbol local sequence leads to a shorter window, and a shorter window results in the accuracy degradation of power spectrum estimation. In order to avoid such performance loss, this paper utilizes two sets of correlators with local sequences of the +Barker13 sequence and -Barker13 sequence, respectively. It should be noted that the -Barker13 set utilizes the windowed received signal at time instantτ, and the +Barker13 set utilizes the windowed received signal at time instant τ−NBK13 (NBK13 is the sample length of the -Barker13 sequence). As a result, Equation (6) is replaced by a smooth estimation, and the k-th sample of the smoothed power spectrum can be expressed as
(9)Pk′τ=XkτXk∗τ+Xkτ−NBK13Xk∗τ−NBK132,k=0,1,⋯,NBK13−1.Equation (6) utilizes one 27-symbol sequence, and Equation (9) utilizes two 13-symbol sequences. Hence, theoretically, the accuracies of Equations (6) and (9) are almost the same, as well as the search ranges. Although utilizing two shorter local sequences does not reduce the computational complexity directly, the shorter local sequences lead to larger Doppler frequency tolerance which is beneficial to reducing the Doppler frequency search times.


## 4.3. A Frequency Domain Version of the Cross Ambiguity Function

Since the DFT of the windowed received signal is obtained and the deterministic local sequence requires no extra computation, it comes naturally to calculate the cross ambiguity function in the frequency domain. According to Parseval’s theorem, the classic cross ambiguity function can be transformed to a frequency domain version:(10)Cτ,γ=∑n=ττ+Ny−1xne−j2πfmin+γdfnTsy∗n−τExτEy=n′=n−τ∑n′=0Ny−1xn′+τyn′ej2πfmin+γdfn′Ts∗ExτEy=∑k=0Ny−1∑n′=0Ny−1xn′+τe−j2πn′k/Ny∑n′=0Ny−1yn′ej2πfmin+γdfn′Tse−j2πn′k/Ny∗ExτEy=∑k=0Ny−1Fxn′+τF∗yn′ej2πfmin+γdfn′TsExτEy,γ=γmin,γmin+1,⋯,γmax,where F· denotes the DFT, Fxn′+τ is the frequency spectrum of the windowed received signal at time instant τ, and F∗yn′ej2πfmin+γdfn′Ts is the conjugation of the frequency-shifted DFT of local sequence yn′. F∗yn′ej2πfmin+γdfn′Ts can be calculated and stored in advance and requires no computation during detection, as well as Ey.The outputs of the two correlator sets in corresponding subbands are averaged to obtain the final output; then, a peak over a certain threshold indicates the existence of an ASM-TER signal. A block diagram of the training sequence detection is shown in Figure6.Figure 6
Block diagram of the training sequence detection.


## 4.4. Computational Complexity Analysis

Given the sample length of the training sequenceNts, the comparison of computational complexity is carried out among direct calculation of the cross ambiguity function, preweighted ZFFT cross ambiguity function [12], and the proposed algorithm. Because complex multiplication is the major burden in digital signal processing, the number of complex multiplications (NCM) is used to measure the computational complexity. The computational complexities of these three algorithms in each window are shown in Table 1.Table 1
Computational complexity comparison.
AlgorithmNCMDirect calculation2NtsMPreweighted ZFFTMNh+M/2log2MThe proposed algorithm2γmax−γmin+3NBK13+1In Table1, Nh is the sample length of segmented data in the preweighted ZFFT method, and the segmentation is based on the assumption that the data could be downsampled without aliasing. If the assumption cannot be satisfied, Nh equals Nts. Assuming that the oversampling ratio p is 4, the number of subbands M without performance loss for the direct calculation of the cross ambiguity function using the whole training sequence is 64; then, Nh=Nts=27×p=108 and NBK13=13×p=52. As can be seen from Figure 4, the Doppler frequency tolerance of the +Barker13 sequence is about half that of the whole training sequence, so the maximum number of subbands when using the proposed algorithm is 32. In such conditions, the NCM of direct calculation, preweighted ZFFT, and the proposed algorithm are 13824, 7104, and 3537, respectively. If the number of subbands in the proposed algorithm is reduced to 1/2 and 1/4 of the maximum number, the NCM of the proposed algorithm is reduced to 1873 and 1041, respectively. Obviously, the proposed algorithm is more computationally efficient than direct calculation and preweighted ZFFT even when the subband number is not reduced, and the NCM of the proposed algorithm keeps decreasing as the subband number decreases.


## 4.5. Fine Doppler Frequency Estimation for Subsequent Data Demodulation

Apart from reducing the computational complexity by increasing the frequency search step, there is another advantage of utilizing two local sequences. After an ASM-TER training sequence is detected using the proposed algorithm, the two peaks of the two correlator sets could be used to finely estimate the Doppler frequency easily. The fine Doppler frequency estimation is based on the phase difference of the two correlator sets’ peak values. Assuming that the peaks occur in subbandγp, the compensated frequency in subband γp is fdp, and the time instant at the beginning of the +Barker13 sequence is 0; then, the peak value of the +Barker13 correlator set’s output without noise is
(11)Vp+=∑n=0NBK13−1ej2πfdnTs∑nt=0NBK13−1gn−nts+nt×e−j2πfdpnTs∑nt=0NBK13−1gn−nts+∗nt=∑n=0NBK13−1∑nt=0NBK13−1gn−nts+nt2ej2πfd−fdpnTs,in which s+n is the zero-padded symbol sequence of the +Barker13 sequence, and the peak value of the -Barker13 correlator set’s output without noise is
(12)Vp−=∑n=NBK132NBK13−1ej2πfdnTs∑nt=0NBK13−1gn−nts−nt×e−j2πfdpn−NBK13Ts∑nt=0NBK13−1gn−nts−∗nt=n′=n−NBK13ej2πfdNBK13Ts∑n′=0NBK13−1∑nt=0NBK13−1gn′−nts−nt2ej2πfd−fdpn′Ts,where s−n is the zero-padded symbol sequence of the -Barker13 sequence. Due to the symmetry of gn and the autocorrelation property of the +/-Barker13 sequence, it is easy to prove that Equation (13) holds for any n∈0,1,⋯,NBK13−1:
(13)∑nt=0NBK13−1gn−nts+nt2=∑nt=0NBK13−1gn−nts−nt2.From Equations (11), (12), and (13), a certain relationship between Vp+ and Vp− could be found:
(14)Vp−Vp+=ej2πfdNBK13Ts,and a fine estimation of the Doppler frequency could be obtained according to Equation (14). However, to avoid ambiguity, the fine Doppler frequency estimation is calculated by
(15)fdf^=fdp+∠Vp−/Vp+e−j2πfdpNBK13Ts2πNBK13Ts,where ∠· denotes the phase.


## 5. Simulation and Analysis

In this section, the coarse Doppler frequency estimation performance is shown by simulation firstly, and the performance of the DC, direct calculation of the cross ambiguity function (noted as Ambg), and the proposed algorithm are compared by simulations. The performance of fine Doppler frequency estimation is shown at last. Since the preweighted ZFFT method is a modified version of the cross ambiguity function with less computational complexity, the detection performance of the preweighted ZFFT should be exactly the same as that of the Ambg, so the performance of the preweighted ZFFT method is not compared.


### 5.1. Coarse Doppler Frequency Estimation Performance

When receiving ASM-TER signals from a satellite, the maximum absolute value of Doppler frequency is about 4 kHz (fmax=4kHz, fmin=−4kHz), and the phase offset is uniformly distributed in −π,π. The oversampling ratio p is set to 4, and the Eb/N0 varies from 0 to 15 dB. The coarse Doppler frequency estimation is simulated 1×105 times for each Eb/N0. The RMSE performance of the coarse Doppler frequency estimation is shown in Figure 7.Figure 7
Root mean square error (RMSE) performance of the coarse Doppler frequency estimation.As can be seen from Figure7, when Eb/N0 is 3 dB, RMSE of the coarse Doppler frequency estimation δ reaches 650 Hz and 3δ reaches 1950 Hz. As shown in Figure 3, the distribution of fdc^n−fd can be approximately regarded as a Gaussian distribution, so the existence of the true peak in fdc^n−1950,fdc^n+1950Hz can be guaranteed with a probability of about 99.7%. Then, the reduced frequency search range is half of the original, as well as the subband number and computational complexity. When Eb/N0 is 7 dB, the computational complexity could be reduced to about 1/4 of the original. As the Eb/N0 increases, the computational complexity could be further reduced.


### 5.2. Detection Performance of DC, Ambg, and the Proposed Algorithm

In this simulation,Eb/N0 varies from -10 to 3 dB, false alarm probability Pfa is set to 1×10−4, and each algorithm is simulated 1×106 times with different numbers of subbands to evaluate the detection probability Pd. All other parameters are the same as those in Section 5.1. Detection performance comparison of the three algorithms is shown in Figure 8.Figure 8
Detection probability whenPfa=1×10−4.As shown in Figure8, the Ambg algorithm with 64 subbands has the best detection performance. As the subband number decreases, the detection performance of the Ambg algorithm deteriorates especially when M equals 16. The proposed algorithm with 64 and 32 subbands shares the same detection performance which is a little worse than that of the Ambg algorithm with 64 subbands. This is because the local sequence in the Ambg algorithm is the whole 27-symbol training sequence, and the local sequences in the proposed algorithm are the +/-Barker13 sequences comprising 26 symbols in total. It can also be seen from Figure 8 that the detection performance of the proposed algorithm with 16 subbands is almost the same as that of the Ambg algorithm with 32 subbands, and it can be explained by the doubled Doppler frequency tolerance as shown in Figure 4. Figure 8 also shows that the detection performance of the DC algorithm is about 4 dB worse than that of the other algorithms with enough subbands. It can be explained by the noncoherent differential operation in the DC algorithm. This simulation proves that the proposed algorithm shares almost the same detection performance with the Ambg algorithm with only half subbands, and the detection performance of the proposed algorithm is far better than that of the DC algorithm.


### 5.3. Detection Performance with CCI

This simulation is conducted to evaluate the detection performance with CCI of the DC, Ambg (64 subbands), and the proposed algorithm (32 subbands). The signal-to-interference ratio (SIR) varies from 0 to 6 dB, and the CCI istd bits later than the desired signal (the maximum possible delay for a satellite operating at a 600 km surround orbit with a field of view (FOV) of 49° is 19 bits, so td is uniformly distributed in 0,19). All other parameters are the same as those in Section 5.2. Detection performance comparison of the three algorithms with CCI is shown in Figure 9.Figure 9
Detection probability with cochannel interference (CCI) whenPfa=1×10−4.It can be seen from Figure9 that the detection performance of the proposed algorithm with CCI is slightly worse than that of the Ambg algorithm, and this can be explained by the shorter total sample length of the local sequences as explained in Section 5.2. Besides this, the performance loss caused by CCI of the proposed algorithm is almost the same as that of the Ambg algorithm. As shown in Figure 9, for the proposed algorithm and the fact that Pd equals 0.8, the case SIR=0dB is about 2 dB worse than the case of no interference. Meanwhile, for the DC algorithm and the fact that Pd equals 0.8, the case SIR=0dB is more than 4 dB worse than the case of no interference. This simulation shows that the proposed algorithm is less sensitive to CCI than the DC algorithm.


### 5.4. Fine Doppler Frequency Estimation Performance

In this section, all parameters are the same as those in Section5.1, and the performance of the fine Doppler frequency estimation is compared with that of the CRLB. The CRLB in this paper is
(16)σCR=3Rs24Eb/N0π2Ne3,where Rs is the symbol rate which equals 9600 symbols per second and Ne is the number of symbols used in estimation. The RMSE performance of the fine Doppler frequency estimation is shown in Figure 10.Figure 10
RMSE performance of the fine Doppler frequency estimation.Figure10 shows that the performance of the fine Doppler frequency estimation is close to that of the CRLB. When Eb/N0 is 5 dB and 10 dB, RMSE of the fine Doppler frequency estimation reaches 13 Hz and 7.5 Hz, respectively. In consideration of the low computational complexity, the performance of the fine Doppler frequency estimation is quite satisfactory.


## 5.1. Coarse Doppler Frequency Estimation Performance

When receiving ASM-TER signals from a satellite, the maximum absolute value of Doppler frequency is about 4 kHz (fmax=4kHz, fmin=−4kHz), and the phase offset is uniformly distributed in −π,π. The oversampling ratio p is set to 4, and the Eb/N0 varies from 0 to 15 dB. The coarse Doppler frequency estimation is simulated 1×105 times for each Eb/N0. The RMSE performance of the coarse Doppler frequency estimation is shown in Figure 7.Figure 7
Root mean square error (RMSE) performance of the coarse Doppler frequency estimation.As can be seen from Figure7, when Eb/N0 is 3 dB, RMSE of the coarse Doppler frequency estimation δ reaches 650 Hz and 3δ reaches 1950 Hz. As shown in Figure 3, the distribution of fdc^n−fd can be approximately regarded as a Gaussian distribution, so the existence of the true peak in fdc^n−1950,fdc^n+1950Hz can be guaranteed with a probability of about 99.7%. Then, the reduced frequency search range is half of the original, as well as the subband number and computational complexity. When Eb/N0 is 7 dB, the computational complexity could be reduced to about 1/4 of the original. As the Eb/N0 increases, the computational complexity could be further reduced.


## 5.2. Detection Performance of DC, Ambg, and the Proposed Algorithm

In this simulation,Eb/N0 varies from -10 to 3 dB, false alarm probability Pfa is set to 1×10−4, and each algorithm is simulated 1×106 times with different numbers of subbands to evaluate the detection probability Pd. All other parameters are the same as those in Section 5.1. Detection performance comparison of the three algorithms is shown in Figure 8.Figure 8
Detection probability whenPfa=1×10−4.As shown in Figure8, the Ambg algorithm with 64 subbands has the best detection performance. As the subband number decreases, the detection performance of the Ambg algorithm deteriorates especially when M equals 16. The proposed algorithm with 64 and 32 subbands shares the same detection performance which is a little worse than that of the Ambg algorithm with 64 subbands. This is because the local sequence in the Ambg algorithm is the whole 27-symbol training sequence, and the local sequences in the proposed algorithm are the +/-Barker13 sequences comprising 26 symbols in total. It can also be seen from Figure 8 that the detection performance of the proposed algorithm with 16 subbands is almost the same as that of the Ambg algorithm with 32 subbands, and it can be explained by the doubled Doppler frequency tolerance as shown in Figure 4. Figure 8 also shows that the detection performance of the DC algorithm is about 4 dB worse than that of the other algorithms with enough subbands. It can be explained by the noncoherent differential operation in the DC algorithm. This simulation proves that the proposed algorithm shares almost the same detection performance with the Ambg algorithm with only half subbands, and the detection performance of the proposed algorithm is far better than that of the DC algorithm.


## 5.3. Detection Performance with CCI

This simulation is conducted to evaluate the detection performance with CCI of the DC, Ambg (64 subbands), and the proposed algorithm (32 subbands). The signal-to-interference ratio (SIR) varies from 0 to 6 dB, and the CCI istd bits later than the desired signal (the maximum possible delay for a satellite operating at a 600 km surround orbit with a field of view (FOV) of 49° is 19 bits, so td is uniformly distributed in 0,19). All other parameters are the same as those in Section 5.2. Detection performance comparison of the three algorithms with CCI is shown in Figure 9.Figure 9
Detection probability with cochannel interference (CCI) whenPfa=1×10−4.It can be seen from Figure9 that the detection performance of the proposed algorithm with CCI is slightly worse than that of the Ambg algorithm, and this can be explained by the shorter total sample length of the local sequences as explained in Section 5.2. Besides this, the performance loss caused by CCI of the proposed algorithm is almost the same as that of the Ambg algorithm. As shown in Figure 9, for the proposed algorithm and the fact that Pd equals 0.8, the case SIR=0dB is about 2 dB worse than the case of no interference. Meanwhile, for the DC algorithm and the fact that Pd equals 0.8, the case SIR=0dB is more than 4 dB worse than the case of no interference. This simulation shows that the proposed algorithm is less sensitive to CCI than the DC algorithm.


## 5.4. Fine Doppler Frequency Estimation Performance

In this section, all parameters are the same as those in Section5.1, and the performance of the fine Doppler frequency estimation is compared with that of the CRLB. The CRLB in this paper is
(16)σCR=3Rs24Eb/N0π2Ne3,where Rs is the symbol rate which equals 9600 symbols per second and Ne is the number of symbols used in estimation. The RMSE performance of the fine Doppler frequency estimation is shown in Figure 10.Figure 10
RMSE performance of the fine Doppler frequency estimation.Figure10 shows that the performance of the fine Doppler frequency estimation is close to that of the CRLB. When Eb/N0 is 5 dB and 10 dB, RMSE of the fine Doppler frequency estimation reaches 13 Hz and 7.5 Hz, respectively. In consideration of the low computational complexity, the performance of the fine Doppler frequency estimation is quite satisfactory.


## 6. Conclusions

This paper proposes a fast computation of the cross ambiguity function to detect an ASM-TER training sequence from a satellite. According to Parseval’s theorem, the proposed algorithm transforms the classic cross ambiguity function to a frequency domain version, in which the frequency spectrum of the windowed received signal could be calculated using the computationally efficient SDFT. To reduce the computational complexity, the frequency search range is reduced according to the Doppler frequency coarsely estimated from the frequency spectrum. To further reduce the computational complexity, the frequency search step is increased by utilizing two local sequences with half-length of the training sequence. What is more, a fine Doppler frequency estimation could be realized according to the correlation peaks of the two local sequences. Simulation results show that the proposed algorithm inherits the performance of the classic cross ambiguity function-based method and the computational complexity is greatly reduced. Simulation results also show that the proposed algorithm is less sensitive to CCI than the DC algorithm, and the performance of the fine Doppler frequency estimation is close to that of the CRLB.



---

*Source: 3625184-2020-06-08.xml*