Advanced
Frame Synchronization Algorithm for LDPC Coded Burst Systems
Frame Synchronization Algorithm for LDPC Coded Burst Systems
ETRI Journal. 2015. Oct, 37(5): 940-944
Copyright © 2015, Electronics and Telecommunications Research Institute (ETRI)
  • Received : November 05, 2013
  • Accepted : March 05, 2014
  • Published : October 01, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Xin Man
Haitao Zhai
Eryang Zhang

Abstract
We present a frame synchronization algorithm for low-density parity-check (LDPC) coded burst transmissions, which combines a conventional pilots-assisted frame synchronization algorithm and a code-aided algorithm based on the mean magnitude of the soft outputs from the LDPC decoder. With moderate computational complexity, the proposed algorithm is more efficient in bandwidth than conventional pilots-assisted algorithms. When compared with other code-aided algorithms, the proposed algorithm offers a better trade-off between complexity and performance. Simulation results in the case of an 8-PSK system with (1944, 972) LDPC code show that the proposed algorithm can achieve a performance equivalent to that of the perfect frame synchronization, with a bandwidth efficiency loss of 0.06 dB due to the use of pilot symbols.
Keywords
I. Introduction
Frame synchronization is an important task for burst communication systems, and conventional frame synchronizers usually make use of pilot symbols [1] . Recent advances in powerful error-correcting codes, such as low-density parity-check (LDPC) codes [2] , make it possible to operate at capacity-approaching signal-to-noise ratios (SNRs). However, operating at such SNRs requires conventional frame synchronization algorithms with many pilot symbols in the burst, leading to both bandwidth inefficiency and power inefficiency.
To cope with this problem, many researchers have presented so-called code-aided algorithms. An algorithm based on detecting the mean magnitude (M-value) of the soft outputs from the LDPC decoder was presented in [3] . Wymeersch and others proposed another algorithm based on the discrete expectation–maximization (EM) algorithm [4] . Although the algorithm in [3] performs better both in terms of complexity and performance, the EM-based algorithm offers the flexibility to use pilot symbols (which often exist in burst transmissions) to improve the detection performance. While both of the aforementioned methods can provide good synchronization performance, they are computationally inefficient; they require several decoding iterations for every possible frame offset candidate. To reduce the computational complexity, Lee and others [5] presented an algorithm (Lee Frame synchronizer) that utilizes the hard decisions of the received symbols to compute the parity-check equations for each constraint node, instead of doing full LDPC iterations. However, this algorithm requires multiple frames to achieve satisfactory performance, which is not practical for burst transmissions where the frame offset is usually assumed to be different from burst to burst.
Based on the M-value algorithm in [3] , we propose a novel frame synchronization algorithm that makes use of a few pilot symbols to reduce the required number of decoding iterations. When compared with conventional pilots-assisted methods, the proposed algorithm is more efficient in bandwidth due to the utilization of the soft outputs of the LDPC decoder. The simulation results show that the new algorithm can approach the performance of perfect frame synchronization with moderate computational complexity and little bandwidth efficiency loss.
II. System Model
We consider a burst transmission system with N + L symbols ( s ) in every burst, which consists of a pilot sequence ( p ) of length L and a coded data sequence ( a ) of length N . Assuming perfect carrier synchronization in the digital receiver, the complex samples at the input of the matched filter can be expressed as
y(k)= k=0 N+L1 s k g(tτkT) + n k ,
where sk is the unit-amplitude transmitted symbol, g ( t ) is the square-root raised-cosine pulse, and nk (where k is an integer between 0 and N + L − 1) is the complex-valued additive white Gaussian noise (AWGN) with two-sided power spectral density N 0 /2; T represents the symbol duration and τ accounts for the unknown propagation delay, which can be broken up as follows:
τ= k τ T+ ε τ ,             T 2 ε τ T 2 ,
where kτ is an integer that denotes an unknown frame offset within the range of [0, Mτ − 1], M is the maximum of the frame offset; the fractional offset, ετ , is assumed to be estimated accurately by a timing algorithm. The interval between bursts exceeds MτT and contains only noise. After sampling the output of the matched filter at time t = kT + ετ , we get the following vector:
r=[ 0 k τ s 0 M τ 1 k τ ]+n,
where 0 k is an array consisting of k zeros, s is an unknown data sequence, and n a complex AWGN vector of length Mτ + L + N .
The goal of frame synchronization is to obtain
k ^ τ
given the observation r , and we will deal with this problem in the following sections.
III. Proposed Frame Synchronization Algorithm
To recover the transmitted symbols, we have to take into account the unknown frame offset kτ . In this section, we present a frame synchronization algorithm with moderate complexity. As shown in Fig. 1 , the new algorithm combines a conventional pilots-assisted correlation algorithm and a code-aided algorithm based on M-value search. In the following subsections, we will introduce the proposed algorithm in detail.
PPT Slide
Lager Image
Architecture for proposed frame synchronizer.
- 1. Conventional Pilots-Assisted Frame Synchronizer
As a part of the proposed algorithm, we choose a conventional pilots-assisted correlation frame synchronizer, which is of low computational complexity and determines the frame starting point according to
k ^ τ =arg  max k ˜ τ [0, M τ1 ] l=0 L1 { r l+ k ˜ τ * p l } ,
where ℜ{ } is an operation to obtain the real part of a complex number, * is the conjugation operation, and
k ˜ τ
is assumed to be the starting location of a frame.
- 2. M-Value-Based Code-Aided Frame Synchronizer
In this subsection, we will introduce the other part of the proposed algorithm. At first, we define M-value as the mean magnitude of the log-likelihood ratio (LLR) outputs from the decoder, which can be expressed as follows:
M (m) ( k ˜ τ )= 1 N i=0 I1 | L i (m) ( k ˜ τ ) | ,
where m is the m th iterative decoding operation, I is the code length, and
L i (m) ( k ˜ τ )
is the LLR of the i th bit after the m th decoding iteration when the frame starts at
k ˜ τ
.
Figure 2 shows the relationship between the M-value and the frame offset candidate
k ˜ τ
after several decoding iterations of the (1944, 972) LDPC code, which is currently in the IEEE 802.11n standard. The true frame offset is kτ = 100. We can see that the M-value has a unique global maximal value at
k ˜ τ =  k τ ;
therefore, the frame offset can be determined by maximizing the M-value as follows:
k ^ τ =arg  max k ˜ τ [0, M τ 1] M (m) ( k ˜ τ ).
PPT Slide
Lager Image
M-value vs. k ˜ τ at Eb/N0 = 3 dB.
- 3. Novel Frame Synchronization Algorithm
As mentioned in Section I, to achieve good performance, the pilots-assisted algorithm requires many pilot symbols and the M-value-based algorithm requires several decoding iterations for every possible frame offset candidate. To acquire a trade-off between the aforementioned methods, we combine them into a novel algorithm as follows:
l ^ τ =arg  max k ˜ τ [0, M τ 1] { α C p ( k ˜ τ )+ M (m) ( k ˜ τ +L) },
where α is a weighted factor and
C p ( k ˜ τ )
is the normalized correlation.
C p ( k ˜ τ )= 1 L l=0 L1 { r l+ k ˜ τ * p l } .
From (7), we can see that the proposed algorithm is a combination of two existing methods, and the choice of α is crucial to the algorithm’s performance. On the one hand, too small an α will make the pilots-assisted algorithm negligible, thus making it nothing more than an approximation of the M-value-based algorithm. On the other hand, too large an α will make the M-value-based algorithm negligible, thus allowing the pilots-assisted algorithm to dominate the performance of (7).
The relationship between the normalized correlation value and the frame offset candidate for different values of L at E b / N 0 = 0 dB is shown in Fig. 3 , where the true frame offset is kτ = 100. From the figure, we can see that the detection result for L ⩾ 30 is more reliable than the case for L < 30.
PPT Slide
Lager Image
Normalized correlation C p ( k ˜ τ ) vs.  k ˜ τ at Eb/N0 = 0 dB.
Further simulation results (not reported due to space limitations) show that a smaller value of L permits reliable detection at higher SNR. So, the choice of α is dependent on SNR. We set α = L / 30 in (7) for simplicity, which means that when the number of pilot symbols is more than 30, the pilots-assisted algorithm will dominate in (7); otherwise, the M-value-based algorithm will be dominant.
IV. Computer Simulations
In this section, we will evaluate the performance of the proposed algorithm through computer simulations with the following assumptions: (a) modulation is 8-PSK with Gray mapping; (b) encoding scheme is rate-1/2 irregular LDPC code with block length 1944; (c) all the results are obtained from 10,000 runs of Monte Carlo simulation and the decoding process is limited to within 20 iterations; (d) for every burst, the frame offset is uniformly distributed and independently chosen from the range [0, Mτ − 1], where Mτ is set to 600.
Apart from the three aforementioned algorithms, we also simulate the EM-based Frame Synchronizer in [4] and Lee Frame Synchronizer in [5] for comparison, where we assume that the Lee algorithm exploits only one frame for burst transmissions.
- 1. Frame Synchronization Error Rate (FSER) Performance
Figure 4 compares the FSER performance of the different frame synchronizers as a function of E b / N 0 . From the figure, we can make the following conclusions:
  • ■ The performance of both the EM-based algorithm and the pilots-assisted correlation algorithm improve as the number of pilot symbolsLincreases.
  • ■ The M-value-based algorithm outperforms the EM-based algorithm for the same simulation conditions, and both algorithms will perform better with increasing decoding iterations.
  • ■ Due to the use of the PN sequence [7], the Lee algorithm performs better than the EM-based and M-value-based methods with one decoding iteration; however, it is not the case whenm= 2 for both of the algorithms.
  • ■ Compared with the EM-based and M-value-based methods, the proposed algorithm can achieve better performance with fewer iterations, leading to lower computational complexity.
  • ■ Benefiting from the soft decoding information, the novel algorithm performs better than the pilots-assisted correlator for the same number of pilots. Moreover, the proposed algorithm with 10 pilots even outperforms the correlator with 20 pilots whenEb/N0> 3 dB. This can be explained by the fact that the soft information is more reliable at moderate/high SNR, which improves the performance of the proposed algorithm significantly.
