Published June 2020
| public
Book Section - Chapter
Optimal Systematic t-Deletion Correcting Codes
- Creators
- Sima, Jin
- Gabrys, Ryan
- Bruck, Jehoshua
Abstract
Systematic deletion correcting codes play an important role in applications of document exchange. Yet despite a series of recent advances made in deletion correcting codes, most of them are non-systematic. To the best of the authors' knowledge, the only known deterministic systematic t-deletion correcting code constructions with rate approaching 1 achieve O(t log² n) bits of redundancy for constant t, where n is the code length. In this paper, we propose a systematic t-deletion correcting code construction that achieves 4t log n + o(log n) bits of redundancy, which is asymptotically within a factor of 4 from being optimal. Our encoding and decoding algorithms have complexity O(n^(2t+1)), which is polynomial for constant t.
Additional Information
© 2020 IEEE. This work was supported in part by NSF grants CCF-1816965 and CCF-1717884.Additional details
- Eprint ID
- 105181
- DOI
- 10.1109/isit44484.2020.9173986
- Resolver ID
- CaltechAUTHORS:20200831-144630883
- 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