Error-Correcting Codes with Large Field Size under Non-Binary Segmented Burst Deletion/Insertion Channels and Unknown Codeword Boundaries

In this paper, we construct non-binary codes of length N which correct errors under a non-binary segment- N maxburst- D deletion and maxburst- S insertion (NB-SBDI( N, D, S )) channel without knowing the codeword boundaries. In this NB-SBDI( N, D, S ) channel, at most a single non-binary burst (a block of consecutive bits/symbols) of deletions or insertions of length up to D or S , respectively, exists in a block of N consecutive non-binary symbols. One code named as BM-DB-MDS consists of a maximum distance separable (MDS) code, a block of periodic de Bruijn (DB) symbols, and a block of proposed periodic binary marker (BM) patterns with a period of S + D + 2. The other code called BM-MDS code consists of a BM code and an MDS code. We show that the rates of BM-DB-MDS and BM-MDS codes achieve λ/λ+1 (1 - 1/2 t ), λ ∈ N + and 1 - 1/ t , respectively, when N → +∞, where λ represent the MDS code shortening factor, and 1/ t is the rough proportion of the maximum length of burst deletions or insertions allowed in a code.