Combinatorial Constructions For Deletion And Insertion-Correcting Codes

Little is known about the theory of deletion and insertion-correcting codes. This dissertation investigates the combinatorial constructions for deletion and insertion-correcting codes. Most of our work is on two kinds of perfect deletion-correcting codes: T~*(t, k, v)-codes and T(t, k, v)-codes. Both a T~*(t, k, v)-code and a T{t, k, v)-code are capable of correcting any combination of up to (k — t) deletions and insertions of letters occurred in transmission of codewords.In Chapter 2, the notion of a generalized candelabra t-system (or t-GCS) is introduced and used to show that a T~*(3, 4, v)-code exists for all odd v. Combining this with Levenshtein's result, the existence problem for a T~*(3, 4, v)-code is solved completely.A directed t-design DB_t(k, 1; v) is equivalent to a T(t, k, v)-code. This idea was first given by Levenshtein. In Chapter 3, the necessary conditions for the existence of a DB(7,1; v) are shown to be sufficient with one exception and 68 possible exceptions. DB(7,1; v)'s can be used to construct T(2, 7, v)-codes.In Chapter 4, the existence of a T~*(2, 7, v)-code with v ≥ 2350 is proved. A large number of explicit constructions for T~*(2, 7, v)-codes with v < 2350 are also presented.In Chapter 5, we obtain an asymptotic result for T(2, k, v)-codes form directed t-designs, and discuss in a nutshell the asymptotic existence of a T~*(2, k, v)-code and the other directed designs which are related to deletion and insertion-correcting codes. We also present some open problems for further study.