2.1. The modulation rules of BeiDou D1 navigation data

D1 navigation data includes the basic navigation information, almanac and also time synchronization information calculated by the BeiDou system. As shown in Figure 1, the data bit rate of the BeiDou D1 navigation message is 50 bps and a data bit lasts 20 milliseconds. The PRN code cycles 20 periods for each data bit, which is similar to the structure of the GPS L1 signal. For the acquisition of legacy GPS, the signal length can be 10 milliseconds. The bit transition can be ruled out after the non-correlation integration of two adjacent 10 milliseconds signal data. The BeiDou navigation data was modulated with NH code, and the data bit rate increases to 1 kbps and 10 bit transitions occur in one navigation data bit. The bit transition can occur in every 1 millisecond random sampling signal, which means that the traditional 1 millisecond coherent integration acquisition is no longer applicable. The PRN code of the BeiDou system is 1 millisecond. As the 1 ms signal data is sampled randomly, the bit transition can be avoided only if the start point of the sampling signal falls into the dashed part of Figure 1. That probability is only 45%. For convenience, the above dashed part is defined as a non-bit-transition section.

Figure 1.

BeiDou D1 navigation message and NH code.

2.2. The characteristics of BeiDou D2 navigation data

The data bit rate of the D2 navigation data is 500 bps, which is ten times the rate of the D1 navigation data. The NH code is not modulated on the D2 navigation data. Since a data bit of D2 navigation data lasts 2 milliseconds, the GEO satellite signal acquisition can be realised by the traditional 1 millisecond coherent integration.

2.3. Classical BeiDou satellites acquisition scheme

At present, subject to the presence of NH code, repeated acquisition based on 1~2 milliseconds of coherent integration is more popular for BeiDou IGSO/MEO, but the fact is that the low success rate of the single acquisition does not change. To improve the success rate of single acquisition, the NH code phase must be taken into account.

As a classical method applicable to a PC-based software-defined receiver, the novel acquisition technique for a long coherent integration implemented in Bhuiyan et al. (Reference Bhuiyan, Söderholm, Thombre, Ruotsalainen and Kuusniemi2014) solved the above problem, which is an excellent example for BeiDou signal acquisition. For IGSO and MEO satellites, a truncated NH code is selected to be multiplied with the locally generated BeiDou PRN codes to form long NH-code-modulated-PRN-code-cycle. A similar phase-preserved scheme was implemented for GEO satellite acquisition. The acquisition was realised with the above modulated code and Fast Fourier Transform (FFT)-based correlation. The above technique was implemented by finding the NH code phase, but the calculation and integration time is challenging. Moreover, the length of incoming signal is long (more than 20 milliseconds) and the frequency bin size for acquisition is small. The traditional BeiDou acquisition technique (Juang et al., Reference Juang, Tsaia and Chena2013) does not consider the impact of NH code on the acquisition. A more simple and effective strategy is necessary.

3.1. The special sequence based on probability statistics

The complexity of acquisition of the BeiDou signal increases due to the presence of the NH code modulation. To achieve signal acquisition successfully, and reduce the effect of the NH code on calculation and acquisition time as much as possible, a special sequence was proposed for fast acquisition based on the analysis of probability statistics about the NH code sequence, which can improve the efficiency of the NH code. The core idea of the above technology is as follows.

In the coarse acquisition stage, a certain number of 1-millisecond-long incoming signals are simultaneously selected for integral correlation. This ensures that at least one of them does not include data bit transition. The maximum of the correlation integral is the signal we need for fine acquisition. The NH code will be stripped in the tracking. To reduce the calculation, the number of 1-millisecond-long signals for coarse acquisition should be as few as possible. In this article, a special sequence of incoming signals was found through probability statistics. Table 1 shows the statistics of the non-bit-transition section. The first column shows the NH code phase that the start point of a 1-millisecond-long incoming signal might fall into, corresponding to 20 bits. The first line shows the number of milliseconds of delay in the incoming signal. Both ‘○’ and ‘●’ mean non-bit-transition.

Table 1.

The statistics of the non-bit-transition section.

1. The statistics indicate that any 1-millisecond-long incoming signal will fall into the non-bit-transition section in no more than 5 milliseconds delay. This means at least one 1-millisecond-long signal does not include a data bit transition in the B1I satellite signal lasting more than 6 milliseconds.

2. Based on the above, the optimal sequence continues to be simplified. We define two indices: the required delay time and the shortest time fall into the non-bit-transition section.

3. Analysing the required delay time. Focusing on [9, 10) and [10, 11), when the start point of the incoming signal falls into these two sections, the signal can fall into the non-bit-transition section with a delay of only 5 milliseconds and 4 milliseconds respectively, which establishes that these are required. When the start point falls into the other 12 start sections, it can fall into the non-bit-transition section based on 5 milliseconds and 4 milliseconds delay.

4. Analysing the required shortest time that falls into the non-bit-transition section. There are six start sections that need to be considered: [0, 1), [5, 6), [6, 7), [7, 8), [8, 9), and [14, 15). They themselves are in the non-bit-transition section which means no time need to delay except [5, 6) and [7, 8). Sections [5, 6) and [7, 8) can fall into the non-bit-transition section in 1 millisecond delay.

In summary, the special sequence {1, 2, 5, 6}, is what is desired. It does not matter where the start point is placed in the 1-millisecond-long incoming signal. Using the time delay, 1 millisecond, 4 milliseconds and 5 milliseconds respectively, four 1-millisecond-long signals are obtained. These signals can evade the bit transitions caused by the NH code and complete the acquisition successfully. Table 2 shows ‘the contribution’ of members in the special sequence for improving the NH code.

Table 2.

The statistics table of the special sequence for non-bit-transition section.

Figure 2 shows the acquisition of the special incoming signal sequence from different start points. The dark rectangle represents successful acquisition; the white rectangle includes a data bit transition which will lead to acquisition failure. Through analysis of the figure it can be found that signals more than 1-millisecond-long fall into the non-bit-transition section in the special sequence {1, 2, 5, 6}. The experiment later will verify that it does not influence the acquisition.

Figure 2.

The acquisition of special incoming sequence.

Due to two consecutive 1-millisecond-long sequences, the special sequence applies to BeiDou GEO at the same time. The proposed technique is a general approach for all types of BeiDou satellites, and is therefore ideal. Referring to Table 2, if the first and second milliseconds are selected first, the probability of a non-bit-transition section is up to 70%. This calculation can be cut by 50%, allowing the special sequence to be divided into two steps. If the first and second millisecond signals for acquisition fail, then the fifth and sixth millisecond signals are taken for acquisition immediately. This two-step strategy can reduce the calculation time.

3.2. Generality of the special sequence in modern GPS and GLONASS-K

As described previously, NH code is also introduced in GPS and GLONASS. The special sequence proposed above is applied in the GPS L5C pilot channel, but the 10-bit NH code (0000110101) is different from the 20-bit NH code. The statistics of the non-bit-transition section aimed at 10-bit NH code are analysed along the same lines. As shown in Figure 3 and Table 3, the special sequence proposed above is also applied for 10-bit NH code.

Figure 3.

10-bit NH code modulated with navigation message.

Table 3.

Non-bit-transition section of 10-bit NH code.

3.3. Parallel code phase search based on the discrete Fourier transform

In coarse acquisition, the non-bit-transition signal, whose peak value of incoherent integration is higher than the threshold, is obtained using the special sequence. The acquisition is completed by a parallel code phase search based on the Discrete Fourier Transform (DFT) to get initial estimates of the code offset and carrier Doppler. As the PRN code is in parallel processing, the two-dimensional searching, including PRN code phase and carrier frequency, is narrowed down to one-dimensional, i.e., go through all the possible carrier frequencies. The calculation time is greatly reduced compared to the serial searching and parallel frequency space searching. Take the B1I signal as an example:

1. 1 After down conversion, sampling and quantisation, the BeiDou signals can be demonstrated as:

   (1) $$S_{}^j = A_{}C_{}^j NH_{20}D{\,^j} \cos (2\pi f_{{\rm IF}}t + \varphi _{{\rm IF}}^j )\,{^\ast}\,N_s$$
   Where A is the signal amplitude, $C_{}^j $ is the pseudo random code, also known as PRN code, NH ₂₀ is the Neumann-Hoffman code of 20 bits; $D\,{^j} $ is the navigation data bit, f _IF is the carrier intermediate frequency (IF), $\varphi\,^j_{{\rm IF}} $ is the signal initial phase. The superscript j is the satellite number, whose range is 1~35, N _s is the sampling sequence of 1 millisecond.

