Decoding on Adaptively Pruned Trellis for Correcting Synchronization Errors

Yuan Liu, Weigang Chen＊

School of Microelectronics, Tianjin Univeristy, Tianjin, 300072, China

* The corresponding author, email： chenwg@tju.edu.cn

I. INTRODUCTION

Since perfect synchronization is usually hard to maintain, insertions/deletions of bits or symbols, i.e., synchronization errors, occur in the received sequence in many applications[1-2]. In this situation, traditional coding techniques designed only for correcting substitution errors, such as traditional convolutional codes, turbo codes and low-density parity-check (LDPC) codes, cannot be directly used. Codes that can correct synchronization errors include algebraic block codes [3-5],convolutional codes [6-7], turbo codes [8] and concatenated codes [9]. Among these coding techniques, the Davey-MacKay (DM) concatenated code, which uses a watermark inner code and a non-binary LDPC (NB-LDPC) outer code, is the most promising scheme for correcting binary synchronization errors. Furthermore, when non-binary signal is transmitted,the received continuous waveform is first sampled to generate the discrete symbol sequences at the receiver. The synchronization loss can result in non-binary insertions/deletions. The transmission scheme designed in [10], which uses concatenation of the watermark code and the LDPC code, is able to correct non-binary synchronization errors and the additive noise. In this scheme, by executing the forward-backward algorithm [9-13] based on a very large scale trellis, the watermark decoder infers positions of synchronization errors and generates log-likelihood ratios (LLRs) for the outer decoder. By using the soft information output from the watermark decoder, the LDPC decoder corrects residual errors.

However, the watermark decoding algorithm in [10] has relatively high computational complexity, which lowers the attractiveness of the concatenation scheme. The complexity of the algorithm is proportional to the size of the trellis, i.e., the number of states in the trellis.The number of states depends on the code length and channel parameters, i.e., insertion/deletion probabilities. When the code length is long and the channel condition is poor, the scale of the trellis for the watermark decoding expands rapidly and thus the number of computations involved in forward/backward quantities increases rapidly.

Trellis reduction techniques, which can be developed to achieve the computational saving of the watermark decoder in this paper, have been applied to the decoding and designing of traditional codes only for substitutions based on the trellis. In order to achieve the significant reduction of complexity, in the trellis of [14], the one with the smallest metric is kept and the others are discarded from paths reaching the same state. Moreover, trellis pruning method is also employed to search for variable-rate convolutional codes [15-16]. In the approach for cooperative communications introduced by [17], in order to increase the free distance of the convolutional code, one of the partner prune edges from the code trellis by using its knowledge of the other node’s relayed data.

Motivated by the trellis pruning technique,an improved decoding scheme which adaptively prunes the trellis is presented in order to scale down the trellis and decrease the number of states involved in the watermark decoding algorithm. The pruning strategy is designed based on the observation that most of the states have near-zero forward/backward quantities, which have less in fluence to the accuracy of LLRs. Since the accuracy of LLRs affects the error-correcting capability of the concatenated code, near-zero forward/backward quantities have less in fluence to the error-correcting capability. Speci fically, in this pruning process, states are adaptively pruned based on the instant forward/backward quantities. Only states with quantities above a certain threshold are considered while those with quantities below the threshold are neglected.Thus, the computational complexity of the watermark decoding scheme is reduced, since the number of states involved in the computation decreases. Furthermore, we demonstrate that with the optimized scaling factor for the adaptively pruned trellis, the algorithm performs much better than the method in [10] using the same number of states, and nearly achieves the best performance which can be achieved using the method in [10] with much more states.

The rest of this paper is organized as follows. In Section II, we describe the original transmission scheme for correcting non-binary synchronization errors, and then we analyze the computational complexity of the watermark decoding scheme. In Section III, we first describe the adaptively pruning strategy and give an adaptively pruned trellis. Then, we propose the proposed watermark decoding scheme and analyze the computational complexity. In Section IV, simulation results show that significant complexity reduction is obtained by using the proposed scheme at the expense of very slight performance degradation.Finally, in Section V, we draw the conclusions.

