Covering sets for limited-magnitude errors

الأصل · EN

For a set ={-μ,-μ+1,, λ}{0} with non-negative integers λ,μ<q not both 0, a subset of the residue class ring modulo an integer q≥ 1 is called a (λ,μ;q)-covering set if ={ms q: m∈,s∈ }=. Small covering sets play an important role in codes correcting limited-magnitude errors. We give an explicit construction of a (λ,μ;q)-covering set which is of the size q¹ ⁺ ᵒ⁽¹⁾{λ,μ}⁻¹/² for almost all integers q≥ 1 and of optimal size p{λ,μ}⁻¹ if q=p is prime. Furthermore, using a bound on the fourth moment of character sums of Cochrane and Shi we prove the bound ωλ,μ(q)≤ q¹⁺ᵒ⁽¹⁾{λ,μ}⁻¹/², for any integer q≥ 1, however the proof of this bound is not constructive.