2. 2 Generate the local carrier and PRN code. The nominal frequency f _B1I of B1I is 1561.098 MHz. The sinusoidal and cosine carrier respectively is:

   (2) $$\eqalign{& I_{carr} = \cos ((\,f_{IF} + N_f\,{^\ast}\,f_d)\,{^\ast}\,2\,{^\ast}\,\pi \,{^\ast}\,T_s\,{^\ast}\,N_s) \cr & Q_{carr} = \sin ((\,f_{IF} + N_f\,{^\ast}\,f_d)\,{^\ast}\,2\,{^\ast}\,\pi \,{^\ast}\,T_s\,{^\ast}\,N_s)} $$
   Where f _d is the step size in searching. N _f is the searching range. T _s is the sampling time.

   The PRN code of the BeiDou B1I signal is $C_{}^j $ , whose rate is 2·046 Mcps and length is 2046. The PRN code is the balanced Gold code which is shortened by 1 code chip, and is generated by two linear sequences G1and G2 modulo 2 sum. The G2 sequence phase offset is realised by different tap of shift registers. Both G1 and G2 sequences are generated by 11 bits shift register, whose generator polynomials are:

   (3) $$\eqalign{& G1(X) = 1 + X + X^7 + X^8 + X^9 + X^{10} + X^{11} \cr & G2(X) = 1 + X + X^2 + X^3 + X^4 + X^5 + X^8 + X^9 + X^{11}} $$
   The PRN code after sampling is:
   (4) $$C_{}^j (n) = G1(X) \otimes G2_j(X){^\ast}N_s$$
   The discrete Fourier transform (DFT) of $C_{}^j (n)$ is $C(k)$ . The next operation will use its conjugated form $\overline {C(k)} $ .

3. 3 Wipe out the carrier and transform to frequency domain. Multiply the local carrier and IF signals respectively.

   (5) $$\eqalign{& i(n) = S_{}^j. \,{^\ast}\,I_{carr} \cr & q(n) = S_{}^j. \,{^\ast}\,Q_{carr}} $$
   Then, $i(n)$ and $q(n)$ are composed as complex vector form, $r_p(n) = i + jq$ . The DFT of $r_p(n)$ is:
   (6) $$R(k) = \sum\limits_{n = 0}^{N - 1} {r_p(n)} e^{\displaystyle{{^{ - 2\pi jkn}} \over N}} = \sum\limits_{n = 0}^{N - 1} {(i + jq)} e^{\displaystyle{{^{ - 2\pi jkn}} \over N}}$$

4. 4 Wipe out the PRN code. For the carrier and PRN code, the correlation calculation in the time domain is equivalent to the multiplication in the frequency domain. So the multiplication between $\overline {C(k)} $ and $R(k)$ can wipe out the PRN code and carrier at same time. The inverse discrete Fourier transform (IDFT) of the multiplication is the correlation value in every code phase.

   (7) $$I + jQ = IDFT\left\{ {\overline {C(k)} *R(k)} \right\}$$

5. 5 The carrier and PRN code are wiped out after the parallel code correlation. The In-phase and Quadrature channels can be demonstrated as:

   (8) $$\eqalign{& I = ANH_{20}D\cos (\varphi _{IF} - \varphi _L) \cr & Q = ANH_{20}D\sin (\varphi _{IF} - \varphi _L)} $$
   Eliminate the interference of carrier phase residual to the acquisition based on the incoherent integration:
   (9) $$\eqalign{V & = I^2 + Q^2 \cr & = [ADNH_{20}\cos (\varphi _{IF} - \varphi _L)]^2 + [ADNH_{20}\sin (\varphi _{IF} - \varphi _L)]^2 \cr & = (ADNH_{20})^2} $$

6. 6 Four sets of incoherent integration are obtained after the above steps. Search the largest peak and second largest peak in corresponding frequencies. Compare the ratio between them with the predetermined acquisition threshold. The satellite is visible if there are ratios that exceed the threshold. On this basis, the maximum is put into fine acquisition.

7. 7 In fine acquisition, the input is the 1-millisecond-long sequence chosen from the above step. The coarse carrier frequency and PRN code are known. The accurate carrier frequency is obtained by a decreased frequency bin size.

The ratio detection method is chosen as the strategy for detecting the visible satellites, which compares the ratio between the two largest correlation peaks against a threshold. Although in terms of receiver operating characteristics, the threshold comparison method, which compares the energy within each cell to a predefined threshold, outperforms the ratio detection method, we choose the latter in consideration of its simplicity in normal signal and the false alarm probabilities are independent of the Signal to Noise Ratio (SNR), which yields a constant false alarm rate for a fixed threshold setting. The probabilities depend on the length of the correlation function, including the code period and the sampling rate (Geiger et al., Reference Geiger, Vogel and Soudan2012). In the coarse acquisition stage, the setting value of the acquisition threshold is 2·5 based on verification in the tracking loop.