A watermark decoding scheme based on an adaptively pruning trellis, which scales down the state space,is presented in this paper.

II. BACKGROUND

2.1 Transmission scheme

Fig. 1 The insertion mode

The decoding trellis is shown in Fig. 3. Define the drift statetiin Fig. 3 to be the number of insertions minus the number of deletions in the channel from the first transmitted symbol x0to the point where the symbol xiis ready to be transmitted. To reduce decoding complexity, the maximum allowed drift is limited totmax. Thus,titakes values in the alphabet Here,tmaxdepends on channel parameters and code length. When a long code is used orPdis high, the scale of the trellis is very large.

Using the forward-backward algorithm [18-19] based on the trellis, the watermark decoder infers the block boundaries of received sequences and provides bit-by-bit log-likelihood ratios (LLRs)lfor the LDPC decoder [10].The LLR sequence is computed as follows.

Fig. 3 The original decoding trellis. The maximum insertion length is 2 at each time

For simplicity, assume the burst length of an insertion event has a maximum insertion lengthI.PcaandQicaare transition probability and conditional probability, respectively.

The backward quantity is de fined as [10]

Initialized byl, the outer decoder corrects misidentified synchronization errors, eliminates effects of additive noise, and produces estimates of information sequences.

2.2 Decoding complexity analysis

III. PROPOSED SCHEME

3.1 Adaptively pruning the trellis

Table I The Computations Needed to Perform the Forward, Middle and Backward Passes in [10]

Fig. 4 Forward quantities of states in the original trellis

Fig. 5 Backward quantities of states in the original trellis

Fig. 6 Adaptively pruned trellis

3.2 Low complexity watermark decoding algorithm

Based on the adaptive truncated trellis, a low complexity watermark decoding algorithm is proposed. In this algorithm, the forward quantity is rewritten as follows.

Similarly, the backward quantity is rewritten as follows.

3.3 Decoding complexity analysis

De fine the ratio

Fig. 7 States of the adaptively pruned trellis for =10

Fig. 8 States of the adaptively pruned trellis for =20

Fig. 9 States of the adaptively pruned trellis for =30

Fig. 10 FERs of the proposed scheme under different

IV. SIMULATION RESULTS

Table II The computations needed to perform the forward, middle and backward passes in the proposed scheme

Forward quantities at the start of the next block are calculated as follows.

Since block boundaries are unknown to the receiver, we initialize the backward pass as follows：

A belief-propagation algorithm in log-domain is used in the LDPC decoder and the maximum number of iterations is set to 20.

First, in order to demonstrate that the proposed scheme can achieve minimum performance loss, frame error rates (FERs) of the is 1/5. The computations needed in the proposed scheme are 1/5 of the original scheme withT=2tmax+1.

Furthermore, in order to demonstrate the efa large number of states having large forward/backward quantities. This decreases the accuracy of LLRs output by the watermark decoder and weakens the error-correcting capability of the concatenated code.

Fig. 11 FERs of the proposed scheme and original scheme with

V. CONCLUSIONS

A watermark decoding scheme based on an adaptively pruning trellis, which scales down the state space, is presented for the forward/backward algorithm in correcting non-binary insertions/deletions. By adaptively truncating the trellis of the watermark decoder according to instant forward/backward quantities, the number of states involved in the computation decreases. As a result, signi ficant reduction in decoding complexity is achieved, considering the forward/backward algorithm occupies most of the computation in the overall decoding.

ACKNOWLEDGEMENTS

This work was supported in part by National Natural Science Foundation of China(61101114, 61671324) and the Program for New Century Excellent Talents in University(NCET-12-0401).

[1] H. Mercier, V. K. Bhargava and V. Tarokh, “A survey of error-correcting codes for channels with symbol synchronization errors,” IEEE Communications Surveys & Tutorials, vol. 12, no. 1, pp.87-94, 2010.

[2] Xiaopeng Jiao and M. A. Armand, “Soft-input inner decoder for the Davey-MacKay construction,” IEEE Communications Letters, vol. 16, no.5, pp. 722-725, May, 2012.

