2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | M.5.2 | ||
| Paper Title | Locally Balanced Constraints | ||
| Authors | Ryan Gabrys, UCSD, United States; Han Mao Kiah, NTU, Singapore; Alexander Vardy, UCSD, United States; Eitan Yaakobi, Yiwei Zhang, Technion - Israel Institute of Technology, Israel | ||
| Session | M.5: Coding for Storage and Memories I | ||
| Presentation | Lecture | ||
| Track | Coding for Storage and Memories | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | Three new constraints are introduced in this paper. These constraints are characterized by limitations on the Hamming weight of every subword of some fixed even length $\ell$. In the \emph{$(\ell,\delta)$-locally-balanced constraint}, the Hamming weight of every length-$\ell$ subword is bounded between $\ell/2-\delta$ and $\ell/2+\delta$. The \emph{strong-$(\ell,\delta)$-locally-balanced constraint} imposes the locally-balanced constraint for any subword whose length is at least $\ell$. Lastly, the Hamming weight of every length-$\ell$ subword which satisfies the \emph{$(\ell,\delta)$-locally-bounded constraint} is at most $\ell/2-\delta$. It is shown that the capacity of the strong-$(\ell,\delta)$-locally-balanced constraint does not depend on the value of $\ell$ and is identical to the capacity of the \emph{$(2\delta+1)$-RDS constraint}. The latter constraint limits the difference between the number of zeros and ones in every prefix of the word to be at most $2\delta+1$. This value is also a lower bound on the capacity of the $(\ell,\delta)$-locally-balanced constraint, while a corresponding upper bound is given as well. Lastly, it is shown that if $\delta$ is not large enough, namely for $\delta < \sqrt{\ell}/2$, then the capacity of the $(\ell,\delta)$-locally-bounded constraint approaches $1$ as $\ell$ increases. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
