Research On Generalized Low Density Codes For Synchronization Errors

Synchronization errors, in forms of insertions and deletions in bit or symbol level in the received sequences, are very common in many communication and recording systems, such as magnetic recording and multimedia digital watermarking systems. A single uncorrected synchronization error can have catastrophic consequences by causing a huge burst of substitution errors lasting until the system is resynchronized. Traditional error correcting codes can not deal with this type of errors and researchers designed a kind of synchronization error correcting codes. Davey and Mackay proposed a concatenated coding scheme which is named as DM construction aiming at random synchronization error corrupting channels. The coding scheme can correct synchronization errors and substitution errors at the same time and is thought as the most promising coding scheme. However, this concatenated coding scheme adopts the non-binary Low-Density Parity-Check(LDPC) code as its outer code, the encoding complexity of which is large. Therefore, for the outer code of the DM construction, we designed a kind of non-binary LDPC codes, which can be encoded in lower complexity and viewed as generalized low-density codes for each row of the parity matrix has the same non-zero entries.Firstly, we designed two non-binary LDPC codes with low encoding complexity using a semi-random construction method. In the progress, we use progressive-edge-growth(PEG) algorithm and quasi-cyclic expansion to construct the parity check matrix of binary LDPC and use an optimized non-zero entry selection method to configure the non-zero entries. The optimized non-zero entry selection method tries to avoid the formation of small circles and decreases the smallest weight of the codes. Therefore the performance of the designed non-binary LDPC codes gets improved. Moreover, an efficient encoding method is presented by modifying the parity check matrix to that having the same form as repeat accumulate codes. This type of non-binary LDPC codes have the same group of non-zero entries for each row and thus are special generalized low density codes.Then we use the designed non-binary LDPC as the outer code of DM construction to correct both substitutions errors and synchronization errors. This optimized scheme employs the watermark code as its inner code to identify the position of synchronization errors to help recover synchronization, and employs the designed non-binary LDPC codes as its outer code to correct substitutions errors and synchronization errors which is decoded with belief propagation algorithm. We check this code scheme in the Binary Insertion-Deletion-Substitution(BIDS) channel and the results show that it has powerful error correcting ability. Meanwhile, the encoding complexity gets reduced.