Investigation On Graph-Based Decoding For Correcting Synchronization Errors

In digital communication systems, synchronization is an important condition to provide reliable transmissions. For the channels with synchronization errors, the Davey-Mackay(DM) construction where a watermark code is used as the inner code and a Non-Binary Low-Density Parity-Check(NB-LDPC) code is used as the outer code is the very efficient scheme, which can correct synchronization errors and substitution errors simultaneously. For the concatenated schemes based on the watermark code and a special class of NB-LDPC code, an improved decoding algorithm is proposed in this thesis.To deal with the problem that the encoding complexity of NB-LDPC in the concatenated schemes is high, a special kind of NB-LDPC codes with lower encoding complexity is applied to the DM construction, which could reduce the encoding complexity significantly. Furthermore, for this kind of NB-LDPC codes, an improved algorithm is proposed. In the presented algorithm, the parity check matrix of NB-LDPC code is divided into two submatrices, BP algorithm and Log-MAP algorithm are used to decode the two submatrices respectively. Simulation results show that, compared to the BP algorithm, the proposed algorithm have a significant gain under a few iteration times.Furthermore, the NB-LDPC code with low encoding complexity and the proposed algorithm are used as the outer code and the outer decoder for DM construction respectively. The complexities of the proposed algorithm and BP algorithm are analyzed. The proposed algorithm needs fewer iteration times compared with the standard BP algorithm, thus it needs the overall optimization on complexity considering the increased complexity in each iteration. Simulation results show that, the DM construction which uses the non-binary cycle codes as the outer code can correct synchronization errors and substitution errors effectively.