[3] J. D. Ullman, “Near-optimal, single-synchronization-error- correcting code,” IEEE Transactions on Information Theory, vol. 12, no. 4, pp. 418-424, April, 1966.

[4] A. S. J. Helberg and H. C. Ferreira, “On multiple insertion/deletion correcting codes,” IEEE Transactions on Information Theory, vol. 48, no. 1,pp. 305-308, January, 2002.

[5] T. G. Swart and H. C. Ferreira, “A note on double insertion/deletion correcting codes,” IEEE Transactions on Information Theory, vol. 49, no. 1,pp. 269-273, January, 2003.

[6] M. F. Mansour and A. H. Tew fik, “Convolutional decoding in the presence of synchronization errors,” IEEE Journal on Selected Areas in Communications, vol. 28, no. 2, pp. 218-227, February, 2010.

[7] V. Buttigieg and N. Farrugia, “Improved bit error rate performance of convolutional codes with synchronization errors,” in Proc. IEEE International Conference on Communications, London,UK, June, 2015, pp. 4077-4082.

[8] M. F. Mansour and A. H. Tew fik, “A turbo coding scheme for channels with synchronization errors,” IEEE Transactions on Communications, vol.60, no. 8, pp. 2091-2100, August, 2012.

[9] M. C. Davey and D. J. C. Mackay, “Reliable communication over channels with insertions, deletions, and substitutions,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 687-698,February, 2001.

[10] R. Yazdani and M. Ardakani, “Reliable communication over non-binary insertion/deletion channels,” IEEE Transactions on Communications,vol. 60, no. 12, pp. 3597-3608, December, 2012.

[11] E. A. Ratzer, “Marker codes for channels with insertions and deletions,” Annals of Telecommunications, vol. 60, no, 1-2, pp. 29-44, 2005.

[12] Tong Wu and M. A. Armand, “The Davey-MacK-ay coding scheme for channels with dependent insertion, deletion and substitution errors,” IEEE Transactions on Magnetics, vol. 49, no. 1, January, 2013.

[13] Feng Wang, D. Fertonani and T. M. Duman,“Symbol-level synchronization and LDPC code design for insertion/deletion channels,” IEEE Transactions on Communications, vol. 59, no. 5,pp. 1287-1297, May, 2011.

[14] J. C. Dany, J. Antoine, L. Husson, et al, “Low complexity algorithm for the decoding of convolutional codes of any rate,” in Proc. IEEE International Conference on Communications, Paris,France, June, 2004, pp. 547-551.

[15] J. Sun, I. S. Reed, H.E. Huey, et al, “Pruned-trellis search technique for high-rate convolutional codes,” IEE Proceedings E - Computers and Digital Techniques, vol. 136, no. 5, pp. 405-414,September, 1989.

[16] A. Katsiotis, P. Rizomiliotics and N. Kalouptsidis,“Flexible convolutional codes: variable rate and complexity,” IEEE Transactions on communications, vol. 60, no. 3, pp. 608-613, March, 2012.

[17] S. V. Maiya and T. E. Fuja, “Cooperation via trellis pruning,” IEEE Transactions on Communications,vol. 59, no. 6, pp. 1563-1569, June, 2012.

[18] J. A. Briffa, H. G. Schaathun and S. Wesemeyer,“An improved decoding algorithm for the Davey-MacKay construction,” in Proc. IEEE International Conference on Communications, Cape Town, South Africa, May, 2010, pp. 1-5.

[19] Xiaopeng Jiao and M. A. Armand, “Interleaved LDPC codes, reduced-complexity inner decoder and an iterative decoder for the Davey-MacKay construction,” in Proc. IEEE International Symposium on Information Theory, St. Petersburg,Russia, July, 2011, pp. 742-746.

[20] Xiaoyu Hu, E. Eleftheriou and D. Arnold, “Regular and irregular progressive edge-growth Tanner graphs,” IEEE Transactions on Information Theory, vol. 51, no. 1, pp. 386-398, January, 2005.