Research On Low-Complexity Schemes For Correcting Symbol-Level Insertions/Deletions

Symbol synchronization is very important in the communication system.The random insertions/deletions errors in the received sequences may cause the system cannot work.Under the insertions/deletions channel with the additive noise,researchers proposed a concatenated coding scheme,which has a good performance.However,the decoding complexity of the synchronization code is too high.In order to overcome the problem above,the main objectives of this thesis include the following three aspects.First,two inner decoding algorithms with low complexity are proposed,which are hard decision forward-backward inner decoding algorithm and the inner decoding algorithm based on dynamic programming.The hard decision forward-backward inner decoding algorithm simplifies the process of computing the likelihood information and then reduces the computational complexity of the standard forward-backward inner decoding algorithm.By using the dynamic programming,the inner decoding algorithm locates the synchronization errors by calculating the weight levenshtein distance and backtracking.The simulation results show that the two proposed algorithms have some loss of performance compared with the standard forward-backward inner decoding algorithms,but the complexity is lower and the practicability is stronger.Secondly,considering that the insertions/deletions probability of the actual channel is small,a new inner decoding algorithm based on the simplified grid-graph dynamic programming is presented.Through limiting the maximum drift caused by insertions/deletions,the algorithm simplifies and redefines the original trellis of the inner decoding algorithm based on the dynamic programming,thus reduces the memory usage and computations.Simulation results show,although the new algorithm has some performance loss,but the complexity is lower.Furthermore,the complexity and relevant influencing factors of the low complexity algorithm for detecting insertions and deletions are analyzed in this paper.Firstly,the complexity of the proposed inner decoding algorithms is analyzed and compared.Secondly,we analyze the characteristics of the insertions/deletions location found by the inner decoding algorithms,the simulation results show,using the success rate of finding insertions/deletions location in the case of allowing certain deviation to characterize the performance of inner decoding algorithm is more reasonable.At last,we analyze the performance of concatenation coding scheme when using the pseudo-random sequence and short-period sequence as the watermark,the simulation results show,the performance of the concatenated codes using the pseudo-random sequence as the watermark is better.