An Iterative Decoding Scheme for Davey-MacKay Construction

Yuan Liu, Weigang Chen＊

School of Microelectronics, Tianjin Univeristy, Tianjin 300072, China

I. INTRODUCTION

In communication systems, loss of synchronization may introduce synchronization errors,i.e., symbol insertions/deletions, into the received sequences. Since insertions/deletions may cause the length of received sequences to be longer or shorter than transmitted sequences, traditional coding techniques that are designed only for correcting substitution errors cannot be directly applied [1].

Codes that can correct synchronization errors have been comprehensively surveyed in[2]. These codes include algebraic block codes[3], convolutional codes, spatially-coupled(SC) codes [4], time-variant block codes [5, 6,7] and concatenated codes [8]. Among these coding techniques, the Davey-MacKay (DM)construction [8], which uses the watermark inner code and the non-binary low-density parity-check (NB-LDPC) outer code, is the most promising candidate. In this scheme, the watermark decoder recovers the synchronization and then produces symbol-by-symbol log-likelihood ratios (LLRs) for the LDPC decoder. The LDPC decoder, which is initialized using LLRs, corrects residual errors from the watermark decoder.

Some researchers generalized the DM construction for other applications, such as in the speech watermarking system [9], where synchronization poses a more acute challenge than in the traditional communication system.By adopting the DM construction, significant improvement is achieved in the speech watermarking. In [5-7], time-varying block codes were designed, which generalized a number of previous synchronization error-correcting codes. Moreover, the maximum a posteriori(MAP) decoder was used and an iterative scheme was considered in [5] to achieve improved performance compared with the DM construction. The DM construction was also adapted to the insertion, deletion, substitution and the additive white Gaussian noise(IDS-AWGN) channel. Then, a soft-input watermark decoder, which was a modification of the original decoder for the DM construction,was developed to correct those errors [10].Furthermore, an iterative decoder for the DM construction over the IDS-AWGN channel was proposed in [11] to improve the performance.In terms of the code construction, a construction method for the watermark was introduced in [12], which achieves performance improvement.

An iterative decoding scheme, in which the estimated average error rate and the estimated transmitted codeword from the outer decoder are fed back into the inner decoder, is presented to improve the performance of the DM construction.

Considering that the original DM construction over the IDS channel is widespreadly used, the improvement of this scheme is investigated in this paper. The watermark decoder for the original DM construction in [8]only knows the average density of the sparse code for the transmitted codewords. Absence of the specific transmitted codeword information decreases the accuracy of the forward/backward quantities, which determine the capability of the watermark decoder to identify synchronization errors. In [13], an alternative symbol-level inner decoding algorithm is presented, which improves the performance by considering the actual transmitted codebook.Furthermore, an iterative decoder based on the symbol-level inner decoder is presented in[14], and the improvement achieved by using the iterative decoding scheme comes at a price of only a small increase in complexity.

In this paper, an iterative decoding scheme based on the bit-level inner decoder is proposed to improve the performance of the DM construction. The estimated average bit error rate and the specific codeword from the LDPC decoder are fed back into the watermark decoder to update branch quantities of the decoding trellis in the subsequent iteration.The refined branch quantities yield accurate forward/backward quantities and reliable soft output LLRs that are utilized by the LDPC decoder to obtain the new estimates of the sparse LDPC codewords. As the iteration increases,the capability of identifying synchronization errors increases, and the number of residual errors and the number of bit errors in the estimated LDPC codeword decrease. Little prior knowledge of the transmitted codewords is required at the start of the iterations. As a result,the proposed iterative decoding scheme outperforms the DM construction by iteratively optimizing the synchronization and error-correcting capability.

The rest of this paper is organized as follows. In Section II, we describe the synchronization error-correcting concatenated scheme,i.e., the DM construction. In Section III, a detailed description of the proposed iterative decoding scheme and the explanation why this method improves the performance are presented. Simulation results are given in Section IV to show the performance gain achieved by the proposed method. In this section, we also analyze the effect of the feedback information on the performance of the proposed method and demonstrate that the setting of the feedback information in this paper is reasonable. Finally, in Section V, we draw the conclusion.

