Detecting Deletions and Insertions for Binary Segmented Channels

An insdel refers to an insertion or a deletion. In this paper, we consider the problem of constructing error-detecting codes for segmented single-insertion/-insdel channel, where the channel's input bit stream is partitioned into segments of length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex>. The value of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> is known to the receiver but the segment boundaries of the receiving string are not. We propose a structure where prefixes and suffixes are the sole additions. In this way, we are able to construct new codes that can detect segmented single-insertion/-insdel errors with redundancy 4 bits and 8 bits per segment, respectively. Moreover, our codes have linear-time encoding/detecting algorithms.