Covering code: Difference between revisions

Revision as of 01:35, 4 July 2008

Revision as of 11:26, 23 August 2008

Line 1:

In [[coding theory]], a '''covering code''' is an object satisfying a certain mathematical property: A code of length ''n'' over ''Q'' is an ''R''-covering code if for every word of <math>Q^n</math> there is a codeword such that their Hamming distance is <math>\le R</math>.

{{intro-tooshort|date=July 2008}}

In [[coding theory]], a '''covering code''' is an object satisfying a certain mathematical property.

== Definition ==

Line 24 ⟶ 23:

Every construction of a covering code gives an upper bound on ''K''_''q''(''n'',&nbsp;''R'').

Lower bounds include the sphere covering bound and

Rodemich’s bounds <math>K_q(n,1)\geq q^{(n-1)}/(n-1)</math> and <math>K_q(n,n-2)\geq q^2/(n-1)</math>.<ref>E.R. Rodemich, Covering by rook-domains, ''[[Journal of Combinatorial Theory]]'', 9 (1970), 117-128</ref>

The covering problem is closely related to the packing problem in <math>Q^n</math>, i.e. the determination of the maximal size of a ''q''-ary ''e''-[[Error detection and correction|error correcting]] code of length ''n''.