4.1. BeiDou signal tracking loop

The main objective of signal tracking is to wipe off the code and the carrier. A four-quadrant arctangent discriminator, which is optimal at high and low C/N0 with a wide frequency pull-in range and offers a linear relationship between the discriminator output and the real frequency error, is widely used in conventional GPS tracking loops. A four–quadrant arctangent discriminator can enhance the robustness of signal tracking and endure large acquisition frequency errors, but it is sensitive to data bit transitions, which may cause a frequency error if they are frequent. In most situations the low data bit rate GPS L1 receiver can meet this condition, but apparently BeiDou cannot. For D1 navigation data, the data bits last 1 millisecond so every pair of adjacent integration values are in different data bit intervals due to the existence of NH code. For D2 navigation data, the data bits last 2 milliseconds due to a high data bit rate. So the four-quadrant arctangent discriminator is no longer applied in the BeiDou receiver.

The two-quadrant arctangent discriminator is insensitive to data bit transition and it is implanted in this paper, but its limitation is that it has reduced tolerance of frequency uncertainty coming from the acquisition stage (Yan et al., Reference Yan, Zhang, Zhang, Xu and Niu2013). It was shown that the frequency uncertainty tolerance is reduced by half, as compared to the conventional four-quadrant arctangent discriminator. So the searching precision of the frequencies must be limited to ±250 Hz to guarantee the normal work of the loop. This is the reason the fine acquisition is included in Section 3.2. In this paper, the searching step in fine acquisition is 100 Hz.

4.2. NH code stripping method

The period of the NH code in BeiDou D1 navigation data is 20 milliseconds, equal to the width of a navigation data bit, and the bit width of the NH code is equal to the period of the PRN code. Evading the influence of the NH code and getting the PRN code phase and carrier frequency in the acquisition, the tracking can be done from the start point of the PRN code and the synchronous period is 1 millisecond, which can evade the influence of the NH code to the tracking loop. The PRN code and carrier were wiped out in the tracking loop and the navigation data with NH code are obtained. In this article, the NH code is stripped in frame synchronization.

In the sub-frame of BeiDou navigation data, the first 1~11 bits, 11 bit modified Baker codes are called the frame synchronization code (Pre). The bit sequence is ‘11100010010’. So the length of Pre is 220 milliseconds, equal to 11 cycles of NH code. Figure 4 shows the flowchart of frame synchronization completed with NH-Pre modulated code.

Figure 4.

The frame synchronization based on NH-Pre modulated code.

As Figure 4 shows, the NH-Pre modulated code is modulated with 11 periods of NH code and the frame synchronization code. The NH-Pre code is used for both frame synchronization and determining the phase of NH code. The sub-frame head is searched via sliding correlation. The inputs are tracking results and the NH-Pre code. Figure 5 shows the NH-Pre modulated code, whose period is 220 milliseconds.

Figure 5.

The NH-Pre modulated code.

Figure 6 shows the correlation of NH-Pre code and an actual sampled signal. The theory value is 220, and the actual correlation output verifies it. The correlation output of pseudo random data and NH-Pre code is 180 from Figure 6. So set the threshold of sub-frame synchronization ${\rm T}_{NH - \Pr e}$ as:

Figure 6.

The sliding correlation of NH-Pre code and tracking results.

The sub-frame head is found when the correlation output is higher than the ${\rm T}_{NH - \Pr e}$ . The length of the sub-frame is 6000 milliseconds. So the sub-frame synchronization can be completed in 6220 milliseconds. If more than one sub-frame head is found in 6220 milliseconds, it indicates the emergence of a false sub-frame head. Here are two solutions:

1. 1. Search the next sub-frame head. Take the sub-frame head as the start point, searching the next sub-frame head 6000 milliseconds later. Two random data points that are separated by 6000 milliseconds are equal to the Pre at the same time. In consideration of the phase reversal in tracking loop, the probability is:

   $$(0\!\cdot\!5^{11} \times 2)^2\,{\rm = 9}\!\cdot\!{5367} \times {\rm 1}{\rm 0}^{ - 7}$$
   This probability is small enough. The sub-frame head can be proved as a correct one if the next Pre is found, otherwise it is just random data.

