Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2020 | public
Book Section - Chapter

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.

Additional Information

© 2020 IEEE. This work was supported in part by NSF grants CCF-1816965 and CCF-1717884.

Additional details

Created:
August 19, 2023
Modified:
October 20, 2023