Covering sets for limited-magnitude errors

Abstract

For a set $\cM=\{-μ,-μ+1,\ldots, λ\}\setminus\{0\}$ with non-negative integers $\lambda ,\mu <q$ not both 0, a subset $\cS$ of the residue class ring ${\mathbb{Z}}_q$ modulo an integer $q\ge 1$ is called a $(\lambda ,\mu ;q)$-\emph{covering set} if $$ \cM \cS=\{ms \bmod q : m\in \cM,\ s\in \cS\}=\Z_q. $$ Small covering sets play an important role in codes correcting limited-magnitude errors. We give an explicit construction of a $(\lambda ,\mu ;q)$-covering set $\cS$ which is of the size $q^{1+o(1)}\max \{\lambda ,\mu {\}}^{-1/2}$ for almost all integers $q\ge 1$ and of optimal size $p\max \{\lambda ,\mu {\}}^{-1}$ if $q=p$ is prime. Furthermore, using a bound on the fourth moment of character sums of Cochrane and Shi we prove the bound $${\omega }_{\lambda ,\mu }(q)\le q^{1+o(1)}\max \{\lambda ,\mu {\}}^{-1/2},$$ for any integer $q\ge 1$, however the proof of this bound is not constructive.

References in corpus (2)

• Trajectory Codes for Flash Memory
• Rank statistics for a family of elliptic curves over a function field