Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic Analysis

Abstract

This work is motivated by the problem of error correction in bit-shift channels with the so-called $(d,k)$ input constraints (where successive $1$'s are required to be separated by at least $d$ and at most $k$ zeros, $0\le d<k\le \infty$). Bounds on the size of optimal $(d,k)$-constrained codes correcting a fixed number of bit-shifts are derived, with a focus on their asymptotic behavior in the large block-length limit. The upper bound is obtained by a packing argument, while the lower bound follows from a construction based on a family of integer lattices. Several properties of $(d,k)$-constrained sequences that may be of independent interest are established as well; in particular, the exponential growth-rate of the number of $(d,k)$-constrained constant-weight sequences is characterized. The results are relevant for magnetic and optical information storage systems, reader-to-tag RFID channels, and other communication models where bit-shift errors are dominant and where $(d,k)$-constrained sequences are used for modulation.

10 pages (double-column), 2 figures. To appear in IEEE Transactions on Information Theory

References in corpus (5)

• Codes in the Space of Multisets---Coding for Permutation Channels with Impairments
• Asymptotically Optimal Codes Correcting Fixed-Length Duplication Errors in DNA Storage Systems
• Zero-Error Capacity of $P$-ary Shift Channels and FIFO Queues
• Improved Bounds on Sidon Sets via Lattice Packings of Simplices
• A Note on Parallel Asynchronous Channels with Arbitrary Skews

Cited by in corpus (6)

• Asymptotically Optimal Codes Correcting Fixed-Length Duplication Errors in DNA Storage Systems
• Zero-Error Capacity of Duplication Channels
• Asymptotic Behavior and Typicality Properties of Runlength-Limited Sequences
• Gilbert-Varshamov Bound for Codes in $L_1$ Metric using Multivariate Analytic Combinatorics
• Evaluation of the Gilbert-Varshamov Bound using Multivariate Analytic Combinatorics
• Optimal Error-Detecting Codes for General Asymmetric Channels via Sperner Theory