2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | A.4.2 | ||
| Paper Title | Maximum Length of Robust Positioning Sequences | ||
| Authors | Duc Tu Dao, Han Mao Kiah, Nanyang Technological University, Singapore; Hengjia Wei, Ben-Gurion University of the Negev, Israel | ||
| Session | A.4: Combinatorial Coding Theory I | ||
| Presentation | Lecture | ||
| Track | Algebraic and Combinatorial Coding Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | An $(n,d)$-robust positioning sequence (RPS) is a binary sequence where every pair of length-$n$ subwords is distance $d$ apart. In this paper, we study the quantity $P(n,d)$, which denotes maximum length of an $(n,d)$-RPS, and provide tight estimates in the range $n/2 < d\le n$. First, we show that the usual Plotkin bound cannot be attained when certain divisibility conditions hold. Next, using the concept of differences, we construct an infinite family of RPSs that attain a modified Plotkin bound. Finally, except for 16 cases, we determine the {\em exact} values of $P(n,d)$ for $\delta(n) \le d\le n\le 50$, where $\delta(n)=\ceiling{n/2}$ if $n\not\equiv 0 \mod{4}$ and $\delta(n)=(n+2)/2$ if $n\not\equiv 0\mod{4}$ | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
