Sima, Jin and Gabrys, Ryan and Bruck, Jehoshua (2020) Optimal Codes for the q-ary Deletion Channel. In: 2020 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 740-745. ISBN 9781728164328. https://resolver.caltech.edu/CaltechAUTHORS:20200831-150933262
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200831-150933262
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.
Item Type: | Book Section | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
ORCID: |
| ||||||
Additional Information: | © 2020 IEEE. This work was supported in part by NSF grants CCF-1816965 and CCF-1717884. | ||||||
Funders: |
| ||||||
DOI: | 10.1109/isit44484.2020.9174241 | ||||||
Record Number: | CaltechAUTHORS:20200831-150933262 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20200831-150933262 | ||||||
Official Citation: | J. Sima, R. Gabrys and J. Bruck, "Optimal Codes for the q-ary Deletion Channel," 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA, 2020, pp. 740-745, doi: 10.1109/ISIT44484.2020.9174241 | ||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
ID Code: | 105183 | ||||||
Collection: | CaltechAUTHORS | ||||||
Deposited By: | Tony Diaz | ||||||
Deposited On: | 08 Sep 2020 19:18 | ||||||
Last Modified: | 16 Nov 2021 18:40 |
Repository Staff Only: item control page