• Source: Covering code

      • In coding theory, a covering code is a set of elements (called codewords) in a space, with the property that every element of the space is within a fixed distance of some codeword.


      Definition


      Let



      q
      ≥
      2


      {\displaystyle q\geq 2}

      ,



      n
      ≥
      1


      {\displaystyle n\geq 1}

      ,



      R
      ≥
      0


      {\displaystyle R\geq 0}

      be integers.
      A code



      C
      ⊆

      Q

      n




      {\displaystyle C\subseteq Q^{n}}

      over an alphabet Q of size |Q| = q is called
      q-ary R-covering code of length n
      if for every word



      y
      ∈

      Q

      n




      {\displaystyle y\in Q^{n}}

      there is a codeword



      x
      ∈
      C


      {\displaystyle x\in C}


      such that the Hamming distance




      d

      H


      (
      x
      ,
      y
      )
      ≤
      R


      {\displaystyle d_{H}(x,y)\leq R}

      .
      In other words, the spheres (or balls or rook-domains) of radius R
      with respect to the Hamming metric around the codewords of C have to exhaust
      the finite metric space




      Q

      n




      {\displaystyle Q^{n}}

      .
      The covering radius of a code C is the smallest R such that C is R-covering.
      Every perfect code is a covering code of minimal size.


      Example


      C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} is a 5-ary 2-covering code of length 4.


      Covering problem


      The determination of the minimal size




      K

      q


      (
      n
      ,
      R
      )


      {\displaystyle K_{q}(n,R)}

      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 Kq(n, R).
      Lower bounds include the sphere covering bound and
      Rodemich's bounds




      K

      q


      (
      n
      ,
      1
      )
      ≥

      q

      n
      −
      1



      /

      (
      n
      −
      1
      )


      {\displaystyle K_{q}(n,1)\geq q^{n-1}/(n-1)}

      and




      K

      q


      (
      n
      ,
      n
      −
      2
      )
      ≥

      q

      2



      /

      (
      n
      −
      1
      )


      {\displaystyle K_{q}(n,n-2)\geq q^{2}/(n-1)}

      .
      The covering problem is closely related to the packing problem in




      Q

      n




      {\displaystyle Q^{n}}

      , i.e. the determination of the maximal size of a q-ary e-error correcting code of length n.


      Football pools problem


      A particular case is the football pools problem, based on football pool betting, where the aim is to come up with a betting system over n football matches that, regardless of the outcome, has at most R 'misses'. Thus, for n matches with at most one 'miss', a ternary covering, K3(n,1), is sought.
      If



      n
      =



      1
      2



      (

      3

      k


      −
      1
      )


      {\displaystyle n={\tfrac {1}{2}}(3^{k}-1)}

      then 3n-k are needed, so for n = 4, k = 2, 9 are needed; for n = 13, k = 3, 59049 are needed. The best bounds known as of 2011 are


      Applications


      The standard work on covering codes lists the following applications.

      Compression with distortion
      Data compression
      Decoding errors and erasures
      Broadcasting in interconnection networks
      Football pools
      Write-once memories
      Berlekamp-Gale game
      Speech coding
      Cellular telecommunications
      Subset sums and Cayley graphs


      References




      External links


      Literature on covering codes
      Bounds on




      K

      q


      (
      n
      ,
      R
      )


      {\displaystyle K_{q}(n,R)}

    Kata Kunci Pencarian: