Correcting Non-Binary Burst Deletions/Insertions with De Bruijn Symbol-Maximum Distance Separable Codes

We propose a deterministic decoding scheme to correct a block of deletions/insertions of length up to N-K=[0.5πL] -1 with a high probability for the de Bruijn symbol-maximum distance separable (DB-MDS (N,K,πL) codes. The DB-MDS (N,K,πL) codes are constructed by combining the MDS (N,K) (maximum distance separable) codes and the de Bruijn (DB) symbol sequence with both the period and field size being πL. The type, length, and positions of burst errors are first guessed and checked and the corrupted DB-MDS code symbol sequence is synchronized, then the errors introduced in the synchronization stage are corrected by the MDS code component of the DB-MDS code. We provide the closed form of the decoding failure for the proposed synchronization algorithm, which decreases as the code length N increases.