PPT Slide
Lager Image
FSER comparisons of different frame synchronizers.
- 2. Frame Error Rate (FER) Performance
To make holistic comparisons of the different algorithms, we express the performance of these methods in terms of their FER, as illustrated in Fig. 5 , where the performance curve for the ideal frame synchronization is also shown as a reference.
From Fig. 5 , we can see that the FER performance of all methods is worse than the corresponding FSER performance. This can be explained by the inherent FER of the code itself (with ideal frame synchronization), which constitutes a lower bound for the FER performances of all the frame synchronization algorithms.
PPT Slide
Lager Image
FER comparisons of different frame synchronizers.
With the exception of the Lee algorithm, all of the other methods can approach an FER performance similar to that for perfect frame detection; the new algorithm is more computationally efficient than the EM-based and M-value-based methods and outperforms the pilots-assisted correlator in terms of efficiency (when pilots are used, there is a 10 log 10 (1 + L / N ) loss in bandwidth efficiency, so the loss corresponding to the proposed algorithm and the conventional correlator is 0.06 dB and 0.13 dB, respectively).
Before ending this section, we will compare the five synchronizers from the points of view outlined in Table 1 ; we note that the proposed algorithm and the EM-based algorithm are more flexible than the other three synchronizers in that they can supply a more flexible choice to make use of the pilot symbols or the soft information from the decoder.
Comparisons of different frame synchronization algorithms.
Corr M-value EM Lee Proposed
Complexity Low High High Low Moderate
Performance Good Good Moderate Poor Good
Bandwidth efficiency Low High Low High Moderate
Flexibility Poor Poor Good Poor Good
Note: “Corr” denotes the pilots-assisted correlation algorithm.
V. Conclusion
In this paper, a novel code-aided frame synchronization algorithm for LDPC coded systems has been presented, which combines a conventional pilots-assisted correlator with an M-value-based synchronizer that makes use of soft LLR information from an LDPC decoder. This proposed algorithm is more efficient in bandwidth than conventional pilots-assisted algorithms, and is of lower computational complexity than other code-aided algorithms. Simulation results in the case of a (1944, 972) LDPC coded 8-PSK system show that this novel algorithm coincides with the ideal synchronization in terms of FER performance with only small bandwidth efficiency loss.
This work is supported by the National Natural Science Foundation of China (Project No. 61101097 and No. 61501484).
BIO
Corresponding Author manxin09@163.com
Xin Man is currently a lecturer at the College of Electronic Engineering, Naval University of Engineering, Wuhan, China. In 2007, he received his BS degree in computer science from Sichuan University, Chengdu, China. He then went on to receive his MS and PhD degrees in information science from the National University of Defense Technology, Changsha, China, in 2009 and 2013, respectively. His current research interests are high-data-rate receivers and iterative code-aided synchronization.
zht25@163.com
Haitao Zhai is a PhD candidate at the School of Electronic Science and Engineering, National University of Defense Technology, Changsha, China. He received his BS and MS degrees in information science from the National University of Defense Technology, Changsha, China, in 2006 and 2009, respectively. His current research interest is high-data-rate modulation technology.
ey_zhang@163.com
Eryang Zhang is a professor and PhD supervisor at the School of Electronic Science and Engineering, National University of Defense Technology, Changsha, China. He received his BS degree in information science from the National University of Defense Technology, in 1963. His research interests include wireless communication and network technology; software radio; space communication; and networking.
References
Massey J.L. 1972 “Optimum Frame Synchronization,” IEEE Trans. Commun. 20 (4) 115 - 119    DOI : 10.1109/TCOM.1972.1091127
Gallager R.G. 1962 “Low-Density Parity-Check Codes,” IRE Trans. Info. Theory 8 (1) 21 - 28    DOI : 10.1109/TIT.1962.1057683
Matsumoto W. , Imai H. 2002 “Blind Synchronization with Enhanced Sum–Product Algorithm for Low-Density Parity-Check Codes,” Int. Symp. Wireless Pers. Multimedia Commun. 3 966 - 970
Wymeersch H. 2006 “Code-Aided Frame Synchronization and Phase Ambiguity Resolution,” IEEE Trans. Signal Process. 54 (7) 2747 - 2757    DOI : 10.1109/TSP.2006.874844
Lee D.-U. 2008 “Pilotless Frame Synchronization for LDPC-Coded Transmission Systems,” IEEE Trans. Signal Process. 56 (7) 2865 - 2874    DOI : 10.1109/TSP.2008.917348