Deletion-codes overhead for varying settings

In a deletion channel, some symbols might be "dropped off" during transmission. The receiver knows that some symbols were omitted, but does not know either their values or their positions. This differs from the more widely studied erasure channel, where the positions of errors are known, and so all of the symbols that have been successfully received are known to be in their correct positions. In recent years, the interest in deletion channels has grown, possibly due to the fact that networks\´ packet loss can be modelled as deletions. Codes and bounds for this error model have been studied. One of the most fundamental works on deletions is that of Levenshtein (1965). This work contains bounds on the size of a maximal binary-alphabet codebook of length n words resilient to s deletions. This paper discusses bounds which are an extension of these bounds to a size q alphabet.