TCS / Research / Publications / Constructions of Mixed Covering Codes
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Constructions of Mixed Covering Codes

Reference:

Patric R. J. Östergård. Constructions of mixed covering codes. Research Report A18, Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory, Espoo, Finland, December 1991.

Abstract:

In this work construction methods for so called mixed covering codes are developed. There has been considerable recent growth in the interest in covering codes. They have the property that all words in the space are within a given Hamming distance, called the covering radius, from some codeword. Traditionally, mainly spaces where all coordinates have the same arity (usually 2 or 3, that is, they are binary or ternary) have been discussed. In this work we consider mixed spaces F_q_1^n_1F_q_2^n_2cdots F_q_m^n_m, where the coordinates can be of varying arities. The approach is very general, no restrictions are set upon m and the arities q_i. The construction methods consist of generalizations of known constructions for covering codes and some completely new constructions. They are divided into three classes; direct constructions, constructions of new codes from old, and the matrix method. Through these constructions upper bounds for the minimal number of codewords in a code covering a certain space with a certain covering radius (K_q_1,q_2, ... ,q_m(n_1,n_2, ... ,n_m;R)) are improved. The results include a new record-breaking binary code, proving K_2(12,2) <= 78.

Keywords:

Covering code, covering radius, football pool problem,mixed code, simulated annealing

Suggested BibTeX entry:

@techreport{HUT-TCS-A18,
    address = {Espoo, Finland},
    author = {Patric R. J. {\"O}sterg{\aa}rd},
    institution = {Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory},
    month = {December},
    number = {A18},
    pages = {44},
    title = {Constructions of Mixed Covering Codes},
    type = {Research Report},
    year = {1991},
}

NOTE: Reprint of Licentiate's thesis; see URL below.
PostScript (442 kB)
GZipped PostScript (123 kB)
See www.tcs.hut.fi ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.