II. DM CONSTRUCTION

2.1 System model

The DM construction, which includes a watermark inner code and a sparsified NB-LDPC outer code, is illustrated in figure 1. The watermark code is employed to correct insertions/deletions and recover the synchronization. The NB-LDPC code [15-18], which is characterized by its sparse parity check matrix defined over Galois field GF(q=2k), is employed to correct residual errors. Using the NB-LDPC code, the information sequence m of lengthKsymbols is encoded into a codeword d with the codelength ofNsymbols. d is then mapped into a sparse code s, where the subsequencewith lengthnhas the minimum average densityf, 0≤i＜N. An example of the one-to-one mapping μ: di→siis shown in Table I. By adding s modulo 2,to the inner watermark code w with the code length ofNc, the transmitted bit vector t is generated, where w is the binary random sequence and is constructed using a uniform random bit generator. The block length of the transmitted sequence t isNc=nNand the overall code rate

Each bittiis sent to the binary IDS channel[3] with an insertion probabilityPi, deletion probabilityPdand transmission probabilityPt=1?Pi?Pd. Then, the transmitted bittiis substituted with the probabilityPs.

By comparing the received sequence r with w, the watermark decoder computes the symbol-by-symbol LLRs l. Finally, by employing l, the NB-LDPC decoder generates the estimate of the information sequence.

2.2 Inner decoder

The received sequence r can be regarded as the observation sequence generated by the hidden Markov model (HMM). The synchronization drifts are the hidden states of the HMM, and the synchronization errors affects the state transition. Then, using the forward-backward algorithm [8, 19-20], the watermark decoder infers the block boundary and provides symbol-by-symbol LLRs l for the NB-LDPC decoder [8]. We assume thatP(di= λ) =P(di=0), and computelias

wheresymbol,Thej-th synchronization driftxjequals the number of insertions minus the number of deletions, whentjis ready to be transmitted, 0≤j＜Nc.xjtakes values

wherexmaxis the maximum allowed drift. In

is the probability that the drift at thej-th point isyand that the subsequenceagrees with r. The maximum length of consecutive insertions isI. Similarly, the backward quantity [8]

is the probability of receiving (rj+y,…,rNc+5xmax)given a drift ofyat thej-th point, where(Nc+ 5xmax) is the end of the sliding-window decoding.Pab=P(xj+1=b|xj=a) is the transition probability andQab,jis the conditional probability of receiving (rj+a,… ,rj+b) given the transition (xj=a) to (xj+1=b). The computation of the branch quantityPabQab,jis given as follows [8].

Fig. 1. Overview of the DM construction.

Table I. The one-to-one mapping μ: di → si (GF(16), n=5).

where γ is the probability with (b?a+1)channel deletions, and β is the probability with (b?a) channel insertions.is the effective substitution rate, i.e., the probability that a received bit does not equal to the corresponding watermark bit.

After performing the inner decoding, the outer decoder, which is initialized using l,corrects misidentified synchronization errors and produces estimates of the information sequences.

III. ITERATIVE DECODING SCHEME

In the DM construction, the bit ‘1’ in the sparse code, which is unknown to the inner decoder, introduces a random independent substitution. The absence of the knowledge of the sparse code decreases the reliability of forward/backward quantities, which affects the ability of the watermark code to identify the position of synchronization errors and the quality of probability information propagated to the outer decoder. As a result, the capability of the inner decoder to recover the synchronization is limited.

In this paper, we attempt to take into account estimates of transmitted sparse codewords, and present an iterative decoding scheme. By adaptively obtaining more accurate information about the codewords, the reliability of forward/backward quantities and the synchronization ability of the inner decoder can be improved. Finally, the overall decoding error probability of the system decreases.

The terms w andPfin the computation of branch quantityPabQab,jallow the inner decoder to admit feedback information, which enables us to use iterative decoding. We assume that the watermark code and the estimate of the sparse codeareknown to the inner decoder, wherehas aone-to-one mapping to, andis updated iteratively. Thus, w in(4) is replaced by t(δ)= w, where,δis the global iteration number. Based on this assumption, the substitutions in r include some substitutions introduced byand others introduced by the channel. Specifically, if the received bit is not equal totakes the error value or thej-th transmitted bit is substituted by a channel substitution.Therefore, in theδ-th iteration, the effective bit substitution rate is calculated as follows.

