Covering sets for limited-magnitude errors

Zhixiong Chen, Igor E. Shparlinski, Arne Winterhof

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

For a set M = {-μ,-μ + 1, . . . , λ} \ {0} with nonnegative integers λ,μ < q not both 0, a subset S of the residue class ring ℤq modulo an integer q ≥ 1 is called a (λ,μ; q)-covering set if MS = {ms mod q : m ε M, s ε S} = ℤq . Small covering sets play an important role in codes correcting limited-magnitude errors. We give an explicit construction of a (λ,μ; q)-covering set S, which is of the size q1+o(1) max{λ,μ} -1/2 for almost all integers q ≥ 1 and optimal order of magnitude (that is up to a multiplicative constant) p max{λ,μ}-1 if q = p is prime. Furthermore, using a bound on the fourth moment of character sums of Cochrane and Shi that there is a (λ,μ; q)-covering set of size at most q1+o(1) max{λ,μ}-1/2 for any integer q ≥ 1, however the proof of this bound is not constructive.

Original languageEnglish
Pages (from-to)5315-5321
Number of pages7
JournalIEEE Transactions on Information Theory
Volume60
Issue number9
DOIs
Publication statusPublished - Sept 2014
Externally publishedYes

Keywords

  • character sums.
  • Covering sets
  • limited-magnitude errors
  • residue class rings

Cite this