All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD6-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$.