On perfect codes and tilings: Problems and solutions. (English) Zbl 0908.94035
This paper contains several new results concerning (linear or nonlinear) perfect binary codes and tilings of binary Hamming spaces, and it is at the same time a good survey of these topics. It is shown that for each \(m \geq 3\), there exists two perfect binary one-error-correcting codes of length \(2^m-1\) such that their intersection consists of two codewords. As all such perfect codes are self-complementary, this is the smallest possible nonempty intersection. Moreover, all possible intersection numbers are determined in the linear case. A necessary and sufficient condition for determining when a perfect binary code has a shorter perfect code embedded in it is given. Finally, the connection between perfect binary codes and tilings is considered. The paper is concluded with a list of important open problems.
Reviewer: P.R.J.Östergård (Helsinki)
MSC:
94B25 | Combinatorial codes |
94B60 | Other types of codes |
05A18 | Partitions of sets |
05B40 | Combinatorial aspects of packing and covering |