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

Construction Methods for Covering Codes

Reference:

Patric R. J. Östergård. Construction methods for covering codes. Research Report A25, Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory, Espoo, Finland, September 1993. Doctoral dissertation.

Abstract:

A covering code in a Hamming space is a set of codewords with the property that any word in the space is within a specified Hamming distance, the covering radius, from at least one codeword. In this thesis, efficient construction methods for such codes are considered. The constructions work, with some exceptions, for codes over alphabets consisting of any number of symbols. Codes over mixed alphabets are also discussed. Most of the methods are developed in order to determine values of K_q(n,R), the minimum number of codewords in a q-ary code of length n and covering radius R. Codes obtained by the constructions prove upper bounds on this function. In many of the constructions simulated annealing, a probabilistic optimization method, has turned out to perform very well. Simulated annealing cannot be used to prove optimality of codes found; in that case, the problem is viewed and solved as a set covering problem. For larger codes, a direct approach is not generally feasible; it is shown how good such codes can be found by combining existing codes, or by imposing some structure on the codes. A matrix method that is presented follows the latter principle; a code constructed by this method consists of cosets of a linear code. To be able to combine existing codes efficiently, it is necessary that the codes involved can be partitioned into subcodes with certain properties; subnorm and norm are concepts that are introduced to describe partitions of codes. Finally, some families of combinatorial methods are presented.

Suggested BibTeX entry:

@techreport{HUT-TCS-A25,
    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 = {September},
    note = {Doctoral dissertation},
    number = {A25},
    pages = {25},
    title = {Construction Methods for Covering Codes},
    type = {Research Report},
    year = {1993},
}

PostScript (324 kB)
GZipped PostScript (89 kB)

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