Codebook and marker sequence design for synchronization-correcting codes

Abstract

We propose a construction based on synchronization and error-correcting block codes and a matched marker sequence. The block codes can correct insertion, deletion and substitution errors within each codeword. The marker sequence allows the decoder to maintain synchronization at codeword boundaries even at high error rates. An upper bound is given for the performance of these codes over a channel with random substitutions and synchronization errors. It is shown that the performance is largely dependent on the code's minimum Levenshtein distance. The performance of these codes is verified by simulation and compared to published results. In concatenation with a non-binary outer code we obtain a significant improvement in frame error rate at similar overall code rates.