Weighed-covering code

Description

A binary or \(q\)-ary code for which balls of some radius centered at its codewords provide a weighted covering of the Hamming space.

Let the outer or weight distribution of a \(q\)-ary string \(x\) with respect to a \(q\)-ary code \(C\) be \(A(x) = \left( A_0(x),A_1(x),\cdots,A_n(x) \right)\), where \begin{align} A_j(x) = \left|\{ c \in C~\text{such that}~ D(c,x)=j \}\right|~, \end{align} and \(D\) is the Hamming distance. Given a tuple \(m=(m_1,m_2,\cdots,m_n)\) of rational numbers, the \(m\)-density of the code at \(x\) is \begin{align} \theta(x) = \sum_{j=0}^n m_j A_j(x)~. \end{align}

A code is an \(m\)-weighed covering if \(\theta(x)\geq1\) for all strings \(x\in GF(q)^n\). The \(m\)-covering radius \(r\) is the largest \(j\) for which \(m_j\) is nonzero.

Notes

See book [1] for an expositions on weighed covering codes and generalized sphere-packing bounds.See book [2], Table 7.5.18 for tables of codes with particular weighed coverings.

Parent

Children

  • Covering code — An \(m\)-weighed covering code for \(m_j=1\) is a covering code of covering radius at most \(r\) ([1], Ch. 13).
  • Quasi-perfect code — A quasi-perfect code is an \(m\)-weighed covering code for \(r=t+1\), \(m_0=m_1=\cdots=m_{t+1}=1\), and \(m_t=m_{t+1}=1/\left\lfloor (n+1)(t+1) \right\rfloor\) ([1], Ch. 13).

References

[1]
G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering codes. Elsevier, 1997.
[2]
J. H. van Lint, Introduction to Coding Theory (Springer Berlin Heidelberg, 1992). DOI

Zoo code information

Internal code ID: weighed_covering

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: weighed_covering

Cite as:
“Weighed-covering code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/weighed_covering
BibTeX:
@incollection{eczoo_weighed_covering, title={Weighed-covering code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/weighed_covering} }
Share via:
Twitter |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/weighed_covering

Cite as:

“Weighed-covering code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/weighed_covering

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/properties/covering/weighed_covering.yml.