2. 2. Decode the sub-frame. Parameters in the sub-frame, including the sub-frame ID (Fra ID), Seconds Of Weeks (SOW) and other parameters determined by Fra ID, their ranges and connections can be used for testing the sub-frame head. The parameters can be decoded via error-correcting decoding.

It should be noted that the BeiDou navigation system chooses the Bose, Chaudhuri, and Hocquenghem encoding (which is BCH (15, 11, 1) for short) and interleaving approach for error correction. The length of BCH code is 15 bits, including 11 data bits and 4 bits of check code. One error data bit can be corrected. The decoding process and de-interleaving mechanism are the same for both D1 and D2 navigation messages. What should be mentioned is that the first 15 bits in the first word of every sub-frame are not BCH encoded, which is convenient for frame synchronization.

The NH code phase is determined when the sub-frame head is found. The NH code stripping can be done with sliding correlation in a tracking loop.

The detailed process of BeiDou NH code evasion and stripping can be illustrated by the flowchart shown in Figure 7.

Figure 7.

Flowchart illustrating BeiDou NH code evasion and stripping.

5.1. The overall acquisition

As Figure 8(b) shows, the B1I signal was collected in the stadium of NUAA Minggugong Campus, where the antenna was placed on a horizontal crossbar of the football goal on the playground. The Beijing time was 09:30 AM (01:30 AM UTC Time), August 28, 2014. The data was collected for about 60 seconds. The BeiDou satellite acquisition is shown in Table 5, including PRN, code phase and carrier frequency. The searching step sizes in course acquisition and fine acquisition are 500 Hz and 100 Hz respectively. The number of visible satellites is ten, including five GEO, three IGSO and two MEO. The chosen signal indicates the signal used for detecting the presence of the satellite, along with the estimation of the carrier Doppler and the code phase.

Table 5.

BeiDou satellites acquisition.

5.2. Single satellite acquisition

Take PRN-7 satellite as an example. The parallel code phase searching results are shown in Figure 10. Only the second millisecond searched an obvious peak (Figure 10(b)), whose code phase is 794 and carrier frequency is 4·131400 MHz. The ratio between peak and mean values in the corresponding frequency is 22·468, which exceeds the threshold. So the PRN-7 satellite is acquired. The other three sampled signals include the NH code transition.

Figure 10.

The coarse acquisition of PRN-7.

Figure 11 shows the two-dimensional projections of two-stage acquisition of the second millisecond, which include the code phase dimensional and carrier frequency dimensional. 794 and 4·131230 MHz are the final results of the PRN-7 acquisition.

Figure 11.

Two-dimensional projections of acquisition.

5.3. Comparing the classical and traditional acquisition scheme

The acquisition in Bhuiyan et al. (Reference Bhuiyan, Söderholm, Thombre, Ruotsalainen and Kuusniemi2014) and repeated 1-millisecond acquisition were taken for comparison, respectively as a classical acquisition scheme and the traditional scheme, and the former coherent integration period was set to 5 milliseconds keeping consistent within this paper. Table 6 shows the comparison results of three acquisition schemes. All of them are FFT-based acquisitions and applied to the PC-based software-defined receiver. This assumes the intermediate frequency, front-end bandwidth, sampling frequency and number of quantisation bits are all the same.

Table 6.

Comparison between two acquisition schemes.

In addition to the theoretical analysis and comparison, the first two schemes were also tested for IGSO/MEO acquisition based on the same incoming signals (collected in Section 5.1) and the same computer (Core i3 processor, 3·40 GHz CPU, 4·00 GB RAM), the frequency searching range and step size are consistent. The actual runtime is also shown in Table 6.

Analysing the data in Table 6, the scheme proposed in this paper and the classical scheme can complete a one-time acquisition. The acquisition scheme proposed in this paper utilises shorter signals and the correlation time summation is much less compared to the classical acquisition scheme. The algorithm is simpler and easier to implement. Due to the coherent integration period and the frequency bin size, its frequency uncertainty tolerance is better. The NH code will be stripped in the tracking stage, and it can be applied to GEO satellites. The actual runtime also proved that the scheme in this paper saved a significant amount of time. Compared to the traditional scheme, the scheme proposed in this paper improves the success rate of single acquisition and reduces the probability of false acquisition due to NH code and navigation bit transition.

Focussing on Table 6, two points need to be stressed. Firstly, the success rate of the single acquisition does not mean the acquisition only executes once. Secondly, a long coherent integration has a natural advantage against noise and weak signals, which is the classical scheme's superiority. The actual sampling experiment above proved that the acquisition scheme in this paper was feasible under normal circumstances.