Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Perfect codes in Cartesian products of 2-paths and infinite paths. | Perfect codes in Cartesian products of 2-paths and infinite paths Paul Dorbec Michel Mollard i ERTe Maths à Modeler Groupe de recherche GéoD Laboratoire Leibniz 46 av. Felix Vỉallet 38031 Grenoble CEDEX FRANCE Submitted Feb 24 2005 Accepted Nov 22 2005 Published Nov 29 2005 Mathematics Subject Classifications 05C69 05C70 94B60 Abstract We introduce and study a common generalization of 1-error binary perfect codes and perfect single error correcting codes in Lee metric namely perfect codes on products of paths of length 2 and of infinite length. Both existence and nonexistence results are given. 1 Introduction Perfect codes appeared in error correcting codes theory during the late 40 s with the work of Golay and Hamming 3 6 . They constructed perfect binary single-error correcting codes of length n where n 2q 1 for some integer q. Later Golomb and Welch 4 5 proved for any length n the existence of perfect single-error correcting codes in Lee metric. Such codes can be considered either as regular periodic tilings of the euclidean space Rn by Lee spheres of radius 1 or as periodic tilings of the grid Zn by balls of radius 1. Perfect codes have also been studied on other alphabets or mixed one see 2 . In 1 Biggs introduced perfect codes in graphs. From this point of view a perfect binary single-error correcting code of length k is a perfect code on the hypercube Qk and a tiling of the grid Zn by balls of radius 1 is nothing more than a perfect code of Zn. ENS Lyon 1CNRS Iphis work was partially supported by PROTEUS THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R65 1 Both Qk and the grid Zn are cartesian products of paths either of length 2 P2 or of inhnite length P1 . We study the existence of perfect codes on the mixed product P a p2 Zu Qk. In the next section we give the dehnitions we will use along this paper. Section 3 presents classical results on error correcting codes. In section 4 we construct new codes and in .