In (5),f(0)is the average sparse density ifδ=0, andf(δ)is the average estimated error probability that thej-th actual sparse bit does not equal toifδ＞0, wherej=ni+l. With the increasing ofδ, the number of the average estimated errors in the estimated codeword decreases. For δ＞ 0, sincef(δ)is unknown to the decoder, we assume that the probability decreases by a constant shrinking factor in each iteration. Thus,

where α is the shrinking factor. In this paper,α is set to 1/δmax. In theδ-th global iteration, the computation ofis rewritten as follows.

In theδ-th global iteration, only forward and backward quantities are updated, the values of the middle quantities remain unchanged. The forward quantity in theδ-th global iteration is described as follows.

Similarly, the backward quantity is computed as follows.

Then, in theδ-th iteration, the symbol-by-symbol LLR is computed as

Figure 2 illustrates the updating procedure for the iterative decoding method. The message is exchanged between the decoding trellis diagram of the inner decoder and the Tanner graph of the outer decoder. In the first iteration,is set to all-zero andf(0)is equal to the average density of.The watermark decoder compares r with t(0), and infers the position of insertions/deletions. Then, the watermark decoder outputs likelihoods for the LDPC decoder. After performing the LDPC decoding, the estimated NB-LDPC codewordis generated, wherehas a one-one correspondence with. Bothand the updatedf(1)are fed back into the inner decoder to update the branch quantityin the iterative decoding scheme. The forward and backward quantities, i.e.,F(1)(y) andB(1)(y), are updated. Then, l(1)is obtained and is used by the LDPC decoder to output. Asδincreases, bit errors indecrease.

When the proposed iterative decoder is employed, the computation of the decoder will increase. Since the computation structure of the inner and outer decoder are not modified and only the effective substitution rateand the reference sequence are updated, the computation needed in the proposed iterative scheme is almost δ*times as much as the computation in the original DM decoding scheme, where δ*is the average number of global iteration. It will be demonstrated later that δ*is quite small for the proposed iterative decoding scheme in Section IV.

Fig. 2. Illustration of the updating procedure for the iterative decoding scheme.

IV. SIMULATION RESULTS

In this part, simulations are performed to verify the iterative scheme. Watermark sequences used in the simulation are binary random sequences. The parameters of the concatenated code are described as follows. The NB-LDPC code is a (999, 888) LDPC code over GF(16).N=999,n=5. The rate of the watermark code isk/n=4/5.f(0)=0.3125. The overall code length and code rate of the DM construction are 4995 and 0.71, respectively.Pi=Pd. The decoding simulation parameters are set as follows. The maximum insertion length is limited toI=2.xmaxis set to be several times larger than the standard deviation of the synchronization drift over one block length [8]. In this paper,xmax=5. The initial drift of thefirst transmitted block is assumed to be zero.F0(x)=1 ifx=0 andF0(x)=0 otherwise. By using the sliding-window decoding, the forward quantities at the start of the next transmitted block are calculated as follows.

Table II. Simulation settings.

Fig. 3. Performance of the proposed iterative decoding scheme under different δmax.

where ε is a normalized constant. The block boundaries are not known at the receiver. The initial values for the backward quantities at position (Nc+ 5xmax) are set to equal probability, i.e., 1/(2xmax+ 1) as follows. The log-domain sum-product algorithm with a maximum local iteration number of 20 is employed in the LDPC decoder. The local iteration number is recorded when the log-domain sum-product algorithm is stop, which means that the codeword is decoded successfully or the iteration number reaches the maximum setting. The maximum global iteration numberδmax, which is the rounds of feeding back the decision information from the outer decoder to the inner decoder, is set to 5, 10, 20, and 30 respectively. The iterative decoding simulation stops when the codeword is decoded successfully orδ=δmax. For conciseness, we list all the simulation parameters in Table II.

Firstly,figure 3 shows the frame error rates(FERs) of the proposed iterative decoding scheme withδmaxfrom 5 to 30 atPs=0 andPs=0.003, respectively. As observed in figure 3, the system with the iterative decoder performs better than the non-iterative counterpart,i.e., the DM construction. It is also clear that the performance gain provided by the proposed scheme does not increase significantly withδmaxincreasing. Thus, we can setδmaxto be a quite small value. In the following, the conclusion will also be verified using the average number of iterations.

Secondly, in figure 4, results of the iterative decoding scheme are given for two settings off(δ)in order to demonstrate the effect off(δ)on the performance gain. It can be observed that the iterative scheme can achieve significant performance gain by using the decreasingf(δ). Furthermore, we also provide the simulation result using constant densityf(δ)=0.001.It can be observed that when using the constant density, iterative scheme can obtain nearly identical performance as the scheme using decreasing density in (6). The method is more convenient for implementation. Considering thatf(δ)decreases in each iteration, it is reasonable to defineshown in (6).

Thirdly, figure 5 illustrates the average number of global iterations δ*for the proposed iterative decoding scheme whenPs=0.003 andPs=0. Simulation stops when the codeword is decoded successfully or the maximum global iteration number of 30 is reached.Figure 5 shows that the average number of global iterations δ*is quite small. Thus, the performance gain achieved by the iterative scheme comes at the price of only a small increase in complexity compared with the DM construction, since computation needed in the proposed scheme are δ*times as much as the DM construction. Moreover, small δ*reveals that the convergence speed of the proposed global iterative scheme is fast, and the average decoding complexity is low. Thus,δmaxcan be set to be a small value and adjusted according to the channel condition.

Fourthly, we demonstrate the synchronization error correction capability of the inner decoder. Actually, the final synchronization accuracy can be evaluated by FERs of the system, which is demonstrated in figure 3. The lower the FER curve is, the better the synchronization performance becomes. Moreover, we also compare the ratio of symbols whose drift position is detected unsuccessfully to the total symbols by using the forward-backward algorithm with the hard-decision in the simulation.As shown in figure 6, by using the proposed iterative decoding scheme, the ratio of the unsuccessfully detected drift position reduces,which means the synchronization accuracy is improved. The gain obtained is small, because the hard-decision results are used and one insertion/deletion may cause multiple symbols drift. However, thefinal overall FER decreases with the iterations significantly since the inner decoder provides the soft probability information for the LDPC decoder.

Fig. 4. Results of the proposed iterative decoding scheme for f()δ=0.001 and f()δ in (6), δmax=5.

Fig. 5. Average number of iterations for the proposed iterative decoding scheme when Ps=0.003 and Ps=0.

Fig. 6. The ratio of symbols whose drift position unsuccessfully detected to the total symbols by using the forward-backward algorithm with the hard-decision in the simulation, Ps=0.003, δmax=20.

Fig. 7. Lower bounds using the iterative decoding scheme under different δmax,Ps=0.

Finally, the lower bounds, obtained using the iterative decoding scheme under different global iteration numberδmax, on the capacity of an insertion/deletion channel without substitution is illustrated in figure 7. According to[8], the lower boundClis obtained by multiplyingCeby the rate of the watermark code,whereCeis the lower bound on the capacity of the effective channel seen by the LDPC code after watermark decoding, andCe=1?H.His the average entropy ofP(di|r) from the watermark decoder.

As shown in figure 7, the iterative decoder enables the communication at the rate greater than the non-iterative system.

V. CONCLUSIONS

An iterative decoding scheme, in which the estimated average error rate and the estimated transmitted codeword from the outer decoder are fed back into the inner decoder, is presented to improve the performance of the DM construction. Furthermore, the effect using different feedback information on the overall synchronization error-correcting performance is analyzed. Compared with the traditional DM construction, the proposed iterative decoding scheme can increase synchronization accuracy and achieve performance gain at the expense of a small increase in complexity.

ACKNOWLEDGEMENTS

This work was supported in part by National Natural Science Foundation of China(61671324) and the Director’s Funding from Qingdao National Laboratory for Marine Science and Technology.

