Research On Synchronization Error-Correcting Codes

Synchronization errors, in forms of insertions and deletions in bit or symbol levelin the received sequences, occur in many communication and recording systems, suchas differential pulse-position modulation (DPPM) and bit patterned magneticrecording (BPMR), and could have disastrous effects on these technologies. Sincechannels with synchronization errors have memory, error-correcting codes designedfor substitution-only channels are not applicable. Researchers have proposed a varietyof coding schemes to tackle with this problem. One of these schemes is aconvolutional coding scheme based on a modified trellis diagram, which can correctinsertion, deletion, and substitution errors simultaneously. However, this scheme iseffective only when the convolutional block boundaries are known to the receiver,which cannot be guaranteed in many practical systems. Therefore, high effectivedecoding schemes to correct errors and to identify block boundaries for convolutionalcodes are designed in this thesis.To deal with the problem that the convolutional coding scheme cannot identifyblock boundaries, two decoding algorithms, bidirectional Viterbi algorithm (BVA)and modified Log-MAP algorithm, are proposed to identify block boundaries and tocorrect errors. The proposed algorithms can inherently identify block boundarieswhile correcting errors, thus no extra computation steps are needed forsynchronization process. Moreover, no changes to the legacy convolutional codingsystems are required. Simulation results show that, the proposed algorithms areeffective even when the block boundaries are unknown to the receiver. An applicationin a DPPM system proves the effectiveness.Furthermore, to improve the performance of the convolutional coding scheme, aniterative decoding scheme for Reed-Solomon (RS) concatenated convolutional codesis proposed. The inner decoder, which is the convolutional decoder, can getsynchronization information of the received sequences and correct errors, whereas theouter decoder, i.e. the RS decoder, can correct bursts of substitution errors caused bythe channel and imperfect synchronization of the inner decoder. Moreover, the outputof the outer decoder can be used to initialize the modified trellis diagram so that iterative coding gains can be achieved. Simulation results show that, this proposedscheme can have a significant gain over the convolutional coding scheme.Above all, this thesis proposes decoding schemes for convolutional codes in thepresence of synchronization and substitution errors when the block boundaries are notknown to the receiver. Furthermore, an iterative decoding scheme is designed forcorrecting synchronization and substitution errors.