| Paper ID | D6-S3-T4.1 |
| Paper Title |
On Multiple-Deletion Multiple-Substitution Correcting Codes |
| Authors |
Wentu Song, Singapore University of Technology and Design, Singapore; Nikita Polyanskii, Technical University of Munich, Germany, and Skolkovo Institute of Science and Technology, Russia, Russia; Kui Cai, Xuan He, Singapore University of Technology and Design, Singapore |
| Session |
D6-S3-T4: Multiple Insertion/Deletion-Correcting Codes |
| Chaired Session: |
Monday, 19 July, 22:40 - 23:00 |
| Engagement Session: |
Monday, 19 July, 23:00 - 23:20 |
| Abstract |
In this paper, by applying the precoding technique in conjunction with the syndrome compression approach, we construct systematic $t$-deletion $s$-substitution correcting codes, where $t$ and $s$ are fixed positive integers. The redundancy of our construction is $(4t+3s)\log n+o(\log n)$ for the binary case and $\left(4t+4s-1-\left\lfloor\frac{2s-1}{q}\right\rfloor\right)\log_q n+ o(\log_q n)$ for the $q$-ary case, where $n$ is the length of the codes and $q>2$ is a fixed prime power. We also construct binary $t$-deletion correcting codes $($i.e., $s=0)$ with redundancy $(4t-1)\log n+o(\log n)$. The encoding/decoding complexities of all constructions are polynomial in $n$.
|