[1] M. Rahmati, T. M. Duman, “Bounds on the capacity of random insertion and deletion-additive noise channels,”IEEE Transactions on Information Theory,vol. 59, no. 9, 2013, pp. 5534-5546.

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

[3] V. Guruswami, C. Wang, “Deletion codes in the high-noise and high-rate regimes,”IEEE Transactions on Information Theory,vol. 63, no. 4,2017, pp. 1961-1970.

[4] R. Goto, K. Kasai, H. Kaneko. “Coding of insertion-deletion-substitution channels without markers,” Proceedings ofIEEE International Symposium on Information Theory,Barcelona,Spain, 2016, pp. 635 – 639.

[5] J. A. Briffa, V. Buttigieg, S. Wesemeyer,“Time-varying block codes for synchronization errors: maximum a posteriori decoder and practical issues,”IET Journal of Engineering, vol.2014, no. 1, 2014, pp. 1-12.

[6] V. Buttigieg, J. A. Briffa, “Improved code construction for synchronization error correction,”Proceedings of International ITG Conference on Systems, Communications and Coding, Hamburg, Germany, 2015, pp. 1-6.

[7] J. A. Briffa, V. Buttigieg, “A MAP decoder for TVB codes on a generalized Iyengar–Siegel–Wolf BPMR Markov channel model,”IEEE Transactions on Magnetics,vol. 52, no. 2, 2016, pp. 1-9.

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

[9] D. J. Coumou, G. Sharma, “Insertion, deletion codes with feature-based embedding: a new paradigm for watermark synchronization with applications to speech watermarking,”IEEE Transactions on Information Forensics and Security,vol. 3, no. 2, 2008, pp. 153-165.

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

[11] Xiaopeng Jiao, Jianjun Mu, Rong Sun, “Iterative decoding for the Davey-MacKay construction over IDS-AWGN channel,”IEICE Transactions on Fundamentals, vol. E96-A, no. 5, 2013, pp. 1006-1009.

[12] P. Nguyen, M. A. Armand, Tong Wu, “On the watermark string in the Davey-MacKay construction,”IEEE Communications Letters,vol. 17,no. 9, 2013, pp. 1830-1833.

[13] J. A. Briffa, H. G. Schaathum, S. Wesemeyer,“An improved decoding algorithm for the Davey-MacKay construction,”Proceedings of IEEE International Conference on Communications,Cape Town, South Africa, 2010, pp. 1-5.

[14] Xiaopeng Jiao, M. A. Armand, “Interleaved LDPC codes, reduced-complexity inner decoder and an iterative decoder for the Davey-MacKay construction,”Proceedings of IEEE International Symposium on Information Theory,Saint Petersburg, Russia, 2011, pp. 747-751.

[15] J. O. Lacruz, F. Garcia-Herrero, M. J. Canet,et al. “High-performance NB-LDPC decoder with reduction of message exchange,”IEEE Transactions on Very Large Scale Integration Systems,vol. 24, no. 5, 2016, pp. 1950-1961.

[16] Weigang Chen, C. Poulliat, D. Declercq,et al.,“Non-binary LDPC codes defined over the general linear group: finite length design and practical implementation issues,”Proceedings of IEEE the 69th Vehicular Technology Conference,Barcelona, Spain, 2009, pp. 1-5.

[17] F. Steiner, G. Bocherer, G. Liva, “Protograph-based LDPC code design for shaped bit-metric decoding,”IEEE Journal on Selected Areas in Communications,vol. 34, no. 2, 2016,pp. 397-407.

[18] J. O. Lacruz, F. Garcia-Herrero, M. J. Canet,et al.,“Reduced-complexity nonbinary LDPC decoder for high-order Galoisfields based on trellis minmax algorithm,”IEEE Transactions on Very Large Scale Integration Systems,vol. 24, no. 8, 2016,pp. 2643-2653.

[19] Tong Wu, M. A. Armand, “The Davey-MacKay coding scheme for channels with dependent insertion, deletion and substitution errors,”IEEE Transactions on Magnetics,vol. 49, no. 1, 2013,pp. 489-495.

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