On the construction of perfect deletion-correcting codes using design theory (Q1894266)

Let \(F\) be an alphabet; if \({\mathbf x}\in F^n\) and \({\mathbf y}\in F^m\) are words over \(F\) with \(n\leq m\), then we call \({\mathbf x}\) a subword of \({\mathbf y}\) if \({\mathbf x}\) can be obtained from \({\mathbf y}\) by deleting \(m-n\) symbols (anywhere in the word) or, equivalently, if \({\mathbf y}\) can be obtained from \({\mathbf x}\) by inserting \(m-n\) symbols (anywhere in the word). A code \(C\) of length \(k\) over \(F\) is said to be a \(t\)-deletion/insertion-correcting code if each word of length \(k-t\) over \(F\) is a subword of at most one codeword in \(C\). A variant of this definition requires that the entries in each codeword are all distinct and that each word consisting of \(k-t\) distinct symbols of \(F\) is a subword of at most one codeword in \(C\). In either case, the definition of a perfect code is obtained by replacing ``at most'' by ``precisely''. Apart from some bounds on the size of a \(t\)-deletion/insertion-correcting code, both in the general and in the perfect case, the paper is primarily concerned with the existence problem for perfect 2- or 3-deletion/insertion-correcting codes of length 4 or 5. The author gives necessary and sufficient conditions for the existence of such codes in terms of the size \(|F|\) of the alphabet. The only cases for which the existence problem remains uncovered by the author's constructions are \(|F|=13,14, 15,16\) and \(|F|\equiv 7\) or \(8\bmod 10\), \(|F|\geq17\). Some of the presented constructions are based on ordered designs, that are designs in which the blocks are ordered \(k\)-tuples with the requirement that every ordered pair of elements is contained as a subword in a fixed number of blocks, usually one. Another series of constructions is based on modifications of existing codes to produce new ones, in particular a procedure based on the extension of the ground alphabet by adjunction of a new symbol and a procedure in which the codewords are punctured at a given symbol or pair of symbols, and then a system of distinct representatives is found for the sets formed by the remaining symbols, in order to get a suitable replacement.