Covering code: Difference between revisions

Revision as of 01:36, 24 October 2023

Revision as of 15:09, 18 June 2024

Line 20:

== Covering problem ==

The [[determination]] of the minimal size <math>K_q(n,R)</math> of a ''q''-ary ''R''-covering code of length ''n'' is a very hard problem. In many cases, only [[upper and lower bounds]] are known with a large gap between them.

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>{{cite journal |author=E.R. Rodemich, |title=Covering by rook-domains, ''|journal=[[Journal of Combinatorial Theory]]'', |volume=9 (|year=1970), |pages=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''.