{'fraction_non_alphanumeric': 0.033685025650953444, 'fraction_numerical': 0.017810473332688027, 'mean_word_length': 4.256423301958789, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
EC-GSM-IoT Network Synchronization with Support for Large Frequency Offsets

EDGE-based EC-GSM-IoT is a promising candidate for the billion-device cellular IoT (cIoT), providing similar coverage and battery life as NB-IoT. The goal of 20 dB coverage extension compared to EDGE poses significant challenges for the initial network synchronization, which has to be performed well below the thermal noise floor, down to an SNR of -8.5 dB. We present a low-complexity synchronization algorithm supporting up to 50 kHz initial frequency offset, thus enabling the use of a low-cost +/-25 ppm oscillator. The proposed algorithm does not only fulfill the 3GPP requirements, but surpasses them by 3 dB, enabling communication with an SNR of -11.5 dB or a maximum coupling loss of up to 170.5 dB.


I. INTRODUCTION
Cellular networks have enabled five billion people to connect to the Internet. This number is expected to rise further, with 4G and 5G standards meeting the high throughput and low latency requirements of mobile phones. In addition to this, it is estimated that billions of devices will also be directly connected to the Internet. The 3GPP has developed three new standards to address the needs of this Internet of Things (IoT): EC-GSM-IoT, LTE Cat-NB (NB-IoT), and LTE Cat-M (eMTC) all provide better coverage and reduce both cost and power consumption for low-rate devices [1].
The vast majority of cellular IoT (cIoT) devices currently use GPRS/EDGE to connect to the Internet [2]. For these, EC-GSM-IoT provides an easy path to improved energy efficiency and a 20 dB coverage improvement. EC-GSM-IoT specifies 164 dB of Maximum Coupling Loss (MCL) and an expected battery life of more than 10 years, matching the other cIoT standards. Additionally, EDGE support provides instantaneous global coverage and allows the throughput to scale up to 355 kbps, comparable to half-duplex LTE Cat-M1. Further, EC-GSM-IoT is expected to have the lowest module cost of the 3GPP standards [2].
The problem of synchronizing to a legacy GSM carrier has been extensively studied and several low-complexity solutions exist [3], [4]. For EC-GSM-IoT, however, the sensitivity requirement is 20 dB more stringent, and the signal level is now well below the thermal noise floor. The legacy algorithms are unable to cope with this, and new approaches are required to synchronize at SNRs as low as −8.5 dB.
In this paper, we present an algorithm, which is able to perform the EC-GSM-IoT network synchronization down to an SNR of −11.5 dB in a low-band STatic (ST) channel. The support for frequency offsets of up to 50 kHz allows the use of a ±25 ppm crystal oscillator and, therefore, enables a low overall module cost. Compared to [5], the Multi-Frame (MF) boundary can be detected at −14.4 dB instead of −11 dB SNR in an ST channel, and the average synchronization time at −8.5 dB SNR has been reduced by 56 % to 1.3 s. The proposed Frequency Offset Estimation (FOE) can accurately estimate the frequency offset at −8.5 dB SNR.
The remainder of this paper is structured as follows: Section II introduces the EC-GSM-IoT MF, the proposed synchronization procedure, the system model, and the synchronization requirements. The proposed algorithms are discussed in detail in Section III. Finally, the performance for synchronizing to a known carrier and the cell search are evaluated in Sections IV and V.

II. EC-GSM-IOT NETWORK SYNCHRONIZATION
A. Multi-Frame Structure Fig. 1 shows the elements in the EC-GSM-IoT MF, which enable the network synchronization. This 235 ms long structure is repeated on the Broadcast Control CHannel (BCCH) carrier. It consists of 51 frames with eight TimeSlots (TSs) each. Five Frequency Bursts (FBs) are transmitted on TS 0 of frames 0, 10, 20, 30, and 40. The legacy Synchronization CHannel (SCH) follows exactly one frame later and carries the current frame number and the Base Station (BS) identity code. Devices may not be able to decode the SCH below the noise floor, and can use the Extended-Coverage SCH (EC-SCH) with 28 blind repetitions over four MFs instead. The presence of the EC-SCH indicates that the networks supports EC-GSM-IoT.

B. Synchronization Procedure
The proposed algorithm performs the synchronization in four sequential steps as shown in Fig. 1. First, the MF boundary Detection (MFD) finds a coarse estimate for the start time of the MF and the frequency offset, using the FBs. After the frequency offset has been corrected for, the fine time offset is estimated using the EC-SCH training sequences. At the same time, the decoding of the EC-SCH is started. The fine FOE can be started, as soon as the fine time offset is known. The device is ready to receive the Extended Coverage BCCH (EC-BCCH), once the EC-SCH has been successfully decoded, and may transmit, once the fine FOE is completed.

C. System Model
We use the same noise figure as the 3GPP reference document: NF = 5 dB [6]. The noise bandwidth is BW = 200 kHz and the sampling frequency is f s = 270.8 kHz. The receiver is powered on at a random time, and the initial frequency offset is uniformly distributed between ±f o,max = ±Rf c . R is the error relative to the carrier frequency f c . The simulations for the low bands were performed at f c = 900 MHz and at f c = 2 GHz for the high bands.
Since the oscillator is a significant factor in the system cost, it is desirable to use a low-cost crystal oscillator for a cIoT application. These typically have an initial accuracy of R = 25 ppm. In the high bands, this corresponds to a maximum frequency offset of ±50 kHz. This offset can be corrected by tuning the oscillator, or compensated for in the digital baseband.

D. Synchronization Requirements
A device is synchronized to the network, if it has successfully decoded the EC-SCH, achieved timing synchronization, and corrected for the offset of the local oscillator. The requirements from the EC-GSM-IoT standard are as follows [1]: R1 The device must be able to synchronize to the BCCH carrier within 2 seconds after power-on, which corresponds to successfully decoding the EC-SCH. R2a Before the first transmission, the timing offset with respect to the BS must be below ±1 symbol periods. R2b Before the first transmission, the relative frequency offset with respect to the BS must be below ±0.1 ppm. Requirement R1 has to be met at the Input Signal Level (ISL) for reference performance of the EC-BCCH, while Requirements R2a and R2b have to be met at the ISL for reference performance of the EC-SCH. These requirements differ for the low and high frequency bands, and are specified for three radio channels conditions: ST, Typical Urban (TU)1.2, and TU50. The latter are fading with a mobile speed of 1.2 km/h and 50 km/h. The EC-SCH and EC-BCCH ISL for the ST channels correspond to an SNR of −8.5 dB and −7.5 dB. The SNRs for the low band TU1.2 channels are −5.5 dB and −3.5 dB respectively. Since no maximum miss rate is specified for Requirement R1, we will use the same as specified for the EC-SCH BLER: 10 % misses.
The 2 s from Requirement R1 equal approximately eight MFs. In the worst-case, it takes seven MFs to receive a complete set of 28 blind EC-SCH repetitions. Therefore, the MFD should usually only require a single MF. If the MFD takes more than four MFs, it is no longer possible to collect all 28 blind repetitions of the EC-SCH within 2 s.

III. NETWORK SYNCHRONIZATION ALGORITHM A. Fine Frequency Offset Estimation
The fine FOE is performed as the last step of the synchronization. This allows us to discuss it as a stand-alone problem, assuming perfect timing synchronization. The FOE estimates the offset of the local oscillator compared to the BS using the regularly transmitted FBs. Each FB consists of a pure sine at f s /4 = 67.7 kHz for 148 symbol durations. The problem of estimating the frequency of a sine in AWGN is a wellstudied problem, and the Cramér-Rao Lower Bound (CRLB) has been derived in [7]. We have adapted it to the GSM noise bandwidth: The Maximum Likelihood (ML) estimator for this problem selects the frequency with the maximum power spectral den- It approaches the CRLB for high SNR and can be approximated using a DFT [7].
To fulfill Requirement R2b at the minimum carrier frequency of 869 MHz, the frequency has to be estimated with a maximum error of 86 Hz. At an SNR of −8.5 dB, the CRLB for the Root Mean Square (RMS) error is 182 Hz, as is shown in Fig. 2. Clearly, this is not sufficient to achieve the required performance. The ML estimator also suffers from a threshold effect, which renders it useless below an SNR of −6 dB.
The proposed algorithm combines the information from several FBs in order to improve the accuracy of the estimate. The phase of the FBs does not provide any information, since GSM has no guaranteed phase coherency between frames. N FBs are used by non-coherently accumulating the power of the individual FBs in the frequency domain: Our simulations show that this non-coherent combination achieves almost the same performance as a coherent combination with perfect knowledge of the phase.
The ML estimator can be approximated using a two-step procedure to keep the implementation complexity low. In the first step a 256-point FFT and the power for the frequency bins of interest are calculated. At this point, the discrete spectrum can be accumulated over multiple FBs. The maximum of these FFT bins is then taken as the coarse location of the spectral peak. In a second step, a three-point interpolation is applied to produce a higher resolution estimate of the sine frequency. The algorithm from [8] calculates a correction term f a using only the power in the three DFT bins, Y −1 , Y 0 , and Y 1 , closest to the spectral peak: The original algorithm in [8] requires a DFT size of 2N . We have modified the derivation of the constants u and v in order to allow for an arbitrary DFT size, such that an FFT can be used: where N is the number of samples and L is the DFT size. Fig. 2 shows the simulated performance of the proposed FOE algorithm in an ST channel, compared to the ML estimator and the CRLB. At the target SNR of −8.5 dB, the RMS frequency estimation error is 36 Hz, clearly meeting Requirement R2b. Once the frequency of the sine has been estimated, it is also possible to estimate the amplitude of the sine from the same DFT bins. This can be used to detect the presence of an FB and the MF boundary.

B. Multi-Frame Boundary Detection
The MFD is the first step in the synchronization process. Its main purpose is to estimate the start time of the MF, and therefore the position of the EC-SCH. One option is the use of an ML estimator, like the one proposed in [9] for NB-IoT. However, the complexity of such an estimator scales with the maximum initial frequency offset and the number of correlated signals. For EC-GSM-IoT the FCCH and the training sequences of the SCH and EC-SCH are known a-priori and can be used for the search. Based on [9], we estimate the complexity for EC-GSM-IoT: Three different signals need to be cross-correlated with, and the maximum frequency offset is three times larger than in [9], resulting in a nine times larger real arithmetic complexity of 2.5 GOP/s. Storing the 9-bit correlation for 96 frequency and 63 750 time offset candidates requires 55 Mb of memory. This is clearly not suited for a lowpower and low-cost implementation and we therefore propose a reduced complexity MFD algorithm.
The proposed MFD algorithm processes the received data in sliding windows of 200 symbols, which are offset by 50 symbols. The FOE procedure is re-used to look for the maximum spectral component in each window. The amplitude at this frequency, C FB [n], and the frequencies of the two highest components are stored. If the window contains an FB, there is a high chance that one of these two frequencies corresponds to the sine. Since 1275 windows, corresponding to one MF, are considered, 3825 elements have to be stored in memory. Once an entire MF worth of samples has been received, the algorithm accumulates the five FB correlations for an MF start in each window: Fig. 3 shows the two metrics in the noiseless case. Note that the normal bursts still result in a non-zero FB correlation. The stored frequencies for the maximum of C M F are then compared. If there is a set of frequencies with a spread below an empirical threshold of 1 kHz, the search is considered successful. Otherwise, additional MFs are searched and C MF is accumulated and the frequencies are updated. On a hit, the frequencies are also used as a coarse estimate of the frequency offset. At an SNR of −8.5 dB in an ST channel, the residual RMS frequency offset is 150 Hz, which is sufficient to continue with decoding the EC-SCH.
One of the main challenges for the MFD is the structure of the GSM MF. The quasi-regular spacing of the FBs implies that the only difference between two MF starts is the location of a single FB. This results in a number of false side-peaks in the MF correlation, as can be seen in Fig. 3. This is especially problematic for fast fading channels, like the TU50 test case. We propose the use of the EC-SCH training sequences to find the actual start of the MF, since they follow a different repetition scheme. To this end, the MFD does not only return the peak of C M F , but also the two positions 10 frames earlier and later as possible MF start candidates. The correct candidate is later found using the EC-SCH training sequences. Fig. 4 shows the performance of the Spectrum MFD for the EC-GSM-IoT channels in the low and high bands. In order to allow the EC-SCH decoding sufficient time, the MFD is terminated after searching 4 MFs and the most likely candidate is used.   The MFD is the computationally most demanding part of the synchronization process. 5400 windows need to be processed every second, each requiring a 256-point FFT. Including the calculation of the power and three-point interpolation, this results in an overall real arithmetic complexity of 40 MOP/s. This is suitable for a low-complexity hardware implementation and should result in a negligible power consumption, compared to the RF receiver.

C. Fine Time Offset Estimation and EC-SCH Decoding
Once the MFD is completed, the time offset is known to within ±80 symbols. In a next step, the accuracy has to be improved to ±1 symbol in order to decode the EC-SCH and fulfill Requirement R2a. This is done by cross-correlating the received EC-SCH training sequences with the known symbols. The time offsets in the range of the residual time offset of ±80 symbols are tried and the best match is selected. In a static channel at an SNR of −8.5 dB, the correct time offset is found in approximately 60 % of all attempts. Blind repetitions of the training sequences are thus received and the correlation outputs K p [η] are combined non-coherently: Seven blind repetitions of the EC-SCH are sufficient to determine the correct time offset at an SNR of −8.5 dB in an ST channel. The correct MF start candidate is selected by choosing the one with the largest K [η] after 28 blind repetitions have been received.
The last steps in the synchronization procedure are the fine frequency offset estimation and the decoding of the EC-SCH, which can be performed simultaneously. The EC-SCH decoding is started together with the fine time offset estimation and uses the most recent result of the latter. Seven repetitions of the EC-SCH are transmitted at the start of every MF and a total of 28 repetitions contain the same data. Repetitions in different MFs however, have different cyclic shifts, which depend on the frame number.
The actual decoding of the EC-SCH is implemented, as described in [5], where the Log-Likelihood Ratios (LLRs) for the EC-SCH repetitions are chase-combined for the four cyclic shift candidates. IQ-combination can significantly improve the channel estimation, especially when short training sequences are used. However, the EC-SCH uses longer training sequences and the phase between repetitions has to be estimated. Our simulations show that IQ-combination does not improve the performance of the decoder due to the phase estimation error at an SNR of −8.5 dB.
One option to detect the cyclic shift is comparing the data received in two successive MFs using a cross-correlation with lag 1. Unfortunately, the correlation output is dominated by noise in the target SNR region, and this method fails. Alternatively, blind decoding attempts can be performed for all cyclic shifts, relying on the Cyclic Redundancy Check (CRC) checksum to filter out the invalid results. But this method also has a flaw, because the decoding attempts on invalid data can result in false positives from the checksum. The problem is further complicated by the relatively short CRC field length of 10 bits. If decoding is attempted after every received repetition, CRC false positives occur up to 19 % of the time. The proposed algorithm alleviates this problem by reducing the number of decoding attempts. In the low SNR region, a decoding attempt is only performed after 7N, N ≥ 4 repetitions have been received. This reduces the maximum false positive rate to 2.7 %. It is below 1 % above −8.5 dB SNR, which is acceptable and has to be handled after the synchronization.

IV. PERFORMANCE EVALUATION
In order to evaluate the performance of the synchronization, we have performed simulations, where all the steps are performed in sequence. Fig. 5 shows the resulting overall miss rate for all of the channels specified for EC-GSM-IoT. 90 % of the simulations succeed at an SNR of −11.5 dB in the low band ST channel and at an SNR of −7.7 dB in the low band TU1.2 channel. This exceeds the 3GPP goals by 3 dB and 2.2 dB, respectively. The Cumulative Distribution Function (CDF) for the synchronization time is shown in Fig. 6. It takes 1.6 s to 1.8 s to achieve 90 % successful synchronizations, meeting Requirement R1. The average synchronization time in an ST channel at −8.5 dB is 1.3 s, corresponding to a 56 % reduction, compared to [5]. The MFD takes 250 ms to 425 ms on average, the rest of the time is spent receiving the EC-SCH. This is good from an energy standpoint, since the receiver can be turned off most of the time during the EC-SCH reception, recalling the MF structure in Fig. 1 Fig. 7 shows the fine time offset at the end of the synchronization process. It is below ±1 symbol in more than 99.5 % of the attempts for all the channels at the ISL for EC-SCH reference performance, which meets Requirement R2a. As shown in Fig. 8, the residual frequency offset after the fine FOE over 40 FBs is below 0.1 ppm in 99 % of the test cases, which meets Requirement R2b.

V. CELL SEARCH
A cell search may have to be performed, whenever the device cannot reach a BS at a known frequency. Then, it has to scan all 298+673 potential low and high band BCCH carriers. Legacy GSM devices look for a suitable carrier by performing receive power measurements, which are not feasible below the noise floor. The duration of the cell search becomes problematic in EC-GSM-IoT, because the device must perform a partial synchronization to all potential carriers [10]. Like other cIoT standards, EC-GSM-IoT trades synchronization time for an improvement in coverage. As in [10], we propose the use of the MFD to detect the presence of a GSM carrier in extended coverage. Their algorithm requires 10 MFs to achieve a 99 % detection rate in a TU1.2 channel. Our proposed algorithm can achieve the same performance after searching only 4 MFs. However, the limiting case is the high band TU50 channel with a maximum frequency offset of ±50 kHz. In this case, 7 MFs are required to achieve a 99 % detection rate. No false detections were simulated in 10 000 test cases. With this 30 % reduction compared to [10], the cell search takes 27 minutes and a maximum of 113 full cell searches are possible with a 5 W h battery 1 .

VI. CONCLUSION
We have presented the first complete set of algorithms, which is able to successfully synchronize at an SNR as low as −11.5 dB. It fulfills the requirements for the synchronization time and the residual time and frequency offset with a low computational complexity. Our simulations show that it exceeds the 3GPP target by 3 dB in the best-case, resulting in an MCL of up to 170.5 dB. In the worst-case the target is exceeded by 2.2 dB, corresponding to an MCL of 166.7 dB. The network synchronization supports a large frequency offset oscillator, enabling a low-cost EC-GSM-IoT implementation.

ACKNOWLEDGMENT
We would like to thank Innosuisse for their financial support through project 18987.1PFNM-NM.