Robust Locally Positioning Sequences and Codes: Capacity, Constructions and Applications

An (n, d, b, k)
q
-robust locally positioning (RLP) sequence s is a q-ary sequence of length n where each subset of b consecutive windows of length k in s is a q-ary code of length k with minimum Hamming distance d. A set of these sequences is called an (n, d, b, k)
q
-robust locally positioning code. The RLP sequence is a generalization of a locally constrained de Bruijn sequence and a robust positioning sequence which have been studied recently owing to their various applications. In this work, we study the RLP sequences and codes with motivation from both practical and theoretical points of view. Firstly, these RLP sequences and codes are useful to combat a combination of substitutions and synchronization errors in the ℓ-symbol read channel. Secondly, the RLP code can be viewed as a combination of an error correcting code and a constrained code avoiding a set of patterns and as such they pose several interesting theoretical challenges in combinatorics, algorithms and coding theory. Finally, from the practical point of view, these sequences and codes have numerous applications, especially error-correction in racetrack memories.Owing to their applications in racetrack memories, we investigate (n, d, b, k)
q
RLP codes with small values of b and d. Numerous techniques are used to compute the maximal asymptotic rate (capacity) of these codes for given set of parameters. The numerical results are computed and tabulated. We also study these codes with large values of b and d for theoretical interests. In some cases, we can construct a code with only a single bit of redundancy.