Technical Report CS0434

Title: Tiling Codes in Hamming Schems
Authors: R.M. Roth and A. Lempel
Abstract: A code C of length n, even minimum Hamming distance d, and covering radius R, over an alphabet Q of q elements is called a tiling code if (i) R=d/2 and (ii) for every two words u and v in Q^n of distance 1 apart there exists a codeword c in C such that both u and v are contained in the sphere of radius R around c. Tiling codes are analogous to the well-known perfect codes, which are defined by R=(d-1)/2 , and which attain the sphere-packing bound. In a similar manner, tiling codes attain a so-called sphere-tiling bound, which is the analogue of the sphere-packing bound for even minimum distances. As might be expected from the said analogy, there exist only a handful of tiling codes over finite fields. A complete characterization of all linear tiling codes is presented. In particular, it is shown that with the exception of the [q+2,q-l,4] MDS code when q is even, there exist no linear extensions of Hamming codes over GF(q) for q >2 which increment both the length and the minimum distance of the code.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1986
To the main CS technical reports page

Computer science department, Technion