CMU-CS-20-103Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-20-103
Zhen Zhou M.S. Thesis May 2020
Keywords:
Coding Theory, Error-Correcting Codes, List Decoding, Non-binary, Indicator Sequence
The problem of constructing codes resilient to log , for length n + O(1))n, have been known since the 60s. Regardless of the alphabet size of the code, the redundancy of a code is measured in bits. Although the optimal binary single-deletion codes have been established, the situation even for two deletions is a lot more complex. A non-constructive greedy argument shows the existence of binary codes of redundancy 4 log, whereas redundancy _{2} n2 log is necessary. Compared with binary deletion codes, the topic of deletion codes over an alphabet of an arbitrary size _{2} nq (or q-ary deletion codes) received much less attention. In this work, we describe 2-deletion codes over an alphabet of size q of redundancy 3 log, assuming _{2} n + O_{q}(log log n) + r_{2}(n)r is the minimum redundancy needed for binary 2-deletion code, thus opening up a new direction of study. Combining with Hastad's list decodable binary 2-deletion codes, which have redundancy _{2}(n)3 log and allow the received word to be list-decoded into at most two possibilities from 2 deletions, we obtain a list-decodable _{2} n + O(log log n)q-ary 2-deletion code with 6 log redundancy and a list size 2. Our approach in the proof uses indicator strings and the run numbers in the string to compute various check sums that together enable recovery of the two missing bits. We hope this new perspective will be a useful way to think about and construct further deletion codes.
_{2} n + O_{q}(log log n)43 pages
Srinivasan Seshan, Head, Computer Science Department
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |