Designing efficient codes for synchronization error channels
Authors:
- 1 June 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1548615X,p. 1-9
Abstract
For communications and networking channels, coding techniques are widely used to correct errors in corrupted messages. The "Quality of Protection" (QoP) that can be provided via error correction directly affects the "Quality of Service" (QoS) experienced by users. The errors are commonly assumed to be substitution or erasure errors. Such systems rely on perfect synchronization so that no bit is deleted and no extra bit is inserted. However, in a system without the presence of perfect synchronization, special coding algorithms may be required to correct potential insertion or deletion errors in transmitted messages. Especially for systems suffering from frequent loss of synchronization, packets may require many retransmissions to guarantee reliable communication. Such schemes may become too expensive to be practical. In this paper, we propose a new synchronization channel error model based on the observations from current communication systems. In this model, the channel introduces at most t synchronization errors in each run of the transmitted sequence. We present run-length limited permutation codes capable of correcting synchronization errors based on this channel error model. Compared to previously developed codes, our codes have the advantage of correcting frequent synchronization errors, and therefore they are suitable for disruptive network channels that suffer severe synchronization failures.Keywords
This publication has 10 references indexed in Scilit:
- Tight asymptotic bounds for the deletion channel with small deletion probabilities2010
- On the deletion channel with small deletion probability2010
- Novel bounds on the capacity of binary channels with deletions and substitutions2009
- Codes for Deletion and Insertion Channels with Segmented Errors2007
- Capacity Upper Bounds for the Deletion Channel2007
- On single-deletion-correcting codes2002
- Construction of fixed-length insertion/deletion correcting runlength-limited codesIEEE Transactions on Information Theory, 1994
- Interactive Communication of Balanced Distributions and of Correlated FilesSIAM Journal on Discrete Mathematics, 1993
- On runlength codesIEEE Transactions on Information Theory, 1988
- Near-optimal, single-synchronization-error-correcting codeIEEE Transactions on Information Theory, 1966