Covering Sets for Limited-Magnitude Errors

DOI10.1109/TIT.2014.2338078zbMATH Open1360.11026arXiv1310.0120OpenAlexW2964005479MaRDI QIDQ2986150FDOQ2986150

Authors:

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: For a set $cM=-mu,-mu+1,ldots,lambdasetminus0$ with non-negative integers $lambda,mu<q$ not both 0, a subset $cS$ of the residue class ring $$ modulo an integer $qge1$ is called a $(lambda,mu;q)$-emph{covering set} if ${\displaystyle }$ cM cS={ms �mod q : min cM, sin cS}=�_q. ${\displaystyle }$ 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 $qge1$ and of optimal size $pmax{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 ${\displaystyle }$omega_{lambda,mu}(q)le q^{1+o(1)}max{lambda,mu}^{-1/2},${\displaystyle }$ for any integer $qge1$, however the proof of this bound is not constructive.

Full work available at URL: https://arxiv.org/abs/1310.0120

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Arithmetic combinatorics; higher degree uniformity (11B30) Sequences (mod (m)) (11B50)

Cited In (5)

• On covering sets for limited-magnitude errors
• Linear covering codes and error-correcting codes for limited-magnitude errors
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• A Coverage Theory for Least Squares
• Title not available (Why is that?)

This page was built for publication: Covering Sets for Limited-Magnitude Errors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986150)