Optimal Codes for the q-ary Deletion Channel

Abstract

The problem of constructing optimal multiple deletion correcting codes has long been open until recent break-through for binary cases. Yet comparatively less progress was made in the non-binary counterpart, with the only rate one non-binary deletion codes being Tenengolts’ construction that corrects single deletion. In this paper, we present several q-ary t-deletion correcting codes of length n that achieve optimal redundancy up to a factor of a constant, based on the value of the alphabet size q. For small q, our constructions have O(n^(2t) q^t) encoding/decoding complexity. For large q, we take a different approach and the construction has polynomial time complexity.