Published June 2020
| public
Book Section - Chapter
Optimal Codes for the q-ary Deletion Channel
- Creators
- Sima, Jin
- Gabrys, Ryan
- Bruck, Jehoshua
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
- Eprint ID
- 105183
- Resolver ID
- CaltechAUTHORS:20200831-150933262
- CCF-1816965
- NSF
- CCF-1717884
- NSF
- Created
-
2020-09-08Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field